Artificial Intelligence (AI)

Chapter - 4
Knowledge and Reasoning
Content
• Knowledge Representation

• Knowledge-Based Systems

• Logical Agents

• Propositional Logic

• Inference in Propositional Logic

• Predicate (First-Order)Logic

• Inference in First-Order Logic

Knowledge
 Knowledge: includes facts about the real world entities and the relationship between
them
 Knowledge-based Systems (KBSs) are useless without the ability to represent knowledge.
 Why Knowledge is important ?
•It enables to:
•Answer users queries
•Make quality decisions - select courses of actions, etc.
•Automate reasoning
•Discover new facts.
•Deduce new facts that follow from the KB
 Hence, there is a need to represent knowledge to ease the development of an
intelligent system.
Knowledge-based Agent (KBA)
 Agents know about their world, and reasoning about their possible courses of action.

 KBA begins with some knowledge of the world and of its actions.
• It uses logical reasoning to maintain a description of the world as new percepts arrive
• Learn new facts/knowledge that are inferred and unseen by current percepts
• Deduce a course of actions that will achieve its goals

 One can also design an autonomous agent that

• learns and construct knowledge with less human interventions

4
Knowledge engineering (KE)
 KE is the process of building a knowledge base through extracting the knowledge from
the human expert.
 Knowledge engineering is the process of
• Extracting the knowledge from the human expert.
• Choose knowledge representation formalism
• Choose reasoning and problem solving strategy.

Knowledge Knowledge
acquisition Representation
(Extract knowledge (Choose KR Method & Knowledge Base
of Human Expert) reasoning strategy)

A knowledge engineer is someone who investigates a particular domain, determines what

concepts are important in that domain, and creates a formal representation of the objects and
relations in the domain. 5
Cont.
 A knowledge engineer has to decide what objects and relations are worth representing,
and which relations hold among which objects
 The two main tasks of KE
 Knowledge acquisition: The knowledge engineer interview the real human experts to be
educated about the domain and to elicit the required knowledge
 Knowledge Representation: Techniques such as logic are a powerful tool for KR and
reasoning
 Knowledge base is used to store a set of facts and rules about the domain expressed in a
suitable representation language
• Each individual representation are called sentences
• Sentences are expressed in a (formal) knowledge representation (KR) language
Knowledge Representation & Reasoning
 Knowledge Representation (KR): express knowledge explicitly in a computer-
tractable way such that the agent can reason out.
 Parts of KR language:
• Syntax of a language: describes the possible configuration to form sentences.
E.g.: if x & y denote numbers, then x > y is a sentence about numbers
• Semantics: determines the facts in the world to which the sentences refer.
E.g.: x > y is false when y is greater than x and true otherwise
 Reasoning: is the process of constructing new sentences from existing facts in the KB.

7
Logic as KR
 A Logic is a formal language in which knowledge can be represented such that
conclusions can easily be drawn.
• It is a declarative language to declare sentences and deduce from sentences.
 Components of a formal logic include syntax, semantics, reasoning and inference
mechanism.
• Syntax: Describes how to make sentences
E.g. mycar (red) is ok, but mycar(grey or green) is not.
• Semantics: Express what sentences mean, in terms of a mapping to real world.
E.g. mycar (red) means that my car is red.
• Reasoning: done using a set of rules. It helps to draw new conclusions from existing
statements in the logic.

8
Logic as KR
 Logic is a language for reasoning and collection of rules are used while doing
logical reasoning
Why formal languages (Logic) ?
 An obvious way of expressing or representing facts and thoughts is by writing them in a
natural language such as English, Amharic, etc. However,
• The meaning of a sentence depends on the sentence itself and on the context on which the
sentence was spoken
E.g. Look!
• Natural languages show ambiguity. A single sentence can usually be interpreted in more than
one way. E.g. Small dogs and cats.

 Ambiguity makes reasoning difficult and incomplete.

• Hence we need formal languages to express facts and concepts in an unambiguous and well-
defined way.
formal language - a language designed for use in situations in which natural
language is unsuitable, as for example in mathematics, logic, or computer
10
programming.
Propositional logic(PL)

 A simple language useful for showing key ideas and definitions

 PL allows facts about the world to be represented as sentences formed from:
 Logical constants: True, False
 Proposition symbols (P, Q, R, …) are used to represent facts about the world:
E.g. P = "It is hot“, Q = "It is humid“, R = "It is raining“
 Logical connectives: not (), and (), or (), implies (), is equivalent, if and
only if ().
 Precedence order from highest to lowest is:  ,  , , , 
E.g. The sentence P v Q  R  S is equivalent to [(P) v (Q  R)]  S
 Parenthesis ( ): Used for grouping sentences and to specify order of precedence

11
Propositional logic (PL) sentences
 A sentence: is made by linking prepositional symbols together using logical
connectives.
• There are atomic and complex sentences.
• Atomic sentences consist of propositional symbol (E.g. p, q, true, false)
• Complex sentences are combined by using connectives or parenthesis:
• While S and T are atomic sentences, S  T, (S  T), (S  T), (S  T), and (S  T) are
complex sentences.
 Examples: Given the following sentences about the “weather problem” convert them
into PL sentences:
• “It is humid.”: Q
• “If it is humid, then it is hot” : Q  P
• “If it is hot and humid, then it is raining”: (P  Q)  R
12
Exercise
Examples: Convert the following English sentences to Propositional logic
Let A = Lectures are active and R = Text is readable, P = Kebede will pass the exam,
then represent the following:
 The lectures are not active: A
 The lectures are active and the text is readable: A  R
 Either the lectures are active or the text is readable: A V R
 If the lectures are active, then the text is not readable: A   R
 The lectures are active if and only if the text is readable: A  R
 If the lectures are active, then if the text is not readable, kebede will not pass the exam:
A  (R  P )
13
Inference In PL
• Modus Ponens

• Modus Tollens

• Hypothetical Syllogism

• Disjunctive Syllogism

• Addition
Terminology
 Valid sentence: A sentence is valid sentence if and only if it is True under all possible
interpretations in all possible worlds.
• Example: “It’s raining or it’s not raining.” (R  R).

 Satisfiable: A sentence is satisfiable if and only if there is some interpretations in some

world for which the sentence is True.
• Example: “It is raining or it is humid”. R v Q

 Unsatisfiable: A sentence is unsatisfiable if and only if it is False under all

interpretations. The world is never like what it describes.
• Example: “It’s raining and it's not raining.” R  R
15
Terminology
 Entailment:
• New sentences are generated that are necessarily true, given that the old sentences are
true.
• α ⊨ β read as “α entails β”, or “β follows logically from α”
• Meaning that in any world in which α is true, β is true as well.
• E.g. R ⊨ Q
 Derivation:
•α ⊢ β read as “α derives β”
• Meaning that using derivation rule “from sentence α, we can obtain sentence β”
•E.g. ¬(A V B) ⊢ (¬A  ¬B)

16
Logical equivalence
Two sentences are logically equivalent if and only if they are true in same models

pνq≡qνp Commutativity of disjunction

pΛq≡qΛp Commutativity of conjunction
(p Λ q) Λ r ≡ p Λ (q Λ r) Associativity of conjunction
(p ν q) ν r ≡ p ν (q ν r) Associativity of disjunction
( ( p) ≡ p Double Negation elimination
pq≡qp contraposition
pq≡pνq implication elimination
Ø(p ν q) ≡ ( p Λ q) De-Morgan
Ø(p Λ q) ≡ ( p ν  q) De-Morgan
(p  q) ≡ (p q) Λ (q  p) Biconditional elimination
p Λ (q ν r) ≡ (p Λ q) ν (p Λ r) Distributive of Λ over ν
17
p ν (q Λ r) ≡ (p ν q) Λ (p ν r) Distributive of ν over Λ
Propositional logic is a weak language
 PL cannot handle even a domain with small worlds.
• The problem is that there are just too many propositions to handle since it only
has one representational device: the proposition

 In PL world consists of just facts. It is hard to:

• Identify individuals: E.g. jack, 3
• Describe properties of (or relations between) individuals. E.g. Belete is taller than Gelaw
• Generalize for a given universe. E.g., all triangles have 3 sides

18
Cont.
First Order Logic
 FOL is type of PC (Predicate calculus)

 First-Order Logic (FOL) is expressive enough to concisely represent any kind of

situation that are expressed in natural language.
• Whereas propositional logic assumes the world contains facts,
• First-order logic (like natural language) assumes the world contains
• Objects: people, houses, numbers, colors, wars, …
• Relations: red, round, brother of, bigger than, part of, comes between, …
• Functions: father of, best friend, one more than, plus, …

20
FOL: Basic elements
• Constants: names (like Jons, Kebede, …), numbers (like 1, 2, … n), ...
• Predicates: Predicates used to relate one object with another. E.g. brotherOf, >,...
• Functions: sqrt, leftLegOf,...
• Variables: x, y, a, b,... Important to increase generalization capability of KB
• Connectives: ¬, ⇒, ∧, ∨, ⇔
• Equality: =
• Quantifiers: ∀, ∃
• Specify whether all or some objects satisfy properties or relations between objects
• Two standard quantifiers:
• Universal - ∀ - (for all, for every) and Existential - ∃ - (there exists, some)

FOL represents objects and relations between objects, variables, and quantifiers in
addition to propositions
FOL Sentence structure
 In FOL the basic unit is a predicate structure also called sentence which represent facts.
predicate (argument/terms)
 A predicate is the one that says something about the subject. E.g., Abebe is tall
• Subject: Abebe, represented as: tall(Abebe)
 Predicate also refers to a particular relation between objects
• Example: likes(X, richard)
 A predicate statement takes the value true or false
 Terms/arguments refer to objects and can be any of:
 Constant symbol, such as ‘chocolate’, Example: likes(abebe, chocolate);
 Variable symbol, such as X ,
 Functions, such as motherof(fred), father-of( father-of( john))
E.g. friends(motherof(jonas), motherof(semu))
22
Sentences
 Atomic sentences: formed from a predicate symbol followed by a parenthesized list of terms
Atomic sentence = predicate (term1,...,termn)
Example: Brother(John, Richard)
Atomic sentences can have arguments that are complex terms (e.g. term = function (term1,...,termn) )
Example: married(fatherof(Richard),motherof(John))

 Complex sentences: complex sentences are made by combining atomic sentences using connectives:
S, S1  S2, S1  S2, S1  S2, S1  S2,
Example. likes(john, mary)  tall(mary)
tall(john)  handsome(john)
Sibling(John, Richard)  Sibling(Richard, John)
 Sentences can also be formed using quantifiers to indicate how to treat variables:
• Universal quantifier: x lovely(x) - Everything is lovely.
• Existential quantifier: x lovely(x) - Something is lovely. 23
Universal quantification

 Universal Quantifiers: makes statements about every object

<variables> <sentence>
• Every elephant is gray:  x (elephant(x)  gray(x))
• Everyone at UoG is smart: X At(X,UoG)  Smart(x)
• All cats are mammals: X cat(x)  mammal(x)
 A common mistake to avoid
• Typically,  is the main connective with 
• Common mistake: the use of  as the main connective with :
x At(x,UoG)  Smart(x) is true if “Everyone is at UoG & everyone is smart”

24
Existential quantification
 Makes statements about some objects in the universe
<variables> <sentence>
• Someone at UoG is smart: x At(x,UoG)  Smart(x)
• There is a white cat: x (cat(X) ^ white(X))

 Common mistake to avoid

• Typically,  is the main connective with 
• Common mistake: using  as the main connective with 

25
Nested quantifiers
 x,y parent(x,y)  child(y,x)
•For all x and y, if x is the parent of y then y is the child of x.
 x y Loves(x,y)
•There is a person who loves everyone in the given world
 y x Loves(x,y)
• Everyone in the given universe is loved by at least one person

Properties of quantifiers
• x y is the same as y x
• x y is the same as y x
• x y is not the same as y x

26
Cont.
 Quantifier duality: each can be expressed using the other, using negation ()
• x Likes(x,icecream)
• x Likes(x,icecream)
• Everyone likes ice cream means that there is nobody who dislikes ice cream
• x Likes(x,cake)
• x Likes(x,cake)
• There is someone who likes cake means that there is no one who dislikes cake
Example
 Sentences can have several quantifiers, e.g.,
x y loves(x, y)
x handsome(x)  y loves(y, x)

 Represent the following in FOL:

• Everything in the garden is lovely  x in(x, garden)  lovely(x)
• Everyone likes ice cream  x likes(x, ice-cream)
• Peter has some friends  y friends(y, Peter)
• John plays the piano or the violin plays(john, piano) v plays(john, violin)
• Some people like snakes  x(person(x) Λ likes(x, snakes))
• Winston did not write Hamlet  write( winston, hamlet)
• Nobody wrote Hamlet  x write(x, hamlet)

28
The End