Tim Axoy
2003-06-01 03:19:50 |
Knights and liars problems
Here is a way to solve Knights and liars problems using propositional logic.
1:Suppose a knight or a liar says,"The proposition P is true."
We notice that if they are a knight,then P is true and if P is true,then they are a knight,so they are a knight if and only if P is true.
In symbols,K<->P is true,where K is the proposition that they are a knight.
2:We use ~ to mean not,& to mean and,v to mean or,-> to mean if-then,and <-> to mean if-and-only-if.
3:In a puzzle with more than one person,we let Kk be the proposition that the kth person is a knight.
4:We let ~K be the proposition that a person is a liar and ~Kk be the proposition that the kth person is a liar.
5:Example:A says,"B and I are both liars."
Let A be the first person and B be the second person,so K1=A is a knight,K2=B is a knight,~K1=A is a liar,and ~K2=B is a liar.
A asserted (~K1)&(~K2),so by 1,K1<->((~K1)&(~K2)) is true.
Obviously K1 is false since if it was true,then K1 and K2 would both be false,which is a contradiction.
Since K1 is false and equivalent to (~K1)&(~K2),(~K1)&(~K2) is also false,but ~K1 is true,so ~K2 is false.
Therefore,K1 is false and K2 is true,so A is a liar and B is a knight. |
Tim Axoy
2003-06-02 02:46:56 |
Another example
This example is called,"Why no one can claim to be a liar."
Obviously,there is no proposition K such that K<->(~K) is true.
Suppose A says,"I am a liar."
A asserted ~K,and by our knights and liars trick,K<->(~K) is true.
However,that is impossible. |
Tim Axoy
2003-06-06 06:14:15 |
Re: Knights and liars problems
Does anyone like this? |
Lewis
2003-06-06 12:21:06 |
Re: Knights and liars problems
Hmmmm.... I was a little confused at first but now I understand. Very nice Tim :) |
Tim Axoy
2003-06-07 09:33:55 |
Re: Knights and liars problems
Anyone else? |
