Recitation 3: Practice with Propositional and Predicate Logic

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

Instructions:

Tic-Tac-Toe

We’ll first represent tic-tac-toe using propositional logic.

1. What predicates would you need to represent a given board state?
   • Would it be useful to know if a space had an X or an O on it?
   • How could you represent each space?
2. How would you check if a move is legal?
   • Define a predicate that returns true if a move is legal and false otherwise.
3. How would you describe a win for the X’s? For the O’s?
4. How would you represent the game board for any given game state? What about the one pictured below?

Knights and Knaves

Now we’ll represent a complicated system of people using propositional logic. Represent the following statements using propositional logic and use them to answer the related questions.

• All knights tell only the truth.
• All knaves tell only lies.
• Lords can tell either truths or lies.
• Lord Arthur is a knight.
• Lord Henry is a knave.
• All knights have squires.
• All squires have a lord.
• Every squire who has a knight only tells the truth.

1. Is there a lord who only lies?
2. Is there a lord who only tells the truth?
3. If there are ten squires, how many knights could there be?
4. If there are ten knights, how many squires could there be?
5. If there are ten knights and ten squires are all of the above statements still true?
6. You meet three individuals. The first says “I am a squire and only a knave would say my lord is a knave.” The second says “This is my squire and we are all knaves.” The third says “I am a knight.” What can you say about each individual?

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. 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?

Challenges:

Sudoku

Sudoku takes place on a 9x9 grid of 81 squares with a 3x3 overlay of 9 blocks, each of which contains 9 squares. The goal is to have each number from one through nine appear exactly once in each row, each column, and each block. A given puzzle is supposed to have a unique solution when these constraints are satisfied.

Represent sudoku using propositional logic. Hint: predicates can take more than just one or two arguments.

• Does representing sudoku this way tell you if a game state is solvable?
• Does representing sudoku this way tell you if a game state has only one solution?
• Does representing sudoku in this way make the game easier to solve?

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?

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.” How can you represent this situation using propositional and predicate logic? Do the islanders leave the island, and if so on what night after the announcement do they?