AI Notes
Master logic for AI. Propositions, operators, truth tables. AI fundamentals 2024.
What is Propositional Logic?
Propositional logic (also called sentential logic or Boolean logic) is the simplest formal logic system. It deals with propositions—declarative statements that are either true or false—and logical connectives that combine them. Every AI reasoning system builds upon propositional logic as its foundation, from expert system inference engines to satisfiability solvers used in hardware verification.
While propositional logic lacks the expressiveness of predicate logic (it cannot reason about objects, properties, or quantifiers), its simplicity makes it computationally tractable for many problems. SAT solvers—algorithms for propositional satisfiability—are among the most practically important tools in computer science, solving problems in circuit design, software verification, planning, and scheduling.
Syntax: Building Blocks
Propositions (Atomic Sentences)
| P | "It is raining" |
| Q | "The ground is wet" |
| R | "I carry an umbrella" |
| S | "The match is today" |
| Each proposition has exactly one truth value | T or F |
Logical Connectives
| ¬P (NOT, negation) | "It is NOT raining" |
| P ∧ Q (AND, conjunction) | "It is raining AND ground is wet" |
| P ∨ Q (OR, disjunction) | "It is raining OR I carry umbrella" |
| P | Q (IMPLIES, conditional): "IF raining THEN ground is wet" |
| P ↔ Q (IFF, biconditional) | "Raining IF AND ONLY IF ground wet" |
Operator Precedence
| Highest | ¬ (not) |
| Lowest | ↔ (iff) |
| Example: ¬P ∧ Q | R means (((¬P) ∧ Q) → R) |
Semantics: Truth Tables
Truth Table for All Connectives
The Material Conditional (→)
The most counterintuitive connective: P→Q is FALSE only when P is true and Q is false.
| "If it rains, the ground is wet" (P | Q) |
| Rain + wet ground = T | T = TRUE ✓ |
| Rain + dry ground = T | F = FALSE ✓ (promise broken!) |
| No rain + wet ground = F | T = TRUE (sprinkler? doesn't violate promise) |
| No rain + dry ground = F | F = TRUE (promise not tested) |
| Key insight | A false premise makes any implication TRUE |
Logical Equivalences
Important Laws
| Double negation | ¬¬P ≡ P |
| Commutativity | P ∧ Q ≡ Q ∧ P; P ∨ Q ≡ Q ∨ P |
| Associativity | (P∧Q)∧R ≡ P∧(Q∧R) |
| Distributivity | P∧(Q∨R) ≡ (P∧Q)∨(P∧R) |
| De Morgan's | ¬(P∧Q) ≡ ¬P∨¬Q |
| Implication: P | Q ≡ ¬P∨Q |
| Contrapositive: P | Q ≡ ¬Q→¬P |
Worked Example: Simplification
| Simplify: ¬(P | Q) ∨ Q |
| Step 1: P | Q ≡ ¬P∨Q |
| Step 2 | De Morgan's on ¬(¬P ∨ Q): |
| Step 3 | Distribute ∨ over ∧: |
| Step 4 | ¬Q ∨ Q ≡ T (tautology): |
| Result: ¬(P | Q) ∨ Q ≡ P ∨ Q |
Inference Rules
Fundamental Rules
| Modus Ponens | Modus Tollens: |
| P | Q P → Q |
| Hypothetical Syllogism | Disjunctive Syllogism: |
| P | Q P ∨ Q |
| Q | R ¬P |
| P | R Q |
Proof Example
| Given: 1. P | Q (If it rains, ground is wet) |
| 2. Q | R (If ground wet, road is slippery) |
| Prove | R (Road is slippery) |
| Step 4 | Q [Modus Ponens on 1, 3] |
| Step 5 | R [Modus Ponens on 2, 4] |
| QED | Road is slippery. |
Normal Forms
Conjunctive Normal Form (CNF)
Conjunction of disjunctions (AND of ORs):
Converting to CNF
| Original: P | (Q ∧ R) |
| Step 1: Eliminate | : ¬P ∨ (Q ∧ R) |
| Step 2 | Distribute ∨ over ∧: (¬P ∨ Q) ∧ (¬P ∨ R) |
Disjunctive Normal Form (DNF)
Disjunction of conjunctions (OR of ANDs):
SAT Problem and Solvers
Boolean Satisfiability
Given a CNF formula, is there a truth assignment making it TRUE?
| Formula | (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ ¬R) |
| (T∨T)=T ∧ (F∨T)=T ∧ (F∨F)=F | FALSE |
| (T∨T)=T ∧ (F∨F)=F | FALSE |
| (T∨F)=T ∧ (F∨T)=T ∧ (T∨F)=T | TRUE! Satisfiable! |
Why SAT Matters in AI
| Planning | "Is there a sequence of actions reaching the goal?" |
| Encode as SAT | solve with modern solvers (millions of variables) |
| Scheduling | "Can all classes be assigned rooms without conflicts?" |
| Model checking | "Does this circuit always produce correct output?" |
Applications in AI
| Expert Systems | Rule conditions are propositional formulas |
| IF (fever ∧ cough) | flu |
| Planning (SATPLAN) | Encode plans as propositional satisfiability |
| State variables at each timestep | find satisfying assignment |
| Game AI | Determine winning strategies via propositional reasoning |
| Knowledge compilation | Convert KB to efficient query form (DNNF, BDD) |
Interview Questions
Q: What is the difference between validity and satisfiability? A: A formula is satisfiable if SOME truth assignment makes it true. It's valid (tautology) if ALL truth assignments make it true. Example: P∨¬P is valid. P∧Q is satisfiable (when both true) but not valid. A formula is unsatisfiable if NO assignment makes it true (e.g., P∧¬P).
Q: Why is implication (P→Q) true when P is false? A: Think of it as a promise: "If it rains, I'll bring an umbrella." If it doesn't rain, I haven't broken my promise regardless of whether I bring an umbrella. The promise is only falsified when the condition holds but the consequence doesn't.
Q: How does resolution work for theorem proving? A: To prove KB ⊨ α, add ¬α to KB, convert everything to CNF, and repeatedly resolve clause pairs. If you derive the empty clause (contradiction), then ¬α is inconsistent with KB, proving α. Resolution is complete for propositional logic.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Propositional Logic - Logical Reasoning.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, knowledge, representation, propositional, logic
Related Artificial Intelligence Topics