Knowledge representation, predicate logic and reasoning notes — Unit 4

Humans are intelligent not just because we can search a maze, but because we know things about the world and can reason to derive new facts. AI systems need a Knowledge Base (KB).

⇒1.1 The Core Mechanism

• Knowledge Base (KB): A set of sentences expressed in a formal representation language.
• Inference Engine: Algorithms that manipulate those sentences to derive new conclusions.

When an agent perceives something new, it `TELL`s the KB. Before acting, it `ASK`s the KB what to do.

The simplest logic. It represents facts as Boolean variables (P, Q) that can be True or False.

⇒2.1 Syntax

We combine propositions using logical connectives: NOT (`¬`), AND (`∧`), OR (`∨`), IMPLIES (`⇒`), and IFF (`⇔`).

⇒2.2 The Problem

Propositional logic is highly expressive but lacks scaling. To express 'All men are mortal', you would have to write a rule for every single man individually (`Man_Socrates ⇒ Mortal_Socrates ∧ Man_Plato ⇒ Mortal_Plato...`). This is computationally unfeasible.

Also known as FOL. It introduces the concept of Objects, Properties, and Relations.

⇒3.1 Syntax

• Constants: Specific objects (e.g., `Socrates`, `Earth`).
• Predicates: Properties or relations that evaluate to True/False (e.g., `Mortal(x)`, `Brother(John, Richard)`).
• Functions: Relations that return an object (e.g., `FatherOf(John)`).

Quantifiers allow us to write rules about groups of objects without naming them individually.

⇒4.1 Universal Quantifier (∀)

Means 'For all'. Used to make sweeping statements.

`∀x (King(x) ⇒ Person(x))` (All kings are persons).

⇒4.2 Existential Quantifier (∃)

Means 'There exists at least one'.

`∃x (Crown(x) ∧ OnHead(x, John))` (There is a crown on John's head).

How does the Inference Engine actually derive new facts?

⇒5.1 Modus Ponens

The classic inference rule. If `A ⇒ B` is True, and `A` is True, then we can conclude `B` is True.

⇒5.2 Resolution

A generalized inference rule used in theorem provers. It requires converting all sentences into Conjunctive Normal Form (CNF). It operates by proof-by-contradiction: to prove `P`, assume `¬P` and show that it leads to a mathematical contradiction in the Knowledge Base.

⇒6.1 Forward Chaining (Data-Driven)

Starts with the known facts in the KB. Iteratively applies rules to generate new facts until the goal is reached or no more facts can be generated. (e.g., A fire alarm system triggering sprinklers).

⇒6.2 Backward Chaining (Goal-Driven)

Starts with the Goal (the hypothesis). Finds rules that could produce that goal, and then checks if the premises for those rules are true in the KB. Used primarily in Expert Systems like medical diagnosis (Goal: 'Patient has flu', check symptoms).