Artificial Intelligence

Knowledge Reasoning And Planning

Propositional Logic

Chapter 1's semantic networks and frames are intuitive but informal — nothing mathematically guarantees that following the "is-a" chain to conclude "Tweety can

JrCodex·8 min read

Jr Codex AI Notes

Level: Intermediate Prerequisites: Chapter 1 Time to complete: ~25 minutes

Table of Contents

  1. Why Formal Logic?
  2. Syntax — Building Valid Sentences
  3. Semantics — Truth Tables
  4. Logical Equivalence
  5. Entailment — the Core Reasoning Question
  6. Checking Entailment with Truth Tables in Code
  7. The Limits of Propositional Logic
  8. Summary & Next Steps

1. Why Formal Logic?

Chapter 1's semantic networks and frames are intuitive but informal — nothing mathematically guarantees that following the "is-a" chain to conclude "Tweety can fly" is actually a valid inference. Propositional logic gives knowledge representation a precise, mathematical foundation — rules for what follows from what, with no ambiguity.

Informal (Ch.1)                        Formal (this chapter)
─────────────────────────────         ─────────────────────────────
  "Tweety is a canary, canaries          Rain ∧ (Rain → WetGround) ⊨ WetGround
  are birds, birds fly, so                (formally PROVABLE, not just
  Tweety probably flies"                    intuitively plausible)
─────────────────────────────         ─────────────────────────────

2. Syntax — Building Valid Sentences

Propositional logic starts with propositions (statements that are either true or false) and combines them with logical connectives.

Propositional Symbols
─────────────────────────────────────────
  P = "It is raining"
  Q = "The ground is wet"
  R = "I bring an umbrella"

  Each is a SIMPLE proposition — atomic, either True or False,
  no internal structure logic can inspect (that's Chapter 3's job).
─────────────────────────────────────────

The Five Logical Connectives
─────────────────────────────────────────
  ¬P          NOT P               "It is NOT raining"
  P ∧ Q        P AND Q              "It is raining AND the ground is wet"
  P ∨ Q          P OR Q               "It is raining OR I bring an umbrella"
  P → Q            P IMPLIES Q         "IF it is raining THEN the ground is wet"
  P ↔ Q              P IFF Q             "It is raining IF AND ONLY IF the ground is wet"
─────────────────────────────────────────

# Representing propositional sentences as Python expressions over booleans
def evaluate_sentence(P, Q):
    not_p = not P
    p_and_q = P and Q
    p_or_q = P or Q
    p_implies_q = (not P) or Q      # P → Q is FALSE only when P is True and Q is False
    p_iff_q = P == Q
 
    return {
        "¬P": not_p, "P∧Q": p_and_q, "P∨Q": p_or_q,
        "P→Q": p_implies_q, "P↔Q": p_iff_q,
    }
 
print(evaluate_sentence(P=True, Q=False))
# {'¬P': False, 'P∧Q': False, 'P∨Q': True, 'P→Q': False, 'P↔Q': False}

The implication P → Q trips up almost every beginner — it's only false when P is true and Q is false; if P is false, P → Q is considered true regardless of Q ("if it's not raining, the umbrella claim is vacuously fine either way").

3. Semantics — Truth Tables

The semantics of a sentence define its truth value under every possible combination of its propositions' truth values — a truth table enumerates all of them.

from itertools import product
 
def truth_table(variables, sentence_fn):
    """Print a full truth table for a sentence over the given variable names."""
    header = variables + ["Result"]
    print(" | ".join(header))
    print("-" * (len(header) * 8))
 
    for values in product([True, False], repeat=len(variables)):
        assignment = dict(zip(variables, values))
        result = sentence_fn(assignment)
        row = [str(assignment[v]) for v in variables] + [str(result)]
        print(" | ".join(row))
 
# P → Q
truth_table(["P", "Q"], lambda a: (not a["P"]) or a["Q"])
# P     | Q     | Result
# ------------------------
# True  | True  | True
# True  | False | False
# False | True  | True
# False | False | True
Reading the Implication's Truth Table
─────────────────────────────────────────
  P=True,  Q=True   →  True   (raining AND ground wet — consistent)
  P=True,  Q=False    →  False  (raining but ground NOT wet — CONTRADICTS the claim)
  P=False, Q=True       →  True   (not raining, but ground wet anyway — claim wasn't about THIS)
  P=False, Q=False        →  True   (not raining, ground not wet — consistent, vacuously)
─────────────────────────────────────────

4. Logical Equivalence

Two sentences are logically equivalent if they have identical truth tables — they mean exactly the same thing, just expressed differently.

def sentences_equivalent(variables, sentence1, sentence2):
    """Check equivalence by comparing truth tables across every assignment."""
    for values in product([True, False], repeat=len(variables)):
        assignment = dict(zip(variables, values))
        if sentence1(assignment) != sentence2(assignment):
            return False
    return True
 
# De Morgan's Law: ¬(P ∧ Q) is equivalent to (¬P ∨ ¬Q)
equiv = sentences_equivalent(
    ["P", "Q"],
    lambda a: not (a["P"] and a["Q"]),
    lambda a: (not a["P"]) or (not a["Q"]),
)
print(equiv)      # True — De Morgan's Law holds
Common Equivalences Worth Recognizing
─────────────────────────────────────────
  De Morgan's Laws:    ¬(P ∧ Q) ≡ (¬P ∨ ¬Q)
                         ¬(P ∨ Q) ≡ (¬P ∧ ¬Q)

  Implication elimination:  (P → Q) ≡ (¬P ∨ Q)
                              (used directly in Section 2's code!)

  Contrapositive:              (P → Q) ≡ (¬Q → ¬P)
─────────────────────────────────────────

These equivalences aren't just theoretical curiosities — automated reasoning systems (Chapter 4) rely on rewriting sentences into equivalent, more convenient forms (like eliminating implications) before applying inference rules.

5. Entailment — the Core Reasoning Question

Entailment, written KB ⊨ α ("knowledge base KB entails sentence α"), is the central question of logical reasoning: given what we know (KB) to be true, must α also be true?

Formal Definition
─────────────────────────────────────────
  KB ⊨ α    means:   in EVERY possible world (every truth
                        assignment) where KB is true, α is
                        ALSO true.

  If there's even ONE assignment where KB holds but α doesn't,
  entailment FAILS — KB does NOT guarantee α.
─────────────────────────────────────────

Worked Example
─────────────────────────────────────────
  KB:  Rain → WetGround   (if it rains, the ground gets wet)
        Rain                 (it IS raining)

  Does KB entail WetGround?

  Check EVERY assignment where BOTH KB sentences are true:
    Rain=True, WetGround=True:   Rain→WetGround = True ✓, Rain = True ✓
                                    → WetGround = True ✓ (holds)
    Rain=True, WetGround=False:    Rain→WetGround = False ✗ (violates KB — excluded)

  In every world where KB is true, WetGround is ALSO true.
  → KB ⊨ WetGround   (entailment holds!)
─────────────────────────────────────────

6. Checking Entailment with Truth Tables in Code

The most basic (if inefficient for large problems) way to check entailment — enumerate every possible world and verify the definition from Section 5 directly.

from itertools import product
 
def check_entailment(variables, kb_sentences, query_sentence):
    """
    KB entails query if, in EVERY assignment where all KB sentences
    are true, the query is ALSO true.
    """
    for values in product([True, False], repeat=len(variables)):
        assignment = dict(zip(variables, values))
 
        kb_holds = all(sentence(assignment) for sentence in kb_sentences)
        if kb_holds and not query_sentence(assignment):
            return False      # found a WORLD where KB is true but query is FALSE — entailment fails
 
    return True      # no counterexample found — entailment holds
 
kb = [
    lambda a: (not a["Rain"]) or a["WetGround"],      # Rain → WetGround
    lambda a: a["Rain"],                                 # Rain (known fact)
]
query = lambda a: a["WetGround"]
 
result = check_entailment(["Rain", "WetGround"], kb, query)
print(result)      # True — KB entails WetGround

This "check every possible world" approach is called model checking — it's guaranteed correct, but its cost doubles with every additional variable (2^n worlds for n variables), motivating Chapter 4's more efficient, targeted inference algorithms.

7. The Limits of Propositional Logic

Propositional logic is precise, but structurally limited — it treats each proposition as an indivisible atom, unable to express relationships between objects or generalize across many individuals.

# Propositional logic CAN express:
#   "Socrates is a man" as a single atomic proposition: SocratesIsMan
 
# But it CANNOT naturally express the GENERAL rule:
#   "ALL men are mortal"
# without a SEPARATE proposition for every individual man:
#   SocratesIsMan → SocratesIsMortal
#   PlatoIsMan → PlatoIsMortal
#   AristotleIsMan → AristotleIsMortal
#   ... (one explicit sentence per person, no way to generalize!)
Why This Is a Real Problem
─────────────────────────────────────────
  A knowledge base about even a MODEST domain (all birds, all
  countries, all customers) would need a SEPARATE, hand-written
  sentence for every single individual — utterly impractical,
  and directly violating Chapter 1's "acquisition efficiency"
  property.

  This exact limitation is what First-Order Logic (Chapter 3)
  is built to solve — introducing VARIABLES and QUANTIFIERS
  so a single sentence can express a rule about EVERY object
  in a domain at once.
─────────────────────────────────────────

8. Summary & Next Steps

Key Takeaways

  • Propositional logic combines atomic true/false propositions using connectives (¬, ∧, ∨, →, ↔), each with a precisely defined truth table.
  • Two sentences are logically equivalent if their truth tables match exactly — De Morgan's Laws and implication elimination are commonly used equivalences.
  • Entailment (KB ⊨ α) asks whether α must be true in every possible world where the knowledge base is true — the central formal reasoning question.
  • Model checking (enumerating every possible world) correctly determines entailment but scales as 2^n with the number of variables — impractical for large knowledge bases.
  • Propositional logic cannot naturally express general rules across many individuals without a separate sentence per individual — motivating First-Order Logic in Chapter 3.

Concept Check

  1. Why is P → Q considered true whenever P is false, regardless of Q's value?
  2. What does it mean, formally, for a knowledge base to "entail" a sentence?
  3. Why does representing "all men are mortal" become impractical in pure propositional logic?

Next Chapter

→ Chapter 3: First-Order Logic

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index