Propositional Logic
Introduction
Propositional logic is the formal language of Chapter 7. It is decidable, has tractable inference algorithms for moderate-sized problems, and is the foundation for all inference algorithms introduced later.
Syntax (BNF Grammar)
Sentence → AtomicSentence | ComplexSentence
AtomicSentence → True | False | Symbol
Symbol → P | Q | R | B_1_1 | Pit_2_3 | ...
ComplexSentence →
¬ Sentence
| Sentence ∧ Sentence
| Sentence ∨ Sentence
| Sentence → Sentence
| Sentence ↔ Sentence
| ( Sentence )Operator Precedence (high → low)
¬(unary, highest)∧∨→(right-associative)↔︎(lowest)
Terminology
- Atom: A propositional symbol or True/False.
- Literal: An atom or its negation.
- Clause: A disjunction of literals:
(L₁ ∨ L₂ ∨ ... ∨ Lk).
Semantics: Truth Tables
All Connectives
| P | Q | ¬P | P∧Q | P∨Q | P→Q | P↔︎Q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Implication key insight: P → Q is false
only when P=T and Q=F. Vacuously true when P=F.
Biconditional: true iff P and Q have the same truth value.
Sentence Evaluation Example
Model: m = {P=T, Q=F, R=T} Sentence:
¬P ∨ (Q → R)
Q → R: F→T = T¬P: ¬T = FF ∨ T= T ✓
Propositional Wumpus World Encoding
-- Breeze-pit axiom for [i,j]:
B_i_j ↔ (P_{i+1,j} ∨ P_{i-1,j} ∨ P_{i,j+1} ∨ P_{i,j-1})
-- Safe square:
OK_i_j ↔ ¬P_i_j ∧ ¬W_i_j
-- Percept at t=0:
¬B_1_1
¬S_1_1
¬P_1_1Inference:
{¬B_1_1, B_1_1 ↔︎ (P_1_2 ∨ P_2_1)} ⊨ ¬P_1_2 ∧ ¬P_2_1
Expressiveness Limitations
- Cannot write “for all squares” — must write one sentence per square.
- Cannot represent changing agent position without time-indexed symbols → symbol explosion.
- No quantifiers, no relations, no functions.
These limitations motivate first-order logic (Chapter 8).