Study guide: Logic Agents and Knowledge Representation

📋 Course Outline

1. Knowledge-Based Agent Architecture
2. Knowledge Bases and Inference
3. Agent Levels and Design Approaches
4. Wumpus World Environment
5. Wumpus World Reasoning and PEAS
6. Logic and Propositional Foundations
7. Propositional Connectives and Equivalence
8. Inference Rules in Propositional Logic
9. First-Order Logic and Quantifiers
10. First-Order Inference and Unification
11. Forward and Backward Chaining

📖 1. Knowledge-Based Agent Architecture

🔑 Key Concepts & Definitions

• Knowledge-based agent: An agent that maintains an internal state of knowledge, reasons over it, updates it after observations, and selects actions using a formal representation of the world.

★ Must-know

• A knowledge-based agent is composed of a knowledge base and an inference system.

• A generic knowledge-based agent receives a percept, tells the KB what it perceives, asks the KB what action to take, tells the KB which action was chosen, and returns that action.

Further detail

• A knowledge-based agent must be able to: represent states and actions, incorporate new percepts, update its internal representation of the world, deduce its internal representation of the world, deduce appropriate actions

• The generic agent begins with background knowledge and a time counter initialized to zero; MAKE-PERCEPT-SENTENCE, MAKE-ACTION-QUERY, and MAKE-ACTION-SENTENCE encode the percept, action query, and executed action, respectively.

💡 Memory Hook

Perceive, update the KB, infer, then act.

📖 2. Knowledge Bases and Inference

🔑 Key Concepts & Definitions

• Knowledge base: A collection of sentences expressed in a knowledge representation language that stores facts about the world.
• Inference: The derivation of new sentences from existing sentences by applying logical rules to a knowledge base.

★ Must-know

• The three knowledge-based agent operations are:
  • TELL: add what the agent perceives to the knowledge base
  • ASK: query which action should be performed
  • PERFORM: carry out the selected action

Further detail

• The knowledge base is updated with new sentences generated by the inference system, supporting learning from experience and action selection.

💡 Memory Hook

The KB stores sentences; the inference system derives new ones.

📖 3. Agent Levels and Design Approaches

★ Must-know

📌 At the knowledge level, the agent is specified by what it knows and its goals; at the logical level, its knowledge is encoded in logical sentences; at the implementation level, the logic and knowledge are physically represented and used to perform actions.

📌 The declarative approach initializes an agent with a knowledge base and adds starting sentences, whereas the procedural approach directly encodes desired behavior as program code.

Further detail

• For an automated taxi travelling from station A to station B, knowing the route is knowledge-level information, expecting arrival at B illustrates the logical level, and carrying out the route illustrates the implementation level.

• A successful real-world agent can combine declarative and procedural approaches, and declarative knowledge can be compiled into more efficient procedural code.

📖 4. Wumpus World Environment

★ Must-know

• The Wumpus world is a cave of 16 rooms arranged in a 4-by-4 grid and connected by passageways.

• The cave contains: a Wumpus that eats anyone entering its room, bottomless pits that trap an agent falling into them, a possible heap of gold in one room

• The agent's goal is to find the gold and climb out without falling into a pit or being eaten by the Wumpus.

Further detail

• The Wumpus world was inspired by Gregory Yob's 1973 video game Hunt the Wumpus.

• The agent has a single arrow that can kill the Wumpus when the agent is facing it.

💡 Memory Hook

Picture a cave grid where nearby hazards leave sensory clues.

📖 5. Wumpus World Reasoning and PEAS

★ Must-know

• In the Wumpus world, the performance measure gives +1000 points for exiting with gold, −1000 for being eaten or falling into a pit, −1 per action, and −10 for using an arrow; the game ends when the agent dies or exits.

• The Wumpus environment is a 4-by-4 grid with the agent initially at [1,1] facing right; the Wumpus and gold are randomly placed outside [1,1], and each other square has pit probability 0.2.

• The Wumpus agent senses: stench in a room directly adjacent to the Wumpus, breeze in a room directly adjacent to a pit, glitter in the room containing gold, a bump when it walks into a wall, a scream anywhere in the cave after the Wumpus is shot

• The Wumpus world is:

  • partially observable
  • deterministic
  • sequential
  • static
  • discrete
  • single-agent

• In the sample exploration, no stench or breeze at [1,1] marks adjacent squares safe; a breeze at [2,1] places a possible pit at [3,1] or [2,2]; no stench at [2,1] and stench at [1,2] locate the Wumpus at [1,3]; and glitter at [2,3] prompts the agent to grab the gold and climb out.

Further detail

• The Wumpus agent's actuators are:

  • left turn
  • right turn
  • move forward
  • grab
  • release
  • shoot

• A Wumpus percept is represented as a five-element list for stench, breeze, glitter, bump, and scream; [Stench, Breeze, None, None, None] represents stench and breeze without the other three percepts.

💡 Memory Hook

No stench or breeze at [1,1] makes adjacent rooms safe.

📖 6. Logic and Propositional Foundations

🔑 Key Concepts & Definitions

• Logic: The proof or validation behind reasoning that supports decisions based on the current situation.

★ Must-know

📌 Deductive logic draws a conclusion from complete evidence, whereas inductive logic reasons from particular observations using a bottom-up approach.

📌 A logic is specified by its syntax, semantics, and syntactic inference method: syntax defines allowable expressions, semantics assigns meanings and truth values, and inference rules derive theorems mechanically.

Further detail

📌 A fact is a claim about the world that may be true or false, whereas a representation is a sentence in a language that encodes objects and relations for a computer program.

💡 Memory Hook

Syntax shapes sentences; semantics assigns their meaning and truth.

📖 7. Propositional Connectives and Equivalence

🔑 Key Concepts & Definitions

• Proposition: A declarative statement that is either true or false, but not both.

★ Must-know

📌 An atomic proposition is a single proposition symbol, whereas a compound proposition combines simpler propositions using connectives and parentheses.

• The five propositional connectives are:
  • negation ¬
  • conjunction ∧
  • disjunction ∨
  • implication →
  • biconditional ⇔

📌 A tautology is always true, a contradiction is always false, and a contingent proposition formula can be either true or false depending on its valuation.

Further detail

• Propositional logic represents knowledge using propositions and logical connectives, and is also called Boolean logic because it works with 0 and 1.

• Questions, commands, and opinions are not propositions because they are not declarative statements with truth values.

💡 Memory Hook

Parentheses, negation, conjunction, disjunction, implication, biconditional.

📖 8. Inference Rules in Propositional Logic

🔑 Key Concepts & Definitions

• Logical equivalence: Two propositions are logically equivalent when their truth-table columns are identical.

★ Must-know

📐 Formula - De Morgan's laws are $\neg(P \land Q) = (\neg P) \lor (\neg Q)$ and $\neg(P \lor Q) = (\neg P) \land (\neg Q)$.

• Propositional logic cannot directly represent quantification such as all, some, or none, or describe objects through their properties and logical relations.

Further detail

• The precedence order is:
  • parentheses
  • negation
  • conjunction
  • disjunction
  • implication
  • biconditional

📐 Formula - Conjunction and disjunction are commutative: $P \land Q = Q \land P$ and $P \lor Q = Q \lor P$.

📐 Formula - Conjunction and disjunction are associative: $(P \land Q) \land R = P \land (Q \land R)$ and $(P \lor Q) \lor R = P \lor (Q \lor R)$.

📐 Formula - Double-negation elimination is $\neg(\neg P) = P$.

📖 9. First-Order Logic and Quantifiers

🔑 Key Concepts & Definitions

• Inference: The derivation of conclusions from evidence and facts by generating new logic from existing logic.

★ Must-know

📌 For an implication P → Q, its converse is Q → P, its contrapositive is ¬Q → ¬P, and its inverse is ¬P → ¬Q; the implication and contrapositive are equivalent, as are the converse and inverse.

• The seven inference rules are:
  • Modus Ponens
  • Modus Tollens
  • Hypothetical Syllogism
  • Disjunctive Syllogism
  • Addition
  • Simplification
  • Resolution

📌 Modus Ponens infers Q from P and P → Q.

Further detail

• Modus Tollens infers ¬P from P → Q and ¬Q.

• Hypothetical Syllogism infers P → R from P → Q and Q → R.

• Disjunctive Syllogism infers Q from P ∨ Q and ¬P.

💡 Memory Hook

Universal means every instance; existential means at least one.

📖 10. First-Order Inference and Unification

🔑 Key Concepts & Definitions

• First-order logic: First-order logic extends propositional logic to represent objects, their properties, and relationships between objects.

★ Must-know

📌 An atomic first-order sentence consists of a predicate applied to a sequence of terms, whereas a complex sentence combines atomic sentences with connectives.

📌 The universal quantifier ∀ expresses that a predicate holds for every object in its domain, whereas the existential quantifier ∃ expresses that it holds for at least one object.

Further detail

• First-order logic distinguishes subjects and predicates, and its domain may include objects, relations such as red or sister-of, and functions such as father-of.

• The basic first-order logic symbols include:

  • constants
  • variables
  • predicates
  • functions
  • connectives
  • equality
  • quantifiers

• Universal quantifiers commute with one another and existential quantifiers commute with one another, but ∃x∀y is not equivalent to ∀y∃x.

📖 11. Forward and Backward Chaining

🔑 Key Concepts & Definitions

• Unification: A process that makes two logical atomic expressions identical by finding a substitution, and fails when no matching substitution exists.
• Horn clause: A disjunction of literals containing at most one positive literal.
• Definite clause: A Horn clause containing exactly one positive literal; a Horn clause without a positive literal is a goal.

★ Must-know

📌 Unification requires matching predicate symbols and equal argument counts, and fails if a variable occurs within the expression it would replace.

📌 Universal instantiation infers P(c) from ∀x P(x) by substituting a ground term c for x.

• Generalized Modus Ponens is the first-order lifted form of Modus Ponens and derives a conclusion when matching premises are made identical by substitution.

📌 Forward chaining begins with known facts and applies rules to generate conclusions, whereas backward chaining begins with a goal and works backward to supporting facts.

Further detail

• The most general unifier for King(x) and King(John) is the substitution {John/x}.

• Universal generalization infers ∀x P(x) when P(c) holds for an arbitrary element c of the domain, with x not free in the relevant assumptions.

📌 Existential instantiation infers P(c) from ∃x P(x) using a new constant c that has not appeared in the knowledge base.

• Existential introduction infers ∃x P(x) from P(c) for an element c in the domain.

• Forward chaining is bottom-up, generally uses breadth-first search, tests available rules, and suits planning, monitoring, control, and interpretation; backward chaining is top-down, generally uses depth-first search, tests relevant rules, and suits diagnosis, prescription, and debugging.

💡 Memory Hook

Forward chaining is data-driven; backward chaining is goal-driven.

📊 Synthesis Tables

Forward and Backward Chaining