Knights and Knaves Propositional Logic

Question

I have a question regarding Knights and Knaves and logical proposition. If I want to solve the puzzle and I assume I have two kinds of citizens: Knights, who always tell the truth, and knaves, who always tell lies. On the basis of utterances from some citizens, I must decide what kind they are.

There are three citizens: a, b and c, who are talking about themselves:

a says: ”All of us are knaves.”
b says: ”Exactly one of us is a knight.”

To solve the puzzle I should determine:

What kinds of citizens are a, b and c?

I should solve the puzzle by modelling the two utterances above using propositional logic, and I assume that I can use p to describe a knight and ¬p to describe a knave. How would I go about doing that? Any hint for someone who hasn't done any noticeable discrete mathematics in college?

Answer 1

I would suggest making a truth table and checking it (removing the need for ¬, you can use T and F for True and False):

 12345678 
aTTTTFFFF
bTTFFTTFF
cTFTFTFTF

Then you can check it.

Statement a is that a=b=c=F, so if a=T it means a=F, so then a=F.
So then it can't be option 8, otherwise a=b=c=F and a=T.
Statement b is that one of a, b and c is =T.
Then if 5 is correct, b=F because there would be two T's.
So 6 or 7 is correct. Since in both there are exactly 1 T, b=T, so then 6 is correct.

And the answer is:

Then a is a knave, b is a knight and c is a knave.

Answer 2

Basically, I would agree with @boboquack that a truth table is the way to go. What you want to say goes beyond what you can represent reasonably in propositional logic. You have people and you have statements. The people make statements about statements. You really want to say something about the relationship of the people to the statements you make and for this you need a more complex notation. You want something like this:

$$\forall (x) (KNIGHT(x) \rightarrow (\forall (y) (SAYS(x, y) \rightarrow y))) $$

That is, anyone who is a knight makes only true statements or "For ALL $x$, IF $x$ is a KNIGHT THEN for ALL $y$, IF $x$ SAYS $y$ THEN $y$ is true." So, $SAYS(x,y)$ means that the "$SAYS$" relationship holds between $x$ and $y$.

Similarly,

$$\forall (x) (\lnot KNIGHT(x) \rightarrow (\forall (y) (SAYS(x, y) \rightarrow \lnot y))) $$

If $x$ is not a knight, and $x$ says $y$ then $y$ is not true.

The first statement made by $a$ becomes:

$$ SAYS(a, \lnot KNIGHT(a) \land \lnot KNIGHT(b) \land \lnot KNIGHT(c)) $$

That is, $a$ says that $a$ is not a knight and $b$ is not a knight and $c$ is not a knight. You can show that assuming the truth of this statement leads to a contradiction. To be thorough, you need to translate all the information into logical notation: $a$, $b$, and $c$ are persons and everyone who is a person must be either a knight or a knave. I leave this for you to work out.

The second statement is also a bit tricky. I would translate part of it as:

$$ SAYS(b, KNIGHT(a) \rightarrow (\lnot KNIGHT(b) \land \lnot KNIGHT(c)) $$

If $a$ is a knight then neither $b$ nor $c$ is a knight. He is also making similar statements about the knighthood of $b$ and $c$. Put this all together and you will (eventually) arrive at the desired conclusion.

A truth table is way easier.

If you want to stick to propositional logic you could write $a$'s first statement as:

$$\lnot PA \land \lnot PB \land \lnot PC$$

where $PA$ represents the statement "$a$ is a truth teller". Similarly for $PB$ and $PC$. You then have to know that $\lnot PA$ implies that this statement itself is false which implies that $PB$ or $PC$ is true... and so on.