Recitation 3: Practice with Propositional and Predicate Logic

In this recitation you will practice translating problems into propositional and predicate logic.

Knights and Knaves

You are on an island populated entirely by an interesting kind of people - each citizen on the island is either a knight or a knave:

All knights tell only the truth.
All knaves tell only lies.

What can you say about each individual in the following situations?

You meet two individuals. The first says “We are both knaves.” The second says nothing.
You meet two individuals. The first says “We are both the same kind.” The second says “We are each a different kind.”
You meet three individuals. The first says “The second is a knave.” The second says “The third is not a knave.” The third says “I am a knight or the first is a knight.”

There is actually another kind of citizen on this island, the noble:

Nobles can tell either truths or lies.

What can you say about each individual in the following situations? If there isn’t a unique answer, try to list all of the possibilities.

You meet three individuals. You know one is a knight, one is a knave, and one is a noble. The first says “The third is a knave.” The second says “The first is a knight.” The third says “I am a noble.”
You meet three individuals. The first says “I am a knave and only a knave would say we are all knaves.” The second says “We are all knaves.” The third says “I am a knight.”

Hat-wearing prisoners

Four prisoners are given the opportunity to end their sentence early if they can solve a puzzle. Their jailer tells them that he has two white hats and two black hats. The jailer seats three of the prisoners in a line, the first facing a wall, the second facing the first, and the third facing the second (he can see the first also). The fourth prisoner is put in a separate room. The jailer then gives each of the prisoners a hat and tells them that if any of them can say the color of their hat with absolute certainty then they can all go free. How can you represent this situation using propositional and predicate logic? How can the prisoners walk free?

Pirates

Let’s consider another complicated system of people using propositional logic. Consider 5 pirates who are deciding how to distribute 100 gold coins amongst themselves. To do this, they have a few rules about how to distribute the gold:

The pirates have seniority levels - let’s say the senior most is Blackbeard, then Ching Shih, then Grace O’Malley, then Barbarossa, then Jack Sparrow.
The most senior pirate (Blackbeard) gets to propose a distribution of coins
All pirates vote on whether to accept the distribution
If a majority doesn’t vote to accept the distribution, the proposer is thrown over and the next most senior pirate makes a new proposal
If there’s a tie, the proposer has the casting vote

Each pirate also has a few rules they want to follow:

Every pirate wants to survive
Given that a pirate is surviving, that pirate wants to maximize the number of gold coins they recieve

Given these rules, What is the distribution of gold coins among the five pirates? What if there were four pirates? What if there were six? What if there were 20? What is the pattern if there are more pirates than coins?

Eye-Color Island

A group of perfect logicians live on an island. There are no mirrors on the island, so no one knows the color of their own eyes. Every night at midnight, a ferry stops at the island. Any islanders who know the color of their eyes are able to leave the island but no one else can. Everyone can see everyone else and keeps a count of how many people have each eye color (except, of course, themselves) but they cannot otherwise communicate. Let’s say there are 100 people with blue eyes and 100 people with brown eyes. One day, the ferryman announces to the island “I can see someone who has blue eyes.” Based on this new information the islanders have, do they leave the island, and if so, on what night after the announcement do they? How can you represent this situation using propositional and predicate logic?