Lady and Tigers (Simple Logic Puzzle)

Question

Do you know Frank Stockton's story "The Lady or the Tiger?," in which the prisoner must choose be­tween two rooms, one of which contains a lady and the other a tiger. If he chooses the former, he marries the lady; if he chooses the latter, he (probably) gets eaten by the tiger.

The king of a certain land had also read the story, and it gave him an idea. "Just the perfect way to try my prisoners!" he said one day to his minister. "Only, I won't leave it to chance; I'll have signs on the doors of the rooms, and in each case I'll tell the prisoner certain facts about the signs. If the prisoner is clever and can reason logically, he'll save his life-and win a nice bride to boot!"

"Excellent idea!" said the minister.

I'll put a lady in one room and a tiger in each of the other two rooms. Then we'll see how the prisoners fare!"

"Excellent ideal" replied the minister.

"Your conversation, though flattering, is just a hit on the repetitious side!" exclaimed the king.

"Excellently put!" replied the minister.

The king did as planned. He offered three rooms to choose from, and he explained to the prisoner that one room contained a lady and the other two contained tigers. Moreover, the king explained that at most one of the three signs was true. Which room contains the lady? Here are the three signs:

Now, how can that be formulated in propositional logic, and maybe as a BDD that will show us the answer?

Side remark: Take my apologies for quoting a puzzle that stems from a time, where gender policies were not really in peoples' minds. Of course, not all prisoners are men, and ladies should not be treated as their awards.

Comments

The problem was taken from the following book:
@book{Smul82,
  author={R.M. Smullyan},
  title={Lady or the Tiger and Other Logic Puzzles},
  publisher={Dover Publications},
  year={1982}
}

Answer 1

(T ∧ !L) v (L ∧ !T) v (T ∧ !L)  Is this correct Sir?

Comments

No, it is not. You cannot solve the puzzle by just having variables T and L that would have only two possibilities for L and T. Instead, you must distinguish for every room whether there is a tiger or a lady, and moreover for each sign whether it is true or false. Hence, I would rather suggest to use variables as follows:

* ladyR1,tigerR1 : whether a lady or tiger is in room R1
* ladyR2,tigerR2 : whether a lady or tiger is in room R2
* ladyR3,tigerR3 : whether a lady or tiger is in room R3
* sign1 : whether sign1 is true
* sign2 : whether sign2 is true
* sign3 : whether sign3 is true

---

I understand sir, Thank you.

---

@a_ did you come up with a solution? Would you like to share it with us?

Answer 2

Okay, here is one way how to solve the puzzle using the following variables:

• ladyR1,tigerR1 : whether a lady or tiger is in room R1
• ladyR2,tigerR2 : whether a lady or tiger is in room R2
• ladyR3,tigerR3 : whether a lady or tiger is in room R3
• sign1 : whether sign1 is true
• sign2 : whether sign2 is true
• sign3 : whether sign3 is true

Using these variables, we can formulate the above facts in propositional logic: 

(ladyR1 <-> not tigerR1) &          // either lady or tiger in room R1
(ladyR2 <-> not tigerR2) &          // either lady or tiger in room R2
(ladyR3 <-> not tigerR3) &          // either lady or tiger in room R3
(sign1 <-> tigerR1) &               // sign1's statement
(sign2 <-> ladyR2)  &               // sign2's statement
(sign3 <-> tigerR2) &               // sign3's statement
(  ladyR1 & tigerR2 & tigerR3       // king's statement about the rooms
| tigerR1 &  ladyR2 & tigerR3
| tigerR1 & tigerR2 &  ladyR3
) &
(sign1 -> !sign2 & !sign3) &        // king's statement about the signs
(sign2 -> !sign1 & !sign3) &
(sign3 -> !sign1 & !sign2)

Now, we can reason about the facts written down in propositional logic: 

• Assume sign1 would be true, then !sign2&!sign3 must hold by the king's statement about the signs, and we would have tigerR1, tigerR2, and ladyR2 which is contradicting about R2. Hence, sign1 is false. 
• Assume sign2 is true, then !sign1&!sign3 must hold by the king's statement about the signs, and we would have ladyR1, ladyR2, ladyR2, which contradicts the king's statement about the rooms. Thus, both sign1 and sign2 must be false. 
• Assume sign3 is also false, then we have ladyR1, tigerR2, ladyR2 which is again a contradiction about R2. 

Hence, sign1 and sign2 are false and sign3 is true, and therefore, we have ladyR1, tigerR2, and tigerR3, and we found out what we find in the rooms. Of course, we can also directly compute a BDD or ZDD to see all models of the above formula. The ZDD looks as follows (note that ZDDs suppress the false variables): 

Answer 3

SPOILER: A SOLUTION WITH THREE VARIABLES

Three variables:

L1, L2, L3 for the three doors behind which the puzzle ends in a non-lethal way.

We have the following insights:

• At least one door is non-lethal: L1 ∨ L2 ∨ L3
• No pair of doors can be non-lethal at the same time (¬L1 ∨ ¬L2) ∧ (¬L2 ∨ ¬L3) ∧ (¬L1 ∨ ¬L3)
• We have three signs: I: ¬L1, II: L2, III: ¬L2
• At least one sign is true: ¬L1 ∨ L2 ∨ ¬L2
• No pair of signs can be true at the same time: (¬¬L1 ∨ ¬L2) ∧ (¬L2 ∨ ¬¬L2) ∧ (¬¬L1 ∨ ¬¬L2)

Hence, we can model the problem as the conjunction of the first and the last two insights:

(L1 ∨ L2 ∨ L3) ∧ (¬L1 ∨ ¬L2) ∧ (¬L2 ∨ ¬L3) ∧ (¬L1 ∨ ¬L3) ∧ (¬L1 ∨ L2 ∨ ¬L2) ∧ (¬¬L1 ∨ ¬L2) ∧ (¬L2 ∨ ¬¬L2) ∧ (¬¬L1 ∨ ¬¬L2)

We can now feed this formula in CNF (almost, we need to remove the double negations) to a SAT solver or a BDD package. However, it just has one solution. And something more impressive: We can solve it by hand by just looking at the third insight:

(¬¬L1 ∨ ¬L2) ∧ (¬L2 ∨ ¬¬L2) ∧ (¬¬L1 ∨ ¬¬L2)

The second clause is a tautology and can be ignored. We write the other ones as implications:

(¬L1 → ¬L2) ∧ (¬L1 → ¬¬L2)

So if ¬L1 holds, both ¬L2 and ¬¬L2 become true. Hence, we know that L1 needs to be true and the first door is non-lethal. If we now plug this result in the second insight, we know that the other two doors are lethal. This also makes precisely the third sign true, which validates our solution.

Comments

That's great!!

---

Actually, if you look at my solution, you will see that many variables were just introduced as definitions of others. We can do an existential quantification to eliminate them (to bring in another VRS topic):


∃tigerR1.∃tigerR2.∃tigerR3.∃sign1.∃sign2.∃sign3.
    (ladyR1 <-> not tigerR1) &          // either lady or tiger in room R1
    (ladyR2 <-> not tigerR2) &          // either lady or tiger in room R2
    (ladyR3 <-> not tigerR3) &          // either lady or tiger in room R3
    (sign1 <-> tigerR1) &               // sign1's statement
    (sign2 <-> ladyR2)  &               // sign2's statement
    (sign3 <-> tigerR2) &               // sign3's statement
    (  ladyR1 & tigerR2 & tigerR3       // king's statement about the rooms
    | tigerR1 &  ladyR2 & tigerR3
    | tigerR1 & tigerR2 &  ladyR3
    ) &
    (sign1 -> !sign2 & !sign3) &        // king's statement about the signs
    (sign2 -> !sign1 & !sign3) &
    (sign3 -> !sign1 & !sign2)

This can be simply done by replacing a variable with its "definition", i.e., sign1,sign2,sign3 with tigerR1, ladyR2, tigerR2 and then tigerR1, tigerR2, tigerR3 with !ladyR1, !ladyR2, !ladyR3. What I then get is the following with the same three variables. I guess that the two formulas are equivalent, are they?
 
    (  ladyR1 & !ladyR2 & !ladyR3       // king's statement about the rooms
    | !ladyR1 &  ladyR2 & !ladyR3
    | !ladyR1 & !ladyR2 &  ladyR3
    ) &
    (!ladyR1 -> !ladyR2 & !!ladyR2) &        // king's statement about the signs
    (ladyR2 -> !!ladyR1 & !!ladyR2) &
    (!ladyR2 -> !!ladyR1 & !ladyR2)

---

haha, of course they are equivalent as both of them are equivalent to L1 ∧ ¬L2 & ¬L3.

You can easily see it for your formula:

  (  ladyR1 & !ladyR2 & !ladyR3       // king's statement about the rooms
    | !ladyR1 &  ladyR2 & !ladyR3
    | !ladyR1 & !ladyR2 &  ladyR3
    ) &
    (!ladyR1 -> false) &        // king's statement about the signs
    (ladyR2 -> !!ladyR1 & !!ladyR2) &
    (!ladyR2 -> !!ladyR1 & !ladyR2)

I replace an unsatisfiable conjunction by false. Now the implication becomes a negation and ladyR1 needs to hold. The other two statements about the signs then just become tautologies. The first statement about the rooms is then the only one that can become true. This implies that ladyR2, ladyR3 are false.

Hence, your solution is also equivalent to L1 ∧ ¬L2 & ¬L3, just like mine. So, all the same.

---

Yes, it must be the same finally, or one of them wouldn't be a correct/complete formulation. Canonical normal forms are great and show us that clearly.

It's great to see different approaches finally converging to the same. My other puzzle is however harder...