Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

    1. Eliminate implications: replace (P -> Q) with (¬P ∨ Q).
    2. Move ¬ inwards (use De Morgan) to get negation only on atoms.
    3. Standardize variables (for FOL): rename bound variables so each quantifier has a unique variable.
    4. Move quantifiers to prenex normal form (pull all quantifiers to the front, preserving scope).
    5. Eliminate existential quantifiers by Skolemization (introduce Skolem functions/constants).
    6. Drop universal quantifiers (all variables now implicitly universally quantified).
    7. 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):

  1. P -> Q
  2. Q -> R
  3. S ∧ P -> T
  4. 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}.

  1. 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):

  1. Resolve clause (¬Q ∨ R) with (¬R) on R: (¬Q). Explanation: (¬Q ∨ R) and (¬R) resolve to ¬Q.
  2. Resolve clause (¬P ∨ Q) with (¬Q) on Q: (¬P). Explanation: (¬P ∨ Q) and (¬Q) resolve to ¬P.
  3. 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):

  1. Eliminate implication: ∀x (¬P(x) ∨ ∃y Q(x,y)).
  2. Move ¬ inwards: already.
  3. Skolemize existentials: replace ∃y Q(x,y) with Q(x, f(x)) (Skolem function f); now ∀x (¬P(x) ∨ Q(x,f(x))).
  4. 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

  1. What is a Horn clause? (one line)
  2. State the resolution rule for propositional logic.
  3. 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?