Chapter Four

Knowledge Representation
and Reasoning

Artificial Intelligence By: Zelalem F. Ambo University

 Outline
2

❖ Introduction
❖ Knowledge Based Agents
❖ Knowledge Representation
➢ Propositional Logic
➢ Predicate (First-Order)Logic
➢ Inference in First-Order Logic

❖ Knowledge Reasoning
➢ Bayesian reasoning
➢ Probabilistic reasoning
➢ Temporal reasoning

❖ Knowledge-based Systems
Artificial Intelligence By: Zelalem F. Ambo University
 Introduction
3

What is knowledge?
❖ Humans are best at understanding, reasoning, and interpreting knowledge.

❖ Human knows things, which is knowledge and as per their knowledge they

perform various actions in the real world.

❖ Humans make decision through reasoning based on internalized of knowledge.

❖ But how machines do all these things comes under knowledge representation

and reasoning.

❖ In AI, this approach to intelligent is done through knowledge based agent.

Artificial Intelligence By: Zelalem F. Ambo University

 Knowledge-based agents
4
Knowledge-based agents
❖ An intelligent agent needs knowledge about the real world for taking decisions
and reasoning to act efficiently.

❖ Knowledge-based agents are those agents who have the capability of

maintaining, reason, update their knowledge after observations and take
actions.

❖ These agents can represent the world with some formal representation and act
intelligently.

❖ Knowledge-based agents are composed of two main parts:

❖ Knowledge-base and Inference system.

Artificial Intelligence Zelalem F. Ambo University
 Knowledge-based agents
5

Knowledge base (KB):

❖ It is a central component of a knowledge-based agent.

❖ A set of sentences that describe the world & its behavior in a formal language

❖ Typically domain specific but large knowledge corpuses are built to provide
general knowledge resources.

❖ It is a collection of sentences (here 'sentence' is a technical term and it is not

identical to sentence in English).

❖ These sentences are expressed in a language which is called a knowledge

representation language..

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
6

Inference engine:
❖ A set of procedures that use the representational language to infer new facts
from known ones or answer a variety of KB queries.

❖ Inference system applies logical rules to the KB to deduce new information.

❖ Inferences typically require search.

❖ Typically domain independent.

❖ An inference system works mainly in two rules which are given as:

• Forward chaining

• Backward chaining

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
7

Example: MYCIN:
❖MYCIN: an expert system for diagnosis of bacterial infections

❖Knowledge base represents

‒ Facts about a specific patient case

‒ Rules describing relations between entities in the bacterial infection

domain

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
8

Example: MYCIN:

▪ MYCIN: an expert system for diagnosis of bacterial infections

▪ Inference engine:

‒ manipulates the facts and known relations to answer diagnostic

queries (consistent with findings and rules)

‒ Inferences are steps in reasoning, moving from premises to

logical consequences; etymologically, the word infer means to
"carry forward".

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
9

Example: MYCIN:
❖Operations Performed by KBA:

❖Following are three operations which are performed by KBA in order to

show the intelligent behavior:

1. TELL: This operation tells the knowledge base what it perceives

from the environment.

2. ASK: This operation asks the knowledge base what action it should
perform.

3. Perform: It performs the selected action.

Artificial Intelligence Zelalem F. Ambo University
 Knowledge-based agents
10
Example: MYCIN:
❖ Operations Performed by KBA:

▪ How to modify the behavior?

‒ Done at the knowledge level
‒ Tell the agent’s its goal, and
‒ Tell the agent what it knows.

▪ Example:
‒ Tell the taxi about bay bridge.
‒ Tell the taxi to go from Ambo to Addis Ababa
‒ Taxi know to cross the bridge.
Artificial Intelligence Zelalem F. Ambo University
 Knowledge-based agents
11

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
12
There are mainly two approaches to build a knowledge-based agent:
1. Declarative approach:
▪ Tell sentences one-by-one until the agent knows what to do in its env’t.
▪ Create KBA by initializing with an empty knowledge base and telling the agent
all the sentences with which we want to start with.
▪ This type of approaches called Declarative approach.
2. Procedural approach:
➢ In this approach, we directly encode desired behavior as a program code.
➢ Which means we just need to write a program that already encodes the desired
behavior or agent.
➢ Best agent combination of both.
Artificial Intelligence Zelalem F. Ambo University
 Knowledge-based agents
13
Example: The Wumpus World
❖ It is an environment in which KBA can show their worth.

❖ The Wumpus world is a cave consisting of rooms connected by passageways.

❖ Lurking somewhere in the cave is the terrible Wumpus, a beast that eats anyone who
enters its room.

❖ The Wumpus can be shot by an agent, but the agent has only one arrow.

❖ Some rooms contain bottomless pits that will trap anyone who wanders into these
rooms (except for the Wumpus, which is too big to fall in).

❖ The only redeeming feature of this bleak environment is the possibility of finding a
heap of gold.

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
14
Example: The Wumpus World
❖PEAS description:

1. Performance measure

2. Environment

3. Actuators

4. Sensors

❖ The agent is in the bottom left corner,

facing east (rightward).

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
15
Example: The Wumpus World
▪ PEAS description: Performance measure:

❖ +1000 for climbing out of the cave with the gold,

❖ –1000 for falling into a pit or being eaten by the Wumpus,

❖ –1 for each action taken,

❖ –10 for using up the arrow.

❖ The game ends either when the agent dies or when the agent climbs out of the

cave.
Artificial Intelligence Zelalem F. Ambo University
 Knowledge-based agents
16

Example: The Wumpus World

▪ PEAS description: Environment:

❖ A 4×4 grid of rooms, with walls surrounding the grid.

❖ The agent always starts in the square labeled [1,1], facing to the east.

❖ The locations of the gold and the Wumpus are chosen randomly, with a

uniform distribution, from the squares other than the start square.

❖ In addition, each square other than the start can be a pit, with probability

0.2.
Artificial Intelligence Zelalem F. Ambo University
 Knowledge-based agents
17
Example: The Wumpus World
▪ PEAS description: Actuators:
❖ The agent can move Forward, TurnLeft by 90◦, or TurnRight by 90◦. If an agent
tries to move forward and bumps into a wall, then the agent does not move.
❖ The action Grab can be used to pick up the gold if it is in the same square as the
agent.
❖ The action Shoot can be used to fire an arrow in a straight line in the direction
the agent is facing. The agent has only one arrow, so only the first Shoot action
has any effect.
❖ Finally, the action Climb can be used to climb out of the cave, but only from
square [1,1].

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based agents
18

Example: The Wumpus World

▪ PEAS description: Sensors:

❖ In the squares directly (not diagonally) adjacent to the Wumpus, the agent
will perceive a Stench.

❖ In the squares directly adjacent to a pit, the agent will perceive a Breeze.

❖ In the square where the gold is, the agent will perceive a Glitter.

❖ When an agent walks into a wall, it will perceive a Bump.

❖ When the Wumpus is killed, it emits a woeful Scream that can be perceived
anywhere in the cave.

Artificial Intelligence Zelalem F. Ambo University

 Knowledge Representation Languages
19

Knowledge Representation
❖Goal: express the knowledge about the world in a computer tractable form.

❖Key aspects of knowledge representation languages:

➢ Syntax: describes how sentences are formed in the language

➢ Semantics: describes the meaning of sentences, what is it the sentence

refers to in the real world

➢ Computational aspect: describes how sentences and objects are

manipulated in concordance with semantical conventions

Artificial Intelligence Zelalem F. Ambo University

 Knowledge Representation Languages
20

▪ There are mainly four ways of knowledge representation which are

given as follows:

1. Logical Representation

2. Semantic Network Representation

3. Frame Representation

4. Production Rules

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
21
What is Logic
❖ Logics form the formal foundation of knowledge representation and reasoning,

which is a fundamental topic in Artificial Intelligence.

❖ Logical languages are widely used for expressing the declarative knowledge

needed in artificial intelligence systems.

❖ Symbolic logic also provides a clear semantics for knowledge representation

languages and a methodology for analyzing and comparing deductive inference

techniques.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
22
What is Logic
❖ Knowledge bases consist of sentences.

❖ Sentence follow the syntax of their representation language when “well-

formed”.

➢ Arithmetic example: “ X + Y + Z = 14 “

❖ Sematic are also defined, which is the meaning of the sentences.

• Defines truth of each sentences wrt each possible world aka model.

• Example: “ X + Y + Z = 14 “ is true where x is 3, y is 5, and z is 6.

False, where x is -1, y is -2 and z is -3

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
23
What is Logic
❖ Logic is defined by: A set of sentences

A sentence is constructed from a set of primitives according to syntax rules.

❖ A set of interpretations

‒ An interpretation gives a semantic to primitives. It associates primitives

with values.

❖ The valuation (meaning) function V

‒ Assigns a truth value to a given sentence under some interpretation

‒ V : sentence × interpretation → {True , False }

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
24

What is Logical Representation

❖ It is a language with some concrete rules which deals with propositions and has

no ambiguity in representation.

❖ It means drawing a conclusion based on various conditions.

❖ This representation lays down some important communication rules.

❖ It consists of precisely defined syntax and semantics which supports the sound

inference.

❖ Each sentence can be translated into logics using syntax and semantics.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
25

What is Logical Representation

❖ Syntax:
❖ Syntaxes are the rules which decide how we can construct legal
sentences in the logic.
❖ The atomic sentences consist of a single proposition symbol.
❖ It determines which symbol we can use in knowledge
representation.
❖ describes how sentences are formed in the language.
❖ How to write those symbols.
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
26

What is Logical Representation

❖ Semantics :
❖ Semantics are the rules by which we can interpret the sentence in
the logic.
❖ Semantic also involves assigning a meaning to each sentence.
❖ Describes the meaning of sentences, what is it the sentence refers to
in the real world.
❖ Many knowledge representation systems rely on some variant of
logic,

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
27

What is Logical Representation

❖A Logical representation of the knowledge representation systems can

be categorized into mainly two logics:

1. Propositional logic

2. First order logic

3. Temporal logic

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
28

❑ Propositional logic (PL)

❖ It is the simplest form of logic where all the statements are made by

propositions.

❖ A proposition is a declarative statement which is either true or false.

❖ It is a technique of KR in logical and mathematical form.

❖ Propositional logic is also called Boolean logic as it works on 0 and 1.

❖ Propositions can be either true or false, but it cannot be both.

Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
29
Propositional Logic(PL)

✓ It consists of an object, relations or function, and logical connectives.

✓ A proposition formula which is always true is called tautology, and it is also

called a valid sentence.

✓ A proposition formula which is always false is called Contradiction.

✓ A proposition formula which has both true and false values is called

Statements, which are questions, commands, or opinions are not propositions.

✓ Example: "How are you", "What is your name", are not propositions.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
30
❑ Propositional logic (PL)

❖ Example:

➢ Today is Sunday.

➢ The Sun rises from West. (False)

➢ 3 + 3 = 7 (False)

➢ 5 is a prime number. True

➢ It is raining today. (either T or F)

➢ How are you? (a question is not a proposition)

Artificial Intelligence Zelalem F. Ambo University

 Propositional Logic
31

❖ Propositional logic P:

❖ Is defined by Syntax + interpretation + semantics of P

❖ Logical constants: true, false.

❖ A set of connectives: ¬,∧ ,∨ ,⇒ ,⇔

❖ Wrapping parentheses: ( … )

❖ Literal: atomic sentence or negated atomic sentence.

❖ User defines the semantics of each propositional symbol like P,R and Q.

 P means “It is hot”, Q means “It is humid” R means “It is raining”

❖ (P  Q) → R: Means If it is hot and humid, then it is raining”

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
32

Propositional logic: Syntax

Sentence → AtomicSentence | ComplexSentence
AtomicSentence → True | False | P | Q | …
ComplexSentence → (Sentence ) | (Sentence )
| ￢ Sentence
| Sentence ∧ Sentence
| Sentence ∨ Sentence
| Sentence ⇒ Sentence
| Sentence ⇔ Sentence
OPERATOR PRECEDENCE : ￢, ∧, ∨, ⇒, ⇔
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
33

Propositional Logic Syntax

❖ Atomic Proposition: they are atomic sentences that consists of a single

proposition symbol in which they must be either true or false.

✓ Example: a) 2+2 is 4, it is an atomic proposition as it is a true fact.

b) "The Sun is cold" is also a proposition as it is a false fact.

❖ Compound proposition: they are constructed from valid sentences by combining

atomic propositions, using parenthesis and logical connectives.

❖ Example: a) "It is raining today, and street is wet.“¬𝑨, 𝑨 ∧ 𝑩 , (𝑨𝒗𝑩),

b) "Alex is a doctor, and his clinic is in Addis.“(𝑨𝒗𝑩), (𝑨 ⇒ 𝑩), (𝑨 ⇔ 𝑩)

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
34
Propositional logic: semantics
❖ The semantic gives or assigning a meaning to each sentence.
❖ The semantics defines the truth of each sentence with respect to each possible
world.
❖ Are the rules by which we can interpret the sentence in the logic.
❖ The semantics in the propositional logic is defined by:

❖ Interpretation of propositional symbols and constants

❖ Semantics of atomic sentences

❖ Through the meaning of connectives

❖ Meaning (semantics) of composite sentences

Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
35

❑ Propositional logic semantics

❖ Sentences are combined by using five logical connectives:

✓ Conjunction

✓ Disjunction

✓ Implies (implication) /

✓ is equivalent (biconditional)

✓ not (negation)
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
36

❑ Propositional logic: Logical Connectives:

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
37

❑ Propositional logic: Logical Connectives Truth table.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
38

❖ The precedence order of propositional connectors or logical operators are:

Precedence Operators
First Precedence Parenthesis
Second Precedence Negation
Third Precedence Conjunction(AND)
Fourth Precedence Disjunction(OR)
Fifth Precedence Implication
Six Precedence Biconditional
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
39
❖ Assume the following sentences:
▪ It is not sunny this afternoon and it is colder than yesterday.
▪ We will go swimming only if it is sunny.
▪ If we do not go swimming then we will take a canoe trip.
▪ If we take a canoe trip, then we will be home by sunset.
❖ Denote:
❖ p = It is sunny this afternoon
❖ q = it is colder than yesterday
❖ r = We will go swimming
❖ s= we will take a canoe trip
❖ t= We will be home by sunset

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
40

❑ Propositional logic:

❖ Some composite sentences may always (under any interpretation)

evaluate to a single truth value:

A. Contradiction and Tautology

➢ Some composite sentences may always (under any interpretation)
evaluate to a single truth value:

‒ Contradiction (always False) P ∧ ¬ P

‒ Tautology (always True) P ∨ ¬ P

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
41

❖ Propositional Logic Example:

❖ Construct a truth table for the formula

❖ Show that is Tautology.

❖ Construct a truth table for

❖ Show that and are logically equivalent.

❖ Prove that: [(p → q) ∧ (q → r)] → [p → r] is a contradiction.

❖ Prove (p → q) ∧ (p → r) ≡ p → (q ∧ r). Equivalent.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
42
❑ Propositional logic:

B. Model, validity and satisfiability

▪ A model (in logic): An interpretation is a model for a set of sentences if it

assigns true to each sentence in the set.

▪ A sentence is satisfiable if it has a model;

‒ There is at least one interpretation under which the sentence can evaluate to

True.

▪ A sentence is valid if it is True in all interpretations.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
43

❑ Propositional logic:

B. Model, validity and satisfiability

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
44
Propositional logic: inference rule:

❖ An argument consists of one or more of the statements is alleged information

(premises) and one statement (the conclusion) is an inference from the alleged

information (premises).

❖ The rules of inference are a logical form consisting of premises (or hypotheses)

and draws a conclusion.

❖ A valid argument is when the conclusion is true whenever all the beliefs are

true, and an invalid argument is called a fallacy.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
45

❑ Propositional logic: inference rule:

❖ In AI, we need intelligent computers which can create new logic from old
logic or by evidence, so generating the conclusions from evidence and facts is
termed as Inference.

❖ Inference rules are those rules which are used to describe certain
conclusions.

❖ The inferred conclusions lead to the desired goal state.

❖ In propositional logic, there are various inference rules which can be

applied to prove the given statements and conclude them.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
46

❑ Propositional logic: inference rule:

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
47

Inference Rule Modus Ponens

Inference Rule: Modus Tollens

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
48

Inference Rule: Hypothetical Syllogism

Inference Rule: Disjunctive Syllogism

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
49

❑ Propositional logic: Limitations

❖ We cannot represent relations like ALL, some, or none with propositional logic.

❖ Example:

❖ All the girls are intelligent.

❖ Some apples are sweet.

❖ Propositional logic has limited expressive power.

❖ PL cannot describe in terms of their properties or logical relationships.

❖ It can only represent the facts, which are either true or false.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
50

First order logic

❖ PL is not sufficient to represent the complex sentences or natural

language statements.

❖ The propositional logic has very limited expressive power.

‒ "Some humans are intelligent", or “Student likes A+ grade.“

❖ To represent the above statements, PL logic is not sufficient, so we

required some more powerful logic, such as first-order logic.

Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
51

First order logic

❖ First-order logic is another way of knowledge representation in artificial

intelligence. It is an extension to propositional logic.

❖ FOL is sufficiently expressive to represent the natural language statements in a

concise way.

❖ FOL is also known as Predicate logic or First-order predicate logic.

❖ It is a formal representation of logic in the form of quantifiers.

❖ In predicate logic, the input is taken as an entity, and the output it gives is
either true or false.
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
52

First order logic

▪ First-order logic does not only assume that the world contains facts like

propositional logic but also assumes the following things in the world:

➢ Objects: A, B, people, houses, numbers, colors, wars, theories, squares, pits,

Wumpus, ......

➢ Relations: It can be unary relation such as: red, round, is adjacent, or n-any

relation such as: the sister of, brother of, has color, comes between

➢ Function: Father of, best friend, third inning of, end of, ......
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
53

First order logic

▪ Syntax and semantics of first-order logic

▪ Models for first-order logic:

❖ Models are structure describing the possible worlds under
consideration.
• Provides for finding truth of any sentences.

❖ Propositional logic link propositional symbols to predefined truth

value.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
54

First order logic

❖ Syntax: It defines the way of representing the given predicates.
❖ As these predicates are represented via quantifiers, there are different types of
quantifiers used:
❖ Universal Quantifier(For all/every): When the predicate is indicating about
all/everything, we use for all quantifier.
• It is denoted as " ∀ "
❖ Existential Quantifier(For some): When the predicate is indicating about
some quantity, we use for some quantifier.
• It is denoted as “∃ ”
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
55

First order logic: Syntax

Sentence → AtomicSentence | ComplexSentence
AtomicSentence → Predicate | Predicate(Term, . . .) | Term = Term
ComplexSentence → (Sentence ) | [ Sentence ]
| ￢ Sentence
| Sentence ∧ Sentence
| Sentence ∨ Sentence
| Sentence ⇒ Sentence
| Sentence ⇔ Sentence
| Quantifier Variable, . . . Sentence
Term → Function(Term, . . .) | Constant | Variable
Quantifier → ∀ | ∃
Constant → A | X 1 | John | ・ ・ ・
Variable → a | x | s | ・・・
Predicate → True | False | After | Loves | Raining | ・
Function → Mother | LeftLeg | ・ ・ ・

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
56
First order logic: Semantics
❖ Semantics: It defines the sense of the given predicate.
❖ It allows to make more logical expression by devising its semantics.
❖ Semantics allow us to understand the sentence meaning.
❖ Let’s understand Predicate logic with the help of examples:
‒ Example 1: Lipton is a tea.
‒ Solution: Here, the object is Lipton.
‒ It will be represented as Tea(Lipton).

❖ Note: In this example, there is no requirement of quantifiers because the

quantity is not specified in the given predicate.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
57

First order logic: Semantics

▪ Assertion and Queries in FOL

❖ Add a sentences to KB using Tell. Is called assertion

❖ Assertion john is king, Richard is person and all kings are person.

• TELL(KB, King(John))

• TELL(KB, Person(Richard))

• TELL(KB, ∀𝑥 𝐾𝑖𝑛𝑔 𝑥 ⇒ 𝑃𝑒𝑟𝑠𝑜𝑛(𝑥))

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
58

First order logic: Semantics

▪ ASK Question of the KB Using ASK:

• ASK(KB, King(John)) return True.

▪ Question are called Query or goals.

▪ Query logically entailed by KB should answered affirmatively.

• ASK(KB, King(John)) should return True too.

▪ Can ask quantified query:

• ASK(KB, ∃𝑥 𝑃𝑒𝑟𝑠𝑜𝑛 𝑥 ) who's are a person?

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
59

❖ First-order logic
✓ It is another way of knowledge representation in artificial intelligence.
✓ It is an extension to propositional logic.
✓ it is sufficiently expressive to represent the natural language statements.
✓ First-order logic is also known as Predicate logic or First-order
predicate logic.
✓ It is a powerful language that develops information about the objects in
a more easy way and can also express the relationship between those
objects.

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
60

❖ First-order logic

➢ Atomic sentences are the most basic sentences of first-order logic.

➢ Basic Elements of First-order logic include:

Constant 1, 2, A, John, Mumbai, cat,....

Variables x, y, z, a, b,....

Predicates Brother, Father, >,....

Function sqrt, LeftLegOf, ....

Connectives ∧, ∨, ¬, ⇒, ⇔

Equality ==

Quantifier ∀, ∃

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
61
❑ First-order logic (FOL) models the world in terms of
➢ Objects, which are things with individual identities
➢ Properties of objects that distinguish them from other objects
➢ Relations that hold among sets of objects
➢ Functions, which are a subset of relations where there is only one “value” for any
given “input”

❑ Examples:
 Objects: Students, lectures, companies, cars ...
 Relations: Brother-of, bigger-than, outside, part-of, has-color, visits, precedes, ...
 Properties: blue, oval, even, large, ...
 Functions: father-of, best-friend, second-half, one-more-than

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
62

❖ First-order logic statements can be divided into two parts:

✓ Subject: Subject is the main part of the statement.

✓ Predicate: it can be defined as a relation, which binds two atoms

together in a statement.

❖ We can represent atomic sentences as Predicate (term1, term2,.., term n).

❖ Example:

❖ Chinky is a cat: => cat (Chinky).

❖ Xavi and Ayew are brothers: => Brothers (Xavi, Ayew).

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
63
❖ Quantifiers in First-order logic:

❖ It is a language element which generates quantification, and quantification

specifies the quantity of specimen in the universe of discourse.

❖ These are the symbols that permit to determine or identify the range and scope

of the variable in the logical expression.

❖ There are two types of quantifier:

✓ Universal Quantifier, (for all, everyone, everything)

✓ Existential quantifier, (for some, at least one).

Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
64

❖ Universal Quantifiers :

✓ Universal Quantifier, (for all, everyone, everything)

✓ It is represented by a symbol ∀, which resembles an inverted A.

✓ If x is a variable, then ∀x is read as: For all x, For each x, For every x.

✓ Example: All man drink coffee.

✓ ∀x man(x) → drink (x, coffee).

✓ It will be read as: There are all x where x is a man who drink coffee.
Artificial Intelligence Zelalem F. Ambo University
 Logical Representation
65
❖ Existential Quantifiers :

✓ Existential quantifier, (for some, at least one, there exists a 'x.’).

✓ Example: ∃x: boys(x) ∧ intelligent(x)

✓ It will be read as: There are some x where x is a boy who is intelligent

Example:
✓ Not all students like both Mathematics and Science.

✓ In this question, the predicate is "like(x, y)," where x= student, and y= subject.

✓ Since there are not all students, so we will use ∀ with negation,

✓ So following representation for this:

¬∀ (x) [ student(x) → like(x, Mathematics) ∧ like(x, Science)].

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
66
Some Examples of First-Order using quantifier:

1. All birds fly.

✓ In this question the predicate is "fly (bird)."

✓ And since there are all birds who fly so it will be represented as follows.

✓ ∀x bird(x) →fly(x).

2. Every man respects his parent.

✓ In this question, the predicate is "respect(x, y)," where x=man, and y= parent.

✓ Since there is every man so will use ∀, and it will be represented as follows:

✓ ∀x man(x) → respects (x, parent).

Artificial Intelligence Zelalem F. Ambo University

 Logical Representation
67
Some Examples of First-Order using quantifier:

Artificial Intelligence Zelalem F. Ambo University

 Knowledge Reasoning
68
▪ There are three factors which are put into the machine, which makes it valuable:

❖ Knowledge: The information related to the environment is stored in the

machine.

❖ Reasoning: The ability of the machine to understand the stored knowledge.

❖ Intelligence: The ability of the machine to make decisions on the basis of the
stored information.

Artificial Intelligence Zelalem F. Ambo University

 Knowledge Reasoning
69
What is Reasoning?

❖ It is a formal manipulation of symbols representing a collection of believed

propositions to produce representations of new ones.

❖ Reasoning bridges the gap between what is represented and what is believed.

❖ The reasoning is the mental process of deriving logical conclusion and making

predictions from available knowledge, facts, and beliefs.

❖ Reasoning is a way to infer facts from existing data.

❖ It is a general process of thinking rationally, to find valid conclusions.

Artificial Intelligence Zelalem F. Ambo University

 Knowledge Reasoning
70

What is Reasoning?
❖ Or we can say, "Reasoning is a way to infer facts from existing data."

❖ In AI, the reasoning is essential so that the machine can also think rationally as a

human brain, and can perform like a human.

❖ In AI Reasoning may be happened in two ways:

❖ Reasoning with Certainty and

❖ Reasoning with Uncertainty(Probabilistic)

Artificial Intelligence Zelalem F. Ambo University

 Knowledge Reasoning
71

Revision on Logic

Artificial Intelligence Zelalem F. Ambo University

 Probabilistic Reasoning
72

Probabilistic Reasoning
❖ Till now, we have learned KR using FOL and PL with certainty, which means we were

sure about the predicates.

❖ So to represent uncertain knowledge, where we are not sure about the predicates, we need

uncertain reasoning or probabilistic reasoning.

❖ Probabilistic Reasoning is the study of building network models which can reason under

uncertainty, following the principles of probability theory.

❖ In probabilistic reasoning, we combine probability theory with logic to handle the

uncertainty.
Artificial Intelligence Zelalem F. Ambo University
 Probabilistic Reasoning
73

Probabilistic Reasoning
❖ Need of probabilistic reasoning in AI:

‒ When there are unpredictable outcomes.

‒ When specifications or possibilities of predicates becomes too large to handle.

‒ When an unknown error occurs during an experiment.

❖ In probabilistic reasoning, there are two ways to solve problems with uncertain

knowledge:

➢ Bayes' rule

➢ Bayesian Statistics
Artificial Intelligence Zelalem F. Ambo University
 Probabilistic Reasoning
74

Probabilistic Reasoning
❖ Probability:
▪ Probability can be defined as a chance that an uncertain event will occur.
▪ It is the numerical measure of the likelihood that an event will occur.
▪ The value of probability always remains between 0 and 1 that represent ideal
uncertainties.
❖ Probability:

1. 0 ≤ P(A) ≤ 1, where P(A) is the probability of an event A.

2. P(A) = 0, indicates total uncertainty in an event A.
3. P(A) =1, indicates total certainty in an event A.
Artificial Intelligence Zelalem F. Ambo University
 Probabilistic Reasoning
75

Probabilistic Reasoning
❖ Probability:

We can find the probability of an uncertain event by using the below formula.

𝑵𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒅𝒆𝒔𝒊𝒓𝒆𝒅 𝒐𝒖𝒕𝒄𝒐𝒎𝒆𝒔

probability 𝐨𝐟 𝐨𝐜𝐜𝐮𝐫𝐞𝐧𝐜𝐞 =
𝑻𝒐𝒕𝒂𝒍 𝒏𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒐𝒖𝒕𝒄𝒐𝒎𝒆𝒔

❖ P(¬A) = probability of a not happening event.

❖ P(¬A) + P(A) = 1.

❖ Event: Each possible outcome of a variable is called an event.

Artificial Intelligence Zelalem F. Ambo University

 Probabilistic Reasoning
76

Probabilistic Reasoning
❖ Review of the Probability model:

❖ Sample space 𝛺 : The collection of all possible events is called sample space.

❖ Mutually exclusive : each group is completely distinct and no overlap.

❖ Collectively exhaustive: the sum(jointly) of all your groups covers all possible

options

❖ Event: subset of the sample space.

Artificial Intelligence Zelalem F. Ambo University

 Probabilistic Reasoning
77

Probabilistic Reasoning: Example

❖ Two different coins are tossed randomly. Find the probability of:
❖ Solution: When two different coins are tossed randomly, the sample space is given
by
▪ Sample space S = {HH, HT, TH, TT}
▪ Therefore, n(S) = 4.
▪ (i) getting two heads:
▪ Let E1 = event of getting 2 heads. Then,
▪ E1 = {HH} and, therefore, n(E1) = 1.
▪ Therefore, P(getting 2 heads) = P(E1) = n(E1)/n(S) = 1/4.

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based Systems
78

What is Knowledge-based Systems

❖ A system which is built around a knowledge base. i.e. a collection of knowledge,

taken from a human, and stored in such a way that the system can reason with it.

❖ What is knowledge?

❖ Knowledge is the sort of information that people use to solve problems.

❖ Knowledge may be:

✓ specific or general

✓ exact or fuzzy

✓ procedural or declarative

Artificial Intelligence Zelalem F. Ambo University

 Knowledge-based Systems
79

❖ What is an expert system?

 A particular kind of knowledge-based system

 One in which the knowledge, stored in the knowledge base, has been
taken from an expert in some particular field.

❖ Experts have three qualities:

 They make good decisions

 They make those decisions quickly

 They are able to cope with a wide range of problems.

Artificial Intelligence Zelalem F. Ambo University

.
80

End of Chapter

Many Thanks!
Artificial Intelligence BY: Zelalem Ambo University