1Basic Syntax & Semantics
Problem 1.1: Propositions
Which of the following are propositions?
a) "It is raining today"
b) "What is 2+2?"
c) "Close the door!"
d) "All birds can fly"
Problem 1.2: English to Logic
Let P = "It's sunny", Q = "It's warm", R = "We go swimming"
Translate: "If it's sunny and warm, then we go swimming"
Problem 1.3: Logic to English
Let P = "It's raining", Q = "I stay home"
Translate: P → Q
Problem 1.4: Complex Translation
Let A = "Alice is happy", B = "Bob is sad", C = "Carol is working"
Translate: "Alice is happy if and only if Bob is not sad, and Carol is working"
2Truth Tables
Problem 2.1: Simple Truth Table
Construct truth table for: P ∧ Q
| P | Q | P ∧ Q |
|---|---|---|
| T | T | |
| T | F | |
| F | T | |
| F | F |
Problem 2.2: Implication Truth Table
Construct truth table for: P → Q
| P | Q | P → Q |
|---|---|---|
| T | T | |
| T | F | |
| F | T | |
| F | F |
Problem 2.3: Complex Truth Table
Construct truth table for: (P ∨ Q) ∧ (¬P ∨ R)
| P | Q | R | P ∨ Q | ¬P | ¬P ∨ R | (P ∨ Q) ∧ (¬P ∨ R) |
|---|---|---|---|---|---|---|
| T | T | T | ||||
| T | T | F | ||||
| T | F | T | ||||
| T | F | F | ||||
| F | T | T | ||||
| F | T | F | ||||
| F | F | T | ||||
| F | F | F |
Problem 2.4: Tautology Check
Is (P → Q) ∨ (Q → P) a tautology?
3Logical Equivalences
Problem 3.1: De Morgan's Laws
Apply De Morgan's law to: ¬(P ∧ Q)
Problem 3.2: Double Negation
Simplify: ¬¬P
Problem 3.3: Distributive Law
Apply distributive law to: P ∧ (Q ∨ R)
Problem 3.4: Absorption Law
Simplify: P ∨ (P ∧ Q)
4CNF Conversion
Problem 4.1: Basic CNF
Convert to CNF: P → Q
Problem 4.2: Complex CNF
Convert to CNF: (P ∨ Q) → R
Problem 4.3: Step-by-Step CNF
Convert to CNF: ¬(P ∧ Q) ∨ R
Problem 4.4: CNF Validation
Given CNF: (A ∨ B) ∧ (¬A ∨ C) ∧ (¬B ∨ D)
Assignment: A=T, B=F, C=T, D=F
Is this assignment satisfying?
5Resolution & Inference
Problem 5.1: Resolution Rule
Given clauses: {P ∨ Q, ¬P ∨ R}
What can you resolve?
Problem 5.2: Modus Ponens
Given: P → Q, P
What can you conclude?
Problem 5.3: Chain Rule
Given: P → Q, Q → R, P
Prove: R
Problem 5.4: Contradiction
Given: P ∨ Q, ¬P, ¬Q
What does this lead to?
6Real-World Applications
Problem 6.1: Wumpus World
Let B = "Breeze", P = "Pit", S = "Stench", W = "Wumpus"
Rule: "If there's a breeze, there's a pit nearby"
Problem 6.2: Medical Diagnosis
Let F = "Fever", C = "Cough", I = "Infection"
Rule: "If fever and cough, then infection"
Problem 6.3: Circuit Logic
Let A = "Switch A", B = "Switch B", L = "Light on"
Rule: "Light is on if and only if both switches are on"
Problem 6.4: Security System
Let M = "Motion detected", D = "Door open", A = "Alarm"
Rule: "Alarm goes off if motion is detected or door is open"