Propositional Logic: Semantics & Satisfiablity
Introduction: The Meaning Behind the Symbols
Welcome to the semantic world of propositional logic—where we discover what logical formulas actually mean! While syntax tells us how to build valid formulas (like grammar rules), semantics reveals their truth and meaning. Think of syntax as learning to spell words correctly, and semantics as understanding what those words actually mean in the real world.
Imagine you're a detective investigating the truth of various claims. Propositional logic semantics gives you the tools to systematically determine when statements are true, false, or even impossible to satisfy. This isn't just academic exercise—these principles power everything from computer chip design to artificial intelligence reasoning systems.
The Big Picture: What Is Semantics?
Semantics in propositional logic is the study of truth—specifically, how we assign truth values (True or False) to logical formulas and what those assignments tell us about the nature of the formulas themselves.
Every logical formula has a "semantic fingerprint" that reveals its fundamental character:
- Some formulas are always true (like mathematical theorems)
- Some are sometimes true (like weather predictions)
- Some are never true (like logical contradictions)
- Some have intricate patterns of truth and falsehood
Understanding semantics is like having X-ray vision for logic—you can see through complex formulas to their essential truth structure.
Truth Assignments: The Foundation of Meaning
What Is a Truth Assignment?
A truth assignment (also called a valuation or interpretation) is simply a way of assigning truth values (T or F) to each atomic proposition in a formula. Think of it as setting the "dials" on a logical machine—each dial can be set to True or False.
Example: For atomic propositions p, q, and r, here are some possible truth assignments:
- Assignment 1: p = T, q = F, r = T
- Assignment 2: p = F, q = F, r = F
- Assignment 3: p = T, q = T, r = T
The Mathematics of Truth Assignments
For a formula with n atomic propositions, there are exactly 2ⁿ possible truth assignments. Why? Because each proposition can be either True or False (2 choices), and we have n independent propositions.
Examples:
- 1 proposition (p): 2¹ = 2 assignments
- 2 propositions (p, q): 2² = 4 assignments
- 3 propositions (p, q, r): 2³ = 8 assignments
- 4 propositions: 2⁴ = 16 assignments
This exponential growth is why analyzing complex logical systems can become computationally challenging!
Truth Tables: The Detective's Toolkit
A truth table is like a systematic investigation report—it lists every possible truth assignment and shows what the formula evaluates to in each case. Truth tables are your crystal ball for understanding logical formulas.
Constructing Truth Tables: Step by Step
Let's build a truth table for the formula: (p ∧ q) → r
Step 1: Identify atomic propositions
- We have: p, q, r (3 propositions = 2³ = 8 rows needed)
Step 2: List all possible truth assignments
| p | q | r | p ∧ q | (p ∧ q) → r |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | F |
| T | F | T | F | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | T | F | F | T |
| F | F | T | F | T |
| F | F | F | F | T |
Step 3: Evaluate subformulas first
- Calculate p ∧ q for each row
- Then calculate (p ∧ q) → r
Key Insight: Notice that (p ∧ q) → r is false in only one case—when both p and q are true, but r is false. This tells us something important about the logical relationship!
Reading Truth Tables Like a Pro
Each row of a truth table tells a story:
- Row 1: "When p, q, and r are all true, the formula holds"
- Row 2: "When p and q are true but r is false, we have a contradiction"
- Rows 3-8: "In all other cases, the formula is satisfied"
This systematic approach removes all guesswork from logical analysis!
The Four Pillars of Satisfiability
Now we arrive at the heart of propositional logic semantics—understanding the different ways formulas can relate to truth. Every formula falls into exactly one of four categories:
1. Satisfiable Formulas: "The Possible"
A formula is satisfiable if there exists at least one truth assignment that makes it true.
Formal Definition: φ is satisfiable if there exists an assignment A such that A(φ) = T
Examples:
- p ∧ q is satisfiable (true when p = T, q = T)
- p ∨ ¬p is satisfiable (actually, it's always true!)
- (p → q) ∧ (q → r) is satisfiable (true in multiple assignments)
Real-world analogy: A satisfiable formula is like a solvable puzzle—there's at least one way to arrange the pieces correctly.
2. Unsatisfiable Formulas: "The Impossible"
A formula is unsatisfiable (or a contradiction) if no truth assignment makes it true.
Formal Definition: φ is unsatisfiable if for all assignments A, A(φ) = F
Examples:
- p ∧ ¬p (Something can't be both true and false)
- (p → q) ∧ p ∧ ¬q (If p implies q, but p is true and q is false, we have a contradiction)
Truth Table Pattern: All entries in the final column are F
Real-world analogy: An unsatisfiable formula is like trying to draw a square circle—logically impossible.
3. Valid Formulas (Tautologies): "The Certain"
A formula is valid (or a tautology) if every truth assignment makes it true.
Formal Definition: φ is valid if for all assignments A, A(φ) = T
Examples:
- p ∨ ¬p (Law of Excluded Middle: something is either true or false)
- (p → q) ↔ (¬q → ¬p) (A conditional and its contrapositive are equivalent)
- ¬(p ∧ q) ↔ (¬p ∨ ¬q) (De Morgan's Law)
Truth Table Pattern: All entries in the final column are T
Special Note: Every valid formula is automatically satisfiable (since it's satisfied by every assignment), but not every satisfiable formula is valid.
4. Contingent Formulas: "The Conditional"
A formula is contingent if it's sometimes true and sometimes false—neither valid nor unsatisfiable.
Examples:
- p ∧ q (true only when both p and q are true)
- p → q (false only when p is true and q is false)
Truth Table Pattern: Mix of T and F in the final column
Most "interesting" logical formulas are contingent—their truth depends on the specific circumstances.
The Semantic Relationships: A Deeper Look
The Satisfiability Hierarchy
Valid Formulas
↓ (subset of)
Satisfiable Formulas
↓ (opposite of)
Unsatisfiable Formulas
Key Insights:
- Every valid formula is satisfiable (but not vice versa)
- A formula is either satisfiable or unsatisfiable (no middle ground)
- If φ is valid, then ¬φ is unsatisfiable (and vice versa)
Logical Equivalence Through Semantics
Two formulas φ and ψ are logically equivalent (φ ≡ ψ) if they have identical truth tables—they're true in exactly the same assignments.
Semantic Test for Equivalence: φ ≡ ψ if and only if φ ↔ ψ is valid
Example: Let's verify that ¬(p ∧ q) ≡ (¬p ∨ ¬q)
| p | q | p ∧ q | ¬(p ∧ q) | ¬p | ¬q | ¬p ∨ ¬q |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | T |
| F | T | F | T | T | F | T |
| F | F | F | T | T | T | T |
The columns for ¬(p ∧ q) and ¬p ∨ ¬q are identical—proving they're equivalent!
Advanced Semantic Concepts
Semantic Entailment: "What Follows From What"
A set of premises Γ semantically entails a conclusion φ (written Γ ⊨ φ) if φ is true in every assignment that makes all premises in Γ true.
Intuitive Meaning: "If the premises are true, the conclusion must be true"
Example:
- Premises: {p → q, p}
- Conclusion: q
- Check: In every assignment where both (p → q) and p are true, q must also be true
This is the semantic foundation of valid reasoning!
The Soundness and Completeness Connection
Here's where semantics meets proof theory:
Soundness: If something can be proven syntactically, it's semantically valid Completeness: If something is semantically valid, it can be proven syntactically
This miraculous correspondence means that semantic truth and syntactic proof are two sides of the same coin!
Practical Applications: Why This Matters
1. Computer Science Applications
Circuit Design:
- Satisfiable formulas → Realizable circuits
- Unsatisfiable formulas → Impossible circuit behaviors
- Valid formulas → Always-working circuits (like safety checks)
Software Verification:
- Program specifications as logical formulas
- Satisfiability checking to find bugs
- Validity checking to prove correctness
2. Artificial Intelligence
Knowledge Representation:
- Facts as satisfiable formulas
- Inconsistent knowledge bases as unsatisfiable sets
- Universal truths as valid formulas
Automated Reasoning:
- SAT solvers finding satisfying assignments
- Theorem provers checking validity
- Planning systems exploring satisfiable scenarios
3. Database Theory
Query Optimization:
- Equivalent queries through logical equivalence
- Impossible queries as unsatisfiable formulas
- Query containment through semantic entailment
Problem-Solving Strategies
Strategy 1: The Systematic Approach
- Identify all atomic propositions
- Calculate the number of truth assignments (2ⁿ)
- Construct the complete truth table
- Analyze the pattern in the final column
- Classify the formula based on the pattern
Strategy 2: The Shortcut Method
For complex formulas, look for:
- Obvious contradictions (like p ∧ ¬p) → Unsatisfiable
- Obvious tautologies (like p ∨ ¬p) → Valid
- Mixed behavior → Contingent
- At least one true case → Satisfiable
Strategy 3: The Equivalence Check
To test if φ ≡ ψ:
- Show that φ ↔ ψ is valid, OR
- Show that φ and ψ have identical truth tables, OR
- Show that (φ ∧ ¬ψ) ∨ (¬φ ∧ ψ) is unsatisfiable
Historical Perspective: The Great Truth Seekers
The concepts you're learning have a remarkable intellectual heritage:
Ancient Origins (4th century BCE):
- Aristotle first systematized logical reasoning
- Recognized the importance of truth conditions
Modern Development (19th-20th centuries):
- George Boole (1854): Algebraic approach to logic
- Gottlob Frege (1879): First modern logical system
- Ludwig Wittgenstein (1922): Introduced truth tables
- Emil Post (1921): Independently developed truth table method
Contemporary Impact:
- Stephen Cook (1971): Proved SAT problem is NP-complete
- Modern SAT solvers: Can handle millions of variables
- Applications: From verifying computer chips to solving Sudoku puzzles
What you're studying isn't just theory—it's the mathematical foundation that makes our digital world possible. Every smartphone, every search engine, every piece of software relies on these principles of logical reasoning.
The beauty of semantics is that it provides absolute clarity in a world of ambiguity. When you master these concepts, you're not just learning logic—you're developing the power to think with mathematical precision about truth itself!