Classical logic and Pinocchio

Last week we hosted a work experience student, Dexter Harland-Hackenschmidt, who is interested in mathematics and logic. We tasked him with a logic problem that we had seen on YouTube. The following is his report in the style of a blog post. Enjoy!

——————————————————————————————————–

In the video “Can you pass this logic test from Brazil?” the following question is proposed:

Assume the following sentences are true:

(1) Pinocchio always lies;

(2) Pinocchio says, “All my hats are green”

We can conclude from these two sentences that:

A) Pinocchio has at least one hat.

B) Pinocchio has only one green hat.

C) Pinocchio has no hats.

D) Pinocchio has at least one green hat.

E) Pinocchio has no green hats.

The video goes on to provide counter examples to options B, D and E, proving that these options cannot be concluded, as they are not true in all cases. After narrowing it down to options A and C, the truth table for implication (→) is invoked to argue that C would make (2) vacuously true (instead of false), and therefore that Pinocchio is not lying and thus the only viable answer, if any, is A. However, it is not made clear why the truth table for implication was used, and the video fails to explain other parts of the question. What does it even mean to conclude something in a logical sense?

An introduction to logic
In order to fully understand the proof for this question we must first understand the basics of classical logic, which the video used in the proposed solution, and first order logic which allows the use of predicates which will be explained later. Classical Logic is built up of 3 core elements: propositions, logical connectives and ‘laws of inference’. Propositions are statements in classical logic which can only be true or false – not both.

Logical connectives connect propositions together and allow us to construct logical statements out of them. The first of the logical connectives used in this proof is conjunction, which is denoted by (ꓥ) and means “and”. For example, the two propositions “it is raining” (R) and “it is cloudy” (C) can be combined using the conjunction connective to form the statement “it is raining and it is cloudy” (R ꓥ C), and for this to be true both the individual propositions must be true as well. The second connective we shall introduce is disjunction, which is denoted by (V) and means “or”. For example, if the propositions “Steve has an apple” (A) and “Steve has an orange” (O) were connected by disjunction to form “Steve has an apple or Steve has an orange” (A V O), then if either of the individual propositions is true then their disjunction is true. The third connective we must define is negation, which is denoted by (¬) and means that if a proposition S is true then the negation of S (¬S) is false. The logical connective referred to as implication is denoted by (→) and means “if … then …”. For example “if Steve has oranges, then he has apples” (O→A). Finally, “if and only if” is denoted by (↔) and means that the propositions on either side have logical equivalence and can be used interchangeably. Basic sentences built out of atomic (i.e. irreducible) propositions A and B with the above connectives return different truth values depending on the truth values of the atomic propositions they act on. These can be summarised into a logical tool called a “truth table” (see Table 1).

Rules of inference allow for simple logical conclusions to be gathered from truth tables (shown below) for example Modus Tollens (if A→B is true and B is false then A is also false). In order to properly apply these connectives to the question being analysed in this blog post, first order logic must also be applied, since this helps in constructing more precise statements to rewrite the question in a logical form. This requires the use of two tools within first order logic, quantifiers such as ꓯ (for all) and ꓱ (there exists), and the use of predicates such as “green” to describe the properties of objects (i.e. hats). This can be written as g = green and h = hat such that g(h) means a hat that is green. These can be constructed into logical sentences such as ꓯh g(h), meaning all hats are green.

Table 1: Truth table of basic sentences built from atomic propositions Q and R and the basic connectives of propositional logic (negation, conjunction, disjunction and implication). The value 0 signifies False and the value 1 signifies True. The truth values of any sentence of propositional logic can be obtained from these basic ones.

Applying first order logic to the problem
In order to apply first order logic to the problem of Pinocchio, we must first rewrite the question using formal notation. In order to do this, we begin by defining the universe or domain of discourse which in this case would be all hats, whether they are owned by Pinocchio or not. Defined as such, let the set of all hats hi be H= {hi} (the subscript ‘i’ refers to the indices with which we label the hats; hi could be any hat within the set, i.e. i = 1, 2, 3, …, N where N is the number of hats). We must also take care to define what the question means by “conclude”. We interpret this to mean that if an option can be concluded, then when Pinocchio makes the statement X the negation of that statement should imply that option for all possible cases. When this is the case, it is called a tautology. An example of a tautology within propositional logic is the logical inference Modus Ponens, which states that if Q → R is true and Q is true, then R is also true. The proof for this statement is demonstrated in truth table below (Table 2).

Table 2: Truth table evaluating the truth values of sentence corresponding to Modus Ponens in all possible cases (Q True, R True or Q True, R False or Q False, R True or Q False, R False). We see that the Modus Ponens sentence is true in all cases thereby making it a tautology i.e. a sentence true in all cases.

The final column in Table 2 is Modus Ponens and since it is true (blue) in all cases, then as described above it is a tautology. We will apply this to Pinocchio’s hats later on but first we must define some of the notation that we will use. Pinocchio will be referred to as ‘P’ and hats will be referred to as ‘h’. The predicate ‘g’ means “green” and the predicate p means “owned by P”.

We can then rewrite the question in formal logic…

Assume the following sentences are true:

  1. If P says X then ¬X; ‘Pinocchio always lies
  2. P says “ꓯhi p(hi) → g(hi)”     ‘Pinocchio says, “All my hats are green” ‘       

(Initially we attempted to use conjunction “p(hi) ꓥ g(hi)” however writing the statement in that way meant that Pinocchio owned all hats in the universe!)

We can conclude from these two sentences that:

A) ꓱhi p(hi)      ‘There exists a hat that is owned by Pinocchio

B) ꓱhi ꓯhj : g(hj) ↔ i=j  ‘There exists precisely one green hat that is owned by  Pinocchio’

C) ¬ꓱhi p(hi)    ‘There does not exist a hat that is owned by Pinocchio’

D) ꓱhi p(hi) ꓥ g(hi)    ‘There exists a hat that is both owned by Pinocchio and is green’

E) ¬ꓱhi p(hi) ꓥ g(hi)    ‘A hat that is both owned by Pinocchio and is green does not exist

(We use X to refer to “ꓯhi p(hi)→g(hi)” for the sake of brevity)

The approach we took in our work was to note that if Pinocchio says X then X is a lie and thus ¬X is true, and if the negation of X implies any of the options is a tautology then the corresponding statement is a valid conclusion from (1) and (2) above. We created a test universe comprising of only two hats and examined the truth table (Table 3) to see if any of the statements were false in any of the models.

We therefore need to negate Pinocchio’s statement X (ꓯhi p(hi)→g(hi)). The first thing to mention is that when negating a sentence that contains the quantifier ꓯ, the ꓯ is replaced with ꓱ. Then, the negation of an implication Q→R can be written as follows:

¬(Q→R) ↔ Q ꓥ ¬R

So, the negation of Pinocchio’s statement reads:

¬X ↔ ¬(ꓯhi p(hi) → g(hi)) ↔ ꓱhi p(hi) ꓥ ¬g(hi)

Table 3: Truth table evaluating the truth value of statements of the form ¬X→Y, where Y represents the proposed conclusions A, B, C, D and E. Only ¬X→A is true in all possible cases and is therefore a tautology. Thus A is the only valid conclusion from the premises (1) and (2).

From Table 3 we can gather that (¬X→B), (¬X→ C), (¬X→ D), and (¬X→E) are not tautologies, since they contain some falsehoods (they are false in some rows or ‘models’). However, (¬X→A) is a tautology in this universe consisting of two hats as it contains only truths in every row (in every ‘model’).

Is this hold if we increase the number of hats arbitrarily? Yes! The way in which we can prove that ¬X→A is a tautology for any number of hats is with the use of the truth table for implication (see the first 3 columns of Table 2). Notice that whenever statement Q is false the statement Q→R is still true. This was mentioned in the video by Presh Talwalker but perhaps not explained fully. What this means is that when the ‘antecedent’ Q is false the ‘consequent’ R is vacuously true; because the statement holds no information it is impossible to prove false and is thus considered true within classical logic. We can apply this to the case of ¬X→A as it is only false in the case of ¬X being true and A being false. This allows us to prove A is a tautology in the following way. A is only false when P owns no hats, however, in that case ¬X is also false because P has to own a hat for ¬X to be true. Therefore whenever A is false ¬X is also false and the implication is true for all possible cases and A can be deemed true.

Conclusions

Although we came to the same logical conclusion as Presh did in his video, we have accomplished it in what we think is a more logical way. We have delved further into formal logic and have applied first order logic which was left unmentioned in the video. If, like us, you were initially confused by the proposed solution, hopefully this blog post has made both the question and the solution more clear.

Undergraduate physics research is on the rise

Today our undergraduate Physics students presented their summer research results at the University’s UROS poster conference (UROS is Undergraduate Research Opportunities Scheme). Physics team was one of the largest in the university while we are the smallest school so far: 3 posters were on Experimental Physics and 3 – on Computational Physics.

Our Physics superheroes of today are:

  • Aaron Adams
  • Christopher Dickens
  • Hannah Thurlbeck
  • Niall Garry
  • Robert Sharp
  • Tom Vale

Their supervisors were: Drs Matt Watkins, Marco Pinna, Fabien Paillusson, Matt Booth and Professor Waqar Ahmed.

The images below will rearrange if you reload the page:

Exploring the Molecular Machines within: a Fantastic Voyage

Maths & Physics News

Physics Christmas Lecture 2015

Dr Danilo Roccatano

Lincoln School of Mathematics and Physics

Wednesday 16th December 2015

at 3.30 pm

EMMTEC Lecture Theatre, Brayford Pool Campus, University of Lincoln

Eventbrite - Physics Christmas Lecture in Lincoln

To see a World in a Grain of Sand
And a Heaven in a Wild Flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.

William Blake, Auguries of Innocence

Roccatano 2015

Nature is a great source of inspiration and emulation for scientist and engineering, and the continuous advance in the knowledge of the complex machinery of life is producing profound impacts in the modern societies. Life, in the form that we know, definitively exploited what we now call “nanotechnology” to emerge. Living cells are crowded of fascinating molecular machines with a large variety of functions not yet completely explored. Nature as a blind and patient engineer builds these machines without a blueprint but using the evolution…

View original post 159 more words

Soft Matter in Rome

Rome_SM

Centre for Computational Physics

On 15-19 September 2013 Manuela, Marco, and Andrei participated in the worlds largest International Soft Matter Conference 2013 held at Sapienza University of Rome. The conference was the 3rd of its kind, which takes place every 3 years. It covered topics of Biological Soft Matter, Colloids, Dynamics of complex fluids, Membranes, Polymers, Self-assembly, Surfaces and interfaces, and Soft Nanotechnology.

View original post

25th National Conference of Undergraduate Research, USA

Centre for Computational Physics

The National Conference for Undergraduate Research (NCUR) in the USA is a yearly run conference aimed to promote research conducted by undergraduate students. The 25th NCUR was held at Ithaca College, Ithaca, New York State from March 31st to April 4th 2011 and I was fortunate enough to attend. There was approximately 4000 presentations given by undergraduates and I was given the opportunity to present two. The first was an oral presentation of the research carried out in the Computational Physics Group; titled “Computer Modelling of Soft-Nanostructures”. The second was a poster presentation of UCLan’s Undergraduate Research Society; which is a society set up by myself and other UCLan students of which I am the chair. The conference was set out to consist of 10 sessions and in each of these sessions there was approximately 52 different classrooms across the campus each with 4 oral presentations in and at the…

View original post 136 more words

Changing the laws of physics research

Centre for Computational Physics

UCLan reports on an undergraduate student success:

The ground-breaking research of an undergraduate Applied Physics student has been published in a top scientific journal.

The work of Ludwig Schreier, an Erasmus exchange student, has appeared on the back cover of the March 2009 issue of Soft Matter, a world leading science journal linking the disciplines of physics, chemistry and biology.

In his third year BSc project, Ludwig predicted how nano-scale material structures could be manipulated with the help of an ordinary electric field. The work was undertaken with the help of Marco Pinna, a research student within UCLan’s Computational Physics Group.

Ludwig comments: “I’d heard good things about UCLan from my fellow students at the University of Applied Sciences in Wiesbaden (Germany) and so I decided to experience it for myself.”

“I was delighted to take up the opportunity offered through the Erasmus exchange program and have really enjoyed my study…

View original post 250 more words

International adventure to the Netherlands

Centre for Computational Physics

Our student, Christine Stokes, went on a research trip to Holland.  Read here UCLan’s news story:

UCLan bursary contributes to outstanding student experience

Chrissystk - View my 'Leiden trip' set on Flickriver

A third year undergraduate physics student recently undertook a research trip of a lifetime having been awarded one of UCLan’s sector-leading internationalisation bursaries worth £700.

Christine Stokes, from Walton-Le-Dale, travelled across the Channel to the renowned Leiden University in the Netherlands where she undertook a one-month research project within the University’s department of Soft Matter Chemistry.

Here is her story:

“When the day came for me to leave England I was filled with a mixture of excitement and trepidation. It was the first time I’d travelled alone and the longest I’d been separated from my family but I was excited at entering a new phase in my personal development and future career path.

“On Tuesday, 18 May 2010 I took a one hour twenty minute flight to…

View original post 557 more words

IoP 2009 best Computational Physics PhD thesis – in Preston !

Centre for Computational Physics

Marco in officeMarco Pinna received the Institute of Physics 2009 prize for the best PhD thesis in Computational Physics !

That is a remarkable achievement for UCLan as the competition was open to all students from an institution in either the UK or Ireland across the entire spectrum of computational physics, and last year, for instance, the prize went to the University of Cambridge !

IoP e-mail says:

“… the Institute of Physics Computational Physics Group Committee have chosen your thesis to be awarded our 2009 annual prize for the work that in our opinion contributes most strongly to the advancement of computational physics.”

See the list of previous recipients here.

Marco’s PhD thesis featured in the IoP newsletter.

Read also UCLan news on Marco’s prize:

Doctoral student awarded for his expertise

Institute of Physics rewards Marco for significant advancement in his field.

A former PhD student from the University…

View original post 449 more words