Artificial Intelligence
Logical Agents – Predicate Logic
Contents
Logical Agents
Predicate Logic – Introduction
Limitations of PL Propositional logic
limited expressiveness
becomes impractical, even for very small worlds
Not possible to represent relations like all, some, or none with
propositional logic
Cannot represent objects, properties and relationships
Roommate Carrying Umbrella
there is an object we call Roommate,
there is an object we call Umbrella,
there is a relationship Carrying between these two objects
Formally, none of this meaning is there
Roommate Carrying Umbrella by P
Language of thoughts
Natural languages are very expressive
Natural languages also suffer from ambiguity, a problem for a
representation language
Combining the formal and natural languages
foundation of propositional logic—a declarative, compositional semantics
that is context-independent and unambiguous
representational ideas from natural language while avoiding its drawbacks
Nouns and noun phrases refer to objects (squares, pits, wumpuses)
Verbs and verb phrases refer to relations among objects (is breezy,
is adjacent to, shoots)
Relations are functions—relations in which there is only one
“value” for a given “input.”
Examples
“One plus two equals three.”
Objects: one, two, three, one plus two
Relation: equals
Function: plus
(“One plus two” is a name for the object that is obtained by applying the function “plus” to
the objects “one” and “two.” “Three” is another name for this object.)
“Squares neighboring the wumpus are smelly.”
Objects: wumpus, squares
Property: smelly
Relation: neighboring
“Evil King John ruled England in 1200.”
Objects: John, England, 1200
Relation: ruled
Properties: evil, king
predicate symbols stand for relations
Predicate Logic
is built around objects and relations
extends the syntax of propositional calculus with predicates
and quantifiers
P(X) – P is a predicate
Atomic sentence is formed from a predicate symbol
optionally followed by a parenthesized list of terms/objects.
Atomic sentence = predicate (term1,...,termn)
Ex:
Brother(Richard, John)
Married(Father(Richard), Mother(John))
Brother(Richard, John) ∧ Brother(John, Richard)
Syntax of FOL: Basic elements
The basic syntactic elements of FOL are the symbols that
stand for objects, relations & functions.
Constants (stand for objects) Sarah, A, B,...
Predicates (stand for relation) Brother, Round,...
Functions (stand for function) FatherOf,...
Variables x, y, a, b,...
Connectives , , , ,
Equality =
Quantifiers ,
Older (S1, 20) Younger(S1, 20)
Universal and Existential quantifier
Quantifiers and
- For all:
x P(x) is read “For all x’es, P (x) is true”
E.g., for all engineering students, they are smart.
- There Exists:
x P(x) is read “there exists an x such that P(x) is true”.
E.g., there exist a engineering student who is not smart.
Relationship between the quantifiers:
x P(x) ¬ (x)¬P(x)
“If There exists an x for which P holds, then it is not true that for all x
P does not hold”.
x, y, z, … can refer to multiple objects
Examples
All cats are mammals - x Cats(x) => Mammals(x)
for all x, if x is a cat, then x is a mammal
Everyone at IIITK is smart - x At(x, IIITK) => Smart(x)
Someone at PSU is smart - x At(x, PSU) Smart(x)
Nested quantifiers - ∀ x ∀ y Brother(x, y) ⇒ Sibling(x, y)
mixtures
∀x ∃y Loves(x, y) - Everybody loves somebody
∃y ∀x Loves(x, y) - There is someone who is loved by everyone
Try
All food are edible
Brothers are siblings
One's mother is one's female parent
Richard has at least two brothers
Try
All food are edible
x food( x) => edible( x)
Brothers are siblings
x,y Brother(x, y) Sibling(x, y).
One's mother is one's female parent
m,c Motherof(c) = m (Female(m) Parent(m, c))
Richard has at least two brothers
∃x,y Brother(x, Richard) ∧ Brother(y, Richard) (why?)
∃x,y Brother(x, Richard) ∧ Brother(y, Richard) ∧ ¬(x = y)
Activity
Aditya, Mahesh and Lokesh belong to the Dept Champions
Club.
Every member of the club is either a soccer or a cricketer .
No cricketer likes rain, and all soccers like snow
Lokesh dislikes whatever Aditya likes and likes whatever
Aditya dislikes
Aditya likes rain and snow
Is there any member of the club who is cricketer but not
soccer?
Translate this problem into FOL Sentences?
Activity
S(x) means x is a soccer
C(x) means x is a cricketer
L(x,y) means x likes y
The English sentences in the prev slide can be translated into
the following FOL:
x Clubmember(x) => S(x) V C (x)
~ x C(x) L(x,rain)
x S(x) => L(x,snow)
y L(Lokesh, y) <=> ~L(Aditya,y)
L(Aditya, rain) ^ L(Aditya,snow)
Example of inference rules
“It is illegal for students to copy music.”
“Joe is a student.”
“Every student copies music.”
Is Joe a criminal?
Knowledge Base:
x, y Student( x) Music( y ) Copies( x, y ) (1)
Criminal(x)
Student(Joe) (2)
x y Student(x) Music(y) Copies( x, y ) (3)
Example cont...
From : x y Student(x) Music(y) Copies( x, y )
y Student(Joe) Music(y) Copies( Joe, y )
Existential Elimination Universal Elimination
Student(Joe) Music(SomeSong) Copies( Joe, SomeSong)
Modus Ponens
Criminal(Joe)
Example partially borrowed from http://sern.ucalgary.ca/courses/CPSC/533/W99/presentations/L1_9A_Chow_Low/main.html
Prolog
Prolog is a logic programming language
Used for implementing logical representations and for
drawing inference
16
Prolog
17
Example 1
Example 2
The End…
20
