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:

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.

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 h_i be H= {h_i} (the subscript ‘i’ refers to the indices with which we label the hats; h_i 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).

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 “ꓯh_i p(h_i) → g(h_i)”     ‘Pinocchio says, “All my hats are green” ‘       

(Initially we attempted to use conjunction “p(h_i) ꓥ g(h_i)” 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) ꓱh_i p(h_i)      ‘There exists a hat that is owned by Pinocchio‘

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

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

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

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

(We use X to refer to “ꓯh_i p(h_i)→g(h_i)” 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 (ꓯh_i p(h_i)→g(h_i)). 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 ↔ ¬(ꓯh_i p(h_i) → g(h_i)) ↔ ꓱh_i p(h_i) ꓥ ¬g(h_i)

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.