Limitation of Propositional Logic

■ The facts:
– “peter is a man”, “paul is a man”, “john is a man” can be symbolized by
P, Q and R respectively in propositional logic,
■ Can’t draw any conclusions about similarities between
P, Q and R.
■ Better to represent these facts as
– MAN(peter), MAN(paul) and MAN(john).
■ Even more difficult to represent sentences like“All men are
mortal” in propositional logic.
• – Such sentences really need quantification.
■ In Predicate Logic, these limitations are removed to great extent.
■ Predicate Logic is logical extension of propositional logic.
■ First Order Predicate Logic is one where the
quantification is over simple variables.
 Predicate Calculus
■ It has three more logical notions as comparedto
propositional calculus.
– Terms
– Predicates
– Quantifiers (universal or existential quantifiers i.e. “for all' and
“there exists”)
■ Term is
– a constant (single individual or concept i.e.,5,john etc.),a variable that stands for
different individuals,
– a function: a mapping that maps n terms to a term i.e., if f is n- place function
■ symbol and: a
Predicate t1,relation that maps
…, tn are terms, then f(t1,n…,
terms
tn) is atoterm.
a truth value true (T)
or false (F).
– LOVE (john , mary)
– LOVE(father(john), john)
– LOVE is a predicate. father is a function.
■ Quantifiers: Variables are used in conjunction with quantifiers.
– There are two types of quantifiers viz.., “there exist” (∃) and “for all”
(∀).
– “every man is mortal” can be representedas (∀x) (MAN(x) →
MORTAL(x)).
Examples
■ A statement “x is greater than y” is represented in predicate
calculus as GREATER(x, y).
■ It is defined as follows:
GREATER( x, y) T , if x > y
= = F,
otherwise
■ The predicate names GREATER takes two terms and map to T
or F depending upon the values of their terms
■ A statement “john loves everyone” is represented as
– (∀x) LOVE(john , x) which maps it to true when x gets instantiated to
actual values.
■ A statement “Every father loves his child” is represented as
– (∀x) LOVE(father(x), x).
– Here father is a function that maps x to his father.
■ The predicate name LOVE takes two terms and map to T or F
depending upon the values of their terms.
Example
Example 1: Translate the text "Every man is mortal.
John is a man. Therefore, John is mortal" into a FOPC
formula.
Solution:Let MAN(x), MORTAL(x) represent that x is a man and
x is mortal respectively.
■
■ John
Everyisman is mortal : (∀x) MAN(john)
a man (MAN(x) → MORTAL(x))
■ John is mortal
: MORTAL(john)
The whole text can: be represented by the following formula.
(∀x) ((MAN(x) → MORTAL(x)) Λ MAN(john))→ MORTAL(john)
Example 2. “ John loves everyone”
∀x: loves(John , x)
• some people like reading and hence they gain good
knowledge”
∃ x: { [person(x)∧ like (x , reading)] gain(x, knowledge) }
• “lord Haggins has a crown on his head”
∃ x: {crown(x)∧onhead (x , Haggins)}
Inference Rules in Predicate Logic
Modus Ponen Rule:
Lemma 1: If α : ( P(x) Q(x) )
(∀x) → Q(c) and
β : P(c) are two formulae, then is a logical
consequence of α and β , where c is a constant.
Modus Tollen Rule:
Lemma 2: If α : (∀x) ( P(x) → Q(x) ) and β :~ Q(c) are
two formulae, then ~ P(c) is a logical consequence of α and
β, where c is a constant.
Example
I. Translate the following English sentences into Predicate Logic
– Everyone is loyal to someone.
– All Romans were either loyal to Caesar or hated him.
– For every number, there is one and only one immediate
successor.
– There is no number for which 0 is immediate successor.
 Nested Quantifiers
• We can use both ∀ and ∃ seperately
• Ex: “ everybody loves somebody ”
∀x: ∃y: loves ( x , y)
• Connection between ∀ and ∃
• “ everyone dislikes garlic”
∀ x: ¬ like ( x , garlic )
This can be also said as:
“there does not exists someone who likes garlic”
¬ ∃x: like (x, garlic)

All Romans were either loyal to Caesar or hated him.

∀x: Roman(x) → loyalto (x, Caesar) ∨ hate(x, Caesar)

Every one is loyal to someone.

∀x: ∃y: loyalto(x, y) ∃y: ∀x: loyalto(x, y)

People only try to assassinate rulers they are not loyal to.

∀x: ∀y: person(x) ∧ ruler(y) ∧ tryassassinate(x, y)→ ¬loyalto(x, y)

Some more examples
1. “all indoor games are easy”
∀x: indoor_game( x) easy(x)
2. “Rajiv likes only cricket”
Like(Rajiv, Cricket)
3. “Any person who is respected by every person is a king”
∃x:∀y: { person(x) ∧ person(y) ∧ respects (y ,x) king( x)}
4. “god help those who helps themselves
∀x: helps( god, helps(x , x))
5. everyone who loves all animals is loved by someone
∀x: [ ∀y: animal (y) loves( x , y) ]

everyone who loves all animals

∃z: loves( z , x ) there exist someone z and z
loves x Thus the predicate sentence is:
∀x: [ [∀y: animal (y) loves( x , y) ] [ ∃z: loves( z , x )
] ]
Unification
● Unification is an algorithm for determining the substitutions needed

to make two predicate calculus expressions match.

● Unification depends on the substitution process.

● It takes two literals as input and makes them identical using

substitution.

● The substitution variables are called Most General Unifier

[(x,y), (2,3)] x=2, y=3

(2/x), (3/y) (2,3), (2,3)

Rules for Unification
● Predicate symbol must be same, atoms or expression with different
predicate symbol can never be unified.
● Number of Arguments in both expressions must be identical.

● Unification will fail if there are two similar variables present in the

expressions.

● Unification can’t be done on two different functions

P(x, g(y)) and P(a, f(z))

a/x

f(z)/g(y)
 Unification
• It’s a matching procedure that compares two literals and
discovers whether there exists a set of substitutions that can make
them identical.
• E.g.

Hate( marcus , Hate (marcus , caesar)

X)
caesar/ X

Hate(X,Y) Hate( john, Z) could be unified as:

John/X andy/z
Unification:
UNIFY(p, q) = unifier θ where SUBST(θ, p) = SUBST(θ, q)

∀x: knows(John, x) → hates(John,

x) knows(John, Jane)
∀y: knows(y, Leonid)
∀y: knows(y, mother(y))
∀x: knows(x, Elizabeth)

UNIFY(knows(John ,x) ,knows(John, Jane)) = {Jane/x}

UNIFY(knows(John, x), knows(y, Leonid)) = {Leonid/x, John/y}
UNIFY(knows(John, x), knows(y, mother(y))) =
{John/y, mother(John)/x}
UNIFY(knows(John, x), knows(x, Elizabeth)) = FAIL
Algorithm Unify(E1,E2): Expression unification
1. if E1 and E2 are constants
then
1.1. if E1=E2
then return { }
1.2. return FAIL
2. if E1 is a variable or E2 is a variable
then
2.1. Exchange E1 with E2 such as E1 to be a variable
2.2. if E1=E2
then return { }
2.3. if E1 occurs in E2
then return FAIL
2.4. return {E1/E2}
3. if E1=simb(t11,…,t1n) and E2=simb(t21,…t2n)
then
3.1 x ← t11, y ← t21
3.2 Rest1 ← t12,…,t1n , Rest2 ← t22,…t2n
3.3 α1 ← Unify(x,y)
3.4 if α1= FAIL
then return FAIL
3.5 G1 ← Rest1 / α1, G2 ← Rest2 / α1
3.6 α2 ← Unify(Rest1, Rest2)
3.7 if α2= FAIL
then return FAIL
else return (α1, α2 )
4. return FAIL
end.
 1. unify((parents X (father X) (mother bill)), (parents bill (father bill) Y))

Unify first elements and apply

return { } return {(mother bill)/Y, bill/X}
substitutions to rest

2. unify(parents, parents) 3. unify((X (father X) (mother bill)),(bill (father bill) Y))

return UFEASR return {(mother bill)/Y}

{bill/X}
4. unify(X,bill) 5. unify(((father bill) (mother bill)),((father bill) Y))
Return {} return {(mother bill)/Y}
UFEASR
6. unify((father bill), (father bill))
11. unify(((mother bill)), (Y))
return { } UFESR return { } UFEASR return { }
return {(mother bill)/Y}

7. unify(father, father) 8. unify((bill), (bill))12. unify((mother bill),

Y)
return { }
UFEASR 13. unify((), ())
9. unify(bill, bill) return { }

10. unify((), ())

 (Original) (parents X (father X) (mother bill)), (parents bill
(father bill) Y)
(parents X (father X) (mother bill)), (parents bill (father bill) mother
bill)

(parents bill (father bill) (mother bill)), (parents bill (father bill) mother
bill)

● p(f(a), g(Y)) and p(X, X)

Ψ1 = p(f(a), g(Y)), and Ψ2 = p(X, X)

led
f ai
SUBST = {f(a) / X}
io n
a t
if ic
Ψ1 = p(f(a),
n
U g(Y)), and Ψ 2
= p(f(a), f(a))

SUBST = {f(a) / g(y)}

Questions
● mgu( h(c,d,g(x,y)), h(z,d,g(g(a,y),z)) )
{ z ≈ c, x ≈ g(a, c), y ≈ c } Unifiable

● mgu( f(g(x,y),c), f(g(f(d,x),z),c) ) Not

unifiable