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 , or are sentences, and if and are sentences, so are , , , and . A model assigns true or false to every atom, and the truth of a compound sentence is computed bottom-up from the connectives' truth tables. Write when is true in , and for the set of such models. Then entailment is containment: iff .
| Name | Equivalence |
|---|---|
| Implication elimination | |
| Biconditional elimination | |
| Contraposition | |
| De Morgan | , and |
| Distributivity | |
| Double negation |
Which sentence is valid?
Show the answer
C.
Contraposition: and have the same models, so the implication between them holds in all four models.
Model checking and its cost
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 models: time (times the cost of evaluating the sentences) but only 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 fails exactly when 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 mean that square is breezy and 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 ( and give ) 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:
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]:
Eliminate :
Eliminate :
Move inward with De Morgan:
Distribute over , leaving three clauses:
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 ∪ newResolution refutation. It always terminates: over symbols there are at most 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: is , and a lone positive literal is a fact. Horn clauses allow at most one positive literal, adding goal clauses such as . 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.
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:
Completeness. When forward chaining stops, let make the inferred atoms true and every other atom false. Each clause holds in : a rule whose premises are all true but whose conclusion is false could still fire. So is a model of the KB:
If , then is true in every model of the KB, in particular in , so was inferred. ∎
A KB contains , and . Can forward chaining derive ?
- Yes: forward chaining is complete for every propositional KB
- No: is not entailed
- No: has two positive literals, so it is not a definite clause; is entailed, but it takes full resolution to show it
- Yes, after rewriting as
Show the answer
C. No: has two positive literals, so it is not a definite clause; 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 is entailed. But no rule ever has all its premises known, so forward chaining never fires. Resolution succeeds: with each rule gives and , which together refute .
First-order logic
First-order logic (FOL) talks about objects. Its vocabulary has constants (), variables (), function symbols () and predicates (, ). Terms denote objects; atomic sentences apply a predicate, or , to terms; connectives and the quantifiers and build everything else.
| English | Correct | Tempting, but wrong |
|---|---|---|
| All kings are persons | says everything is a king | |
| Some king is evil | is true as soon as anything is not a king | |
| Everyone loves someone | says one person is loved by all | |
| Not everyone is happy | says nobody is happy |
A structure has domain , and holds for exactly the pairs and . Which sentence is true in it?
Show the answer
B.
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 . 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 iff . Church and Turing (1936) proved that no algorithm decides entailment: it is only semi-decidable, since a proof search halts if but may run forever otherwise.
Key takeaways
- Semantics first: iff every model of is a model of , iff is valid, iff is unsatisfiable.
- Truth-table model checking is sound and complete but takes time; propositional entailment is co-NP-complete.
- Resolution on CNF clauses is sound and refutation-complete: iff is derivable from .
- 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.
To prove by resolution, you…
- convert the KB to CNF and derive directly
- add to the KB, convert to CNF and derive the empty clause
- add to the KB and check that no contradiction arises
- check that is satisfiable
Show the answer
B. add to the KB, convert to CNF and derive the empty clause
iff is unsatisfiable, and resolution is refutation-complete: it derives from every unsatisfiable set of clauses.
Which is a CNF sentence equivalent to ?
Show the answer
C.
.
Which problem is co-NP-complete?
- Deciding whether a propositional KB entails a given sentence
- Deciding whether a set of Horn clauses is satisfiable
- Deciding first-order entailment
- Deciding whether a given model satisfies a given sentence
Show the answer
A. Deciding whether a propositional KB entails a given sentence
iff is satisfiable, an NP-complete question, so entailment is co-NP-complete.
Forward chaining over definite clauses is…
- sound, but incomplete even for atomic queries
- complete for every propositional KB
- exponential in the worst case, like truth tables
- 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.
A first-order prover has searched for a week for a proof of without finding one. What can you conclude?
- Nothing definite: entailment is semi-decidable, so a search halts if a proof exists but may run forever if none does
- is inconsistent
- 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 , so the search would find it eventually, but no algorithm can bound how long it takes; and if the search may never halt (Church–Turing).
Go deeper
- Resolution & Completeness · One inference rule to prove them all.
- First-Order Inference & Unification · Lifting propositional reasoning to variables.
- Decidability & the Limits of Logic · Gödel, Church–Turing and what no reasoner can do.
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).