Logic Puzzles: Knights and Knaves

There are some fun (and often frustrating) logic puzzles that involve knights and knaves.  Knights always tell the truth, and knaves always lie.  Here is a sample of a puzzle:

There are three people (Alex, Brook and Cody), one of whom is a knight, one a knave, and one a spy.

The knight always tells the truth, the knave always lies, and the spy can either lie or tell the truth.

Alex says: "Cody is a knave."
Brook says: "Alex is a knight."
Cody says: "I am the spy."

Who is the knight, who the knave, and who the spy?

This comes from the website  http://www.mathsisfun.com/puzzles/knights-and-knaves.html (which includes a solution).  The website is a great source for other logic puzzles.

Here is an image that relates to work we have done in class.  Patrick says "I am a knight and Quin is a knight".  Quin says "Patrick is not a knight".  The first row of the table would be if they are both knights, but then this contradicts what Quin says.  The second row is when Patrick is a knight and Quin is a knave.  This row contradicts their statements.  The third row is when Patrick is a knave and Quin is a knight.  This does NOT contradict their statements.  The fourth row is when they are both knaves, but then Quin's statement would be true which is a contradiction.  So only the third row works, Patrick is a knave and Quin is a knight.



Knights and Knaves puzzles are so popular that they even have their own wikipedia page:
http://en.wikipedia.org/wiki/Knights_and_Knaves

Here is a video showing how to solve a knights and knaves problem:
https://www.youtube.com/watch?v=tQr7D92Plck

They are great ways to frustrate your friends :)

Different Kinds of Infinity

Two sets are equivalent if the elements from one set can be put in one-to-one correspondence with the elements of another.  For example, if A = {a,b,c} and B = {1,2,3}, then the sets are not equal but they are equivalent, we could match a with 1, b with 2, and c with 3.  For finite sets, you just need to check the cardinalities.  If n(A)=n(B) then A and B are equivalent.

What about infinite sets?  Things get really interesting :)

The naturals {1,2,3,...} are said to be countably infinite.  We can show that this set is equivalent to the evens {2,4,6,...} (seems a bit counter-intuitive, but infinite sets are pretty cool that way).  We can also show that it is equivalent to the integers {..., -2, -1, 0, 1, 2, 3, ...}.  Any set that can be shown to be equivalent to the naturals is countably infinite.  Are all infinite sets countable?  Nope.  The reals are not, and Cantor's diagonal proof is an example of some beautiful mathematics (we will talk about it in class).

Here is a link to more math about infinite sets: http://www.trottermath.net/personal/infinity.html

And here is a link to a really cool video by Vi Hart about the different infinities:
How many kinds of infinity are there?
Proof some infinities are bigger than others