Knowledge-based agents and logic
Study notes on knowledge-based agents and logic: definitions, laws, CNF conversion, inference (forward/backward chaining, resolution), worked examples, common mistakes and exam tips.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Knowledge-based agents use explicit knowledge (facts and rules) to make decisions. Logic is the most common formal language for that knowledge: it supports precise representation, automatic inference (proving new facts), and verification — used in expert systems, verification, planning, and parts of NLP and robotics.
Key ideas
Start from first principles: logic gives a precise language to state facts and rules, plus semantics that say when a statement is true.
Knowledge base (KB): a set of sentences in a logical language that the agent knows. (Defined as the stored information used for inference.)
Sentence: a well-formed closed formula (no free variables). In propositional logic it is built from propositional atoms and logical connectives; in first-order logic it is built from terms (variables, constants, function symbols), predicate symbols applied to terms, logical connectives, and quantifiers. Define each connective when used below.
Model: an assignment of truth values (for propositional logic) or an interpretation (for first-order logic) under which a sentence is true. (Model = a world where sentence holds.)
Satisfiable: a sentence is satisfiable if it has at least one model. Unsatisfiable if it has no models.
Valid (tautology): a sentence is valid if it is true in every model.
Entailment (semantic consequence): KB |= α means every model that makes KB true also makes α true. This is a semantic relation.
Logical equivalence: two sentences are logically equivalent if each entails the other (they have the same set of models).
Inference / Proof / Derivation: a sequence of applications of inference rules to derive new sentences syntactically from the KB. We write KB ⊢ α if α is derivable by some proof system.
Soundness: A proof system is sound if whenever KB ⊢ α then KB |= α. (All provable are true semantically.)
Completeness: A proof system is complete if whenever KB |= α then KB ⊢ α. (All semantic consequences are provable.)
Modus Ponens (MP): the basic inference rule: from P and (P -> Q) infer Q. (State: if both premises are true in a model then the conclusion is true.)
Horn clause: a clause (disjunction of literals) with at most one positive literal; commonly written as an implication A1 ∧ A2 ∧ ... ∧ An -> B (head B, body Ai's). Important because many efficient algorithms exist for Horn KBs.
Forward chaining (data-driven): repeatedly apply rules whose premises are known true to infer new facts until the query is found or no more inferences possible. Completeness: for propositional definite Horn clauses, forward chaining is sound and complete.
Backward chaining (goal-driven): start from query and try to prove it by finding rules that produce the query and recursively prove their premises. Efficient for sparse proofs and used in Prolog (with depth-first strategy and potential non-termination).
Conjunctive Normal Form (CNF): a conjunction of clauses, where a clause is a disjunction of literals. CNF is required by many inference algorithms like resolution.
Resolution rule (propositional): from (A ∨ l) and (B ∨ ¬l) infer (A ∨ B); where l is a literal and A,B are (possibly empty) disjunctions of literals. Resolution is a single, uniform syntactic rule for propositional inference. For propositional logic, resolution is sound and complete.
Refutation by resolution: to show KB |= α, prove that KB ∧ ¬α is unsatisfiable by converting to CNF and deriving the empty clause via repeated resolution. This is the standard method used in exams.
Robinson's resolution theorem (first-order): resolution with unification is sound and refutation-complete for first-order logic after conversion to clause form (Skolemization). Important caveats: first-order logic is only semi-decidable (if entailment holds, search may find proof; if not, it may never halt). State assumptions: clauses must be in clause normal form and include unification. Completeness stated here is for pure first-order logic without built-in equality; with equality, add equality axioms or use paramodulation to retain completeness.
Conversion steps to CNF (these are often required to be written exactly in exams):
- Eliminate implications: replace (P -> Q) with (¬P ∨ Q).
- Move ¬ inwards (use De Morgan) to get negation only on atoms.
- Standardize variables (for FOL): rename bound variables so each quantifier has a unique variable.
- Move quantifiers to prenex normal form (pull all quantifiers to the front, preserving scope).
- Eliminate existential quantifiers by Skolemization (introduce Skolem functions/constants).
- Drop universal quantifiers (all variables now implicitly universally quantified).
- Distribute ∨ over ∧ to get CNF (conjunction of disjunctions).
Complexity notes (assumptions): Propositional satisfiability is NP-complete. Forward chaining on propositional Horn clauses runs in linear time in the size of KB (each rule fired at most once if implemented with counters); resolution search can be exponential in worst case.
Diagram instructions (draw exactly):
- To show entailment by truth table (propositional): Draw a table with columns for each propositional symbol (one column per atom), then columns for each subformula used in the argument, and a final column for (KB -> α) or for KB ∧ ¬α. Fill rows for all 2^n assignments, mark rows where KB is true, and check α in those rows. If you include a (KB -> α) column, it must be T in all rows to establish entailment; if you include a (KB ∧ ¬α) column, it must be F in all rows. Alternatively, filter to the rows where KB is T and verify α is T in those rows. Label axes: columns top header with symbol names; bottom show which rows satisfy KB.
Formulas
KB |= α — KB semantically entails α; holds when every model of KB is a model of α.
KB ⊢ α — α is syntactically derivable from KB by a proof procedure.
(P -> Q) ≡ (¬P ∨ Q) — implication elimination; applies in propositional and first-order formulas.
¬(P ∧ Q) ≡ (¬P ∨ ¬Q) and ¬(P ∨ Q) ≡ (¬P ∧ ¬Q) — De Morgan laws.
Resolution: (A ∨ l), (B ∨ ¬l) ⊢ (A ∨ B) — A,B are disjunctions of literals, l is a literal to resolve.
Modus Ponens: P, (P -> Q) ⊢ Q — basic rule used in forward/backward chaining.
CNF form: ∧_{i}(∨_{j} literal_{ij}) — a conjunction of clauses, each clause is a disjunction of literals.
Explain symbols: KB, α are sentences; P,Q are propositional atoms; l is literal (atomic or negated atomic). Units: not applicable.
Worked examples
Example 1 — Forward and backward chaining (Horn clauses). KB (in implication form):
- P -> Q
- Q -> R
- S ∧ P -> T
- P Query: R and T
Forward chaining (data-driven): Step 1: Known facts: P (from 4). Step 2: From 1 (P -> Q) and known P, by Modus Ponens infer Q. (now known: P,Q) Step 3: From 2 (Q -> R) and Q infer R. (now known: P,Q,R) Step 4: From 3 (S ∧ P -> T) we need S as well as P; S is not known, so cannot infer T. Conclusion: R is proved; T not proved by forward chaining.
Backward chaining (goal-driven) to prove T: Goal T. Find rule with head T: rule 3 requires S and P. P is known (4). Need to prove S. There is no rule that produces S and S is not a fact; backward chaining fails for T (unless more KB facts are given). For R, backward chaining would find R <- Q <- P and succeed using P.
Notes: This shows forward/backward chaining behavior and completeness for Horn: they will find R.
Example 2 — Resolution refutation (propositional). Show KB |= R for KB = {P -> Q, Q -> R, P}.
- Convert to clauses (implication elimination): (¬P ∨ Q), (¬Q ∨ R), P To prove R, add ¬R and show contradiction.
Clauses set: C = {¬P ∨ Q, ¬Q ∨ R, P, ¬R}
Resolution steps (numbered):
- Resolve clause (¬Q ∨ R) with (¬R) on R: (¬Q). Explanation: (¬Q ∨ R) and (¬R) resolve to ¬Q.
- Resolve clause (¬P ∨ Q) with (¬Q) on Q: (¬P). Explanation: (¬P ∨ Q) and (¬Q) resolve to ¬P.
- Resolve (¬P) with (P): empty clause ☐ (contradiction).
Because we derived the empty clause, KB ∧ ¬R is unsatisfiable; therefore KB |= R. Final answer bold in exam: R is entailed.
Example 3 — CNF conversion (short): Convert ∀x (P(x) -> ∃y Q(x,y)) to clause form (describe steps):
- Eliminate implication: ∀x (¬P(x) ∨ ∃y Q(x,y)).
- Move ¬ inwards: already.
- Skolemize existentials: replace ∃y Q(x,y) with Q(x, f(x)) (Skolem function f); now ∀x (¬P(x) ∨ Q(x,f(x))).
- Drop ∀, produce clause: ¬P(x) ∨ Q(x,f(x)). This is ready for resolution (after optionally treating variables as implicitly universally quantified). Note: verify Skolem function choice in review.
Common mistakes
- Forgetting to convert to CNF correctly (especially: not eliminating implications or not distributing ∨ over ∧ correctly).
- Incorrect Skolemization: using a constant where a Skolem function is required (when existential depends on universal variables).
- Assuming resolution completeness for first-order logic without stating Skolemization and unification conditions.
- Treating forward chaining as complete for non-Horn KBs (it is complete only for Horn clauses).
- Missing the empty clause as the indicator of contradiction in resolution proofs.
- In truth-table method, forgetting to check only rows where KB is true when testing entailment.
For your exam
Typical question types:
- Definitions: define model, satisfiable, valid, entailment, Horn clause, forward/backward chaining, resolution. Full marks: concise definitions and an example.
- Short notes: explain CNF conversion, Skolemization, soundness/completeness of resolution. Full marks: list steps and state assumptions/limitations.
- Derivation/proof: use resolution to show KB entails α or produce a forward-chaining trace. Full marks: show clause conversion, numbered resolution steps, final empty clause or successful derivation, and a short concluding sentence.
- Diagram/truth table: show entailment by truth table. Full marks: full table with labeled columns and highlighted rows.
- Algorithm complexity: ask time complexity for forward chaining on Horn KB. Full marks: state linear-time claim and explain why (each rule's counter decremented at most number of body literals iterations; each clause fired once).
In answers always: (1) show CNF steps explicitly if using resolution; (2) label each inference step with the rule used; (3) conclude with semantic statement (KB |= α) when appropriate.
Quick check
- What is a Horn clause? (one line)
- State the resolution rule for propositional logic.
- Why do we add ¬α to KB when using refutation by resolution?
Answers: 1) A clause with at most one positive literal (often written as A1 ∧ ... ∧ An -> B). 2) From (A ∨ l) and (B ∨ ¬l) infer (A ∨ B), resolving on literal l. 3) To show KB |= α by contradiction: we prove KB ∧ ¬α is unsatisfiable, deriving empty clause; this establishes entailment.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?