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?

Challenge: 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?