Artificial Intelligence (AI)
Part - 2, Lecture – 12
Unification in First-order logic
Lecturer: Dr. Md Akhtaruzzaman
Assistant Professor, CSE, MIST
akhter900@gmail.com
June 13, 2021, MIST, Dhaka.
Recap
Unification
Unification Algorithm
Examples
akhter900@gmail.com 2
Inference in FoL
FoL inference rules for quantifier
◦ Universal Generalization (UG)
◦ Universal Instantiation (UI)
◦ Existential Instantiation (EI)
◦ Existential introduction/Generalization (EG)
Exercise
akhter900@gmail.com 3
Unification is a process of making two
different logical atomic expressions identical
by finding a substitution.
Unification depends on the substitution process.
It takes two literals as input and makes them identical
using substitution.
Let Ψ1 and Ψ2 be two atomic sentences and 𝜎 be a
unifier such that, Ψ1 𝜎 = Ψ2 𝜎 , then it can be
expressed as 𝑼𝑵𝑰𝑭𝒀(𝚿𝟏 , 𝚿𝟐 ).
akhter900@gmail.com 4
Example 1:
Find the Most General Unifier (MGU) for
𝑼𝒏𝒊𝒇𝒚{𝑲𝒊𝒏𝒈(𝒙), 𝑲𝒊𝒏𝒈(𝑨𝒑𝒑𝒍𝒆)}
◦ Let Ψ1 = 𝐾𝑖𝑛𝑔(𝑥), Ψ2 = 𝐾𝑖𝑛𝑔(𝐴𝑝𝑝𝑙𝑒)
◦ Substitution 𝜽 = {𝑨𝒑𝒑𝒍𝒆/𝒙} is a unifier for these atoms
◦ By applying this substitution both expressions will be
identical.
◦ Ψ1 = 𝐾𝑖𝑛𝑔 𝐴𝑝𝑝𝑙𝑒 & Ψ2 = 𝐾𝑖𝑛𝑔(𝐴𝑝𝑝𝑙𝑒)
◦ So, MGU is 𝜽 = {𝑨𝒑𝒑𝒍𝒆/𝒙}
akhter900@gmail.com 5
Example 2:
◦ There are two different expressions, 𝑷(𝒙, 𝒚), and 𝑷(𝒂, 𝒇(𝒛)).
◦ Now, make both statements identical to each other (perform the
substitution).
Solution:
◦ 𝑷(𝒙, 𝒚) Expression-1
◦ 𝑷(𝒂, 𝒇(𝒛)) Expression-2
◦ Substitute 𝒙 with 𝒂, and 𝒚 with 𝒇(𝒛) in the first expression, thus it
will be represented as 𝒂/𝒙 and 𝒇(𝒛)/𝒚.
◦ With both the substitutions, the first expression will be identical to
the second expression.
◦ The substitution set will be: [𝒂/𝒙, 𝒇(𝒛)/𝒚].
akhter900@gmail.com 6
The UNIFY algorithm is used for unification, which
takes two atomic sentences and returns a unifier
(substitution set) for those sentences (If exist).
Unification is a key component of all Frst-order
inference algorithms.
It returns FAIL/FALSE if the expressions do not match
with each other.
The substitution variables are called Most General
Unifier (MGU).
akhter900@gmail.com 7
Rules/conditions of the Unification Algorithm
1. Predicate symbol must be same (atoms or expression with
different predicate symbol can never be unified).
𝑷 𝒙, 𝒚 & 𝑸(𝒂, 𝒃) ----- ×
2. Number of Arguments in both expressions must be identical.
𝑷(𝒙, 𝒚, 𝒛), & 𝑸(𝒂, 𝒃) ----- ×
3. Unification will FAIL if there are two similar variables present in the
same expression.
𝑃(𝑿, 𝑿), & 𝑄(𝑎, 𝑓(𝑏)) ----- ×
𝑃(𝒇(𝑿), 𝒇(𝑿)), & 𝑄(𝑎, 𝑓(𝑏)) ----- √
4. Unification will FAIL if 𝚿𝟏 is a variable and 𝚿𝟏 exists in 𝚿𝟐 (and
vice versa).
𝑃(𝑋, 𝒀), & 𝑄(𝑎, 𝑓(𝒀)) ----- ×
akhter900@gmail.com 8
Algorithm
◦ If Ψ1 or Ψ2 is a variable or constant or term, then:
a) If Ψ1 or Ψ2 are identical, then return NIL.
b) Else if Ψ1 is a variable,
a. then if Ψ1 occurs in Ψ2 , then return FALSE
b. Else return { (Ψ2 /Ψ1 )}.
c) Else if Ψ2 is a variable,
a. If Ψ2 occurs in Ψ1 then return FALSE
b. Else return { (Ψ1 /Ψ2 )}.
d) Else return FALSE.
◦ If the initial Predicate symbol in Ψ1 and Ψ2 are not same, then return FALSE.
◦ IF Ψ1 and Ψ2 have a different number of arguments, then return FALSE.
◦ Set Substitution set(SUBST) to NIL.
◦ For 𝑖 = 1 to the number of elements in Ψ1 .
a) Call Unify function with the 𝑖th element of Ψ1 and 𝑖th element of Ψ2 , and put the result into 𝑆.
b) If 𝑆 = failure then returns FALSE
c) If 𝑆 ≠ NIL then do,
a. Apply S to the Ψ1 and Ψ2 .
b. SUBST= APPEND(S, SUBST).
◦ Return SUBST.
akhter900@gmail.com 9
Example 3:
◦ Find the MGU of 𝑼𝑵𝑰𝑭𝒀(𝒑𝒓𝒊𝒎𝒆 (𝟏𝟏), 𝒑𝒓𝒊𝒎𝒆(𝒚))
Solution:
◦ Here, 𝚿𝟏 = 𝒑𝒓𝒊𝒎𝒆(𝟏𝟏) , and 𝚿𝟐 = 𝒑𝒓𝒊𝒎𝒆(𝒚)
◦ So, {𝒑𝒓𝒊𝒎𝒆(𝟏𝟏) , 𝒑𝒓𝒊𝒎𝒆(𝒚)}
◦ 𝑺𝑼𝑩𝑺𝑻 𝜽 = {𝟏𝟏/𝒚}
◦ Thus, {𝒑𝒓𝒊𝒎𝒆(𝟏𝟏) , 𝒑𝒓𝒊𝒎𝒆(𝟏𝟏)} , Successfully UNIFIED.
◦ Unifier: {11/y}.
akhter900@gmail.com 10
Example 4:
◦ Find the MGU of {𝑸(𝒂, 𝒈(𝒙, 𝒂), 𝒇(𝒚)), 𝑸(𝒂, 𝒈(𝒇 𝒃 , 𝒂), 𝒙)}
Solution:
◦ Here, 𝚿𝟏 = 𝑸 𝒂, 𝒈 𝒙, 𝒂 , 𝒇 𝒚 , and 𝚿𝟐 = 𝑸 𝒂, 𝒈 𝒇 𝒃 , 𝒂 , 𝒙
◦ So, 𝑸 𝒂, 𝒈 𝒙, 𝒂 , 𝒇 𝒚 , 𝑸(𝒂, 𝒈 𝒇 𝒃 , 𝒂 , 𝒙)
◦ 𝜽 = {𝒇(𝒃)/𝒙}
◦ {𝑸 𝒂, 𝒈 𝒇 𝒃 , 𝒂 , 𝒇 𝒚 , 𝑸(𝒂, 𝒈 𝒇 𝒃 , 𝒂 , 𝒙)}
◦ 𝜽 = {𝒇(𝒚)/𝒙}
◦ {𝑸 𝒂, 𝒈 𝒇 𝒃 , 𝒂 , 𝒇 𝒚 , 𝑸(𝒂, 𝒈 𝒇 𝒃 , 𝒂 , 𝒇(𝒚))}
◦ 𝚿𝟏 & 𝚿𝟐 are UNIFIED
◦ Unifier = {𝒂Τ𝒂 , 𝒇 𝒃 Τ𝒙 , 𝒇(𝒚)/𝒙}
akhter900@gmail.com 11
Example 5:
◦ UNIFY(knows(Richard, x), knows(Richard, John))
Solution:
◦ Here, 𝚿𝟏 = 𝐤𝐧𝐨𝐰𝐬(𝐑𝐢𝐜𝐡𝐚𝐫𝐝, 𝐱), and 𝚿𝟐 = 𝐤𝐧𝐨𝐰𝐬(𝐑𝐞𝐚𝐜𝐡𝐚𝐫𝐝, 𝐉𝐨𝐡𝐧)
◦ 𝜽 = {𝑱𝒐𝒉𝒏/𝒙}
◦ So, {knows(Reachard, John), knows(Reachard, John)}
◦ Successfully Unified
◦ Unifier = {John/x}
akhter900@gmail.com 12
Example 6:
◦ Find the MGU of {p (X, X), and p (Z, f(Z))}
Solution:
◦ Here, 𝚿𝟏 = p (X, X), and 𝚿𝟐 = p (Z, f(Z))
◦ So, {p (X, X), p (Z, f(Z))}
◦ SUBST θ= {Z/X}
◦ {p (Z, Z), p (Z, f(Z))}
◦ SUBST θ= {f(Z) / Z}, Unification Failed.
akhter900@gmail.com 13
Example 7:
◦ Find the MGU of {𝒑(𝒇(𝒂), 𝒈(𝒀)) and 𝒑(𝑿, 𝑿)}
Solution:
◦ Here, 𝚿𝟏 = 𝒑(𝒇(𝒂), 𝒈(𝒀)), and 𝚿𝟐 = 𝒑(𝑿, 𝑿)
◦ SUBST 𝜽 = {𝒇(𝒂) / 𝑿}
◦ 𝚿𝟏 = 𝒑(𝒇(𝒂), 𝒈(𝒀)), and 𝚿𝟐 = 𝒑(𝒇(𝒂), 𝒇(𝒂))
◦ SUBST 𝜽 = {𝒇(𝒂) / 𝒈(𝒚)}, Unification failed.
akhter900@gmail.com 14
Example 8:
◦ Find the MGU of {p(b, X, f(g(Z))) and p(Z, f(Y), f(Y))}
Solution:
◦ Here, 𝚿𝟏 = 𝒑(𝒃, 𝑿, 𝒇(𝒈(𝒁))) , and 𝚿𝟐 = 𝒑(𝒁, 𝒇(𝒀), 𝒇(𝒀))
◦ { 𝒑(𝒃, 𝑿, 𝒇(𝒈(𝒁))); 𝒑(𝒁, 𝒇(𝒀), 𝒇(𝒀))}
◦ SUBST 𝜽 = {𝒃/𝒁}
◦ { 𝒑(𝒃, 𝑿, 𝒇(𝒈(𝒃))); 𝒑(𝒃, 𝒇(𝒀), 𝒇(𝒀))}
◦ SUBST 𝜽 = {𝒇(𝒀) /𝑿}
◦ { 𝒑(𝒃, 𝒇(𝒀), 𝒇(𝒈(𝒃))); 𝒑(𝒃, 𝒇(𝒀), 𝒇(𝒀))}
◦ SUBST 𝜽 = {𝒈(𝒃) /𝒀}
◦ { 𝒑(𝒃, 𝒇(𝒈(𝒃)), 𝒇(𝒈(𝒃)); 𝒑(𝒃, 𝒇(𝒈(𝒃)), 𝒇(𝒈(𝒃))} Unified Successfully.
◦ Unifier = { 𝒃/𝒁, 𝒇(𝒀) /𝑿 , 𝒈(𝒃) /𝒀}.
akhter900@gmail.com 15
Example 9:
◦ Find the MGU of {𝑭(𝑿, 𝒇(𝒚)) and 𝑭(𝒂, 𝒇(𝒈(𝒛)))}
Solution:
◦ Here, 𝚿𝟏 = 𝐅 𝐗, 𝐟 𝐲 and 𝚿 = 𝑭 𝒂, 𝒇 𝒈 𝒛
◦ So, 𝑭 𝑿, 𝒇 𝒚 , 𝑭 𝒂, 𝒇 𝒈 𝒛
◦ 𝜽 = {𝒂/𝑿}
◦ 𝑭 𝒂, 𝒇 𝒚 , 𝑭 𝒂, 𝒇 𝒈 𝒛
◦ 𝜽 = {𝒈(𝒛)/𝒚}
◦ 𝑭 𝒂, 𝒇 𝒈(𝒛) , 𝑭 𝒂, 𝒇 𝒈 𝒛 , Successfully Unified.
◦ Unifier = {𝒂/𝑿, 𝒈(𝒛)/𝒚}
akhter900@gmail.com 16
Example 10:
◦ Consider, F(x, f(y)).
Now, determine the following that they are unified or not.
Also identify the unifier set.
𝑭(𝒛, 𝒚): 𝑼𝒏𝒊𝒇𝒊𝒄𝒂𝒕𝒊𝒐𝒏 𝑭𝒂𝒊𝒍𝒆𝒅, 𝑼𝒏𝒊𝒇𝒊𝒆𝒓 = {𝒛/𝒙, ? ? }
𝑭(𝒛, 𝒈(𝒛)): 𝑼𝒏𝒊𝒇𝒊𝒄𝒂𝒕𝒊𝒐𝒏 𝑭𝒂𝒊𝒍𝒆𝒅, 𝑼𝒏𝒊𝒇𝒊𝒆𝒓 = {𝒛/𝒙, ? ? }
𝑭 𝒑, 𝒇 𝒑 : 𝑺𝒖𝒄𝒄𝒆𝒔𝒔𝒇𝒖𝒍, 𝑼𝒏𝒊𝒇𝒊𝒆𝒓 = {𝒑/𝒙, 𝒑/𝒚}
𝑭(𝒄, 𝒇(𝒈(𝒅))): 𝑺𝒖𝒄𝒄𝒆𝒔𝒔𝒇𝒖𝒍, 𝑼𝒏𝒊𝒇𝒊𝒆𝒓 = {𝒄/𝒙, 𝒈(𝒅)/𝒚}
akhter900@gmail.com 17
Understand before act,
as what is seen may not be the actual
reflection of a state.
Thank You
18
