Summary of Chapter 4: Knowledge Representation and Reasoning
Introduction
Knowledge Representation and Reasoning (KRR) enables machines to mimic human intelligence by storing
and processing knowledge to make decisions. Intelligence involves using knowledge gained through experience,
and reasoning is the process of deriving decisions from this knowledge. Machines require correct knowledge
representation to avoid erroneous outputs.
Knowledge Representation Techniques
KRR represents real-world data for machines to solve complex problems, such as natural language communication.
Four main representation methods are:
• Logical Representation: Uses formal languages like propositional and predicate (first-order) logic with
defined syntax and semantics for sound inference. Propositional logic handles true/false statements (e.g.,
2 + 3 = 5), while predicate logic depends on parameters (e.g., x + 3 = 5 becomes a proposition when x = 2).
• Semantic Network Representation: Stores knowledge as a graph of meaningful relationships (e.g., ”Ram is
a boy” and ”Ram has a cycle” are nodes connected by edges like ”owns”).
• Rules-Based Representation: Uses if-then statements (e.g., ”If temperature is below 10, then the weather
is cold”) for decision-making.
• Frame Representation: Organizes knowledge as records with attributes and values (e.g., a book frame with
slots for title, author, and edition).
Knowledge-Based Agents
Knowledge-based agents maintain a knowledge base (KB), a set of sentences in a formal language, and an inference
engine to derive new knowledge. They observe the environment, update the KB, reason over it, and act. The
KB must represent states, actions, goals, and allow updates to deduce hidden properties and optimal actions.
Propositional Logic
Propositional logic uses formal syntax and semantics to represent information with true/false propositions.
Atomic propositions are simple (e.g., ”2+2=4”), while compound propositions combine them using connectives:
• Negation (¬P ), Conjunction (P ∧ Q), Disjunction (P ∨ Q), Implication (P → Q), Biconditional (P ⇔ Q).
Truth tables define connective semantics, and logical equivalences (e.g., De Morgan’s laws) enable inference.
Entailment (KBα) means α is true in all models where KB is true. Inference rules like Modus Ponens, Modus
Tollens, and Resolution derive conclusions. Conjunctive Normal Form (CNF) is used for resolution, representing
sentences as conjunctions of disjunctions.
First-Order Logic (FOL)
FOL, or predicate logic, is more expressive than propositional logic, representing objects, relations, and functions.
It includes:
• Constants (e.g., Haileselassie), Predicates (e.g., Brother), Functions (e.g., Sqrt).
• Quantifiers: Universal (∀, ”for all”) and Existential (∃, ”there exists”). E.g., ∀xBird(x) → Fly(x) means
all birds fly.
1
FOL sentences combine atomic sentences (e.g., TeammateOf(Kenenisa, Haile)) using connectives. Inference rules
like Universal Instantiation (UI) and Existential Instantiation (EI) derive new facts. UI substitutes constants
into universal statements, while EI introduces new constants for existential ones.
Inference in FOL
FOL inference deduces new facts from existing sentences using UI, EI, Universal Generalization, and Existential
Introduction. Propositionalizing a KB converts FOL sentences to propositional logic for entailment-preserving
inference.
This chapter covers KRR’s role in AI, detailing representation techniques, knowledge-based agents, and logical
systems (propositional and first-order) with their syntax, semantics, and inference mechanisms, using examples
like semantic networks and truth tables.