UNIT – IV

Knowledge representation

Knowledge representation in Artificial Intelligence (AI) is the field focused on how to symbolically
represent information about the world in a form that a computer system can utilize to solve complex
tasks such as diagnosing a medical condition, understanding language, or playing chess.

An AI system must represent, store, and manipulate knowledge to:

 Reason about the world

 Draw inferences
 Make decisions
 Communicate with humans and other machines

Types of Knowledge Represented

1. Declarative Knowledge: Facts about objects, events (e.g., "Paris is the capital of
France").
2. Procedural Knowledge: How-to information (e.g., how to solve a math problem).
3. Meta-Knowledge: Knowledge about knowledge (e.g., "I know that I don’t know").
4. Heuristic Knowledge: Rules of thumb (e.g., "If a car won’t start, check the battery").
5. Common-Sense Knowledge: Basic understanding of everyday life (e.g., "Water is wet").

Methods of Knowledge Representation

1. Semantic Networks
Graphs of connected concepts and relationships.
2. Frames
Data structures for representing stereotypical situations.
3. Rules (Production Systems)
IF-THEN rules (used in expert systems).
4. Logic (Propositional & Predicate Logic)
Symbolic logic used for formal reasoning.
5. Ontologies
Structured frameworks that define the relationships between concepts.
6. Bayesian Networks
Represent probabilistic relationships among variables.

An AI system must represent, store, and manipulate knowledge to:

  Reason about the world
 Draw inferences
 Make decisions
 Communicate with humans and other machines

Types of Knowledge Represented

1. Declarative Knowledge: Facts about objects, events (e.g., "Paris is the capital of
France").
2. Procedural Knowledge: How-to information (e.g., how to solve a math problem).
3. Meta-Knowledge: Knowledge about knowledge (e.g., "I know that I don’t know").
4. Heuristic Knowledge: Rules of thumb (e.g., "If a car won’t start, check the battery").
5. Common-Sense Knowledge: Basic understanding of everyday life (e.g., "Water is wet").

Methods of Knowledge Representation

1. Semantic Networks
Graphs of connected concepts and relationships.
2. Frames
Data structures for representing stereotypical situations.
3. Rules (Production Systems)
IF-THEN rules (used in expert systems).
4. Logic (Propositional & Predicate Logic)
Symbolic logic used for formal reasoning.
5. Ontologies
Structured frameworks that define the relationships between concepts.
6. Bayesian Networks
Represent probabilistic relationships among variables.

Wumpus World Problem

The Wumpus World is a classic problem in Artificial Intelligence (AI) designed to illustrate concepts like
knowledge representation, reasoning, and decision-making in uncertain environments. It's a grid-based
world where an agent must navigate to find gold while avoiding hazards like pits and a dangerous
creature called the Wumpus.

Wumpus World Overview

 Environment: A 4×4 grid of rooms (16 total).

 Agent: Starts at position (1,1), facing right.
 Hazards:
o Wumpus: A deadly creature that kills the agent if they enter its room.
o Pits: Bottomless traps that cause the agent to fall and perish.
 Goal: Find the gold and return safely to the starting position.

Percepts and Actions

 Percepts:
o Breeze: Indicates a pit in an adjacent room.
o Stench: Indicates the Wumpus is in an adjacent room.
o Glitter: Indicates the gold is in the current room.
o Scream: Heard when the Wumpus is killed.
o Bump: Occurs when the agent hits a wall.
 Actions:
o Move forward
o Turn left/right
o Grab (pick up gold)
o Shoot (use an arrow to kill the Wumpus)
o Climb (exit the cave)

PEAS Description

 Performance Measure:
o +1000: Successfully find gold and return.
o -1000: Fall into a pit or get eaten by the Wumpus.
o -1: Each move.
 o -10: Use the arrow.
 Environment: 4×4 grid with pits, Wumpus, and gold.
 Actuators: Move, turn, grab, shoot, climb.
 Sensors: Breeze, stench, glitter, scream, bump.

Sample Grid Layout

Here's a visual representation of a possible Wumpus World setup:

diff
CopyEdit
+---+---+---+---+
| S | B | | P |
+---+---+---+---+
| W | | G | |
+---+---+---+---+
| B | | | |
+---+---+---+---+
| P | | | |
+---+---+---+---+

 S: Start position of the agent.

 B: Breeze (adjacent to a pit).
 W: Wumpus.
 G: Gold.
 P: Pit.

Agent's Reasoning Process

1. Initial Perception: The agent starts at (1,1) and perceives no breeze or stench, indicating
adjacent rooms are safe.
2. Exploration: The agent moves cautiously, using perceptions to infer the presence of hazards:
o If a breeze is sensed, at least one adjacent room contains a pit.
o If a stench is sensed, the Wumpus is in an adjacent room.
3. Decision Making: Based on gathered information, the agent plans its path to avoid hazards and
reach the gold.

Propositional Logic: Syntax, Semantics, Knowledge Base, and Inferences

Propositional logic is a formal system in logic that is used to represent statements (propositions)
that can be either true or false. It is foundational for many areas of artificial intelligence,
particularly knowledge representation and reasoning. Below is a breakdown of its syntax,
semantics, knowledge base construction, and inferences.
 1. Syntax of Propositional Logic

Syntax defines the rules for constructing well-formed formulas (WFFs) in propositional logic.
These formulas are composed of:

 Propositions (Atomic Propositions): These are basic statements that can be either true
or false. For example, P, Q, R represent propositions.
 Logical Connectives:

o Conjunction (∧): Represents "and". Example: P ∧ Q means "P and Q".

o Negation (¬): Represents "not". Example: ¬P means "not P".

o Disjunction (∨): Represents "or". Example: P ∨ Q means "P or Q".

o Implication (→): Represents "if... then". Example: P → Q means "If P then Q".
o Biconditional (↔): Represents "if and only if". Example: P ↔ Q means "P if and
only if Q".
Well-formed formula (WFF): A valid expression formed using these atomic
propositions and connectives. Example: (P ∧ (Q ∨ R)) → ¬S is a WFF.


2. Semantics of Propositional Logic

Semantics defines the meaning of the propositions and the truth values they can take.

 Truth Values: Each proposition is either true (T) or false (F).

 Truth Tables: Used to define the truth value of complex formulas based on the truth

o Conjunction (∧): P ∧ Q is true if both P and Q are true, otherwise false.

values of their components.

o Disjunction (∨): P ∨ Q is true if at least one of P or Q is true.

o Implication (→): P → Q is false only when P is true and Q is false; otherwise, it's
true.
o Negation (¬): ¬P is true if P is false, and false if P is true.

Example of a Truth Table for Conjunction (P ∧ Q):

P∧
PQ
Q
T T T
T F F
F T F
F F F

3. Knowledge Base Construction

A knowledge base (KB) in propositional logic is a collection of logical sentences (propositional
formulas) that represent knowledge about the world.

 Knowledge Representation: In AI, the KB can store facts and rules about the world. For
example, the KB might contain the following:
o P: "It is raining."
o Q: "The ground is wet."
o P → Q: "If it is raining, the ground is wet."
 Constructing KB:
o Facts: The KB contains facts (atomic propositions) that are assumed to be true.
Example: P (It is raining).
o Rules: The KB can include logical implications or conditions. Example: P → Q (If
it is raining, the ground is wet).

The KB allows for automated reasoning by checking the consistency of facts and rules
and enabling inferences.

4. Inferences in Propositional Logic

Inference is the process of deriving new knowledge from existing knowledge in the knowledge
base.

 Modus Ponens (Valid Inference Rule):

o If P → Q and P are both in the KB, then infer Q.

Example:

oGiven P → Q (If it is raining, the ground is wet) and P (It is raining), we can infer
Q (The ground is wet).
 Modus Tollens (Valid Inference Rule):
o If P → Q and ¬Q (not Q) are both in the KB, then infer ¬P (not P).

Example:

o Given P → Q (If it is raining, the ground is wet) and ¬Q (The ground is not wet),
we can infer ¬P (It is not raining).
 Resolution (General Inference Method):
o A technique for automated reasoning where clauses are combined to derive new
clauses.
o Example:
 P ∨ Q and ¬Q ∨ R can be resolved to give P ∨ R.
5. Example Problem (Knowledge Base and Inference)

Problem: Let's say we have the following knowledge:

1. P: It is raining.
2. P → Q: If it is raining, then the ground is wet.
3. ¬Q: The ground is not wet.

KB: {P, P → Q, ¬Q}

We want to infer whether it is raining (P).

Solution:

 From P → Q and ¬Q, we apply Modus Tollens to infer ¬P (It is not raining).
 Therefore, based on the KB, we conclude that it is not raining.

Inference in Predicate Logic

In predicate logic, inference rules are used to derive new statements from known facts or premises.
Inference in FOL can be more complex than in propositional logic because it involves quantifiers and
variables.

Key Inference Rules in Predicate Logic

1. Universal Instantiation (UI):

o If we know that something is true for all members of a set, we can infer that it's true for
any particular member of that set.
o Example:
 Premise: ∀x IsHuman(x) (Everyone is human)
 Inference: IsHuman(John) (John is human)
2. Existential Instantiation (EI):
o If we know that something exists, we can instantiate it as a specific object (variable).
o Example:
 Premise: ∃x Loves(x, Mary) (Someone loves Mary)
 Inference: Loves(John, Mary) (John loves Mary)
3. Universal Generalization (UG):
o If a property is true for an arbitrary individual, we can generalize it to all individuals.
o Example:
 Premise: IsHuman(John) (John is human)
 Inference: ∀x IsHuman(x) (Everyone is human)
4. Existential Generalization (EG):
o If a property is true for a specific individual, we can infer that there exists some
individual for which that property holds.
o Example:
 Premise: Loves(John, Mary) (John loves Mary)
  Inference: ∃x Loves(x, Mary) (Someone loves Mary)
5. Modus Ponens (MP):
o Similar to propositional logic, if P → Q and P are both true, then Q must be true.
o Example:
 Premise 1: ∀x (IsHuman(x) → CanSpeak(x)) (If someone is human, they
can speak)
 Premise 2: IsHuman(John) (John is human)
 Inference: CanSpeak(John) (John can speak)
6. Modus Tollens (MT):
o If P → Q and ¬Q (not Q) are both true, then ¬P (not P) is true.
o Example:
 Premise 1: ∀x (IsHuman(x) → CanSpeak(x)) (If someone is human, they
can speak)
 Premise 2: ¬CanSpeak(John) (John cannot speak)
 Inference: ¬IsHuman(John) (John is not human)

Reasoning Patterns in Predicate Logic

The reasoning patterns in predicate logic involve using these inference rules to build logical arguments,
prove statements, and derive new knowledge. Some common reasoning techniques include:

Deductive Reasoning

This involves drawing specific conclusions from general premises or facts using inference rules. In
predicate logic, you can apply universal and existential quantifiers to deduce specific facts.

o Premise 1: ∀x (IsHuman(x) → CanSpeak(x)) (If someone is human, they can

 Example:

speak)
o Premise 2: IsHuman(John) (John is human)
o Deductive Conclusion: CanSpeak(John) (John can speak)

Inductive Reasoning

Inductive reasoning, in general, is about making generalizations based on specific observations. While
predicate logic is more often used for deductive reasoning, inductive reasoning can be applied
informally by identifying patterns in specific cases.

Abductive Reasoning

Abductive reasoning involves forming the most likely explanation from available evidence. In predicate
logic, it may involve inferring the best possible explanation given certain facts and premises, often used
for problem-solving or diagnosis.
Representing facts in logic,syntax and semantics

example, "All humans are mortal" can be represented in predicate logic as ∀x (Human(x)
 Logic: Use logical expressions like propositional or predicate logic to model facts. For

→ Mortal(x)).
 Syntax: Focus on the structure of expressions. Syntax dictates how symbols can be
combined to form valid statements, ensuring clarity and proper organization of facts. For
instance, logical syntax includes operators like AND (∧), OR (∨), and NOT (¬).
 Semantics: This relates to the meaning behind the expressions. It ensures the
interpretation of syntactic structures is clear and corresponds accurately to real-world
concepts or scenarios.

Unification Algorithm

The Unification Algorithm is a process used in artificial intelligence and logic programming to
find a substitution that makes two logical expressions identical. Here's a concise explanation for
four marks:

 Input: Two expressions (terms) to be unified.

 Output: A substitution set (if unification is possible) or failure (if not possible).
 Steps:
o Check if the two terms are identical; if yes, unification succeeds with an empty
substitution.
o If one term is a variable, substitute it with the other term, ensuring no cyclic
references.
o Recursively unify sub-terms of compound expressions.
o If terms are incompatible (e.g., different operators), the unification fails.
 Termination: Repeat until all terms are unified or unification fails.

Knowledge Representation Using Rules and Semantic Nets

1. Rules:
Rules represent knowledge as "if-then" statements, often used in expert systems.
o
They are logical expressions that define actions or conditions. For example: If
o
temperature > 100°C, then turn off the heat.
o These are good for procedural knowledge, enabling automated reasoning via rule-
based inference engines.
2. Semantic Nets:
o Semantic nets use graphs to represent knowledge visually as nodes (concepts) and
edges (relationships).
 o For example, in a semantic net: Cat → (is a) → Animal Cat → (has) →
Whiskers
o This is ideal for representing associative and hierarchical relationships.

Knowledge Representation Using frame references

Frames are a data structure used for knowledge representation, inspired by how humans use
mental models to organize and retrieve information. They represent knowledge in a structured
format, consisting of attributes and their associated values. Here's an overview:

1. Structure: A frame is a collection of slots (attributes) and slot values. For example, a
frame for "Car" might include:
o Car Frame:
 Slots:
 Make: Toyota
 Model: Corolla
 Color: Red
 Engine: Petrol
2. Inheritance: Frames are often organized hierarchically. Sub-frames (specific instances)
can inherit properties from parent frames (general categories). For example:
o Vehicle Frame:
 Slots: Wheels, Engine, Max Speed
o Car Frame (inherits Vehicle):
 Additional Slots: Make, Model, Fuel Type
3. Reasoning and Defaults: Frames allow reasoning through the use of default values and
procedural attachments. For instance:
o If the "FuelType" slot is unspecified, the default value could be "Petrol."
o Procedural attachments can include actions like checking slot values or updating
them based on input.
4. Applications:
o Used in AI systems for representing knowledge in natural language processing,
expert systems, and object-oriented programming.

Uncertain Knowledge and Reasoning Methods

Uncertain knowledge refers to situations where the available information is incomplete,

ambiguous, or not fully reliable. Reasoning under such uncertainty is a key challenge in artificial
intelligence, and various methods are employed to address it:

1. Bayesian Networks:
o Probabilistic graphical models that represent variables and their dependencies.
o Use conditional probabilities to reason about uncertain events.
o Example: Diagnosing diseases based on symptoms with probabilities attached.
2. Fuzzy Logic:
 o Deals with reasoning that allows for degrees of truth rather than binary true/false
values.
o Useful in real-world scenarios where boundaries are not clearly defined, such as
"hot" or "cold."
o Example: Controlling room temperature in air conditioning systems.
3. Dempster-Shafer Theory:
o A framework for reasoning with uncertainty that combines evidence from
different sources.
o Assigns degrees of belief to propositions and allows for reasoning even with
incomplete data.
4. Non-Monotonic Reasoning:
o Reasoning that allows for conclusions to be withdrawn or revised based on new
evidence.
o Often used in AI for common-sense reasoning.
o Example: Assuming "birds can fly" but revising it when learning about penguins.
5. Rule-Based Systems with Certainty Factors:
o Extend traditional rule-based systems by associating certainty factors (CFs) to
conclusions.
o CFs represent confidence levels in a particular rule or inference.
6. Monte Carlo Methods:
o Use random sampling to estimate outcomes and make decisions under
uncertainty.
o Common in fields like finance, physics, and engineering.