Artificial Computational Intelligence

First Order Logic, Forward Chaining, and Backward Chaining

Published: 2026-07-19

Level: postgraduate

Audience: Postgraduate students in Artificial Computational Intelligence

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Propositional logic, symbols, and logical connectives — covered in Lecture 9 (Propositional Logic and the Wumpus World)
Truth tables and entailment — covered in Lecture 9 (Propositional Logic and the Wumpus World)
Theorem proving with logical equivalences — covered in Lecture 10 (Propositional Logic Inference Techniques)
PL resolution using CNF and the DPLL algorithm — covered in Lecture 10 (Propositional Logic Inference Techniques)
Predicate logic preview (why propositional logic is not enough) — covered in Lecture 10 (Propositional Logic Inference Techniques)

First Order Logic, Forward Chaining, and Backward Chaining

Propositional logic is great for fixed facts, but it cannot talk about objects, relations, or quantities. This lecture builds first order logic on top of it, shows how to translate English into predicate logic, and then turns those rules into working inferences with forward and backward chaining. We close with a first look at reasoning under uncertainty.

11.1 Propositional Logic: Strengths and Limitations

Hook: Imagine you want to tell a computer "If it rains, the ground gets wet." Propositional logic handles this perfectly. But what if you want to say "Every country that has missiles is dangerous"? Propositional logic hits a wall — and that wall is exactly why first order logic exists.

11.1.1 Strengths of Propositional Logic

Before we see where propositional logic falls short, let us understand why it works so well for simple problems. Think of propositional logic as a set of light switches — each one is either on (true) or off (false). You can combine switches with rules, but you cannot peek inside them.

Intuition: Propositional logic is like a circuit board with labeled wires. Each wire (proposition) carries a truth value. You connect wires with gates (AND, OR, NOT). The circuit does not care about what the wires represent — it only cares about truth values flowing through.

Strength 1 — Declarative. You write what is true, not how to check it. The meaning does not depend on the order you write sentences. Compare this with a Python program where the order of statements matters. In logic, A ∧ B means the same thing whether you wrote A first or B first.

Strength 2 — Partial, disjunctive, or negated information. You can directly negate something. In a database, to negate a value you store it in a different field. In logic, you write ¬A directly. You can also say "A or B" without knowing which one is true — databases cannot do this natively.

Strength 3 — Compositional. You can combine sentences using logical rules. If B11 and P12 are both true, you can apply and-elimination to conclude B11 alone. You can chain rules: modus ponens (A, A → B ⊢ B), modus tollens (¬B, A → B ⊢ ¬A), and all the other equivalences from propositional calculus.

Strength 4 — Context-independent. Natural language has ambiguity — that is why prompt engineering exists. In logic programming, a statement has exactly one interpretation. "Bank" in English could mean a river bank or a financial bank. In propositional logic, B means exactly one thing.

11.1.2 Limitations of Propositional Logic

Intuition: Think of propositional logic as a language that can only name things with stickers. Each sticker is an opaque label — you cannot look inside. You can say "sticker A is true" or "sticker B implies sticker C," but you cannot say anything about what the stickers represent.

Propositional logic has limited expressive power. You are restricted to connectives: AND, OR, NOT, implication (→), and biconditional (↔). You cannot express relationships, quantification, or structure.

The wumpus world problem. Consider the statement: "Pits cause breezes in adjacent squares." You cannot write this as a single propositional sentence. Why? Because "adjacent" is a relation between squares — and propositional logic cannot represent relations. You would need one sentence per square pair:

P1,2 → (B1,1 ∨ B1,3 ∨ B2,2) ... and so on for every square.

For a 4×4 grid, this explodes into dozens of separate rules. Change the grid size, and you rewrite everything.

The quantification problem. Consider: "Some students are brilliant." In propositional logic, you define X = "a student is brilliant" and Y = "someone is brilliant", then write X → Y. But the word "some" — how many? One? Half? All? — is lost. The quantifier information disappears entirely.

Pitfall: Do not confuse propositional logic's limitation with a bug. It was designed for truth-functional reasoning about fixed facts. The limitation is that it cannot express structure — objects, relations, and quantities. That is what first order logic adds.

These two limitations — no relations, no quantifiers — lead us to predicate logic (also called first order logic, or FOL). The two names mean exactly the same thing.

Propositional logic gives us declarative, compositional, unambiguous reasoning about fixed facts. But it cannot express relations between objects or quantify over collections. First order logic solves both problems — that is where we are headed next.

In the real world, propositional logic powers SAT solvers — engines that check whether a set of constraints can be satisfied. Modern hardware verification, scheduling, and AI planning all use SAT solvers as a core component. But for knowledge-rich domains like medicine ("all patients with condition X should receive treatment Y"), propositional logic alone cannot capture the generality. That is the bridge to first order logic.

11.2 First Order Logic (Predicate Logic)

Hook: In propositional logic, you can say "It is raining" (true or false). But you cannot say "Every city in Kerala gets rain in June." First order logic adds exactly what is missing — the ability to talk about objects, relationships between them, and quantities like "all" or "some."

Intuition: Think of propositional logic as a flat photograph — it captures a scene, but you cannot zoom into individual objects or ask "which ones?" First order logic is like a 3D model — it has objects you can point to, relationships between them, and ways to say "check all of them" or "find at least one."

The analogy breaks down because a 3D model is visual, while FOL is symbolic. But the core idea holds: FOL gives structure to knowledge that propositional logic treats as a flat blob.

11.2.1 What FOL Adds Over Propositional Logic

Propositional logic assumes the world contains facts — flat, atomic truths. First order logic assumes the world contains objects, relations, and functions — just like natural language.

Everything in propositional logic carries over to FOL. You can still use AND, OR, NOT, implication (→), and biconditional (↔). But FOL adds three new kinds of building blocks:

Objects — things in the world: people, houses, numbers, colors, countries
Relations (predicates) — how objects connect: "is-a-brother-of," "is-less-than," "is-adjacent-to"
Functions — mappings from objects to objects: "left-leg-of," "square-root-of," "father-of"

The textbook (AIMA Ch. 8) makes the distinction precise: propositional logic commits only to the existence of facts, while FOL commits to the existence of objects with relations. This is called the ontological commitment of the logic — what it assumes about the nature of reality.

11.2.2 Syntax of FOL

The syntax of FOL builds on propositional logic and adds new vocabulary:

Element	Role	Examples
Constants	Name specific objects	KingJohn, 2, NUS, Pit
Predicates	State relations or properties	Brother, LessThan, Person
Functions	Map objects to objects	SquareRoot, LeftLegOf, CrownOf
Variables	Range over objects	x, y, z
Connectives	Combine sentences	∧, ∨, ¬, →, ↔ (same as propositional)
Quantifiers	Express "all" or "some"	∀ (for all), ∃ (there exists)
Equality	Assert same object	= (Father(John) = Henry)

The key addition is quantifiers — they let you express statements like "all kings are persons" or "some student is brilliant" in a single sentence. We cover them in detail in Section 11.3.

Every predicate and function symbol has an arity — the number of arguments it takes. Brother has arity 2 (binary). Person has arity 1 (unary). LeftLegOf has arity 1 (unary function).

11.2.3 Atomic Sentences

An atomic sentence is the simplest kind of statement in FOL. It consists of a predicate applied to terms. A term is any expression that refers to an object — a constant, a variable, or a function applied to terms.

Pattern: $P r e d i c a t e (t er m_{1}, t er m_{2}, \dots)$

Example 1: $B r o t h er (K in g J o hn, R i c ha r d T h e L i o n H e a r t)$

Brother is the predicate (relation between two people)
KingJohn and RichardTheLionHeart are constants (terms)
This sentence is true if the brotherhood relation holds between these two objects in the model

Example 2: Length(LeftLegOf(Richard))

LeftLegOf is a function — it maps a person to their left leg
Length is another function (or predicate) applied to the result
You evaluate inside-out: first compute LeftLegOf(Richard) (gives Richard's left leg), then take its Length

A function term like LeftLegOf(Richard) is just a complicated name for an object. It is not a "subroutine call" — there is no LeftLeg function that runs. It is a symbolic expression that refers to a specific object in the model.

Worked Example — Evaluating Atomic Sentences

Model: Objects = {John, Richard, John's left leg, Richard's left leg, a crown}

Interpretation:

KingJohn → John
Richard → Richard
LeftLeg maps John → John's left leg, Richard → Richard's left leg
Brother = {⟨Richard, John⟩, ⟨John, Richard⟩} (they are brothers)

Evaluate Brother(KingJohn, Richard): Substitute → Brother(John, Richard). Is ⟨John, Richard⟩ in the brotherhood relation? Yes. Sentence is true.

Evaluate LeftLeg(KingJohn): Substitute → LeftLeg(John) → John's left leg. This is a term, not a sentence — it names an object, not a truth value.

Evaluate Brother(LeftLeg(Richard), John): First compute LeftLeg(Richard) → Richard's left leg. Then ask: is ⟨Richard's left leg, John⟩ in the brotherhood relation? No. Sentence is false.

11.2.4 Complex Sentences

Complex sentences are built from atomic sentences using the same connectives as propositional logic.

Example: Sibling(KingJohn, Richard) → Sibling(Richard, KingJohn)

Sibling(KingJohn, Richard) is atomic
Sibling(Richard, KingJohn) is atomic
The → connective joins them into a complex sentence
Read as: "If King John is a sibling of Richard, then Richard is a sibling of King John"

You can build arbitrarily complex sentences by nesting: ¬(A ∧ B) ∨ ∃x P(x), and so on. The grammar of FOL is shown in Figure 8.3 of AIMA — operator precedence follows: ¬, =, ∧, ∨, →, ↔, with quantifiers binding everything to their right.

11.2.5 Truth in First Order Logic

Sentences are true or false with respect to a model and an interpretation.

A model contains a set of objects (the domain) and relations among them. For example, a healthcare AI model contains doctors, nurses, patients, and the manager-employee relation. A model is domain-specific — a healthcare model will not contain automobile data.

An interpretation maps symbols to objects and relations:

Constant symbols → objects in the domain
Predicate symbols → relations over those objects
Function symbols → functions over those objects

An atomic sentence P(t₁, t₂) is true if and only if the objects referred to by terms t₁ and t₂ stand in the relation referred to by predicate P.

Q: What is a model in FOL?

A: A model is a mathematical structure that represents a possible world. It contains a set of objects (the domain) and an interpretation that maps constant symbols to objects, predicate symbols to relations, and function symbols to functions. For example, a healthcare model contains doctors, patients, and relationships like "manages" or "treats." The model is domain-specific — it will not contain automobile data.

Pitfall: Do not confuse a model with the real world. A model is a mathematical structure — a set of objects plus an interpretation. The truth of a sentence depends on which model you evaluate it in. King(John) might be true in one model (where John is a king) and false in another.

Scope: FOL is more expressive than propositional logic, but it still has limits. It cannot express statements about relations themselves (that requires higher-order logic). For example, "every relation that is transitive is also reflexive" cannot be stated in FOL. For most AI applications, FOL is sufficient.

Q: What is the difference between a predicate and a function?

A: A predicate returns a truth value (true/false) — it states whether a relation holds. A function returns an object — it maps inputs to an object in the domain. Brother(x, y) is a predicate (true or false). LeftLeg(x) is a function (returns a leg object). In programming, both look like "functions," but in logic they play different roles.

Several students asked this question — it is a common point of confusion because both use parentheses and take arguments.

Q: Does Person(X) not show a relation between two items, so how can it be a predicate?

A: A predicate does not need two arguments. Person(X) is a unary predicate — it is a property of one object, not a relation between two. Think of it as "X has the property of being a person." You can later combine it with connectives: Person(X) ∧ Male(X).

First order logic extends propositional logic with objects, relations, functions, and quantifiers. Sentences are evaluated against a model and interpretation. The syntax mirrors natural language: nouns become constants, verbs become predicates, and "all"/"some" become quantifiers. Next, we look at quantifiers in detail.

FOL is the foundation of knowledge representation in AI. Prolog — a logic programming language — is built entirely on FOL (with some restrictions). Database query languages like SQL also trace their roots to relational logic, which is a restricted form of FOL. Medical expert systems, legal reasoning engines, and formal verification tools all use FOL as their representation language.

11.3 Quantifiers

Hook: In propositional logic, you cannot say "all kings are evil" as a single rule — you would need one sentence per king. Quantifiers fix this. With just two symbols — ∀ ("for all") and ∃ ("there exists") — you can express statements about entire collections of objects in one line.

Intuition: Think of ∀ as a universal scanner that sweeps over every object in the domain and checks a condition. Think of ∃ as a spotlight that searches for at least one object satisfying a condition.

∀ is like a teacher checking "every student submitted the homework" — all must pass.
∃ is like a teacher checking "at least one student got an A" — one is enough.

Quantifiers are the most powerful addition in predicate logic. They let you express statements like "some students are smart" or "all women are intelligent" — impossible in propositional logic.

11.3.1 Universal Quantifier

The universal quantifier is written as $\forall x$ . It means "for all x," "for each x," "for every x" — all equivalent. This is called universal quantification.

Template: $\forall x P (x)$ — "For every object x in the domain, P(x) is true."

Example: "All men drink coffee."

$\forall x (M an (x) \to D r ink s C o f f ee (x))$

Read as: "For every x, if x is a man, then x drinks coffee."

This means: X₁ drinks coffee, X₂ drinks coffee, X₃ drinks coffee — for every man in the domain. The universal quantifier with implication expands to a conjunction (AND) of all instantiations:

$(M an (X_{1}) \to D r ink s C o f f ee (X_{1})) \land (M an (X_{2}) \to D r ink s C o f f ee (X_{2})) \land \dots$

Why implication, not conjunction? This is the most common mistake. If you write $\forall x (M an (x) \land D r ink s C o f f ee (x))$ , it says everything in the domain is a man AND drinks coffee — including dogs, chairs, and numbers. The implication restricts the claim to only those x that are men.

Worked Example — Universal Quantifier

Domain: {John, Richard, Fido}

Statement: "All kings are persons."

$\forall x (K in g (x) \to P er so n (x))$

Expand by substituting each domain element:

x = John: $K in g (J o hn) \to P er so n (J o hn)$ — if John is a king, then John is a person
x = Richard: $K in g (R i c ha r d) \to P er so n (R i c ha r d)$
x = Fido: $K in g (F i d o) \to P er so n (F i d o)$

In the model, only John is a king. So the first sentence gives us the real claim: John is a person. The other two are vacuously true (Fido is not a king, so the implication holds regardless). That is exactly right — "all kings are persons" says nothing about dogs.

Another example: "All ACA classes this semester are interesting."

$\forall c (A C A C l a ss (c) \to I n t er es t in g (c))$

This expands to: Class₁ is interesting AND Class₂ is interesting AND ... AND Class₁₆ is interesting.

11.3.2 Existential Quantifier

The existential quantifier is written as $\exists x$ . It means "there exists x," "for some x," "at least one x."

Template: $\exists x P (x)$ — "There is at least one object x in the domain for which P(x) is true."

Example: "Some boys are intelligent."

$\exists x (B oy (x) \land I n t e l l i g e n t (x))$

Read as: "There exists an x such that x is a boy AND x is intelligent."

The existential quantifier with conjunction expands to a disjunction (OR) of all instantiations:

$(B oy (X_{1}) \land I n t e l l i g e n t (X_{1})) \lor (B oy (X_{2}) \land I n t e l l i g e n t (X_{2})) \lor \dots$

Why conjunction, not disjunction? If you write $\exists x (B oy (x) \lor I n t e l l i g e n t (x))$ , it says "there exists something that is a boy or is intelligent" — which is true if any object in the domain is intelligent, even a rock. The conjunction ensures you find one object satisfying both conditions.

Worked Example — Existential Quantifier

Domain: {Alice, Bob, Carol}

Statement: "Some student passed the exam."

$\exists x (S t u d e n t (x) \land P a sse d (x, E x am))$

Expand:

x = Alice: $S t u d e n t (A l i ce) \land P a sse d (A l i ce, E x am)$
x = Bob: $S t u d e n t (B o b) \land P a sse d (B o b, E x am)$
x = Carol: $S t u d e n t (C a r o l) \land P a sse d (C a r o l, E x am)$

If Alice is a student who passed, the whole statement is true — regardless of Bob and Carol. It only takes one.

Pitfall: The most common error is swapping the connectives. Remember: ∀ uses → (implication), ∃ uses ∧ (conjunction). If you write ∀ with ∧, you claim everything is both things. If you write ∃ with →, the statement is true whenever any object fails the premise (because false → anything is true).

11.3.3 Summary: Quantifier Patterns

Quantifier	Symbol	Pairs with	Expansion	Example
Universal (for all)	$\forall$	Implication ( $\to$ )	Conjunction (AND)	"All kings are persons"
Existential (there exists)	$\exists$	Conjunction ( $\land$ )	Disjunction (OR)	"Some boy is intelligent"

Q: Why not jump directly to first order logic if propositional logic has limitations?

A: You can — and FOL is strictly more expressive. But propositional logic is simpler, decidable, and has efficient SAT solvers. For problems without relations or quantification, propositional logic is the better tool. Use the simplest logic that fits your problem.

Q: Is the existential quantifier equivalent to OR, and universal to AND?

A: That is the right intuition for the expansion. Universal ∀ expands to AND of implications. Existential ∃ expands to OR of conjunctions. But the quantifiers themselves pair with the opposite connective in the formula. This is the key pattern to remember.

Quantifiers add "for all" (∀) and "there exists" (∃) to logic. Universal pairs with implication and expands to AND. Existential pairs with conjunction and expands to OR. Getting the connective right is the single most important pattern in FOL. Next, we practice translating English sentences into predicate logic.

Quantifiers are used everywhere in mathematics and computer science. Database queries use universal quantification (SQL's NOT EXISTS for universal checks). Type systems in programming languages use universal types (forall a. ...). Formal verification proves properties like "for all inputs, the program returns the correct output." The quantifier patterns you learn here appear across all of these fields.

11.4 Translating English to Predicate Logic

Hook: This is the skill you will be tested on. The examination expects one or two marks just for the English-to-logic conversion step. The good news: there is a repeatable recipe.

Intuition: Translating English to predicate logic is like filling out a form. The verb gives you the predicate name. The nouns give you the arguments. The words "all," "some," "every," "no" tell you which quantifier to use and in what order.

This is a procedural skill — a recipe you follow. Here is the recipe, then we trace it on two examples.

Recipe for English → Predicate Logic:

Find the verb (action or relation). This becomes your predicate name.
Ask who/what/whom/where about the verb. Each answer is an argument to the predicate.
Check for quantifier words. "All," "every," "each" → ∀. "Some," "there exists," "at least one" → ∃. "No," "none" → ¬∃ or ∀...¬.
Assign variables to quantified nouns. Each quantified noun gets its own variable.
Choose the right connective. ∀ pairs with →. ∃ pairs with ∧ (remember Section 11.3).
Write the formula with quantifiers in order. The order matters when you mix ∀ and ∃.

11.4.1 Worked Example: "John is teaching ML course for some students"

Step 1 — Find the verb. The verb is "teaching."

Step 2 — Ask questions about the action.

Who is teaching? → John
What is he teaching? → ML course
For whom? → some students

Step 3 — Check for quantifier words. The sentence is about a specific teacher, a specific course, and specific students. No "all" or "some" appears. But we are asserting that this particular teaching event exists.

Step 4 — Write the predicate.

$T e a c hin g (J o hn, M L, S t u d e n t s)$

If we want to generalize (who teaches what to whom):

$\exists x, c, s T e a c hin g (x, c, s)$

where x is a person, c is a course, s are students.

Why existential and not universal? Because not every teacher teaches ML to all students. We are saying: there exists some teacher who teaches some course to some students. The quantifier ∃ matches "there is a specific arrangement."

Q: How do we say "John teaches ML to all students"?

A: You mix quantifiers — existential for John (he is specific) but universal for students:

$\exists x (T e a c h er (x) \land \forall s T e a c hin g (x, M L, s))$

You cannot write it with a single quantifier because John is a specific person (∃) while students are universally quantified (∀).

11.4.2 Worked Example: "Seller sells all the products to customers"

Step 1 — Find the verb. "Sells."

Step 2 — Ask questions.

Who sells? → some seller
Sells what? → all products
To whom? → customers

Step 3 — Check quantifier words. "All products" → ∀P. "Some seller" → ∃S. "Customers" → ∃C (some customers, not necessarily all).

Step 4 — Write the formula.

$\exists S \forall P \exists C S e l l s (S, P, C)$

Read left to right: "There exists a seller S such that for every product P, there exists some customer C such that S sells P to C."

Step 5 — Verify the connectives. Since all quantifiers wrap the whole formula, we do not need explicit → or ∧ here. The quantifier order already captures the meaning.

Pitfall: If you wrote $\forall S, P, C S e l l s (S, P, C)$ , it would mean "ALL sellers sell ALL products to ALL customers" — a much stronger (and likely false) claim. The order and type of quantifiers matters critically.

Alternative explicit notation. You can also write:

$\forall P \exists S, C S e l l s (S, P, C)$

This makes explicit that P is universal while S and C are existential. Both notations mean the same thing.

Translating English to predicate logic follows a recipe: find the verb, identify arguments, choose quantifiers from keywords ("all" → ∀, "some" → ∃), pick connectives (∀ with →, ∃ with ∧), and write quantifiers in order. This is a key exam skill. Next, we study the properties of quantifiers — especially what happens when you change their order.

This translation skill is the bridge between natural language knowledge and formal reasoning. In knowledge engineering, domain experts describe rules in English, and the knowledge engineer converts them to predicate logic. Getting the translation wrong means the system reasons incorrectly — a bug that is hard to trace.

11.5 Properties of Quantifiers

Hook: You have two quantifiers (∀ and ∃) and a bag of properties (commutativity, negation, duality). The critical fact: swapping two ∀'s is fine. Swapping ∀ and ∃ changes the meaning entirely. Get this wrong on the exam, and your answer is backwards.

Intuition: Think of ∀ as a "for each" loop and ∃ as a "find one" search. Two nested "for each" loops can run in either order — you check all pairs either way. But a "find one" inside a "for each" is different from a "for each" inside a "find one."

11.5.1 Commutativity of Same-Type Quantifiers

When you have only one type of quantifier, order does not matter:

$\exists x \exists y P (x, y) \equiv \exists y \exists x P (x, y)$

$\forall x \forall y P (x, y) \equiv \forall y \forall x P (x, y)$

Example for universal: "For all men, for all women" is the same as "for all women, for all men." You are checking every pair either way.

Example for existential: "There exists a man and there exists a woman such that..." is the same regardless of which you name first.

11.5.2 Non-Commutativity of Mixed Quantifiers

When you mix ∀ and ∃, order matters critically. This is the most tested property.

Statement 1: $\exists x \forall y L o v es (x, y)$

Meaning: "There is one specific person who loves everyone."

Statement 2: $\forall y \exists x L o v es (x, y)$

Meaning: "For each person y, there is some person x who loves y (possibly a different x for each y)."

These are completely different claims. Statement 1 is much stronger — it says one person loves the entire world. Statement 2 is weaker — it just says nobody is unloved, but the lover could be different for each person.

Worked Example — Mixed Quantifier Order

Domain: {Alice, Bob, Carol}

∃x ∀y Loves(x, y): Is there one person who loves everyone?

Check x = Alice: Does Alice love Alice AND Bob AND Carol? If yes → statement is true.
If no single person loves everyone → statement is false.

∀y ∃x Loves(x, y): For each person, does someone love them?

y = Alice: Is there some x who loves Alice? (Maybe Bob.)
y = Bob: Is there some x who loves Bob? (Maybe Carol.)
y = Carol: Is there some x who loves Carol? (Maybe Alice.)

The second statement can be true even when the first is false — as long as everyone is loved by someone.

Pitfall: Statement 1 (∃x ∀y) always implies Statement 2 (∀y ∃x), but not the reverse. If one specific person loves everyone, then certainly everyone is loved by someone. But the reverse does not hold.

11.5.3 Negation of Quantifiers

When you negate a quantifier, the quantifier flips:

$\neg\forall x P (x) \equiv \exists x \neg P (x)$

$\neg\exists x P (x) \equiv \forall x \neg P (x)$

Worked Example — Negation

"Not all students like math."

$\neg\forall x L ik es M a t h (x) \equiv \exists x \neg L ik es M a t h (x)$

"There exists a student who does not like math." Flip ∀ to ∃, negate the predicate.

"No student likes homework."

$\neg\exists x L ik esH o m e w or k (x) \equiv \forall x \neg L ik esH o m e w or k (x)$

"For all x, x does not like homework." Flip ∃ to ∀, negate the predicate.

These are the De Morgan rules for quantifiers — they generalize the familiar De Morgan laws for propositional logic:

Propositional	Quantifier
¬(A ∧ B) ≡ ¬A ∨ ¬B	¬∀x P(x) ≡ ∃x ¬P(x)
¬(A ∨ B) ≡ ¬A ∧ ¬B	¬∃x P(x) ≡ ∀x ¬P(x)

11.5.4 Duality

Duality means representing the same fact using double negation.

Worked Example — Duality

"Everyone likes ice cream."

Original: $\forall x L ik es (x, I ce C r e am)$

Dual: $\neg\exists x \neg L ik es (x, I ce C r e am)$ — "No one dislikes ice cream."

Both mean the same thing. The dual keeps the original quantifier, negates the predicate, and wraps the whole thing in another negation.

Key distinction: Negation flips the quantifier (∀ → ∃). Duality represents the same fact using double negation — the quantifier type stays, but the predicate is negated and the whole statement is negated.

Another example: "Everybody is intelligent in my class" = "Nobody is dumb in my class."

Pitfall: Do not confuse negation with duality. Negation changes the truth value (true becomes false). Duality preserves the truth value — it is just a different way of saying the same thing.

Q: What happens if we accidentally interchange predicates while writing?

A: If you swap the order of arguments in a predicate (e.g., writing Loves(y, x) instead of Loves(x, y)), you change the meaning — "x loves y" becomes "y loves x." If you swap the order of mixed quantifiers (∃x ∀y vs ∀y ∃x), the meaning changes dramatically. Always check: which variable is universally quantified and which is existential, and keep them in the right order.

Same-type quantifiers commute. Mixed quantifiers do not — ∃x ∀y is much stronger than ∀y ∃x. Negation flips quantifiers (∀ ↔ ∃). Duality restates the same fact with double negation. These properties are exam favorites. Next, we see how to instantiate quantified sentences with specific objects.

11.6 Instantiation

Hook: You have a rule that says "all kings are evil." You know John is a king. How do you conclude John is evil? You instantiate — substitute John for x and drop the quantifier. This simple move is the engine behind forward and backward chaining.

Intuition: Instantiation is like plugging a specific value into a formula. If ∀x P(x) is a vending machine that works for any coin, instantiation is putting a specific coin (John) in and getting P(John) out.

11.6.1 Universal Instantiation

Universal instantiation (UI) says: if $\forall v α$ is true, then you can substitute any ground term G (a term with no variables) for variable v in α, and the result is also true.

Rule: From $\forall x α$ , infer $SUBST ({x / G}, α)$ for any ground term G.

A ground term is a term with no variables — a constant like John or a function applied to constants like Father(John).

Worked Example — Universal Instantiation

Given: $\forall x (K in g (x) \to E v i l (x))$

Fact: King(John) is true.

Substitute x = John:

$K in g (J o hn) \to E v i l (J o hn)$

We removed the quantifier. Now we have a plain implication. Since King(John) is given, by modus ponens: Evil(John) is true.

We can also substitute x = Father(John):

$K in g (F a t h er (J o hn)) \to E v i l (F a t h er (J o hn))$

This is valid even though we may not know whether Father(John) is a king. The implication is still a true sentence.

11.6.2 Existential Instantiation

Existential instantiation (EI) says: if $\exists v α$ is true, then you can replace v with a new constant that appears nowhere else in the knowledge base. This new constant is called a Skolem constant.

Rule: From $\exists x α$ , infer $SUBST ({x / k}, α)$ where k is a fresh constant (a Skolem constant) not used anywhere else.

Worked Example — Existential Instantiation

Given: $\exists x (C r o w n (x) \land O n H e a d (x, J o hn))$

"There is a crown on John's head." We do not know which crown, but we know one exists.

Introduce Skolem constant C₁:

$C r o w n (C_{1}) \land O n H e a d (C_{1}, J o hn)$

C₁ represents "some crown" — we gave it a name so we can reason about it. The name must be fresh — you cannot reuse C₁ for a different existential claim.

Why Skolem constants matter. Without them, you cannot chain inferences. If Rule 1 says "there exists a crown on John's head" and Rule 2 says "anything on John's head is precious," you need a name for the crown to connect the two rules. The Skolem constant provides that name.

Pitfall: You can apply universal instantiation many times — once for each ground term. Existential instantiation is applied once per sentence, and then the existentially quantified sentence can be discarded. EI introduces one witness; UI applies to everything.

Q: As the number of objects in the knowledge base becomes very large (millions), do we still generate all possible instances?

A: No. That is the whole point of forward and backward chaining — they apply inference directly on the predicate logic rules, generating only the instances needed for the query. Full propositionalization (enumerating all instances) is impractical for large domains.

Universal instantiation substitutes any ground term into a ∀-quantified sentence. Existential instantiation introduces a fresh Skolem constant for an ∃-quantified sentence. UI can be applied repeatedly; EI is applied once per existential claim. These are the building blocks of FOL inference. Next, we see how to convert FOL entirely to propositional logic.

11.7 Reduction to Propositional Inference

Hook: Can you just convert all of first order logic into propositional logic and use the SAT solvers you already know? Yes — in principle. But the catch is that the conversion can produce infinitely many sentences.

Intuition: Think of propositionalization as "unpacking" every quantified rule into individual facts. If you have 3 objects and one universal rule, you get 3 propositional sentences. If you have a million objects, you get a million. And if function symbols are allowed (like Father), you can nest them forever — Father(Father(Father(...))) — creating infinitely many terms.

11.7.1 The Conversion Process

FOL can be converted to propositional logic by enumeration (also called propositionalization):

Take every universally quantified sentence $\forall x α$ and instantiate it for every ground term in the domain.
Take every existentially quantified sentence $\exists x α$ and apply existential instantiation once (introduce a Skolem constant).
Replace all remaining ground atomic sentences with propositional symbols.

Once converted, you can apply any propositional logic technique: truth tables, DPLL, or resolution with CNF.

Worked Example — Propositionalization

Knowledge base:

$\forall x (K in g (x) \to P er so n (x)), K in g (J o hn), G r ee d y (J o hn), B r o t h er (R i c ha r d, J o hn)$

Domain: {John, Richard}

Step 1 — Instantiate ∀x with both objects:

$K in g (J o hn) \to P er so n (J o hn)$

$K in g (R i c ha r d) \to P er so n (R i c ha r d)$

Step 2 — Replace with propositional symbols:

A = King(John), B = Person(John), C = King(Richard), D = Person(Richard)

Propositional KB: {A → B, A, Greedy(John), Brother(Richard, John)}

From A and A → B, conclude B: Person(John). Done.

11.7.2 When to Use This Approach

When to use: If the domain is small (few objects, few relations), converting to propositional and applying known techniques can be effective. Prolog compilers sometimes do this internally for small predicate sets.

When not to use: For large domains with millions of objects, enumeration is impractical. The number of ground facts grows as $p \cdot n^{k}$ where p is the number of predicates, n is the number of constants, and k is the maximum arity. With function symbols, the set of ground terms is infinite.

Key insight: Predicate logic can always be converted to propositional logic (by enumeration), but propositional logic cannot be converted to predicate logic. FOL is strictly more expressive.

Scope: Propositionalization is a theoretical tool for proving completeness results (Herbrand's theorem). In practice, forward and backward chaining work directly on the predicate logic, generating only the instances needed. The textbook notes that forward chaining on definite clauses is complete for Datalog (no function symbols).

FOL can be reduced to propositional logic by enumerating all ground instances, but this is exponential or infinite in general. Forward and backward chaining avoid this by generating only relevant instances. This conversion shows FOL is at least as powerful as propositional logic. Next, we study forward chaining — the first practical FOL inference method.

11.8 Forward Chaining

Hook: Imagine you are a detective with a table of clues. You keep matching clues against rules: "If A and B, then C." Every time a rule fires, you add the conclusion to your clue table. You keep going until no new clues appear — or until you find what you are looking for. That is forward chaining.

11.8.1 What Is Forward Chaining?

Forward chaining is an inference technique for first order logic. It is a bottom-up approach — you start from the facts and work toward the goal.

Purpose: Forward chaining derives all facts that can be proved from a knowledge base of definite clauses. It answers open-ended queries like "Who are all the enemies of America?" by generating every derivable fact.

A definite clause is either an atomic fact or an implication whose antecedent is a conjunction of positive literals and whose consequent is a single positive literal. Example: $A (x) \land B (x) \to C (x)$ .

Inputs & Outputs:

Input: A knowledge base of first order definite clauses + a query α
Output: A substitution θ that makes α true, or false if α cannot be derived
Side effect: The knowledge base grows as new facts are added

Steps:

Start with all known facts in the knowledge base
For each rule, match its LHS (premises) against known facts using unification
When all premises of a rule are satisfied, derive the RHS (conclusion) as a new fact
Add the new fact to the knowledge base (if not already present)
Repeat until no new facts are added (fixed point) or the query is answered

Best suited for: Open-ended queries — "Who are all the enemies of America?" "What weapons has West sold?" You explore all possibilities and generate all derivable facts.

11.8.2 Worked Example: "West is a Criminal"

Trace — Forward Chaining on the Crime Problem

The problem (in English): "The law says it is a crime for an American to sell weapons to hostile nations. The country Nono, an enemy of America, has some missiles. All of its missiles were sold to it by Colonel West, who is American."

Query: Prove that West is a criminal.

Step 1 — Identify predicates and translate to rules:

Rule 1 (the law):

$\forall X, Y, Z (A m er i c an (X) \land W e a p o n (Y) \land S e l l s (X, Y, Z) \land H os t i l e (Z) \to C r imina l (X))$

Rule 2 (missiles sold by West):

$\forall X (M i ss i l e (X) \land O w n s (N o n o, X) \to S e l l s (W es t, X, N o n o))$

Rule 3 (missiles are weapons):

$\forall X (M i ss i l e (X) \to W e a p o n (X))$

Rule 4 (enemies are hostile):

$\forall X (E n e m y (X, A m er i c a) \to H os t i l e (X))$

Step 2 — Atomic facts (given):

American(West)
Missile(M1) — existential instantiation of "Nono has some missiles"
Owns(Nono, M1)
Enemy(Nono, America)

Step 3 — Round 1 of forward chaining:

Fact	Derived from
Weapon(M1)	Rule 3, X = M1
Sells(West, M1, Nono)	Rule 2, X = M1
Hostile(Nono)	Rule 4, X = Nono

Step 4 — Round 2:

All four premises of Rule 1 now match: American(West), Weapon(M1), Sells(West, M1, Nono), Hostile(Nono).

Substitution: {X/West, Y/M1, Z/Nono}

Derive: Criminal(West) — proved.

Sense-check: West sold missiles (weapons) to Nono (hostile, enemy of America). The law says that makes him a criminal. The derivation matches our intuition.

11.8.3 Properties of Forward Chaining

Scope: Forward chaining is sound (every derived fact is true) and complete for definite clause knowledge bases (it finds every derivable fact). For Datalog (no function symbols), it always terminates. With function symbols, it may not terminate — e.g., the Peano axioms generate NatNum(S(0)), NatNum(S(S(0))), forever.

Drawbacks:

May generate many irrelevant facts not related to your query
May perform redundant rule matching — re-checking rules that cannot fire
For close-ended (yes/no) queries, it does more work than necessary

The textbook describes optimizations: incremental forward chaining (only check rules triggered by newly added facts), the Rete algorithm (retain partial matches across iterations), and magic sets (backward preprocessing to restrict forward chaining to relevant bindings).

Pitfall: Forward chaining is like exploring every room in a building looking for one specific book. If you only need a yes/no answer, backward chaining (going directly to the shelf) is more efficient.

Forward chaining starts from facts, applies rules bottom-up, and derives all reachable conclusions. It is sound, complete, and best for open-ended queries. The West-is-Criminal example shows the full two-round derivation. Next, we see backward chaining — the top-down, goal-driven alternative.

Forward chaining powers production systems (like XCON/R1, one of the first commercial expert systems) and rule engines in business logic. Modern systems like Drools (Java) and CLIPS use forward chaining for event-driven reasoning: when new facts arrive, rules fire automatically. Database trigger systems and complex event processing also follow this pattern.

11.9 Backward Chaining

Hook: Forward chaining explores everything. But what if you just want to know: "Is West a criminal?" — a yes or no answer. Backward chaining starts from the goal and works backward, checking only what is needed. It is like solving a maze from the exit, not the entrance.

11.9.1 What Is Backward Chaining?

Backward chaining starts from the goal (RHS of rules) and works backward to the facts (LHS). It is a top-down approach, similar to backtracking.

Purpose: Backward chaining proves (or disproves) a specific query by decomposing it into sub-goals. It is focused — it only explores paths relevant to the goal.

Inputs & Outputs:

Input: A knowledge base of definite clauses + a query (goal)
Output: A substitution θ that proves the goal, or failure if it cannot be proved

Steps:

Start with the goal (what you want to prove)
Search for a rule whose RHS matches the goal (using unification)
Replace the goal with the LHS of that rule — these become sub-goals
For each sub-goal: if it is already a fact, it is resolved. If not, recursively apply backward chaining
If all sub-goals resolve to facts, the original goal is proved
If any sub-goal fails (no matching rule or fact), backtrack and try another rule

Best suited for: Close-ended queries — "Is West a criminal?" You start directly from the answer you want to check.

11.9.2 Worked Example: Same Problem, Backward Chaining

Trace — Backward Chaining on Criminal(West)

Goal: Criminal(West)

Step 1 — Find a rule whose RHS matches. Rule 1: $am er i c an (X) \land W e a p o n (Y) \land S e l l s (X, Y, Z) \land H os t i l e (Z) \to C r imina l (X)$

Unify RHS with goal: {X/West}. LHS becomes four sub-goals:

American(West) — already a fact → resolved
Weapon(Y) — Y unknown
Sells(West, Y, Z) — Y, Z unknown
Hostile(Z) — Z unknown

Step 2 — Resolve Weapon(Y). Find Rule 3: $M i ss i l e (X) \to W e a p o n (X)$ . Unify: {X/Y}. Sub-goal: Missile(Y). Check facts: Missile(M1) matches. Resolved. Y = M1.

Step 3 — Resolve Sells(West, M1, Z). Find Rule 2: $M i ss i l e (X) \land O w n s (N o n o, X) \to S e l l s (W es t, X, N o n o)$ . Unify: {X/M1}. Sub-goals:

Missile(M1) — fact → resolved
Owns(Nono, M1) — fact → resolved

Sells(West, M1, Nono) proved. Z = Nono.

Step 4 — Resolve Hostile(Nono). Find Rule 4: $E n e m y (X, A m er i c a) \to H os t i l e (X)$ . Unify: {X/Nono}. Sub-goal: Enemy(Nono, America) — fact → resolved.

All sub-goals resolved. West is a criminal. Proved.

The proof tree is read depth-first, left to right. Each node is an AND — all children must be resolved. If one child fails, the system backtracks and tries another rule.

11.9.3 Properties of Backward Chaining

Backward chaining is more focused than forward chaining. It only explores facts and rules relevant to the goal.

It is efficient for close-ended queries because it does not generate irrelevant facts.

Drawback: If the query is false, backward chaining may explore many paths before concluding it cannot be proved. It is a depth-first search — it can get stuck in infinite loops if the rule set has cycles.

Pitfall: Backward chaining can suffer from infinite recursion. If a rule's RHS matches its own LHS (circular reasoning), the algorithm loops forever. Prolog handles this with depth limits, but pure backward chaining does not guarantee termination.

11.9.4 Forward vs. Backward Chaining: When to Use Which

Feature	Forward Chaining	Backward Chaining
Direction	Bottom-up (facts → goal)	Top-down (goal → facts)
Starting point	All known facts	The query/goal
Best for	Open-ended queries	Close-ended queries
Exploration	Generates all derivable facts	Only explores relevant paths
Example	"List all enemies of America"	"Is West a criminal?"
Analogy	Flood fill from all sources	Tracing one river upstream

Both techniques can be used for both types of queries, but suitability differs. Use forward chaining when you need all answers. Use backward chaining when you need one specific answer.

Q: If both reach the same conclusion, how do we decide which is more suitable?

A: Close-ended (yes/no) → backward chaining (start from goal, stop as soon as proved). Open-ended (list answers) → forward chaining (generate all derivable facts, filter for the query).

Q: Why does the derivation tree for the West problem contain only AND gates and no OR?

A: In this particular problem, each sub-goal matches exactly one rule. If multiple rules could prove the same sub-goal (e.g., two different ways to prove Weapon(Y)), the tree would have OR branches — you would need to try each alternative.

Backward chaining starts from the goal, decomposes it into sub-goals, and resolves each against facts or further rules. It is focused and efficient for yes/no queries. The West-is-Criminal example shows the full four-step backward derivation. Together with forward chaining, these are the two main practical inference methods for FOL.

Prolog — the most widely used logic programming language — is built entirely on backward chaining. When you write a Prolog query like criminal(West), the engine applies depth-first backward chaining with unification. The :- operator in Prolog is written "backwards" from standard implication: C :- A, B means $A \land B \to C$ . Prolog's execution model is exactly the backward chaining algorithm described here, with some practical additions (arithmetic built-ins, I/O, database modification).

11.10 Practice Exercise: Jack and Curiosity

Hook: This is the kind of problem you will see on the exam. Jack owns a dog. Every dog owner loves animals. No animal lover kills an animal. Either Jack or Curiosity killed a cat named Tuna. Did Curiosity kill the cat? The answer requires translating English to predicate logic, then applying backward chaining.

11.10.1 Problem Statement

Problem: Jack owns a dog. Every dog owner is an animal lover. No animal lover kills an animal. Either Jack or Curiosity killed a cat, who is named Tuna. Did Curiosity kill the cat?

Query: Did Curiosity kill the cat? — This is a close-ended query (yes/no), so use backward chaining.

Full Solution — English to Predicate Logic + Backward Chaining

Step 1 — Extract predicates:

Owns(x, y) — x owns y
Dog(x) — x is a dog
DogOwner(x) — x is a dog owner
AnimalLover(x) — x is an animal lover
Animal(x) — x is an animal
Cat(x) — x is a cat
Kills(x, y) — x kills y

Step 2 — Translate English to predicate logic:

"Jack owns a dog."

$\exists d (D o g (d) \land O w n s (J a c k, d))$

"Every dog owner is an animal lover."

$\forall x (\exists d (D o g (d) \land O w n s (x, d)) \to A nima l L o v er (x))$

"No animal lover kills an animal."

$\forall x \forall y (A nima l L o v er (x) \land A nima l (y) \to \neg K i l l s (x, y))$

"Either Jack or Curiosity killed the cat Tuna."

$K i l l s (J a c k, T u na) \lor K i l l s (C u r i os i t y, T u na)$

Also assert: Cat(Tuna), Animal(Tuna) (cats are animals), Dog(d) for some d.

Step 3 — Apply backward chaining:

Goal: Did Curiosity kill Tuna? i.e., Kills(Curiosity, Tuna)?

From statement 4: Either Jack or Curiosity killed Tuna. Try backward chaining on Kills(Curiosity, Tuna).

Check statement 3: If AnimalLover(Curiosity) and Animal(Tuna), then ¬Kills(Curiosity, Tuna).

Is Curiosity an animal lover? Statement 3 says animal lovers do not kill animals. If Curiosity killed Tuna (an animal), then Curiosity is NOT an animal lover. That is consistent — but we need to determine which path holds.

From statement 4: Kills(Jack, Tuna) ∨ Kills(Curiosity, Tuna).

From statement 2: Jack owns a dog → Jack is an animal lover (DogOwner(Jack) → AnimalLover(Jack)).

From statement 3: AnimalLover(Jack) ∧ Animal(Tuna) → ¬Kills(Jack, Tuna).

So Jack did NOT kill Tuna (he is an animal lover, and animal lovers do not kill animals).

From statement 4, since ¬Kills(Jack, Tuna), by disjunctive syllogism:

Kills(Curiosity, Tuna) — Yes, Curiosity killed the cat.

11.10.2 Predicates and Translation

The predicates to extract: Owns, Dog, DogOwner, AnimalLover, Kills, Cat, Animal.

The key translation challenges:

"Every dog owner" → universal quantifier with implication
"No animal lover kills" → universal with negation in the consequent
"Either Jack or Curiosity" → disjunction of two ground literals

11.10.3 Exam Relevance

Exam note: This problem type — English to predicate logic conversion followed by chaining — is directly examinable. Expect one or two marks for the conversion step and another one or two marks for applying the chaining technique. Practice translating "no," "every," "some," and "either...or" into the correct quantifier patterns.

11.11 Introduction to Probabilistic Reasoning

Hook: Logic says: "If it is raining, the ground is wet." But what if the sprinkler was on? Or the sensor is faulty? Real life is uncertain. Probabilistic reasoning handles degrees of belief — not just true/false, but "70% likely." This is the bridge from logic to the next unit on Bayesian networks.

11.11.1 Why Probability?

Logic is monotonic — once you prove something, it stays proved. But real-world knowledge is often non-monotonic — new evidence can change your conclusion.

Monotonic vs. Non-monotonic:

Monotonic (logic): Adding new facts never invalidates old conclusions. If KB ⊨ α, then KB ∪ {β} ⊨ α.
Non-monotonic (default reasoning): "Birds fly" — until you learn it is a penguin. New evidence retracts the conclusion.

Probability gives a principled way to reason under uncertainty. Instead of "true" or "false," statements have a degree of belief between 0 and 1.

11.11.2 Bangalore Airport Example

Scenario: You are at Bangalore airport. Your flight is delayed. Is it because of weather, air traffic, or a mechanical fault? You cannot know for certain. But you can assign probabilities based on what you observe (rain outside, news of congestion) and reason about the most likely cause.

Worked Example — Flight Delay Reasoning

Let D = "flight delayed," W = "bad weather," C = "air traffic congestion."

From experience:

Observation	Belief
Rain visible outside	P(W) is high
News reports congestion	P(C) is high
No storm, clear skies	P(W) is low

Given W and C, P(D) increases. You reason: "It is probably weather or congestion, not a mechanical fault." This is probabilistic, not logical — you are not certain, just more confident.

11.11.3 Probability Basics

Axioms of Probability:

$0 \leq P (A) \leq 1$

$P (T r u e) = 1, P (F a l se) = 0$

$P (A \lor B) = P (A) + P (B) - P (A \land B)$

Conditional probability:

$P (A ∣ B) = \frac{P ( A \land B )}{P ( B )}$

Chain rule (product rule):

$P (A \land B) = P (A ∣ B) P (B) = P (B ∣ A) P (A)$

11.11.4 Joint Probability Distribution

Worked Example — Toothache, Cavity, Catch

Consider three Boolean variables: Toothache (T), Cavity (C), Catch (Catch — the probe catches on a cavity).

The joint distribution P(Toothache, Cavity, Catch) has $2^{3} = 8$ entries. A small slice:

Toothache	Cavity	Catch	P
true	true	true	0.108
true	true	false	0.012
true	false	true	0.016
true	false	false	0.064
false	true	true	0.072
false	true	false	0.008
false	false	true	0.144
false	false	false	0.576

Marginalization: To find P(Cavity), sum over the other variables:

$P (C a v i t y) = t, c \sum P (T oo t ha c h e = t, C a v i t y, C a t c h = c)$

From the table: P(Cavity = true) = 0.108 + 0.012 + 0.072 + 0.008 = 0.20.

Conditional probability: Given a toothache, what is the chance of a cavity?

$P (C a v i t y ∣ T oo t ha c h e) = \frac{P ( C a v i t y \land T oo t ha c h e )}{P ( T oo t ha c h e )}$

P(Toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.20.

P(Cavity ∧ Toothache) = 0.108 + 0.012 = 0.12.

$P (C a v i t y ∣ T oo t ha c h e) = \frac{0.12}{0.20} = 0.60$

So a toothache raises the probability of a cavity from 0.20 to 0.60.

11.11.5 What Is Coming Next

This lecture ends the logic unit. The next unit covers probabilistic reasoning in depth — Bayesian networks, inference in graphical models, and decision-making under uncertainty.

Exam note: You are not expected to compute full Bayesian inference in this lecture — that comes later. But you should understand why probability is needed (uncertainty, non-monotonic reasoning) and be able to compute basic conditional probabilities and marginalizations from a joint distribution, as shown above.

Exam Guidance Summary

This lecture covers first order logic and its inference methods. The following points are the most likely to appear in the examination.

Propositional logic limits: Know why propositional logic cannot express "all humans are mortal" compactly — it needs a separate fact per individual. FOL fixes this with objects, predicates, functions, and quantifiers.
FOL syntax: Be able to identify constants, predicates, functions, variables, and quantifiers in a formula. Distinguish atomic sentences from complex sentences.
Quantifiers: Universal (∀) means "for all" with implication. Existential (∃) means "there exists" with conjunction. Never swap them — ∀x (P(x) → Q(x)) is not the same as ∃x (P(x) ∧ Q(x)).
English to FOL: Translate "every," "some," "no," "only if," and "either...or" into the correct quantifier patterns. This is a recurring exam question.
Quantifier duality: ∀x ¬P(x) ≡ ¬∃x P(x) and ∃x ¬P(x) ≡ ¬∀x P(x). You may be asked to apply De Morgan's laws for quantifiers.
Instantiation: Universal instantiation substitutes a ground term. Existential instantiation introduces a new Skolem constant. Know the restrictions (UI works on any term; EI needs a fresh constant).
Reduction to propositional inference: With only ground (instantiated) sentences, FOL inference becomes propositional inference. This is the basis of DPLL and WalkSAT on the propositionalized KB.
Forward chaining: Bottom-up, starts from facts, derives all reachable conclusions. Sound and complete for definite clauses. Best for open-ended queries.
Backward chaining: Top-down, starts from the goal, decomposes into sub-goals. Focused and efficient for close-ended (yes/no) queries. Watch for infinite recursion.
Forward vs. backward: Know when to use each. Open-ended → forward. Close-ended → backward.
Practice problem: The Jack-and-Curiosity exercise (English → FOL → chaining) is directly examinable. Practice the full conversion and the chaining trace.
Probabilistic reasoning: Understand why probability is needed (uncertainty, non-monotonic reasoning). Be able to compute conditional probability and marginalization from a joint distribution.

Key Industry Applications

First order logic and its inference methods are not just academic — they power real systems across industry.

Expert systems: Early commercial systems like XCON/R1 used forward chaining to configure computer orders from a rule base. Modern rule engines (Drools, CLIPS, Jess) use the same forward-chaining pattern for business logic, fraud detection, and loan approval.
Logic programming: Prolog — built on backward chaining — is used in natural language processing, theorem proving, and rapid prototyping of symbolic AI. Its depth-first backward chaining is exactly the algorithm covered in Section 11.9.
Knowledge graphs: Query languages like SPARQL and Datalog (a subset of FOL) power Google's Knowledge Graph and Wikidata. Forward chaining (materialization) pre-computes inferred facts for fast retrieval.
Automated theorem proving: Tools like Vampire, E, and Prover9 use resolution (the propositional-reduction technique from Section 11.7) to verify hardware and software correctness, and to prove mathematical theorems.
Semantic web: OWL (Web Ontology Language) and RDFS use description logic — a decidable fragment of FOL — to reason about web resources, enabling intelligent search and data integration.
Database systems: Datalog and recursive SQL queries apply forward chaining to compute transitive closures (e.g., "find all parts reachable from a component").
Diagnostic systems: Medical diagnosis (e.g., MYCIN's successors) and fault diagnosis in manufacturing use backward chaining to explain symptoms by tracing back to likely causes.
Probabilistic reasoning: The transition to probability (Section 11.11) underpins spam filters, recommendation systems, medical risk scoring, and self-driving car perception — all of which reason under uncertainty.

ACI Lecture 11 notes · First Order Logic, Forward Chaining, and Backward Chaining

Artificial Computational Intelligence· postgraduate· 2026-07-19

Sections Breakdown

111.1 Propositional Logic: Strengths and Limitations

Why propositional logic is declarative and compositional but cannot express relations or quantification.

211.2 First Order Logic (Predicate Logic)

Objects, relations, functions, and quantifiers; atomic and complex sentences; truth in a model.

311.3 Quantifiers

Universal and existential quantifiers, the connectives they pair with, and worked examples.

411.4 Translating English to Predicate Logic

A repeatable recipe for converting English sentences into predicate logic formulas.

511.5 Properties of Quantifiers

Commutativity, non-commutativity of mixed quantifiers, negation, and duality.

611.6 Instantiation

Universal instantiation substitutes ground terms; existential instantiation introduces Skolem constants.

711.7 Reduction to Propositional Inference

How FOL can be propositionalized by enumerating ground instances, and when this is practical.

811.8 Forward Chaining

Bottom-up inference from facts, the West-is-criminal worked example, and properties.

911.9 Backward Chaining

Top-down goal-driven inference, the same worked example backward, and forward vs backward comparison.

1011.10 Practice Exercise: Jack and Curiosity

Full English-to-FOL translation and chaining solution for the Jack and Curiosity problem.

1111.11 Introduction to Probabilistic Reasoning

Why probability is needed for uncertainty and non-monotonic reasoning; axioms, conditional probability, joint distributions.

12Exam Guidance Summary

The most examinable points from the lecture.

13Key Industry Applications

Real-world systems powered by first order logic and its inference methods.

Postgraduate students in Artificial Computational Intelligence

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Propositional Logic: Strengths and Limitations

Must-know: Propositional logic reasons about fixed true/false facts using AND, OR, NOT, and implication. It is declarative and compositional, but it cannot express relations between objects or quantify over collections — that needs first order logic.

$P_{1, 2} \to (B_{1, 1} \lor B_{1, 3} \lor B_{2, 2})$

⚠️ Top pitfall: Thinking propositional logic can express "all" or "some". It cannot — you must write a separate sentence for every object and every square pair.

Self-check: Why does the wumpus world need dozens of separate rules in propositional logic?

Connects to: First Order Logic (Predicate Logic), Quantifiers.

First Order Logic (Predicate Logic)

Must-know: FOL adds objects, relations (predicates), functions, and quantifiers on top of propositional logic. Atomic sentences are Predicate(term, ...); complex sentences combine them with connectives.

$B r o t h er (K in g J o hn, R i c ha r d) and \forall x (K in g (x) \to P er so n (x))$

⚠️ Top pitfall: Confusing predicates (return true/false) with functions (return an object). LeftLeg(x) names a leg; Brother(x, y) states a relation.

Self-check: Is Person(x) a relation between two items? Why or why not?

Connects to: Quantifiers, Atomic and Complex Sentences.

Quantifiers

Must-know: Universal ∀ pairs with implication (→) and expands to AND. Existential ∃ pairs with conjunction (∧) and expands to OR. Swapping the connective is the single most common mistake.

$\forall x (P (x) \to Q (x)) \exists x (P (x) \land Q (x))$

⚠️ Top pitfall: Writing ∀x (P(x) ∧ Q(x)) claims everything is both P and Q. Writing ∃x (P(x) → Q(x)) is true whenever any object fails P.

Self-check: Why does "all kings are persons" use → but "some boy is intelligent" uses ∧?

Connects to: Properties of Quantifiers, Translating English to Predicate Logic.

Translating English to Predicate Logic

Must-know: Follow the recipe: find the verb (predicate), identify arguments, pick quantifiers from keywords ("all" → ∀, "some" → ∃), choose connectives (∀ with →, ∃ with ∧), write quantifiers in order.

$\exists S \forall P \exists C S e l l s (S, P, C)$

⚠️ Top pitfall: Getting quantifier order wrong. ∃S ∀P means one seller sells everything; ∀P ∃S means each product has some seller (possibly different).

Self-check: Translate "John teaches ML to all students" — which quantifier is existential, which universal?

Connects to: Quantifiers, Properties of Quantifiers.

Properties of Quantifiers

Must-know: Same-type quantifiers commute. Mixed quantifiers do not: ∃x ∀y Loves(x, y) (one person loves all) is much stronger than ∀y ∃x Loves(x, y) (everyone loved by someone). Negation flips ∀ ↔ ∃.

$\neg\forall x P (x) \equiv \exists x \neg P (x) \neg\exists x P (x) \equiv \forall x \neg P (x)$

⚠️ Top pitfall: Believing ∃x ∀y implies ∀y ∃x but not vice versa. Also confusing negation (flips quantifier) with duality (same fact, double negation).

Self-check: Is "nobody is unloved" the negation or the dual of "everyone is loved"?

Connects to: Quantifiers, Translating English to Predicate Logic.

Instantiation

Must-know: Universal instantiation substitutes any ground term into a ∀ sentence (repeatable). Existential instantiation introduces one fresh Skolem constant for an ∃ sentence (once only).

$\frac{\forall x α}{SUBST ({ x / G } , α )} \frac{\exists x α}{SUBST ({ x / k } , α )} (k fresh)$

⚠️ Top pitfall: Reusing a Skolem constant across different existential claims, or applying EI many times. EI is applied once per sentence.

Self-check: From ∀x (King(x) → Evil(x)) and King(John), what can you derive by UI?

Connects to: Reduction to Propositional Inference, Forward Chaining.

Reduction to Propositional Inference

Must-know: FOL can be reduced to propositional logic by instantiating all quantifiers over the domain, then treating ground atoms as propositional symbols. Impractical for large or infinite domains.

$\forall x (K in g (x) \to P er so n (x)) \Rightarrow (K in g (J o hn) \to P er so n (J o hn)) \land (K in g (R i c ha r d) \to P er so n (R i c ha r d))$

⚠️ Top pitfall: Assuming propositionalization is always finite. With function symbols (e.g., Father), the set of ground terms is infinite.

Self-check: Why is full enumeration impractical when the domain has millions of objects?

Connects to: Instantiation, Forward Chaining.

Forward Chaining

Must-know: Forward chaining is bottom-up: start from facts, fire rules whose premises match, add conclusions, repeat. Sound and complete for definite clauses. Best for open-ended queries.

$A (x) \land B (x) \to C (x) fires when A (t), B (t) known, deriving C (t)$

⚠️ Top pitfall: Using forward chaining for a yes/no query — it generates many irrelevant facts. Use backward chaining instead.

Self-check: In the West-is-criminal example, which rule fires in round 1 to derive Weapon(M1)?

Connects to: Backward Chaining, Reduction to Propositional Inference.

Backward Chaining

Must-know: Backward chaining is top-down: start from the goal, replace it with the LHS of a matching rule, resolve sub-goals recursively. Focused and efficient for close-ended queries.

$C r imina l (W es t) \leftarrow A m er i c an (W es t) \land W e a p o n (Y) \land S e l l s (W es t, Y, Z) \land H os t i l e (Z)$

⚠️ Top pitfall: Infinite recursion when a rule's head matches its own body (circular rules). Prolog adds depth limits; pure backward chaining may not terminate.

Self-check: Why does backward chaining on "Is West a criminal?" avoid generating irrelevant facts?

Connects to: Forward Chaining, Practice Exercise: Jack and Curiosity.

Practice Exercise: Jack and Curiosity

Must-know: Translate English to FOL, then chain. Jack owns a dog → animal lover → cannot kill animals. Since Jack did not kill Tuna, by disjunctive syllogism Curiosity did.

$K i l l s (J a c k, T u na) \lor K i l l s (C u r i os i t y, T u na), \neg K i l l s (J a c k, T u na) ⊢ K i l l s (C u r i os i t y, T u na)$

⚠️ Top pitfall: Forgetting that "every dog owner is an animal lover" makes Jack an animal lover, which blocks him from killing Tuna.

Self-check: Why can we conclude Jack did NOT kill Tuna?

Connects to: Translating English to Predicate Logic, Backward Chaining.

Introduction to Probabilistic Reasoning

Must-know: Probability handles uncertainty and non-monotonic reasoning where logic (monotonic) cannot. Degrees of belief live in [0, 1]; new evidence updates them.

$P (A ∣ B) = \frac{P ( A \land B )}{P ( B )} P (A \land B) = P (A ∣ B) P (B)$

⚠️ Top pitfall: Treating probability as just "true/false with noise". It is a different formalism — degrees of belief, not monotonic proof.

Self-check: From the toothache table, why does P(Cavity | Toothache) rise from 0.20 to 0.60?

Connects to: Forward Chaining, Backward Chaining.

Previous LectureLecture 10 · Inference Techniques in Propositional Logic

Next LectureLecture 12 · Bayesian Networks

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.