Knowledge Representation Using Logics

Knowledge Representation Using Logics

The first half of the course dealt with problem solving — search techniques, informed and uninformed search, evolution and genetic algorithms, game playing and adversarial search. This module shifts gears into the computational side: how an agent stores knowledge, how it derives new knowledge from what it already has, how multiple agents work together, and how probability fits in. The plan for the remaining classes: logic for today and the next class, then multi-agent systems, then probability and reasoning over time, and the course closes with AI ethics in the final class. Today and next class form one combined agenda: we look at a sample agent and why logic is needed, then inference using truth tables, inference using resolution by contradiction, and predicate logic in the next class.

9.1 Knowledge-Based Agents

9.1.1 What an Agent Knows and How It Knows It

So far in the course, nothing was said about what knowledge an agent has, how that knowledge is stored, or how it is inferred. The search algorithms assumed a tree or a game state exists in memory, and that was the end of it. A knowledge-based agent works differently: it solves problems by representing knowledge in a state space, reasoning about the solution, and revising what it knows as it goes.

The central component of such an agent is its knowledge base (KB for short). The central question of this module is knowledge representation: how an agent stores what it knows in a form it can later reason over.

How does this differ from the search agents of the earlier classes? A problem-solving agent knows what actions are available and what each action does, but it knows no general facts: an 8-puzzle agent does not know that two tiles cannot occupy the same square. That knowledge lives in the designer, not in the agent. A knowledge-based agent, by contrast, stores general rules and facts as sentences, and can combine and recombine them to serve purposes it was never explicitly programmed for — exactly what a human does when they reason from what they know.

Real-world: today's modern agent loops — the kind that carry a context, update a memory, and reason over it — still rest on this same rudimentary core: storing knowledge and inferring from stored knowledge. What we study here is the very basic foundation of how knowledge systems work. The names change (context windows, memory banks), the loop does not: keep a body of knowledge, add to it, ask it questions, act on the answers.

9.1.2 The Knowledge Base: Tell, Ask, and Update

Every time a knowledge-based agent is invoked, it does one of three things: it can tell, it can ask, or it can update.

The same interface, from a database point of view: if you have worked with databases, this is similar to CRUD operations — create, read, update, delete. The tell/ask/update cycle is the logical cousin of that pattern. In your databases course the operations are about records; here they are about sentences of knowledge.

9.1.3 Knowledge-Based Agents vs Learning Agents

How is this different from a learning agent? At the end of the day, every learning agent — whatever loop or architecture it uses — fundamentally has to store some data, and from that stored data it has to infer something. If you agree with that, then this is exactly what we are looking at: how knowledge is stored and how it is inferred. Today's loop-based agents and knowledge systems are way, way ahead of this, but viewed from the right angle, all of them rely on these fundamentals.

The lesson: the learning-versus-knowledge divide is smaller than it looks. A learning agent is, at its core, a knowledge-based agent whose sentences (or parameters) were learned from data instead of being written by a designer. The lecture's point is that the storage-and-inference fundamentals are common to both.

9.1.4 Prolog: A Language for Logic

You can build knowledge-based systems in higher-level languages like Python or Java, but it is not comfortable: you would spend most of your time writing the inference machinery yourself. There is a separate language built exactly for this: Prolog.

9.2 The Wumpus World

9.2.1 The Setup: Grid, Pit, Wumpus, and Gold

The problem used to understand logic in this class is a small game: a 4 × 4 grid with a few elements in it. There is a start cell — this is where the agent is. There is a pit — actually there can be several pits, placed anywhere. There is a wumpus — the wumpus is like a devil — sitting somewhere. And there is gold. The aim: the agent must reach the gold and pick it up. The agent starts at cell (1,1), facing right. The grid is the setup for every example that follows, and the setup varies from game to game: in one configuration the pits are in these locations, the wumpus there, the gold here; in another configuration everything is somewhere else.

Three rules define the danger:

• If the agent enters a pit cell, it falls and dies.
• If it enters the wumpus cell, the wumpus eats it — the agent dies.
• The gold: the agent wants to grab it, and grabbing it (then climbing out) is the win condition.

The pit, the wumpus, and the gold are static — they do not move while the agent moves. This is not Pacman; the enemies do not play back. Only the agent navigates, from the start, and it must find its way without getting killed.

The performance measure, using the PEAS ideas from the earlier classes:

• +1000 if the agent gets the gold.
• −1000 if it dies — meaning it falls in a pit or is eaten by the wumpus.
• −1 (or +1, your choice) for each action taken, because walking each cell costs energy.
• −10 for using the arrow — but the arrow variant is not covered in this discussion.

The arrow concept exists in the game: the agent has only one arrow, and it can shoot it; if the wumpus is in the next room the wumpus gets killed, but if the wumpus is not there the arrow just hits the wall or falls into a pit and is wasted. That arrow part is a variant we do not discuss further.

9.2.2 Percepts and Sensors

Wherever there is a pit, the four cells around it — above, below, left, and right — have breeze. There is a hole dug out of the ground, so in the adjacent cells you feel the breeze. Wherever the wumpus is, the four cells around it — above, below, left, and right — have stench, a bad smell. Gold glitters, but only in its own cell — the shine does not radiate to other rooms. Two more percepts: bump, when the agent walks onto a wall and cannot go further; and scream, when the wumpus is killed — the scream is perceived everywhere in the cave.

There is exactly one wumpus and exactly one gold, but there can be many pits. There are no false alerts in this environment — it is a standard problem, the sensors and percepts are always correct. A smell always means a real wumpus nearby, and a breeze always means a real pit nearby; the agent never has to second-guess its sensors.

9.2.3 Actuators, Rewards, and the Arrow

Since the agent starts at (1,1) facing right, it cannot go left at the start; from (1,1) it can only move right or up. That one constraint matters for the first deductions: the two cells the agent can reach are (2,1) to the right and (1,2) above — and those are exactly the two cells the OK percept will first rule out as dangerous.

9.2.4 Environment Characteristics

Classifying the Wumpus World with the properties from the early classes:

The sequential and partially observable entries are the two that make this problem interesting: because the world is sequential, today's moves decide tomorrow's percepts, and because it is partially observable, the agent must infer the hidden board from the local percepts it collects along the way.

9.2.5 The Symbol Legend

All the diagrams in the rest of the module use a fixed set of symbols — the legend that lets you read a board diagram at a glance:

Pictures that also appear on the diagrams: P? means "a pit is possible here" (one of the suspect cells) and W! means "the wumpus is definitely here" (deduced, not perceived).

To read such a diagram: picture the board as a grid of squares, rows numbered 1 to 4 from bottom to top and columns numbered 1 to 4 from left to right, with the start square (1,1) in the bottom-left corner. In each square the diagram marks what the agent knows — a visited square carries its symbol (A, OK, V, B, S, G), an inferred square carries P? or W! — and the unmarked squares are simply unknown. The story of every diagram is the same: a spread of known symbols in the visited region, question marks where inference is still undecided, and a clear safe corridor toward the gold.

9.2.6 General Rules for Pits and Wumpus

Starting from the given knowledge of the game, we write generic statements that hold for any cell $(x,y)$. The first statement: if there is a pit in cell $(x,y)$, then you will feel breeze in the cell to its right, the cell to its left, the cell above it, and the cell below it. Written as logic:

Now comes the interesting direction. If I see breeze at $(x,y)$, where could the pit be? It could be to the right, to the left, above, or below — any one of the four adjacent cells. I cannot put an "and" here, because I do not know which one it is; I must put an "or":

$$\text{Breeze}(x,y)\to (\text{Pit}(x+1,y)\vee \text{Pit}(x-1,y)\vee \text{Pit}(x,y+1)\vee \text{Pit}(x,y-1))$$

And the same for stench: if I see stench at $(x,y)$, the wumpus is in at least one of the four adjacent cells:

$$\text{Stench}(x,y)\to (\text{Wumpus}(x+1,y)\vee \text{Wumpus}(x-1,y)\vee \text{Wumpus}(x,y+1)\vee \text{Wumpus}(x,y-1))$$

All of these facts can be negated as well. If I do not find a pit, there is no breeze in its adjacent cells; if I do not find a wumpus, the four sides do not have stench. So:

$$\neg \text{Breeze}(x,y)\to \neg \text{Pit}(x+1,y)\wedge \neg \text{Pit}(x-1,y)\wedge \neg \text{Pit}(x,y+1)\wedge \neg \text{Pit}(x,y-1)$$

$$\neg \text{Stench}(x,y)\to \neg \text{Wumpus}(x+1,y)\wedge \neg \text{Wumpus}(x-1,y)\wedge \neg \text{Wumpus}(x,y+1)\wedge \neg \text{Wumpus}(x,y-1)$$

No stench at $(x,y)$ means there is no wumpus in any adjacent cell, and no breeze at $(x,y)$ means there is no pit in any adjacent cell. This absence direction is what makes an OK percept so valuable: one cell with no percept clears all of its neighbors.

9.2.7 Worked Reasoning Example 1: The Numbered Grid

The first configuration has numbered cells, so every deduction can be followed precisely.

The agent keeps all of this in memory as a percept vector — one entry per visited cell: at (1,1) it was OK, at (2,1) it felt breeze, at (1,2) it felt stench. That vector is its knowledge base, and it can consult it on every move. Notice what made the (2,2) deduction possible: the agent remembered what it did not perceive in earlier cells — the absence of stench at (2,1) and the absence of breeze at (1,2). A knowledge base that stored only positive percepts could never have done this.

9.2.8 Worked Reasoning Example 2: The Lean Grid

The second problem is the same Wumpus World but with no cell numbers — a leaner diagram, the kind you should be able to read directly from the symbols. The reasoning is identical, so we track it in relative terms: up, right, below, above.

Every step of this walkthrough is the same pattern: "when I was in this cell I did not perceive smell, so the wumpus is not there; when I was in that cell I did not feel breeze, so the pit is not there; so the pit is here, the wumpus is there." That is what the agent does at a very low level, and that is the whole heart of logic.

9.2.9 Student Questions and Answers

A first cluster of questions is about the game itself — where things can be placed and what the agent senses.

The next cluster is about the key deduction of the first walkthrough — why cell (2,2) is safe, and how far the reasoning reaches.

Then the questions about the agent's memory and knowledge between moves.

The questions below are about the edges of the rules — walls, dead wumpus, sensor trust, and the overall intent of the problem.

9.2.10 Why This Is Logic, Not Probability

That question came up twice and the answer matters. The agent does not need to visit a cell to confirm it has no pit, because the problem is built so that breeze or stench in an adjacent cell lets you conclude it. Probability-based reasoning is a different type of system that comes later in the course — this module is pure logic and seen evidence. The word "guaranteed" is doing real work here: in logic, a correct deduction from true premises is certain, not likely. A probabilistic system would say "there is an 80 percent chance of a pit here"; the logical agent says "there is definitely no pit here, because I perceived no breeze in a cell that would have shown one."

9.3 What Is Logic?

9.3.1 The Definition of Logic

Logic, in this course, means: combine the current percept with the existing knowledge base, and do logical reasoning to identify state information. Reasoning is conducted or assessed according to the available knowledge about the domain. The Wumpus World showed exactly this: the only information given was "you are in cell (1,1) and you are OK" — that was all. But from that alone the agent inferred: if I am OK here, I am safe, so there is no wumpus and no pit here, and no gold here; and near me — on top and to the right — there is no pit or wumpus either. All of that is inferencing. Reasoning is assessed according to available knowledge, and from that knowledge you can create more knowledge and new percepts.

Logics are formal languages for representing information such that conclusions can be drawn from it. The phrase "formal languages" is the key: like programming languages, they are precise — every symbol, every combination rule, every meaning is fixed in advance. That precision is what makes certain inference possible. Human language is too messy for this job; a formal logic is not.

9.3.2 Syntax and Semantics

Every sentence or premise is expressed according to the syntax of the representation language — the set of rules that decides which strings count as sentences at all.

9.3.3 Models

9.3.4 Entailment

Entailment is written with the symbol $\models$. "$X$ entails $Y$" — $X\models Y$ — means: in every model where $X$ is true, $Y$ is also true. In set terms:

$$X\models Y⟺M(X)\subseteq M(Y)$$

Every model of $X$ is also a model of $Y$ — the set of worlds where $X$ holds is a subset of the worlds where $Y$ holds. Note the direction: if $X\models Y$, then $X$ is the stronger statement — it rules out more possible worlds.

And note the vocabulary bridge: what discrete mathematics calls inference, AI calls entailment — it is the same thing, just the AI term for it.

9.3.5 Propositions: What Counts and What Does Not

Propositional logic is Boolean logic. A sentence qualifies as a proposition if at the end you can say whether it is true or false — it may not always be true; a false statement is perfectly acceptable as a proposition. Assessability is everything.

• "The sun rises in the east and sets in the west" — a proposition; at the end it is true or false.
• "1 + 1 = 2" — a proposition.
• "1 + 2 = 5" — a proposition! Its validity is false, but we can assess it — that is all that matters.
• "B is a vowel" — also a proposition; its truth value is false, and that is okay.

But these are not propositions: "Will you go to office today?" — there is no true or false value, you cannot correctly answer; "You are beautiful!" — exclamatory; and instructions and warnings, like "Read this carefully" — you cannot validate an instruction. Question marks, exclamation marks, instructions — those are not logic statements.

A mixed case: "$x-y=6$" is not a proposition when $x$ and $y$ are unknown — there is no way to assess it. But if the values of $x$ and $y$ are given, then it becomes assessable, and then it is a proposition. The same statement becomes a proposition once its variables are fixed.

From the standard discrete mathematics book come a couple of negation exercises: "Michael's PC runs Linux" is a proposition, and its negation is "Michael's PC does not run Linux." "Vandana's smartphone has 32 GB" — express it in simple English and then negate it, same pattern: "Vandana's smartphone does not have 32 GB." The negation of a proposition is always another proposition: whatever the original claims, the negation claims the opposite, and exactly one of the two is true.

9.3.6 Is This Really Intelligence?

9.4 Propositional Logic: Connectives and Truth Tables

9.4.1 The Five Connectives

Propositional logic defines the language of allowable sentences. A sentence is a single propositional statement or a symbol, and complex sentences are constructed by joining them with logic connectives. For the Wumpus World, a proposition such as "the wumpus is in (1,3)" is written as a symbol, usually upper case, such as $W_{1,3}$ — the full line is a proposition, and the symbol indicates that proposition. You can use $P$, $Q$, $R$, $S$, and so on. The names are arbitrary but chosen to be mnemonic: $W_{1,3}$ stands for "the wumpus is in (1,3)", $P_{3,1}$ for "there is a pit in (3,1)". Note that $W_{1,3}$ is a single atomic symbol — the $W$, $1$, and $3$ are not meaningful parts you can separate.

9.4.2 Truth Tables for Each Connective

A truth table is a tabular compilation of the possible truth values of a sentence over its symbols. Truth tables are used most of the time to verify entailment and similar claims — you may have seen them in earlier courses.

Negation: if the premise is true, the negation is false; if the premise is false, the negation is true.

Conjunction: $P\wedge Q$ is true only when both $P$ and $Q$ are true; every other combination is false.

Disjunction: $P\vee Q$ is true as long as at least one of them is true; the only false case is when both are false.

Implication: $P\to Q$ is false only in the single case where the premise is true and the conclusion is false; all other cases are true.

Double implication: $P\leftrightarrow Q$ is the same as writing $(P\to Q)$ and $(Q\to P)$ together — both directions. It is true when both are true and when both are false; in the other two cases it is false.

For $n$ symbols there are $2^n$ combinations, and there are tricks for filling the columns: for the rightmost column alternate T F T F T F…; the next column TT FF TT FF…; the next TTTT FFFF… and so on, and the table is done. The trick works because the columns are independent: the last column is the fastest-changing bit, and each column to its left changes half as often.

A note on "or": the $\vee$ used here is the inclusive or — true when one or both parts are true. A different connective, XOR (exclusive or), yields false when both disjuncts are true. XOR also exists and is part of the same family; it is exactly the gate used when two switches must differ to pass current.

Real-world: all of these truth tables are implemented in computers using gates — AND, OR, XOR, NOR, NOT. The gates are the hardware versions of the connectives. You may have met the same material in discrete mathematics, or in computer organization courses; these days it even shows up in school curricula.

9.4.3 The Tricky Row: Why Implication with a False Premise Is True

The one row of the implication table that students find strange is "false premise → anything". Example: "If I am elected, then I will lower taxes." If I am not elected, what can you say about lowering the taxes? You are not expecting anything — and the statement as a whole is still true. Voters would expect the politician to lower taxes if elected; also, if the politician is not elected, voters will not have any expectation — although the person may still have enough influence to cause those in power to lower taxes, you are not worried about that. It is only when the politician is elected and still does not reduce the tax — premise true, consequent false — that the implication becomes false. If the premise itself did not happen, there is no way to verify the implication, so it stays true.

The cleanest way to hold this row in your head: "$P\to Q$" says "If $P$ is true, then I am claiming that $Q$ is true; otherwise I am making no claim." An implication makes a promise only about the case where its premise holds. Where the premise does not hold, there is nothing to check — so the sentence cannot be called false.

9.4.4 Precedence and Ambiguous Sentences

Some sentences are ambiguous if the parentheses are missing. Consider a line with negation and conjunction: should you first do the negation of $A$, and then AND that result with $B$? Or should you first do the AND and then negate the whole line? Without precedence rules or parentheses, you do not know what to do first — such a line is ambiguous:

$$\neg A\wedge B\text{vs}\neg (A\wedge B)$$

These two are different sentences. The first negates $A$, then ANDs with $B$; the second performs the AND first, then negates the whole answer. The resolution is done using precedence — knowing which connective binds first resolves the ambiguity.

The standard order, from highest to lowest precedence:

$$\neg >\wedge >\vee >\to >\leftrightarrow$$

The negation $\neg$ binds most tightly: in the sentence $\neg A\wedge B$, the $\neg$ attaches to $A$ first, giving $(\neg A)\wedge B$, not $\neg (A\wedge B)$. The analogy with arithmetic is exact: $-2+4$ means $(-2)+4=2$, not $-(2+4)=-6$. When in doubt, parentheses remove all doubt — use them freely, and the sentence becomes unambiguous.

9.4.5 Connectives as Hardware Gates

The truth tables of the connectives are constant — you cannot change them; $P\to Q$, and, or, and the biconditional tables are always the same. In a computer these are the logic gates: AND gates, OR gates, XOR gates, NOR gates, NOT gates.

9.5 Wumpus World as a Propositional Knowledge Base

9.5.1 Symbols for Pits, Wumpus, Breeze, and Stench

Now the Wumpus World knowledge is translated into propositional logic. For each location $(x,y)$:

• $P(x,y)$ is true if there is a pit in $(x,y)$.
• $W(x,y)$ is true if there is a wumpus in $(x,y)$.
• $B(x,y)$ is true if the agent perceives a breeze in $(x,y)$.
• $S(x,y)$ is true if the agent perceives stench in $(x,y)$.

That is all — the plain English of the problem is now a set of symbolic statements. Every percept the agent can record and every hidden fact it cares about has one symbol. From here on, "the agent feels breeze at (2,1)" and "the formula $B_{2,1}$ is in the knowledge base" mean the same thing.

9.5.2 The Knowledge Base Sentences

Given a particular configuration, the knowledge base contains these sentences, labeled R1 through R5 — R stands for rule:

$$\begin{array}{rcl}{R}_1& :& \neg P_{1,1}\\ R_2& :& B_{1,1}\leftrightarrow (P_{1,2}\vee P_{2,1})\\ R_3& :& B_{2,1}\leftrightarrow (P_{1,1}\vee P_{2,2}\vee P_{3,1})\\ R_4& :& \neg B_{1,1}\\ R_5& :& B_{2,1}\end{array}$$

In plain English: R1 says there is no pit in (1,1). R2 says the agent perceives breeze at (1,1) if and only if there is a pit at (1,2) or a pit at (2,1) — those are the only cells adjacent to (1,1). R3 says breeze at (2,1) if and only if a pit is at (1,1), (2,2), or (3,1) — the cells adjacent to (2,1). R4 says no breeze was perceived at (1,1). R5 says breeze was perceived at (2,1).

Notice the two kinds of sentences. R2 and R3 are general rules — they hold in every Wumpus World, because they are just the adjacency fact of section 9.2 written with a biconditional: a square is breezy if a neighbor has a pit, and a square is breezy only if a neighbor has a pit. R1, R4, and R5 are percepts — facts about this particular world, gathered by the agent's sensors.

9.5.3 Literals, Facts, and Rules

Each atom inside these sentences — for example $P_{1,1}$, $B_{1,1}$, $P_{3,1}$, $P_{2,2}$ — is called a literal. The negation symbol is an operator, not a literal: a literal is either an atomic sentence (a positive literal, like $P_{1,1}$) or a negated atomic sentence (a negative literal, like $\neg P_{1,1}$). The symbol $P_{1,1}$ itself is one literal whether it appears bare or with a $\neg$ in front of it.

In the knowledge base above, that makes exactly seven unique literals. This count is not a trivia detail — it decides the size of the truth table in the next section: seven literals means $2^7=128$ models.

9.5.4 The Query: Is There a Pit in (1,2)?

The agent now has to decide: should I move to cell (1,2)? Before moving, it should make sure there is no pit there and no wumpus there. So the query asked of the knowledge base is: is $\neg P_{1,2}$ — "there is no pit in (1,2)" — entailed by the knowledge base? In other words, can this be inferred from the knowledge base; can the agent tell that this is true from what it already knows?

If $\neg P_{1,2}$ turns out to be true, the agent can go to (1,2). If it turns out false — there is a pit — the agent will not go there. And after the query is resolved, the answer becomes knowledge: when the query is solved, it is added as a new sentence in the knowledge base. The agent works exactly like this internally: it is given a body of knowledge, it answers queries, and each resolved query extends the KB.

How do you resolve such a query? There are several techniques: a truth table, theorem proving, resolution, contradiction — and there is an algorithm for it. The next section looks at the truth table approach in full.

9.6 Inference by Truth Table

9.6.1 The Five Steps

The question is: is $\neg P_{1,2}$ entailed from the knowledge base? The truth table approach has five steps.

1. Extract all the literals from the knowledge base. In this KB there are seven: $P_{1,1}$, $B_{1,1}$, $P_{1,2}$, $P_{2,1}$, $P_{2,2}$, $P_{3,1}$, $B_{2,1}$. Do not count the operators.
2. Enumerate all models — all combinations of true/false assignments to the propositional symbols. With two variables, $P$ and $Q$, there are four combinations: both true, both false, one true and one false, the other true and the other false. With $n$ symbols there are $2^n$ combinations — for seven literals, $2^7=128$ rows. Use the filling tricks: T F T F…, TT FF TT FF…, TTTT FFFF…, and the table is done.
3. In all the models, find those where the KB is true — that is, where every sentence R1 through R5 is true.
4. In those models, check the query sentence.
5. If the query is true in all the models where the KB is true, it entails; otherwise it does not.

That is the whole approach — it takes many pages in a logic textbook to explain, but the essence is these five steps. The algorithm is sound (it directly implements the definition of entailment, so it can never announce a false conclusion) and complete (it always terminates and always finds the answer, because there are only finitely many models to inspect).

9.6.2 Step by Step on the Real Knowledge Base

9.6.3 The Verdict on the Query

9.6.4 Other Queries on the Same Table

The same table answers further queries.

The same table also illustrates how the whole method generalizes: the algorithm walks the models one by one, keeps only the rows where the KB is true, and checks the query in those rows only. That recursive enumeration — assigning symbols one at a time and pruning branches where the KB is already false — is exactly how a program such as the classic TT-ENTAILS procedure implements these five steps.

9.6.5 Complexity and Practicality

For this one entailment, an entire table of 128 rows had to be built, every rule column computed, the KB column ANDed, and then the query checked. Is it even practical? For a computer, 128 rows is nothing — it scales fine. In an exam, it is not scalable. But what about a million records? The time complexity is $2^n$ — big O of $2^n$ — and that is bad, that is worse than fine. Every time you add one more literal to the knowledge base, the table doubles in size. (In fact, propositional entailment is co-NP-complete, so every known inference algorithm has worst-case exponential time — the truth table is not uniquely slow, just honestly slow.)

Space complexity is still okay: you hold the table in memory — one row at a time, if you enumerate carefully, the memory used stays linear in the number of symbols, even though the time does not.

9.7 Logical Equivalences: Theorems for Faster Inference

9.7.1 Logical Equivalence and the Laws

The truth table approach is complete but exponential. Theorem proving is the alternative: apply clever rules, and deduce the same answer in four lines instead of 128 rows. The first concept needed is logical equivalence: alpha logically implies beta — written $\alpha \equiv \beta$ — when the two sentences have the same truth value in every model. Equivalences play the same role in logic that arithmetic identities ($2+3=3+2$) play in ordinary math: they let you rewrite a sentence into a friendlier shape without changing its meaning. There are many equivalence laws, all from discrete mathematics:

$$\alpha \wedge \beta \equiv \beta \wedge \alpha ,\alpha \vee \beta \equiv \beta \vee \alpha$$

• Commutativity: $\alpha \wedge \beta$ is the same as $\beta \wedge \alpha$; $\alpha \vee \beta$ is the same as $\beta \vee \alpha$ — the order of the two sentences does not matter.
• Associativity: the same regrouping for conjunctions and disjunctions — $(\alpha \wedge \beta )\wedge \gamma \equiv \alpha \wedge (\beta \wedge \gamma )$, and the same shape for $\vee$. When everything is an and, the grouping is irrelevant.

$$\neg \neg \alpha \equiv \alpha$$

• Double negation: the negation of the negation of alpha gives alpha — the two negations cut each other and only alpha remains. "It is not the case that the wumpus is not in (1,3)" is just "the wumpus is in (1,3)".
• Contrapositive: $\alpha \to \beta$ is equivalent to $\neg \beta \to \neg \alpha$. If being a wumpus cell implies being smelly, then not smelling implies not being the wumpus cell.

$$\alpha \leftrightarrow \beta \equiv (\alpha \to \beta )\wedge (\beta \to \alpha )$$

• Biconditional: $\alpha \leftrightarrow \beta$ is equivalent to $(\alpha \to \beta )\wedge (\beta \to \alpha )$ — both directions together. This is the elimination rule that will start the five-step proof below.
• Implication elimination: $\alpha \to \beta \equiv \neg \alpha \vee \beta$ — "if the premise holds, the conclusion follows" is the same as "either the premise fails or the conclusion holds". This is exactly the single-false-row reading of the implication table from section 9.4.
• De Morgan's laws: $\neg (\alpha \wedge \beta )\equiv (\neg \alpha \vee \neg \beta )$ and $\neg (\alpha \vee \beta )\equiv (\neg \alpha \wedge \neg \beta )$ — negation distributes over and/or by flipping the connective: "not (A and B)" means "not A or not B".
• Idempotence law — $\alpha \wedge \alpha \equiv \alpha$ and $\alpha \vee \alpha \equiv \alpha$ — repeating a sentence adds nothing.
• Distributivity and more — $\wedge$ distributes over $\vee$ and $\vee$ distributes over $\wedge$, exactly like multiplication distributes over addition; the textbook table includes domination laws and others besides.

Using these laws, you can quickly arrive at the same entailment conclusion. The practical skill is recognizing which law applies where — the same way you decide which arithmetic identity makes an expression simpler.

9.7.2 Proving the Laws with Truth Tables

Every equivalence law can itself be proved with a truth table — the very method that was just declared too slow is the perfect tool for proving the shortcuts. Take alpha and beta; write the possible truth values; compute the column for $\alpha \wedge \beta$ and the column for $\beta \wedge \alpha$ — the two columns are identical, and that is why the commutativity law exists.

The homework tradition when logic is taught: take the left-hand side of each law in one column of a truth table and the right-hand side in another column; if the two columns are exactly the same, the law is proved.

Go practice these laws the same way: solve an entailment with a truth table first, then verify the same conclusion by applying the laws. Kenneth Rosen's Discrete Mathematics and Its Applications, shown in class, is the reference for the full list of laws, with many exercises.

9.7.3 Inference Rules for the Next Class

Before the next class, read up on the basic inference rules — especially modus ponens, modus tollens, and and-elimination.

With those, the same entailment that took a full truth table can be deduced in about five statements, applying one rule after another:

There is no fixed order of application: one person may reach the result in ten steps by starting with biconditional elimination then contraposition; someone else who starts with De Morgan may take a bigger route. The difficulty is proficiency — knowing which law to apply where, so that you are quicker and do not go in circles. For that reason, even further techniques exist — conjunctive normal form (CNF) and resolution — which are also covered next class.

9.7.4 Prolog in Practice

The first webinar (coming Tuesday) teaches some of these laws along with Prolog. In Prolog you put these statements directly — the sentences of the knowledge base — then ask the query, and the program answers whether it entails or not. That is a very powerful language: it is a language for logic programming.

Real-world: Prolog is used in assignments and the webinar; it is pretty simple, you can download it and run it in a command line. What the program does when you press enter is theorem proving: it applies the same inference rules this lecture introduced — modus ponens, modus tollens, and-elimination — to chain from your facts to your query. After the webinar you will also understand the labels: entailment checks, modus ponens, modus tollens, and-elimination — the same ideas in a running system.

Exam Guidance Summary

The exam guidance for the final exam was given at the end of this class. The items below are the ones that matter for how you prepare.

• Syllabus: the open book final exam covers all classes 1 through 16 — not just the post-mid-semester ones. Everything taught in the course is examinable, including this lecture's logic topics.

• Open book logistics: a single PDF combining all sixteen class decks will be uploaded before the final class (around the 15th class), with this year's watermark — that alone is allowed into the exam. Do not print the individual weekly decks, and do not print books — book printouts are outright illegal (copyright); buy the book instead.

• Solved problems: per clear guidelines, no solved problems or past exam questions will be in the final PDF. They are taught in class but not carried into the exam.

• Depth expectation: the slides are the bare minimum — they get you to about 50% of the marks. Going to the textbook gets you to 75%; one more step beyond that gets you to 90%. The slide decks have been intentionally toned down to fit the class modality, so slide-only preparation leaves half the paper on the table.

• Genetic algorithm question (from the mid-semester): implementation was not asked — you only had to list the steps: where selection happens, roulette wheel, next generation, and so on. The same pattern applies to the key: sample keys are not the only correct answer; if you solved it better, you get the credit.

• Truth table inference: the 128-row table is not scalable — in the exam, know the five steps of the truth table approach and the reasoning, not brute-force enumeration.

• Must know before the next class: logical equivalence laws (commutativity, associativity, double negation, contrapositive, biconditional, De Morgan, idempotence) and the inference rules modus ponens, modus tollens, and and-elimination.

• Background reading: Kenneth Rosen's discrete mathematics textbook — chapter 1, sections 1.1 (propositional logic) and 1.2 (applications of propositional logic) are required; sections up to 1.4 are also part of the course from the AI angle. The book has dozens of exercises (about 54 on truth values) — practice converse, inverse, and truth table conversions.

• Revaluation requests: be specific — point out where you deserve more marks and why, challenge the evaluators with arguments. Vague requests like "please give me more marks" are not useful.

• Remaining weightage: after the mid-semester, more than 60% of the weightage is still ahead — quiz 2, assignment 2, and the final exam. The logic topics of this module will carry real marks in that remaining weight.

• Question paper philosophy: the paper will be different from what was discussed in class — that is the interest.

Key Industry Applications

The ideas of this lecture are the foundation of several systems you will meet in industry and in later coursework.

• Prolog — a logic programming language: write sentences with and, or, and implications; ask a query; get the entailment answer. Used in the webinar and assignments; downloadable and runs in a command line. In industry, Prolog and its descendants power rule-based systems in legal reasoning, scheduling, and natural-language parsing, where explicit sentences and queries are more useful than opaque models.

• Modern agent loops — today's knowledge-based systems and loop-based agents with context and memory updates still rest on the tell / ask / update fundamentals of a knowledge base. Large-language-model agents, chatbot memory, and retrieval pipelines are the modern names for the same pattern: store what happened, ask the store for guidance, act.

• CRUD in databases — the tell, ask, update cycle of a knowledge-based agent is the logical equivalent of create, read, update, delete operations on records. The skill of designing a clean knowledge base transfers directly to designing a clean database schema.

• Hardware logic gates — the truth tables of negation, conjunction, disjunction, implication, and biconditional are implemented directly in computers as AND, OR, XOR, NOR, and NOT gates. Every CPU you use executes the connectives of this lecture millions of times per second; compiler writers and hardware engineers reason about these tables constantly.

• The Wumpus World — the classic grid-world problem for demonstrating knowledge representation and logical inference in agents; the design pattern of "general rules + percepts + entailment queries" is the template for modern knowledge-based agent design. Beyond games, the same pattern appears in diagnostic systems (symptoms + rules + what disease is entailed), in circuit fault-finding, and in any domain where certainty of deduction matters more than the average-case guess.