Propositional Logic — Truth Tables, SAT and Resolution

In this tutorial, you'll learn about Propositional Logic. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Propositional logic is the foundation of Formal Verification — it models software conditions as true or false statements and enables automated reasoning about program correctness.

Learning Path

flowchart LR
  A["Formal Methods
Overview"] --> B["Propositional Logic
Truth Tables & SAT"]
  B --> C["First-Order Logic"]
  B --> D["SAT & SMT Solving"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Basic algebra and logical thinking. Familiarity with boolean variables (true/false) from any programming language.

What Is Propositional Logic?

Propositional logic works with statements that are either true or false. You connect them with logical operators: AND (∧), OR (∨), NOT (¬), implication (→), and equivalence (↔).

A propositional variable represents a basic statement. For example: p = "file is open", q = "buffer is full". You can build complex formulas like p ∧ q meaning "file is open AND buffer is full".

Step-by-Step: Truth Tables

Step 1: List All Variables

For two variables p and q, there are 4 possible assignments.

Step 2: Compute Each Operator

Build a truth table for p → q (if p then q):

def implies(p, q):
    return not p or q

print("p     q     p -> q")
print("-------------------")
for p in [True, False]:
    for q in [True, False]:
        print(f"{p!s:5} {q!s:5} {implies(p, q)!s:5}")

Expected output:

p     q     p -> q
-------------------
True  True  True
True  False False
False True  True
False False True

Step 3: Check Tautologies

A formula is a tautology if it is true for all assignments. Check (p ∧ q) → p:

def tautology_check():
    for p in [True, False]:
        for q in [True, False]:
            if (p and q) and not p:
                return False
    return True

print(f"Formula is a tautology: {tautology_check()}")

Expected output:

Formula is a tautology: True

Step-by-Step: SAT Solving

The Boolean satisfiability problem (SAT) asks: does there exist an assignment that makes the formula true?

Convert your formula to Conjunctive Normal Form (CNF): an AND of OR clauses.

# Formula: (p OR q) AND (NOT p OR r) AND (NOT r OR q)
clauses = [
    [1, 2],    # p OR q  (1=p, 2=q)
    [-1, 3],   # NOT p OR r (3=r)
    [-3, 2]    # NOT r OR q
]

def solve_sat(clauses, assignment, var):
    if var > 3:
        return all(any(assignment[abs(l)] if l > 0 else not assignment[abs(l)]
                      for l in c) for c in clauses)
    for val in [True, False]:
        assignment[var] = val
        if solve_sat(clauses, assignment, var + 1):
            return True
    return False

result = solve_sat(clauses, {}, 1)
print(f"Satisfiable: {result}")

Expected output:

Satisfiable: True

A satisfying assignment is p=True, q=True, r=True.

Resolution Proofs

Resolution proves unsatisfiability by deriving an empty clause from the CNF.

Resolution Rule

From clause (A OR x) and (B OR NOT x), derive (A OR B).

Example: To prove (p OR q) and (NOT p) implies q:

# Clauses: [p, q], [NOT p]
# Resolve on p: [q]  (since p and NOT p cancel)
clause1 = ["p", "q"]
clause2 = ["not p"]

def resolve(c1, c2, var):
    new = [l for l in c1 if l != var and l != "not " + var]
    new += [l for l in c2 if l != var and l != "not " + var]
    return list(set(new))

result = resolve(clause1, clause2, "p")
print(f"Resolved clause: {result}")

Expected output:

Resolved clause: ['q']

Common Errors

1. Confusing Implication Direction

p → q is NOT the same as q → p. Only the first is false when p is true and q is false.

2. Missing Parentheses

p AND q OR r is ambiguous. Always use parentheses: (p AND q) OR r vs p AND (q OR r).

3. Incorrect CNF Conversion

Distributing AND over OR incorrectly. Remember: (A ∧ B) ∨ C becomes (A ∨ C) ∧ (B ∨ C).

4. Off-by-One Variable Indexing

SAT solvers use integer variable indices starting at 1. Index 0 often represents an unused variable.

5. Assuming SAT Means All True

A formula can be satisfiable with many false variables. SAT just requires at least one satisfying assignment.

Practice Questions

Q1: Is (p → q) → (¬q → ¬p) a tautology?

Yes. This is the contrapositive law and holds for all assignments.

Q2: What is the CNF of p XOR q?

(p ∨ q) ∧ (¬p ∨ ¬q).

Q3: How many satisfying assignments does p ∧ ¬p have?

Zero. It is unsatisfiable.

Q4: What does a SAT solver return for an unsatisfiable formula?

UNSAT. Modern solvers also produce an unsatisfiability proof or core.

Q5: Can SAT solving be used for program verification?

Yes. Bounded Model Checking converts program paths to SAT formulas and checks them with a SAT solver.

Challenge

Express the following puzzle as a SAT formula: three people each make one statement. At least one is true and at least one is false. Person A says "B is guilty". Person B says "C is guilty". Person C says "I am innocent". Determine who is guilty using resolution.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.