Lecture 09.1: Knowledge-Based Agents and Logic

Early AI research was dominated by two contrasting paradigms: connectionist models (such as early neural networks) and symbolic reasoning. In the 1970s and 1980s, pioneering researchers like Marvin Minsky helped shift the focus of AI toward symbolic reasoning and explicit knowledge representation.

Historical Context & The Evolution of Symbolic AI

• "Perceptrons" (1969): Marvin Minsky and Seymour Papert co-authored Perceptrons, an influential book that mathematically demonstrated the severe limitations of early single-layer neural networks (such as their inability to compute the exclusive-OR function). This critique triggered a critical turning point in AI research, shifting resources away from simple sub-symbolic networks toward explicit, symbolic knowledge representation.
• Introducing "Frames" (1970s): Recognizing that pure formal logic was too rigid and simple networks too unstructured to capture complex human knowledge, Minsky proposed Frames as a model for structured, contextual knowledge.
  • Key Features of Frames: Hierarchical organization of information, slots for object properties, default values, and inheritance capabilities.
  • Legacy: Concepts such as classes, objects, properties, inheritance, and encapsulation in modern programming languages (Smalltalk, C++, Java) directly reflect this legacy.
• Knowledge Representation in the 1980s: Early AI systems by Allen Newell (such as List Processing, Logic Theorist, and General Problem Solver) laid the groundwork for formal reasoning. By the 1980s, Knowledge Representation emerged as an explicit subfield of AI focused on building systems that store, manipulate, and reason over structured facts.

---

Knowledge-Based Agents

A Knowledge-Based Agent is an intelligent AI system that relies on an explicit representation of knowledge to reason, make decisions, and plan actions.

Human intelligence goes beyond pure reflexes or simple stimulus-response reactions. Humans make complex choices using internal mental representations of the world. Knowledge-based agents mirror this approach.

Components of a Knowledge-Based Agent

1. Knowledge Base (KB): A collection of sentences expressed in a formal representation language. Facts, rules, and relationships are written out directly (e.g., $\text{Raining} \Rightarrow \text{Wet}(\text{Ground})$) rather than buried implicitly in millions of numeric weights. The knowledge is visible, human-readable, and easily inspected or updated.
2. Inference Engine: The reasoning component that applies logical rules to the stored KB to derive new facts, answer queries, or decide on actions.

---

What is a Logic?

A logic is a formal language governed by concrete mathematical rules of syntax and semantics.

• No Ambiguity: Unlike natural languages (e.g., English), logical statements have exact, unambiguous meanings.
• Classical Logic vs. Fuzzy Logic: Classical logic operates on Boolean truth values ($\text{True}$ or $\text{False}$). In contrast, Fuzzy Logic extends classical logic by allowing degrees of truth represented as continuous values between $0$ and $1$.
• Logic vs. Logical Reasoning: A logic is the representation language itself, whereas logical reasoning is the algorithmic process executed by an inference engine using that logic.

---

Propositional Logic

Propositional logic is the simplest formal logical language. It deals with atomic propositions (indivisible statements that evaluate to $\text{True}$ or $\text{False}$) and combines them using logical connectives.

Connectives and Compound Sentences

There are five fundamental types of compound sentences in propositional logic:

1. Negation (NOT): $\neg P$ (e.g., "It is not raining" $\equiv \neg \text{Raining}$)
2. Conjunction (AND): $P \land Q$ (e.g., "It is raining and I have an umbrella" $\equiv \text{Raining} \land \text{Umbrella}$)
3. Disjunction (OR): $P \lor Q$ (e.g., "It is raining or it is snowing" $\equiv \text{Raining} \lor \text{Snowing}$)
4. Implication (IF-THEN): $P \Rightarrow Q$ (Material Implication: $P$ is the antecedent, $Q$ is the consequent. False only when $P$ is true and $Q$ is false):

$P \Rightarrow Q \equiv \neg P \lor Q$

5. Biconditional (IFF): $P \Leftrightarrow Q$ (True if and only if both $P$ and $Q$ have the exact same truth value):

$P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P) \equiv (\neg P \lor Q) \land (\neg Q \lor P)$

Truth Tables for Implication and Biconditional

Logical Equivalences

Logical equivalences allow us to rearrange and simplify logical expressions:

Limitations of Propositional Logic

While propositional logic is easy to automate, it lacks expressiveness. Because atoms have no internal structure, propositional logic cannot express properties of objects, relationships between objects, or general statements using quantifiers ("for all", "there exists").

[!NOTE] Expressiveness Benchmark (Chess Rules):

• In Propositional Logic, fully encoding the rules of chess requires 100,000 pages of logic.
• In First-Order Logic, the exact same rules fit onto 1 page.

---

First-Order Logic (FOL)

First-Order Logic (FOL) (also called Predicate Logic) extends propositional logic by introducing objects, properties, relationships, functions, and quantifiers.

Comparing Propositional Logic and Predicate Logic

Elements of First-Order Logic

1. Constants: Represent specific objects in the world (e.g., $\text{John}$, $\text{Apples}$, $\text{Socrates}$).
2. Predicates: Represent properties of objects or relationships between them; evaluate to True or False (e.g., $\text{IsWet}(x)$, $\text{Likes}(\text{John}, \text{Apples})$).
3. Functions: Map an object or tuple of objects to another object (e.g., $\text{fruit\_of}(\text{AppleTree})$, $\text{Father}(\text{John})$).
4. Variables: Lowercase placeholders representing generic domain objects (e.g., $x$, $y$, $z$).
5. Quantifiers: Allow generalized statements over domain elements.

---

Quantifiers in FOL

FOL uses two quantifiers to express general rules over sets of objects:

1. Universal Quantifier ($\forall$)

Expresses that a sentence holds true for all objects in the domain ("For all...", "Every...").

• Example 1: "All dogs like bones."

$\forall x (\text{Dog}(x) \Rightarrow \text{Likes}(x, \text{Bones}))$

• Example 2: "Anything with a beak and feathers is a bird."

$\forall x (\text{HasBeak}(x) \land \text{HasFeathers}(x) \Rightarrow \text{Bird}(x))$

• Example 3: "All men are mortal."

$\forall x (\text{Man}(x) \Rightarrow \text{Mortal}(x))$

2. Existential Quantifier ($\exists$)

Expresses that a sentence holds true for at least one object in the domain ("There exists...", "There is some...").

• Example 1: "There is someone who likes liver."

$\exists x \text{Likes}(x, \text{Liver})$

• Example 2: "Mary owns a coat."

$\exists x (\text{Owns}(\text{Mary}, x) \land \text{Coat}(x))$

---

Key Quantifier Rules and Nuances

Quantifier Order Matters

The order of quantifiers significantly alters statement semantics:

• $\forall x \exists y \text{Loves}(x, y)$
  • Meaning: "For every person $x$, there exists a person $y$ whom $x$ loves." (Everyone loves someone.)
• $\exists x \forall y \text{Loves}(x, y)$
  • Meaning: "There exists a person $x$ who loves every person $y$." (There is one universally loving person.)

Translating Complex Domain Statements

Consider the sentence: "Every rose has a thorn."

• English Breakdown: For all $x$, if $x$ is a rose, then there exists some $y$ such that $y$ is a thorn and $x$ has $y$.
• FOL Representation:

$\forall x (\text{Rose}(x) \Rightarrow \exists y (\text{Has}(x, y) \land \text{Thorn}(y)))$

Logical Inference Example in FOL

Given the general rule:

$\forall x (\text{King}(x) \land \text{Greedy}(x) \Rightarrow \text{Evil}(x))$

Inference in FOL allows substituting any constant term or function for variable $x$:

• $\text{King}(\text{John}) \land \text{Greedy}(\text{John}) \Rightarrow \text{Evil}(\text{John})$
• $\text{King}(\text{Richard}) \land \text{Greedy}(\text{Richard}) \Rightarrow \text{Evil}(\text{Richard})$
• $\text{King}(\text{Father}(\text{John})) \land \text{Greedy}(\text{Father}(\text{John})) \Rightarrow \text{Evil}(\text{Father}(\text{John}))$