Chapter 4

Knowledge Representation and Reasoning

Compiled by: Misgana B

 Outlines

• Logic and Inference

• Logical Agents

• Reasoning

• Propositional Logic

• Predicate Logic

• Inference In First-order Logic

• Knowledge Representation
 Logic and Inference
• Logic as a formal language to represent knowledge with precise syntax and semantics.

• Logic formalizes knowledge; inference derives new facts using rules like deduction,
induction, and abduction.

• Types of Inference:

• Deduction: Deriving specific facts from general rules (e.g., modus ponens).

– Deriving specific conclusions from general principles (e.g., "All humans

are mortal. Socrates is human. Therefore, Socrates is mortal.").

• Induction: Generalizing from specific instances to broader generalizations

(e.g., observing multiple white swans and concluding all swans are white

• Abduction: Inferring the best explanation for observed data.

– Inferring the most likely explanation for observed data (e.g., seeing the
ground wet and inferring it rained).
 Reasoning
Reasoning in AI
– The process of thinking logically to generate new knowledge from existing
knowledge.
– Inference Rules: Prescribed procedures for deriving conclusions, such as
modus ponens, resolution, etc.
– Types of Reasoning:
• Deduction: Conclusions follow logically from premises.
• Induction: Generalizations from specific examples.
• Abduction: Inferring possible causes for observations.
Knowledge Representation: How knowledge about the world is encoded for
reasoning.
 Logical Agents

 An agent that uses logical representations of knowledge to decide actions.

 Use knowledge bases and inference to perceive, reason, and act in

environments.

 Architecture:

• Sensors perceiving the environment.

• Knowledge base storing facts and rules.

• Inference engine deriving new facts.

• Actuators performing actions.

 Propositional Logic: Syntax

Syntax:

o Rules for constructing legal sentences in the logic

o Which symbols we can use (English: letters, punctuation)

o How we are allowed to combine symbols

Symbols

 logical constants: True, False

 Propositional symbols: P, Q, …

 Logical connectives (∧, ∨, ¬, →, ↔) and () )

Sentence
 Atomic Sentence : Atomic Sentence → True | False | P | Q | R | ..

 Complex Sentence : complex Sentence → Sentence Connective Sentence.

Eg. p ∧ q
 Propositional Logic: Semantics

Semantics:

 Truth tables define how connectives affect truth values.

 Propositional Logic is also known as Classical or Boolean Logic.

 It defines how logical connectives (such as AND, OR, NOT, IMPLIES,

IFF) affect the truth values of statements.

 The logic uses truth tables to determine the truth value of complex
statements based on their components.

 Equivalence: Two formulas are equivalent if they are true in the same
models.
 Example

P Q P∧ Q P∨Q P→Q

T T T T T

T F F T F

F T F T T

F F F F T
 Propositional Logic: Equivalency

Two sentences are logically equivalent iff true in same models: α ≡ ß iff α╞ β
and β╞ α
 Propositional Logic: Validity, Satisfiability.

• Truth tables can be used to test sentences for validity.

 Valid: A sentence is valid if it is true in all sentence

– True in all models.

– Example:

A ¬A A∨¬A A→A

T F T True

F T T True
 Satisfiable: A sentence is Satisfiable if it is true in some sentence

– True in at least one model.

– Example: A ↔ B, A ∨ B, A → B and A ↔B

A B A↔B A∨B A→B A ∧B

T T T T T T
T F F T F F
F T F T T F
F F T F T F
Unsatisfiable:

– A sentence is Unsatisfiable if it is true in no sentence

– True in no model.

– Example: A∧¬ A

A ¬A A∧¬ A
T F F
F T F
 Predicate Logic
Propositional logic: combines atoms: An atom contains no propositional connectives

 Have no structure

 Ethiopia_is_beutiful, bezabih_loves_seblewengel)

Predicates: allow us to talk about objects

 Properties: is_beutiful (Ethiopia)

 Relations: loves(bezabih, seblewengel)

 True or false

 In predicate logic each atom is a predicate

o E.g. first order logic, higher-order logic

 First Order Logic
First-order logic is symbolized reasoning in which each sentence, is broken
down into a subject and a predicate.

• The predicate defines the properties of the subject.

o Constants are objects: bezabih, S/wengel

o Predicates are properties and relations:

 loves(bezabih, seblewengel)

o Variables represent any object:

 loves(X, seblewengel)
Quantifiers:

 ∀ (for all): True for all objects (Universal):

o Example:

 ∀ X. loves(X, seblewengel)

 ∀x (Human(x) → Mortal(x)).

 ∃ (exists): Exists at least one object (Existential):

o Example:

 ∃ X. loves(X, seblewengel)
 Inference in First-Order Logic (FOL)

Inference rules
 Inference rules are templates for valid reasoning, used to derive new facts from existing
sentences.

 In AI, inference in FOL helps deduce additional information, forming proofs that lead to
desired conclusions, thereby expanding the system's knowledge base.

 Inference Methods (Types of Inference rules): it includes:

 Modus ponens

 Modus tollens

 Hypothetical syllogism

 Disjunctive syllogism.
 Modus Ponens
 The Modus Ponens rule states that if P and P → Q is true, then we can infer
that Q will be true.

Example: Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

 Statement-2: "I am sleepy" ==> P

 Conclusion: "I go to bed." ==> Q.

 Hence, we can say that, if P→ Q is true and P is true then Q will be true.
 Hypothetical Syllogism:
The Hypothetical Syllogism rule state that if P→R is true whenever P→Q is true, and
Q→R is true.

Example:

– Statement-1: If you have my home key then you can unlock my home. P→Q

– Statement-2: If you can unlock my home then you can take my money. Q→R

– Conclusion: If you have my home key then you can take my money. P→R
 Modus Tollens
• The Modus Tollens rule state that if P→ Q is true and ¬ Q is true, then ¬ P
will also true. It can be represented as:

Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

Statement-2: "I do not go to the bed."==> ~Q

conclusion: Which infers that "I am not sleepy" => ~P

 Disjunctive syllogism
The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true, then Q will be
true. It can be represented as:

Example:

 Statement-1: Today is Sunday or Monday. ==>P∨Q

 Statement-2: Today is not Sunday. ==> ¬P

 Conclusion: Today is Monday. ==> Q

 Knowledge Representation

Knowledge Representation (KR)

 It is a concept in Artificial Intelligence that focuses on how machines store and

use knowledge about the real world.

 It is part of AI that focuses on how intelligent agents think and make decisions.

 Just like humans use their knowledge to understand situations and make
decisions, computers also need a structured way to represent information so
they can reason, learn and solve problems smartly.
 Types of knowledge
Declarative Knowledge: Knowledge about facts and concepts it answers what something is .

o Example: Paris is the capital of France.

Procedural Knowledge: Knowledge about how to perform a task or solve a problem.

o Example: Steps to sort numbers using an algorithm.

Meta knowledge: Knowledge about other knowledge or how knowledge is used.

o Example: Knowing that a certain rule works better for solving math problems.

Heuristic Knowledge: Experience based knowledge or rules of thumb used by experts.

o Example: A doctor using past experience to guess a possible disease.

Structural Knowledge: Knowledge that shows relationships between concepts.

o Example: A car is a type of vehicle.

Techniques of knowledge representation
 Logical Representation

Definition: Uses formal rules and logic to represent knowledge.

Purpose: Facilitates reasoning and decision-making.

Components:

 Syntax: Rules for writing symbols and sentences.

 Semantics: Meaning of logical sentences.

Main Types:

 Propositional Logic

 Predicate Logic
 Semantic Network Representation
Knowledge represented as a graph with nodes (concepts) and arcs (relationships).

Relationships:

 IS-A (inheritance)

 Kind-of (category)
 Frame Representation
Frame

 It is a data structure used to represent knowledge about an object or

situation.

 It contains slots (attributes) and values that describe an entity.

 It help organize related information together.

 Frames are similar to modern classes and objects in programming and

are widely used in NLP and computer vision.

 Example: A frame for a Book may include slots such as title, author,
year and pages.
 Production Rules

 Production rules represent knowledge in the form of IF–THEN rules.

 When a condition is satisfied, the system performs the corresponding

action.

 A production rule system has three main parts:

– Set of rules

– Working memory (current problem state)

– Recognize act cycle (process of checking conditions and applying

rules)

• Example: IF (bus arrives) THEN (get into the bus)