Lecture 09.1: Knowledge-Based Agents and Logic

Early AI research (like neural networks) relied heavily on implicit knowledge buried inside mathematical weights. In the 1970s and 1980s, driven by researchers like Marvin Minsky, AI shifted focus toward symbolic reasoning and explicit knowledge representation.

A Knowledge-Based Agent is an intelligent AI system that uses an explicit representation of knowledge to reason and make decisions. It has two main components:

1. Knowledge Base (KB): The facts, rules, and relationships are written out directly (e.g., $\text{Raining} \Rightarrow \text{Wet}(\text{Ground})$). The knowledge is visible and checkable.
2. Inference Engine: Performs logical reasoning to derive new facts or actions from the stored knowledge.

To store and process this knowledge, we need formal logical languages.

---

Propositional Logic

Propositional logic is a simple language consisting of basic atoms (propositions) that are either true or false. We combine these simple sentences using connectives to form compound sentences:

• Negation (NOT): $\neg P$ (e.g., "It is not raining" $\neg \text{Rain}$)
• Conjunction (AND): $P \land Q$ (e.g., "It is raining and it is cold" $\text{Rain} \land \text{Cold}$)
• Disjunction (OR): $P \lor Q$ (e.g., "It is raining or it is snowing" $\text{Rain} \lor \text{Snow}$)
• Implication (IF-THEN): $P \Rightarrow Q$ (e.g., "If it is raining, the ground is wet" $\text{Rain} \Rightarrow \text{Wet}$)
• Biconditional (IFF): $P \Leftrightarrow Q$ (e.g., "It is raining if and only if there are clouds" $\text{Rain} \Leftrightarrow \text{Clouds}$)

Logical Equivalences

To manipulate logical statements in a Knowledge Base, we rely on standard logical equivalences:

Limitations of Propositional Logic

Propositional logic lacks expressiveness. It can only express relationships between fixed, specific facts. It cannot generalize.

[!NOTE] Propositional vs. First-Order Logic Size Comparison: To represent the rules of chess in Propositional Logic, it would require 100,000 pages of logic sentences. In First-Order Logic, it takes only 1 page.

---

First-Order Logic (FOL)

First-Order Logic (FOL), or Predicate Logic, is a generalization of propositional logic that allows us to represent objects, properties of objects, and relationships.

• Constants: Specific objects in the domain (e.g., $\text{John}$, $\text{Apples}$).
• Predicates: Properties and relations that evaluate to true or false (e.g., $\text{Likes}(\text{John}, \text{Apples})$).
• Functions: Mapping from objects to another object (e.g., $\text{fruit\_of}(\text{AppleTree})$).
• Variables: Placeholders for objects (e.g., $x$, $y$).

Quantifiers

FOL introduces quantifiers to make sweeping statements about groups of objects:

1. Universal Quantifier ($\forall$)

Means "For all..." or "Every..."

• Example: "All dogs like bones."

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

Explanation: "For any object $x$, if $x$ is a dog, then $x$ likes bones."

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

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

2. Existential Quantifier ($\exists$)

Means "There exists at least one..." or "There is some..."

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

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

• Example: "Mary owns a coat."

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

---

Critical Quantifier Rules

Quantifier Order Matters

The order of quantifiers is extremely important. Swapping them changes the entire meaning:

• $\forall x \exists y \text{ Loves}(x, y)$ Meaning: "For every person $x$, there exists a person $y$ that $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 super-loving person).

Translating Complex Sentences

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

• 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)))$