by Brian Bosse, Copyright March 26, 2008, all rights reserved. 32 views
You are on a game show where there are two doors in front of you - door #1 and door #2. The host of the show tells you that behind one of the doors is one million dollars and behind the other door is nothing. It is your job to figure out behind which door is the million dollars. The host says to you, "You may make one statement (proposition) to my assistant to which she will answer either 'true' or 'false'. My assistant either always tells the truth or always lies."
Problem: Given the above information, construct a sentence so that after the assistant answers you know behind which door is the million dollars.
Solution: The assistant is a truth teller if and only if the million dollars is behind door #1. (Highlight the prior area to see one possible answer.)
There is a way to construct such a sentence on purpose. To begin, let's use the following scheme of abbreviation:
P: The assistant always tells the truth.
Q: The million dollars is behind door #1.
To begin, we will construct the following truth-table…
P | Q | Desired Response | Value of Sentence
T T
T F
F T
F F
At this point we have simply listed all of the possible truth-value combinations for P and Q. The column labled 'desired response' is simply what we want the assistant to answer in each particular situation given our sentence. As such, we choose to create a sentence that if the assistant always tells the truth and the million dollars is behind door #1, then the assistant answers 'true'. In other words, if P=T and Q=T, then the desired response is 'true'. (Note: we could just as easily choose the desired response to be 'false'.)
In like manner, if the assistant always tells the truth and the million dollars is not behind door #1, then the assistant answers 'false' to our sentence. In other words, if P=T and Q=F, then the desired response is 'false'. Here is what this looks like…
P | Q | Desired Response | Value of Sentence
T T True
T F False
F T
F F
At this point, if we are fortunate to get a truth telling assistant, then we have a way of knowing behind which door contains a million dollars. All we need to do is construct a sentence using P and Q such that if Q=T, then the sentence is true, and if Q=F, then the sentence is false. So, if the assistant were to answer 'true' to our statment, then we would know that the million dollars is behind door #1. If the assistant were to answer 'false' to our statment, then we would know that the million dollars is behind door #2. This is what this looks like…
P | Q | Desired Response | Value of Sentence
T T True True
T F False False
F T
F F
This good as far as things go, but we still have a problem. We do not know if the assistant is in fact a truth teller. She may well be a liar. What do we do now? Well, we still want the assistant to answer 'true' when the million dollars is behind door #1 and false when it is not. That is to say, if P=F (the assistant is not a truth teller), then she answers 'true' if Q=T, and she answers 'false' is Q is false. This looks like this…
P | Q | Desired Response | Value of Sentence
T T True True
T F False False
F T True
F F False
If we can find a sentence that would produce these kinds of results, then we would be good. In this situation, no matter whether or not the assistant is a truth teller, a response of 'true' tells you that the million dollars is behind door #1 and a response of false is behind door #2. So, what would be the truth value of a given sentence if the assistant was a liar (P=F), and the person answered 'true'? The sentence must be false. By the same token, if the assistant answers 'false', then the sentence must be true. This looks like this…
P | Q | Desired Response | Value of Sentence
T T True True
T F False False
F T True False
F F False True
Consider the column with the red values. If we can construct a sentence using P and Q such that its truth value is <T, F, F, T>, then we have our answer. A way to determine a sentence is to consider its Disjunctive Normal Form (DNF). That just means that we look at the values for P and Q when the sentence is true. Notice, the sentence is true only when both P and Q are true (P ∧ Q) or when both P and Q are false (¬P ∧ ¬Q) . This is symbolized as: ((P ∧ Q) ∨ (¬P ∧ ¬Q)), and is one answer. It says, "either the assistant is a truth teller and the million dollars is behind door #1 or the assistant is not a truth teller and the million dollars is not behind door #1."
Another answer is to use the Conjunctive Normal Form. The first step is to take the dual of the DNF, which means exchanging every '∧' for '∨' and vice versa, along with changing every sentence letter to its negation. This gives us: ((¬P ∨ ¬Q) ∧ (P ∨ Q)). The negation of the dual is tautologically equivalent to the DNF. So, we negate the dual for the answer: ¬((¬P ∨ ¬Q) ∧ (P ∨ Q)). This sentence says, "It is not the case that (either the assistant is not a truth teller or the million dollars is not behind door#1) and (either the assistant is a truth teller or the million dollars is behind door #1)." Of course, both of these sentences are a little complicated. Is there a more simple answer? Yes, there is…
By definition, here is a list of some truth values for our various logical connectives…
P | Q | ¬P | P → Q | P ∧ Q | P ∨ Q | P ↔ Q
T T F T T T T
T F T F F T F
F T F T F T F
F F T T F F T
As you can see, P ↔ Q has the very truth value we are looking for. As such, this is a very simple answer. It says, "The assistant is a truth teller if and only if the million dollars is behind door #1."
-----No comments yet.