Artificial Intelligence 3451: UNIT: 03 Knowledge Representation (First Order Logic)

Artificial Intelligence 3451
UNIT: 03
Knowledge Representation(First Order Logic )
Lecture: 08
Farhad Muhammad Riaz

Limitations of Propositional logic
• 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.
• In propositional logic, we cannot describe statements
in terms of their properties or logical relationships.
Theory of First-order Logic
 First-order logic is also called Predicate logic and First-
order predicate calculus (FOPL).
 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.
Syntax and Semantics of FOPL
 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 “Ǝ”
 Nested Quantifiers:
 It is the nesting of the same type of quantifier. One predicate is nested under the
other predicate.
 Atomic Sentences:
 These sentences are formed via predicate symbols may or may not be followed by a
list of terms.
Example
 Parents(Jawad, Aysha) where Jawad and Aysha are the
parents.
 Complex Sentences:
 These sentences make use of logical connectives to construct more
complex sentences.
 Equality:
 We use the equality symbol to express that two terms refer to the same
object.
 For example, Thirteenth_President(Pakistan)= Dr. Arif-ur-Rehman Alvi.
Here, both LHS is equal to RHS. It means that both terms refer to the same
entity/ person.
 Atomic sentences:
o Atomic sentences are the most basic sentences of first-order logic. These
sentences are formed from a predicate symbol followed by a parenthesis
with a sequence of terms.
o We can represent atomic sentences as Predicate (term1, term2, ......,
term n).
 Example: Ali and umar are brothers: => Brothers(Ali, umar).
Chinky is a cat: => cat (Chinky).
Constant 1, 2, A, John, Mumbai, cat,....
Variables x, y, z, a, b,....
Predicates Brother, Father, >,....
Function sqrt, LeftLegOf, ....
Connectives ∧, ∨, ¬, ⇒, ⇔
Equality ==
Quantifier ∀, ∃
Elements and their symbols in
Predicate Logic
 The elements for which different symbols are defined
are:
 Objects:
 It refers to an entity that exists in the real world.
 For example, Jawad, John, etc. are referred to as Objects.
 Functions:
 Any function performed by the object/on the object.
 For example, LeftLeg, writes, eats, etc. are some of the functions.
 Relations:
 The relation of an object with the other object defines its relation.
 For example, brother, mother, king, etc. are some types of relations which
exist in the real world.
Symbols used to represent these
elements
 Constant Symbols:
 These symbols are used to represent the objects.
 Predicate Symbols:
 These symbols are used to represent relations.
 Function Symbols:
 These symbols are used to represent the functions performed
by the object.
Semantic
 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 below
examples:
 Example 1: Lipton is a tea.
 Solution: Here, the object is Lipton.
 It will be represented as Tea(Lipton).
 Example 2: Every man is mortal.
 Solution: Here, the quantifier is the universal identifier, and the object is
man.
 Let x be the man.
 Thus, it will be represented as x: man(x) → mortal(x).
 Example 3: All girls are intelligent.
 Solution: Here, we are talking about all girls. It means universal quantifier
will be used. The object is girls. Let, y be the girls.
 Therefore, it will be represented as girls(y) → intelligent(y).
 Example 4: All that glitters is not gold.
 Solution: Here, we will represent gold as x.
 Therefore, it will be represented as glitters(x) → ¬gold(x).
 Example 5: Some boys are obedient.
 Solution: Here, boys are objects. The quantifier used will be existential
quantifier. Let x be the boys. Thus, it will be represented as
 Ǝx: boys(x) → obedient(x).
 Example 6: Some cows are black and some cows are white.
 Solution: Let, x be the cows. Therefore, it will be represented as:
 Ǝx: cows(x) → black(x) Ʌ white(x).
Knowledge Engineering in FOPL
 Knowledge engineering is the process where a knowledge
engineer investigates a specific domain, learn the
important concepts regarding that domain, and creates the
formal representation of the objects and relations in that
domain.
Knowledge Engineering Process
 An engineering term is used when we are talking about
any project.
 Therefore, knowledge engineering over a project
involves the below described steps:
Inference in First-order Logic
 While defining inference, we mean to define effective
procedures for answering questions in FOPL.
 FOPL offers the following inference rules:
 Inference rules for quantifiers
 Universal Instantiation (UI):
 In this, we can infer any sentence by substituting a ground term (a
term without variables) for the variables.
 In short, when we create the FOPL of the given statement, we can
easily infer any other statement using that FOPL
 Notation:
 Let, SUBST( θ , α ) be the result of the given sentence α , and
its substitute is θ.
where v is the variable and g is the ground term.

 For example: Every man is mortal.
 It is represented as ∀ x: man(x) → mortal(x).
 In UI, we can infer different sentences as:
 man(John) → mortal(John)
 man(Aakash) → mortal(Aakash), etc.
 Existential Instantiation(EI):
 In EI, the variable is substituted by a single new constant
symbol.
 Notation:
 Let, the variable be v which is replaced by a constant symbol k for any
sentence α The value of k is unique as it does not appear for any other
sentence in the knowledge base.
 Such type of constant symbols are known as Skolem constant.
 As a result, EI is a special case of Skolemization process.
 For example:
 ∃x:steal(x, Money).
 We can infer from this: steal(Thief, Money)
Example
 Jack owns a dog.
 Every dog owner is an animal lover.
 No animal lover kills an animal.
 Either Jack or Curiosity killed the cat, who is named Tuna.
 Did Curiosity kill the cat?
knowledge base
 Forward Chaining:
 In forward chaining, we start with the atomic sentences in the
knowledge base and apply Modus Ponen in forward direction.
Also adding new sentences until any inference is not made.
 Backward Chaining:
 This algorithm is opposite of forward chaining algorithm. It
works in backward direction. It starts from the goal, chain
through the rules to search the known facts and infer sentences
from the given facts in backward direction.
Example knowledge base
 The law says that it is a crime for an American to sell weapons
to hostile nations. The country Nono, an enemy of America,
has some missiles, and all of its missiles were sold to it by
Colonel West, who is American.
 Prove that Col. West is a criminal

it is a crime for an American to sell weapons to hostile nations:
American(x)  Weapon(y)  Sells(x,y,z)  Hostile(z)  Criminal(x)
Nono … has some missiles, i.e., x Owns(Nono,x)  Missile(x):
Owns(Nono,M1) and Missile(M1)
… all of its missiles were sold to it by Colonel West
Missile(x)  Owns(Nono,x)  Sells(West,x,Nono)
Missiles are weapons:
Missile(x)  Weapon(x)
An enemy of America counts as "hostile“:
Enemy(x,America)  Hostile(x)
West, who is American …
American(West)
The country Nono, an enemy of America …
Enemy(Nono,America)

Artificial Intelligence 3451: UNIT: 03 Knowledge Representation (First Order Logic)

Uploaded by

Copyright:

Available Formats

Artificial Intelligence 3451: UNIT: 03 Knowledge Representation (First Order Logic)

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Artificial Intelligence 3451: UNIT: 03 Knowledge Representation (First Order Logic)

Uploaded by

Copyright:

Available Formats

Artificial Intelligence 3451

Farhad Muhammad Riaz

Predicates Brother, Father, >,....

Function sqrt, LeftLegOf, ....

where v is the variable and g is the ground term.

 Prove that Col. West is a criminal

You might also like