Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

Propositional & First-Order Logic

Syntax, semantics, entailment and inference.

Truth tables settle every question of propositional logic, but they double with every new symbol, and first-order logic has no tables at all: a sentence can have models of every size, infinite ones included. This lesson builds the real machinery: exact semantics, proofs as symbol manipulation, and the theorems that tie the two together.

What you’ll learn

  • Define the syntax and semantics of propositional logic, and reduce entailment to validity and to unsatisfiability.
  • Run truth-table model checking, state its cost, and explain why entailment is co-NP-complete.
  • Convert sentences to CNF, carry out resolution refutations, and prove resolution sound.
  • Use forward chaining on Horn clauses and explain its linear-time completeness guarantee.
  • Read and write first-order sentences, give their semantics in a structure, and explain why first-order entailment is only semi-decidable.

Syntax and semantics

Propositional logic has a two-line grammar. Atoms such as PP, QQ or Rain\mathit{Rain} are sentences, and if α\alpha and β\beta are sentences, so are ¬α\neg\alpha, (α∧β)(\alpha\land\beta), (α∨β)(\alpha\lor\beta), (α⇒β)(\alpha\Rightarrow\beta) and (α⇔β)(\alpha\Leftrightarrow\beta). A model mm assigns true or false to every atom, and the truth of a compound sentence is computed bottom-up from the connectives' truth tables. Write m⊨αm\models\alpha when α\alpha is true in mm, and M(α)M(\alpha) for the set of such models. Then entailment is containment: α⊨β\alpha\models\beta iff M(α)⊆M(β)M(\alpha)\subseteq M(\beta).

NameEquivalence
Implication eliminationα⇒β ≡ ¬α∨β\alpha\Rightarrow\beta\ \equiv\ \neg\alpha\lor\beta
Biconditional eliminationα⇔β ≡ (α⇒β)∧(β⇒α)\alpha\Leftrightarrow\beta\ \equiv\ (\alpha\Rightarrow\beta)\land(\beta\Rightarrow\alpha)
Contrapositionα⇒β ≡ ¬β⇒¬α\alpha\Rightarrow\beta\ \equiv\ \neg\beta\Rightarrow\neg\alpha
De Morgan¬(α∧β)≡¬α∨¬β\neg(\alpha\land\beta)\equiv\neg\alpha\lor\neg\beta, and ¬(α∨β)≡¬α∧¬β\neg(\alpha\lor\beta)\equiv\neg\alpha\land\neg\beta
Distributivityα∨(β∧γ) ≡ (α∨β)∧(α∨γ)\alpha\lor(\beta\land\gamma)\ \equiv\ (\alpha\lor\beta)\land(\alpha\lor\gamma)
Double negation¬¬α ≡ α\neg\neg\alpha\ \equiv\ \alpha
Each row can be checked with a four- or eight-row truth table. These are exactly the rewrites used to reach conjunctive normal form below.
Check your understanding

Which sentence is valid?

  1. (P⇒Q)⇒(Q⇒P)(P\Rightarrow Q)\Rightarrow(Q\Rightarrow P)
  2. (P∨Q)⇒(P∧Q)(P\lor Q)\Rightarrow(P\land Q)
  3. (P⇒Q)⇒(¬Q⇒¬P)(P\Rightarrow Q)\Rightarrow(\neg Q\Rightarrow\neg P)
  4. ((P⇒Q)∧P)⇒¬Q\big((P\Rightarrow Q)\land P\big)\Rightarrow\neg Q
Show the answer

C. (P⇒Q)⇒(¬Q⇒¬P)(P\Rightarrow Q)\Rightarrow(\neg Q\Rightarrow\neg P)

Contraposition: P⇒QP\Rightarrow Q and ¬Q⇒¬P\neg Q\Rightarrow\neg P have the same models, so the implication between them holds in all four models.

Model checking and its cost

text
function TT-ENTAILS(KB, α) returns true or false
  symbols ← the proposition symbols in KB and α
  return TT-CHECK-ALL(KB, α, symbols, {})

function TT-CHECK-ALL(KB, α, symbols, model) returns true or false
  if symbols is empty then
    if PL-TRUE(KB, model) then return PL-TRUE(α, model)
    else return true                    // KB false here: nothing to check
  P ← FIRST(symbols);  rest ← REST(symbols)
  return TT-CHECK-ALL(KB, α, rest, model ∪ {P = true}) and
         TT-CHECK-ALL(KB, α, rest, model ∪ {P = false})

Depth-first enumeration of all 2n2^n models: O(2n)\order{2^n} time (times the cost of evaluating the sentences) but only O(n)\order{n} space.

TT-ENTAILS is sound and complete, since it checks the definition of entailment literally. No known algorithm does fundamentally better in the worst case: satisfiability (SAT) is NP-complete, and because KB⊨α\text{KB}\models\alpha fails exactly when KB∧¬α\text{KB}\land\neg\alpha is satisfiable, entailment is co-NP-complete. A countermodel is a short certificate that an entailment fails; for entailments that hold, no short certificate is known in general.

Try it in the wumpus world (Russell & Norvig): an agent explores a cave grid in which the squares next to a pit are breezy. Let Bx,yB_{x,y} mean that square [x,y][x,y] is breezy and Px,yP_{x,y} that it holds a pit; the widget writes them B21, P22 and so on.

Proofs: CNF and resolution

An inference rule is sound if its premises entail its conclusion; modus ponens (α⇒β\alpha\Rightarrow\beta and α\alpha give β\beta) is the classic example. A proof is a sequence of sentences, each a premise or obtained by a sound rule, so everything proved is entailed. Resolution works on clauses, disjunctions of literals, and needs just one rule:

C∨ℓD∨¬ℓC∨D\frac{C\lor\ell\qquad D\lor\neg\ell}{C\lor D}
From two clauses containing a complementary pair of literals, derive the clause of all their other literals, with duplicates merged. With CC empty it is modus ponens in disguise: ℓ\ell and ¬ℓ∨D\neg\ell\lor D (that is, ℓ⇒D\ell\Rightarrow D) give DD.

Resolution needs its input in conjunctive normal form, a conjunction of clauses. Four rewriting stages get there, shown here on the breeze rule for square [1,1]:

DerivationCNF conversion of the breeze rule
  1. (B1,1⇒(P1,2∨P2,1))∧((P1,2∨P2,1)⇒B1,1)\big(B_{1,1}\Rightarrow(P_{1,2}\lor P_{2,1})\big)\land\big((P_{1,2}\lor P_{2,1})\Rightarrow B_{1,1}\big)

    Eliminate ⇔\Leftrightarrow:

  2. (¬B1,1∨P1,2∨P2,1)∧(¬(P1,2∨P2,1)∨B1,1)(\neg B_{1,1}\lor P_{1,2}\lor P_{2,1})\land\big(\neg(P_{1,2}\lor P_{2,1})\lor B_{1,1}\big)

    Eliminate ⇒\Rightarrow:

  3. (¬B1,1∨P1,2∨P2,1)∧((¬P1,2∧¬P2,1)∨B1,1)(\neg B_{1,1}\lor P_{1,2}\lor P_{2,1})\land\big((\neg P_{1,2}\land\neg P_{2,1})\lor B_{1,1}\big)

    Move ¬\neg inward with De Morgan:

  4. (¬B1,1∨P1,2∨P2,1)∧(¬P1,2∨B1,1)∧(¬P2,1∨B1,1)(\neg B_{1,1}\lor P_{1,2}\lor P_{2,1})\land(\neg P_{1,2}\lor B_{1,1})\land(\neg P_{2,1}\lor B_{1,1})

    Distribute ∨\lor over ∧\land, leaving three clauses:

text
function PL-RESOLUTION(KB, α) returns true or false
  clauses ← the clauses of CNF(KB ∧ ¬α)
  loop do
    new ← {}
    for each pair of clauses Ci, Cj in clauses do
      resolvents ← PL-RESOLVE(Ci, Cj)
      if resolvents contains the empty clause then return true
      new ← new ∪ resolvents
    if new ⊆ clauses then return false        // saturated: KB does not entail α
    clauses ← clauses ∪ new

Resolution refutation. It always terminates: over nn symbols there are at most 3n3^n distinct clauses, since each symbol occurs positively, negatively or not at all.

Horn clauses and chaining

Full resolution is complete but can be slow. Many knowledge bases need only definite clauses, clauses with exactly one positive literal, which read as rules: ¬L∨¬M∨P\neg L\lor\neg M\lor P is L∧M⇒PL\land M\Rightarrow P, and a lone positive literal is a fact. Horn clauses allow at most one positive literal, adding goal clauses such as ¬A∨¬B\neg A\lor\neg B. For definite clauses, forward chaining fires every rule whose premises are all known and adds its conclusion, until the query appears or nothing new follows. Backward chaining works from the query back toward the facts, as Prolog does.

DerivationWhy it is linear and complete
  1. work=O(∑rules∣rule∣)=O(∣KB∣)\text{work}=\order{\textstyle\sum_{\text{rules}}|\text{rule}|}=\order{|\text{KB}|}

    Linear time. Keep, for each rule, a counter of premises not yet known. When an atom is first inferred, decrement the counter of every rule with that atom among its premises; a counter that reaches zero fires its rule. Each premise occurrence is handled once:

  2. m⊨KBm\models\text{KB}

    Completeness. When forward chaining stops, let mm make the inferred atoms true and every other atom false. Each clause holds in mm: a rule whose premises are all true but whose conclusion is false could still fire. So mm is a model of the KB:

  3. KB⊨q ⟹ m⊨q ⟹ q was inferred\text{KB}\models q\ \Longrightarrow\ m\models q\ \Longrightarrow\ q\ \text{was inferred}

    If KB⊨q\text{KB}\models q, then qq is true in every model of the KB, in particular in mm, so qq was inferred. ∎

Check your understanding

A KB contains Rain∨Sprinkler\mathit{Rain}\lor\mathit{Sprinkler}, Rain⇒Wet\mathit{Rain}\Rightarrow\mathit{Wet} and Sprinkler⇒Wet\mathit{Sprinkler}\Rightarrow\mathit{Wet}. Can forward chaining derive Wet\mathit{Wet}?

  1. Yes: forward chaining is complete for every propositional KB
  2. No: Wet\mathit{Wet} is not entailed
  3. No: Rain∨Sprinkler\mathit{Rain}\lor\mathit{Sprinkler} has two positive literals, so it is not a definite clause; Wet\mathit{Wet} is entailed, but it takes full resolution to show it
  4. Yes, after rewriting Rain∨Sprinkler\mathit{Rain}\lor\mathit{Sprinkler} as Rain⇒Sprinkler\mathit{Rain}\Rightarrow\mathit{Sprinkler}
Show the answer

C. No: Rain∨Sprinkler\mathit{Rain}\lor\mathit{Sprinkler} has two positive literals, so it is not a definite clause; Wet\mathit{Wet} is entailed, but it takes full resolution to show it

Every model has rain or the sprinkler on, and either way the grass is wet, so Wet\mathit{Wet} is entailed. But no rule ever has all its premises known, so forward chaining never fires. Resolution succeeds: ¬Wet\neg\mathit{Wet} with each rule gives ¬Rain\neg\mathit{Rain} and ¬Sprinkler\neg\mathit{Sprinkler}, which together refute Rain∨Sprinkler\mathit{Rain}\lor\mathit{Sprinkler}.

First-order logic

First-order logic (FOL) talks about objects. Its vocabulary has constants (Socrates\mathit{Socrates}), variables (xx), function symbols (MotherOf(x)\mathit{MotherOf}(x)) and predicates (Human(x)\mathit{Human}(x), Loves(x,y)\mathit{Loves}(x,y)). Terms denote objects; atomic sentences apply a predicate, or ==, to terms; connectives and the quantifiers ∀x\forall x and ∃x\exists x build everything else.

EnglishCorrectTempting, but wrong
All kings are persons∀x (King(x)⇒Person(x))\forall x\,(\mathit{King}(x)\Rightarrow\mathit{Person}(x))∀x (King(x)∧Person(x))\forall x\,(\mathit{King}(x)\land\mathit{Person}(x)) says everything is a king
Some king is evil∃x (King(x)∧Evil(x))\exists x\,(\mathit{King}(x)\land\mathit{Evil}(x))∃x (King(x)⇒Evil(x))\exists x\,(\mathit{King}(x)\Rightarrow\mathit{Evil}(x)) is true as soon as anything is not a king
Everyone loves someone∀x ∃y Loves(x,y)\forall x\,\exists y\,\mathit{Loves}(x,y)∃y ∀x Loves(x,y)\exists y\,\forall x\,\mathit{Loves}(x,y) says one person is loved by all
Not everyone is happy¬∀x Happy(x)≡∃x ¬Happy(x)\neg\forall x\,\mathit{Happy}(x)\equiv\exists x\,\neg\mathit{Happy}(x)∀x ¬Happy(x)\forall x\,\neg\mathit{Happy}(x) says nobody is happy
The rule of thumb: ∀\forall goes with ⇒\Rightarrow, and ∃\exists goes with ∧\land.
Check your understanding

A structure has domain {Ann,Bob}\{\mathit{Ann},\mathit{Bob}\}, and Loves\mathit{Loves} holds for exactly the pairs (Ann,Bob)(\mathit{Ann},\mathit{Bob}) and (Bob,Ann)(\mathit{Bob},\mathit{Ann}). Which sentence is true in it?

  1. ∃y ∀x Loves(x,y)\exists y\,\forall x\,\mathit{Loves}(x,y)
  2. ∀x ∃y Loves(x,y)\forall x\,\exists y\,\mathit{Loves}(x,y)
  3. ∃x Loves(x,x)\exists x\,\mathit{Loves}(x,x)
  4. ∀x ∀y Loves(x,y)\forall x\,\forall y\,\mathit{Loves}(x,y)
Show the answer

B. ∀x ∃y Loves(x,y)\forall x\,\exists y\,\mathit{Loves}(x,y)

Each person loves someone: Ann loves Bob and Bob loves Ann. But nobody is loved by everyone, because nobody loves themselves, so swapping the quantifiers gives a false sentence.

Inference lifts to FOL. Instantiating universal sentences with ground terms makes a problem propositional, and Herbrand's theorem says finitely many instances suffice whenever Γ⊨φ\Gamma\models\varphi. With function symbols there are infinitely many instances to choose from, and unification (Robinson, 1965) chooses lazily, instantiating only as far as a proof needs. Two landmark facts frame the subject. Gödel's completeness theorem (1930) gives proof systems in which Γ⊨φ\Gamma\models\varphi iff Γ⊢φ\Gamma\vdash\varphi. Church and Turing (1936) proved that no algorithm decides entailment: it is only semi-decidable, since a proof search halts if Γ⊨φ\Gamma\models\varphi but may run forever otherwise.

Key takeaways

  • Semantics first: α⊨β\alpha\models\beta iff every model of α\alpha is a model of β\beta, iff α⇒β\alpha\Rightarrow\beta is valid, iff α∧¬β\alpha\land\neg\beta is unsatisfiable.
  • Truth-table model checking is sound and complete but takes O(2n)\order{2^n} time; propositional entailment is co-NP-complete.
  • Resolution on CNF clauses is sound and refutation-complete: KB⊨α\text{KB}\models\alpha iff □\square is derivable from KB∧¬α\text{KB}\land\neg\alpha.
  • For definite clauses, forward chaining is complete for atomic queries and runs in linear time.
  • First-order logic adds objects, functions and quantifiers. It has complete proof systems (Gödel), but its entailment is only semi-decidable (Church–Turing).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

To prove KB⊨α\text{KB}\models\alpha by resolution, you…

  1. convert the KB to CNF and derive α\alpha directly
  2. add ¬α\neg\alpha to the KB, convert to CNF and derive the empty clause
  3. add α\alpha to the KB and check that no contradiction arises
  4. check that KB∧α\text{KB}\land\alpha is satisfiable
Show the answer

B. add ¬α\neg\alpha to the KB, convert to CNF and derive the empty clause

KB⊨α\text{KB}\models\alpha iff KB∧¬α\text{KB}\land\neg\alpha is unsatisfiable, and resolution is refutation-complete: it derives □\square from every unsatisfiable set of clauses.

Question 2

Which is a CNF sentence equivalent to P⇔QP\Leftrightarrow Q?

  1. (P∨Q)∧(¬P∨¬Q)(P\lor Q)\land(\neg P\lor\neg Q)
  2. (P∧Q)∨(¬P∧¬Q)(P\land Q)\lor(\neg P\land\neg Q)
  3. (¬P∨Q)∧(P∨¬Q)(\neg P\lor Q)\land(P\lor\neg Q)
  4. ¬P∨Q\neg P\lor Q
Show the answer

C. (¬P∨Q)∧(P∨¬Q)(\neg P\lor Q)\land(P\lor\neg Q)

P⇔Q≡(P⇒Q)∧(Q⇒P)≡(¬P∨Q)∧(¬Q∨P)P\Leftrightarrow Q\equiv(P\Rightarrow Q)\land(Q\Rightarrow P)\equiv(\neg P\lor Q)\land(\neg Q\lor P).

Question 3

Which problem is co-NP-complete?

  1. Deciding whether a propositional KB entails a given sentence
  2. Deciding whether a set of Horn clauses is satisfiable
  3. Deciding first-order entailment
  4. Deciding whether a given model satisfies a given sentence
Show the answer

A. Deciding whether a propositional KB entails a given sentence

KB⊭α\text{KB}\not\models\alpha iff KB∧¬α\text{KB}\land\neg\alpha is satisfiable, an NP-complete question, so entailment is co-NP-complete.

Question 4

Forward chaining over definite clauses is…

  1. sound, but incomplete even for atomic queries
  2. complete for every propositional KB
  3. exponential in the worst case, like truth tables
  4. sound and complete for atomic queries, and linear-time
Show the answer

D. sound and complete for atomic queries, and linear-time

The atoms inferred at the fixpoint form a model of the KB, so every entailed atom is among them; premise counters make the run linear.

Question 5

A first-order prover has searched for a week for a proof of Γ⊨φ\Gamma\models\varphi without finding one. What can you conclude?

  1. Γ⊭φ\Gamma\not\models\varphi
  2. Nothing definite: entailment is semi-decidable, so a search halts if a proof exists but may run forever if none does
  3. Γ\Gamma is inconsistent
  4. The prover is unsound
Show the answer

B. Nothing definite: entailment is semi-decidable, so a search halts if a proof exists but may run forever if none does

By Gödel's completeness theorem a proof exists if Γ⊨φ\Gamma\models\varphi, so the search would find it eventually, but no algorithm can bound how long it takes; and if Γ⊭φ\Gamma\not\models\varphi the search may never halt (Church–Turing).

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapters 7–9.
  • J. A. Robinson, "A machine-oriented logic based on the resolution principle," Journal of the ACM 12(1) (1965), 23–41.
  • W. F. Dowling & J. H. Gallier, "Linear-time algorithms for testing the satisfiability of propositional Horn formulae," Journal of Logic Programming 1(3) (1984), 267–284.
  • H. B. Enderton, A Mathematical Introduction to Logic, 2nd ed. (Academic Press, 2001).