In: Advanced Math
You are a famous archaeologist/treasure hunter ́a la Indiana Jones. After following a treasure map you find yourself deep inside a Babylonian temple. As you reach the end of a long corridor you find it splits into two paths. Above the first path you make out some text carved into the rock. Shining your torch you manage to make out the following two inscriptions on the wall:
1. L1 ∧ T2
2. (L1 ∧T2)∨(L2 ∧T1)
Knowing that the Babylonians were great mathematicians, you’re not surprised to see that they had developed such a refined system of propositional logic centuries before it should have been. The historians of mathematics will surely want to hear of this discovery when you’re done!
Having no idea what these variables could mean however, you look down at your map to see if there are any hints. You notice scrawled in the margins of the map “L1: First Path Leads to Being Lost Forever”, “L2: Second Path Leads to Being Lost Forever”, “T1: First Path Leads To Treasure” and “T2: Second Path Leads To Treasure”.
Reading the first inscription you quickly translate the treasure is down the second path. However, as you’re about to step into the tunnel you remember something the map seller said as you were leaving his shop: “One tells the truth and the other is a lie!” You had thought that was cryptic nonsense at the time but thank goodness you remembered! He seemed like a trustworthy guy so you’ll assume that his statement was true and that one inscription is lying and the other is telling the truth.
Q: (20 points) Assuming the lying inscription is true and the truthful inscription is false leads to a contradiction. Prove this using the laws of propositional logic. First, combine the two statements into a single boolean expression (adding a ¬ to the expression that you’re assuming is false). Then proceed using the laws of propositional logic to arrive at “False”. You must show each step and identify which law you are applying. You must use the distributive law at least once; we are looking for you to demonstrate mastery over several laws rather than a quick solution.
Let us assume first inscription (L1 ∧ T2) is true. It means that the treasure is in the second path. But, since we assumed L1 ∧ T2 is true that leads to (L1 ∧T2)∨(L2 ∧T1) also being true because of the domination law for tautologies. Domination laws states that A ∨ T = T. However, the map seller mentioned that only one inscription is true, hence the assumption led us to a contradiction. Therefore, it is beyond doubt that (L1 ∧ T2) is false and (L1 ∧T2)∨(L2 ∧T1) is true.
Now, in the question he asked us to assume that the lying inscription is true and the truthful inscription is false. And, he asked us to combine these two statements into a single Boolean expression. So, we are assuming L1 ∧ T2 is true and (L1 ∧T2)∨(L2 ∧T1) is false.
(L1 ∧ T2) ∧ (¬ ( (L1 ∧T2)∨(L2 ∧T1) ) )
= (L1 ∧ T2) ∧ ( ¬ (L1 ∧T2) ∧ ¬ (L2 ∧T1) ) (Since, De Morgan's Law: ¬ (A v B) = ¬A ^ ¬B )
= ( (L1 ∧ T2) ∧ ¬ (L1 ∧T2) ) ∧ ¬ (L2 ∧T1) (Since, Associative Law: A ^ (B ^ C) = (A ^ B) ^ C )
= F ∧ ¬ (L2 ∧T1) (Since, A ^ ¬ A = F)
= F (Since, F ^ A = F)
Hence, by taking the lying inscription as true and the truthful inscription as false, we got contradiction (F) as the result.
Now, Let us also consider (L1 ∧ T2) is false and (L1 ∧T2)∨(L2 ∧T1) is true and check to verify.
¬(L1 ∧ T2) ∧ ( (L1 ∧T2)∨(L2 ∧T1) ) (Since, Distributive Law: A ^ (B v C) = (A ^ B) v (A ^ C) )
= ( ¬(L1 ∧ T2) ∧ (L1 ∧T2) ) ∨ ( ¬(L1 ∧ T2) ∧ (L2 ∧T1) )
= F ∨ ( ¬(L1 ∧ T2) ∧ (L2 ∧T1) ) (Since, F v A = A)
= ( ¬(L1 ∧ T2) ∧ (L2 ∧T1) ) (Since, we assumed (L1 ∧ T2) = F. So, ¬(L1 ∧ T2) = T)
= T ∧ (L2 ∧T1) (Since, T ^ A = A)
= L2 ∧T1 ( According to our assumption L2 ∧T1 is true)
As we have assume (L1 ∧ T2) is False and (L1 ∧T2)∨(L2 ∧T1) is true, it means L2 ^ T1 is true. Hence, we verified too.