Knowledge Representation, Propositional Logic & Inference

Master formal logical reasoning in AI. Covers Knowledge Bases, Propositional Calculus, Truth Tables, Modus Ponens/Tollens, Resolution Refutation, Wumpus World navigation, and Horn Clauses.

KBS Architecture & Declarative vs Procedural Knowledge

A Knowledge-Based System consists of a Knowledge Base (storing facts and rules declaratively) and an Inference Engine (deriving new facts using domain-independent inference algorithms).

Knowledge-Based Agent Architecture

Sensors

ref

TELL(KB, Percept)

Inputs

Knowledge Base

ref

Axioms & Rules

KB Storage

Inference Engine

ref

ASK(KB, Query)

Outputs

Figure 1: Knowledge-Based Agent pipeline — Percepts are stored into KB, and Inference Engine resolves optimal actions.

Definition: Declarative Knowledge

Representing knowledge explicitly as logical sentences (what is true), allowing the inference engine to reason about actions dynamically.

Propositional Calculus Syntax & Truth Tables

Propositional logic evaluates sentences built from atomic propositions (P, Q, R) and logical connectives (not ~, and ^, or v, implies =>, iff <=>).

Inference Rules: Modus Ponens, Tollens & Resolution

Inference rules derive new true sentences from existing premises without generating full exponential truth tables.

Best Practices (Do)

✓Apply Modus Ponens when antecedent P and rule P => Q are both affirmatively known.
✓Transform sentences to Conjunctive Normal Form (CNF) before applying resolution refutation.
✓Restrict knowledge representation to Horn clauses when real-time linear performance is critical.

Common Pitfalls (Don't)

✕Do not commit the fallacy of Affirming the Consequent (given P => Q and Q, inferring P).
✕Do not assume P => Q is false when P is False (an implication is vacuously True).
✕Do not execute cyclic backward chaining without an active recursion visited check.

Key Takeaways & Summary

•Soundness guarantees no invalid conclusions are drawn; completeness ensures all truths are provable.
•Horn clauses permit linear-time O(N) forward and backward chaining inference.
•Resolution refutation proves a sentence by showing that the negation of the goal with the KB is unsatisfiable.

PROLOGProlog Horn Clause Rule Example

1% Knowledge Base
2man(socrates).
3mortal(X) :- man(X).
4 
5% Query: ?- mortal(socrates).
6% Answer: Yes.

Output

Yes.

Quick Syntax & Reference Sheet

Concept / Rule	Syntax / Usage
Modus Ponens	`P => Q, P \|- Q`
Modus Tollens	`P => Q, ~Q \|- ~P`
Hypothetical Syllogism	`P => Q, Q => R \|- P => R`
Disjunctive Syllogism	`P v Q, ~P \|- Q`
Resolution Rule	`P v Q, ~P v R \|- Q v R`
Implication Elimination	`P => Q === ~P v Q`
De Morgan 1	`~(P ^ Q) === ~P v ~Q`
De Morgan 2	`~(P v Q) === ~P ^ ~Q`
Horn Clause	`P1 ^ P2 ^ ... ^ Pn => Q`

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Assuming P => Q is false when P is False

Why it happens: An implication P => Q is vacuously TRUE whenever the antecedent P is False. It is ONLY false when P is True and Q is False.

Correction: Remember: 'A promise is only broken if the condition was met but the promise was not kept.'

✕ Mistake 2:

Confusing Modus Tollens with Affirming the Consequent

Why it happens: Given P => Q and Q, concluding P is a logical fallacy. (e.g. 'If it rains the ground is wet. The ground is wet. Therefore it rained' is invalid because a sprinkler could have caused it).

Correction: Modus Tollens only works backward by negating the consequent: P => Q and ~Q implies ~P.

Frequently Asked Questions

What is the difference between Soundness and Completeness?

An inference algorithm is SOUND if it only derives true entailed sentences (no false conclusions). It is COMPLETE if it can derive all sentences that are logically entailed (no missed conclusions).

What is a Horn Clause and why is it important in AI?

A Horn Clause is a rule with a conjunction of positive literals on the left and a single positive literal on the right (P1 ^ P2 => Q). Forward and Backward Chaining on Horn clauses runs in linear O(N) time instead of exponential O(2^N).