Logic Puzzles Lab

Unit 5: Introduction to Logic in AI — Lab

75 Points Total

Logic puzzles are one of the oldest forms of reasoning training. Long before computers, mathematicians and philosophers used puzzles to sharpen their deductive skills. In this lab you will solve classic logic puzzles using Python — translating natural language clues into propositional and first-order logic formulas, then writing code to evaluate those formulas systematically.

Lab Objectives

By completing this lab, you will:

  1. Translate natural language puzzle clues into propositional logic formulas

  2. Apply truth tables and systematic search to find consistent solutions

  3. Represent family relationships using first-order logic predicates

  4. Implement a Python truth table generator

  5. Practice constraint satisfaction as a logical reasoning strategy

Prerequisite concepts from this unit:

  • Propositions and propositional variables (Section 5.2)

  • Logical connectives: ∧, ∨, ¬, →, ↔ (Section 5.2)

  • Truth tables and logical equivalence (Section 5.3)

  • Entailment: α ⊨ β (Section 5.3)

  • First-order logic predicates and quantifiers (Section 5.5)

Lab Structure

Part Task Points

1

Knights and Knaves Puzzle

20

2

Who Owns the Zebra?

25

3

Family Relationships in FOL

15

4

Build a Truth Table Solver

15

Lab Notebook

Download the Jupyter notebook with starter code and complete the TODO sections.

File: Logic_Puzzles_Lab.ipynb

Download Logic_Puzzles_Lab.ipynb

Lab workflow overview:

  1. Download the notebook and open it in Google Colab or a local Jupyter environment

  2. Read the background and constraints for each part before coding

  3. Complete each TODO section with working Python code

  4. Add markdown cells explaining your logical reasoning

  5. Run all cells to verify correct output

  6. Rename the file Logic_Puzzles_Lab_[YourLastName].ipynb and submit

Part 1: Knights and Knaves (20 points)

Background: On an isolated island, every inhabitant is either a Knight (who always tells the truth) or a Knave (who always lies). You meet three inhabitants: Alice, Bob, and Carol.

The statements:

  • Alice says: "I am a knave."

  • Bob says: "Alice is a knight."

  • Carol says: "Bob is a knave."

Setting up the logic:

Let KA, KB, KC be propositions meaning "Alice/Bob/Carol is a Knight."

The key constraint:

  • If a person is a Knight, their statement is true

  • If a person is a Knave, their statement is false

So Alice’s statement ("I am a knave") translates as: KA ↔ ¬KA

Wait — that is a contradiction! That means the only consistent assignment for Alice is Knave (since if she were a Knight she would be telling the truth about being a Knave, which contradicts being a Knight). Work through Bob and Carol similarly.

Your tasks:

  1. Translate each statement into a propositional logic formula (5 pts)

  2. Create a truth table listing all 8 possible knight/knave assignments for Alice, Bob, and Carol (5 pts)

  3. Apply logical consistency rules to eliminate impossible assignments (5 pts)

  4. Determine who is a Knight and who is a Knave (5 pts)

Part 2: Who Owns the Zebra? (25 points)

Background: This is a classic constraint-satisfaction puzzle (also called "Einstein’s puzzle"). Five houses stand in a row, each a different color. One person per house, each of a different nationality. Each person drinks a different beverage, smokes different cigarettes, and keeps a different pet.

The 15 clues:

  1. The Brit lives in the red house

  2. The Swede keeps dogs

  3. The Dane drinks tea

  4. The green house is directly to the left of the white house

  5. The green house owner drinks coffee

  6. The person who smokes Pall Mall keeps birds

  7. The owner of the yellow house smokes Dunhill

  8. The person in the center house drinks milk

  9. The Norwegian lives in the first house

  10. The person who smokes Blend lives next to the cat owner

  11. The horse owner lives next to the Dunhill smoker

  12. The BlueMaster smoker drinks beer

  13. The German smokes Prince

  14. The Norwegian lives next to the blue house

  15. The Blend smoker lives next to the water drinker

Your tasks:

  1. Represent the problem using first-order logic predicates (10 pts):

    • Define predicates for house, nationality, beverage, cigarette, and pet assignments

    • Express each clue as a logical formula

  2. Implement a constraint satisfaction solution in Python using itertools to generate and check permutations (10 pts)

  3. Determine who owns the zebra and who drinks water (5 pts)

Use Python’s itertools.permutations to generate all arrangements of nationalities, beverages, etc. across the five houses. Write a check_constraints function that tests all 15 clues against a given arrangement. Return the first arrangement that satisfies all constraints.

Part 3: Family Relationships in FOL (15 points)

Define family relationships using first-order logic predicates and rules.

Base predicates (given):

  • Parent(x, y) — x is a parent of y

  • Male(x) — x is male

  • Female(x) — x is female

Your tasks — define each derived relation (3 points each):

  1. Father(x, y) — x is the father of y

  2. Mother(x, y) — x is the mother of y

  3. Sibling(x, y) — x is a sibling of y (share at least one parent; x ≠ y)

  4. Grandparent(x, y) — x is a grandparent of y

  5. Uncle(x, y) — x is an uncle of y (male sibling of a parent)

Example format:

Father(x, y) ≡ Parent(x, y) ∧ Male(x)

"x is the father of y if x is a parent of y AND x is male."

For each definition, also write a Python function that accepts a list of known Parent, Male, and Female facts and determines whether the derived relation holds for a given pair.

Part 4: Build a Truth Table Solver (15 points)

Implement a Python function that automatically generates and displays a truth table for any propositional logic formula.

Requirements:

  1. Accept formulas using Python syntax: and, or, not, → for implication (3 pts)

  2. Parse the formula to extract all unique variable names (3 pts)

  3. Generate all 2n truth value combinations for n variables (4 pts)

  4. Display the results in a formatted table (5 pts)

Expected output for formula "P → Q":

P | Q | P -> Q
--+---+-------
T | T |   T
T | F |   F
F | T |   T
F | F |   T

Test your solver on at least three formulas: * "P and Q" * "not P or Q" (verify it matches "P → Q") * "(P or Q) and (not P or R)"

Submission Requirements

Requirement Details

File name

Logic_Puzzles_Lab_[YourLastName].ipynb

Completeness

All TODO sections replaced with working code

Execution

All cells executed with visible output (no errors)

Explanations

Markdown cells showing logical reasoning and derivation steps

Test results

All provided test cases pass

Submission steps:

  1. Run all cells in order (Kernel → Restart and Run All)

  2. Confirm no errors appear

  3. Save the notebook

  4. Rename: Logic_Puzzles_Lab_[YourLastName].ipynb

  5. Submit via Brightspace: Assignments → Logic Puzzles Lab

Grading Rubric

Criterion Description Points

Correctness

Solutions are logically sound; correct answers for all four parts

40

Code Quality

Clean, well-commented code following Python best practices

15

Explanations

Markdown cells clearly explain reasoning and logical derivations

15

Completeness

All parts attempted; all provided test cases pass

5

TOTAL

75

Going further:

The Python logic and pysat libraries provide production-quality SAT solvers. The python-constraint library implements constraint satisfaction similar to what you built in Part 2 but with much greater efficiency. The sympy.logic module offers symbolic logic tools. If you found Part 2 interesting, explore how modern SAT solvers handle millions of variables using the DPLL algorithm or CDCL (Conflict-Driven Clause Learning).

See the Solution Walkthrough →

Next: 5.W Wrap-Up and Self-Assessment →

Lab code adapted from aima-python, MIT License, Copyright 2016 aima-python contributors.

This work is licensed under CC BY-SA 4.0.