Propositional logic also describes information flows based on observations or facts that are stated. A simple example shows how.
Consider a simple party with only three possible invitees Anna, Bob and Claudia. Every invitee actually comes to the party. What invitation can you send without conflict due to the constraints below?
- Bob comes to the party if Ann or Claudia comes."
- Ann comes to the party if Claudia does not come."
- If Ann comes to the party, Bob does not.
We use the letters \(a\), \(b\) and \(c\) respectively for "Ann comes to the party.", "Bob comes to the party.", and "Claudia comes to the party." We put a dash above the letter if the person does not come to the party. The \(\bar{a}\) indicates that Ann does not to the party. There are basically \(2^3=8\) possible compositions of the party: \(abc\), \(ab\bar{c}\), \(a\bar{b}c\), \(\bar{a}bc\), \(\bar{a}\bar{b}c\), \(\bar{a}b\bar{c}\), \(a\bar{b}\bar{c}\), and \(\bar{a}\bar{b}\bar{c}\).
The first statement is the proposition \(a\lor c\rightarrow b\) and excludes the options \(a\bar{b}c\), \(\bar{a}\bar{b}c\), and \(a\bar{b}\bar{c}\).
The second statement is the proposition \(\neg\, c\rightarrow a\) and excludes two more options: \(\bar{a}b\bar{c}\) and \(\bar{a}\bar{b}\bar{c}\).
The third message is the proposition \(a\rightarrow \neg\, b\) and excludes two more options: \(abc\) and \(ab\bar{c}\)
The only composition of the party left is \(\bar{a}bc\). In short: send Bob and Claudia an invite to the party to avoid conflict.
The reasoning is more formal when we construct a truth table for the propositions \(u_1: (a\lor c)\rightarrow b\), \(u_2: \neg\,c\rightarrow a\), \(u_3: a\rightarrow \neg\,b\), and \(u_1\land u_2\land u_3\). \[\begin{array}{ccc|cccc} a & b & c & u_1 & u_2 & u_3 & u_1\land u_2\land u_3\\ \hline 0 & 0 & 0 & 1 &0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{array}\] Line 4 in the table is the only line that has the truth value 1 (symbolising true) in the last column. This is the situation that Bob and Claudia come to the party. You can send them an invitation without getting into trouble.
You can also solve riddles with propositional logic!
There are three chairs in a row and three boys each take a seat on one of these chairs. A friend of theirs says he has 5 caps: two blue and three red. He puts a cap on each of them without the boys being able to see which cap they are wearing themselves. The boy at the back sees the caps of the two boys sitting in front of him. The middle one only sees the cap of the front boy in the row, who does not see any cap himself.
The boy in the back seat is asked: “Do you know what is the colour of the cap you are wearing?” He looks at the two caps in front of him, thinks for a moment, and then answers truthfully, “No.” Then the middle boy gets the same questions. He sees only one cap in front of him, thinks and also answers in the negative. The boy in front is silent for a moment and then says: "Then I know the colour of my cap!"
What colour is that?
The boy in the front seat is wearing a red cap.
We can look at all possible distributions of the caps: \(rrr\), \(rrb\), \(rbr\), \(brr\), \(bbr\), \(brb\) and \(rbb\), where the letter \(r\) symbolises a red cap and \(b\) a blue cap; in addition, from left to right, the letters are in order of rear, middle, and front cap wearer.
The answer of the boy in the back seat rules out the \(rbb\) option: if he sees 2 blue caps, then he knows from the friend's information about using 3 red and 2 blue caps that he has a red cap. But he says he doesn't know. So \(rbb\) is impossible.
The answer of the boy in the middle seat excludes the options \(rrb\) and \(brb\) : if the boy in the front seat is wearing a blue cap, then he cannot also be wearing a blue cap because the boy in the back row would then have known what cap he was wearing.
Only options remain with the letter on the right equal to \(r\): the boy in the front seat is therefore wearing a red cap.
In the solution of the riddle above, we have looked at all possible cap distributions and what remains of them in the scenario. But with complicated riddles, the number of possibilities is immense. A shorter solution of the riddle without first listing all possible cap distributions goes as follows.
The last boy does not see two blue caps in front of him because then he could conclude that he is wearing a red cap because there are no more caps of a different colour available.
This means that there are three possible cap distributions for the boys in the middle and front seats: \(rr\), \(rb\) and \(br\). But if the boy in the middle seat sees a blue cap in front of him, then he already knows the colour of his own cap: if it were blue, the boy in the back seat would also have known what kind of cap he is wearing. The remaining option \(rb\) is also dropped.
Because the boy in the middle seat answers "No.", the boy in the front seat knows that the only remaining options are \(rr\) and \(br\). In both cases he wears a red cap. So he knows the colour of his cap.
The puzzle below is from the book The lady or the tiger? by Raymond Smullyan.
The king of a land far away takes pleasure in letting his captives solve logic puzzles. He also wants to give his two daughters in marriage to a man who masters the art of reasoning like a true master. A prisoner has the choice to open one of two doors. Behind every door is either a lady or a tiger. There are signs on the doors that give the prisoner information:
Door 1: "Behind this door is a lady, and behind the other door is a tiger."
Door 2: "Behind one of the two doors is a lady, and behind the other a tiger."
The king tells the prisoner that one of the two signs is telling the truth, but the other is not. If the king is telling the truth and the prisoner would rather marry the lady than be eaten by the tiger, which door should he open?
He must open Door 2 to mary a lady.
Exactly one of the two signs is true. So suppose the sign on door 1 is true. Then behind door 1 a lady is waiting and behind door 2 a tiger. That also makes the sign on door 2 true, but that cannot be because the king said that only one of the two signs was true. So we have a contradiction. From this we can conclude that the sign on door 1 is false and the sign on door 2 is true, that is, behind one of the doors is a lady and behind the other a tiger. Because the sign on door 1 is false, it cannot be the case that the lady is behind door 1 and the tiger is behind door 2. The only possibility is that the lady is in the room behind door 2 and the tiger is in the room behind door 1. The prisoner better opens door 2 to marry the lady.
Now let us formalise and solve the problem using propositional notation. There are four possible situations, because behind each door there can be either a lady or a tiger. Let \(p_1\) symbolise "There is a lady in the room behind door 1." , and let \(p_2\) stand for "There is a lady in the room behind door 2." The four possible situations then correspond to the four possible truth-value assignments to these two statements. The statement on door 1 can now be written as \[p_1\land \neg\,p_2\] while the statement on door 2 can be written as \[(p_1\lor p_2)\land (\neg\,p_1 \lor \neg\, p_2)\] which means: there is a lady in room 1 or 2, and there is a tiger (and therefore: no lady) in room 1 or 2. Let us abbreviate these two formulas as \(d_1\) and \(d_2\), respectively. The king says that exactly one of the two signs must be true, so \[(d_1 \land \neg d_2) \lor (\neg d_1 \land d_1)\] Now that the problem has been transcribed into propositional language, the question is: in what situations is this formula true? The truth table for the last formula gives the answer: \[\begin{array}{cc|ccc} p_1 & p_2 & d_1 & d_2 & (d_1 \land \neg d_2) \lor (\neg d_1 \land d_1)\\ \hline 0 & 0 & 0 & 0 &0 \\ 0 & 1 & 0 & 1 &1 \\ 1 & 0 & 1 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 \end{array}\] So there is only one situation where the king tells the truth, line 2 of the truth table, the situation where the tiger is behind door 1 and the lady is behind door 2.
Strictly speaking, we do not need the last column because we can also see in the partial table with the first four columns that there is only one row in which one of the statements on the doors is true (which is also what the king says).
Logic puzzles
