Artificial Intelligence A popular children’s riddle is “Brothers and sisters hav

Question

Artificial Intelligence

A popular children’s riddle is “Brothers and sisters have I none, but that man’s father is my son.” Use the rules of the family domain to show who that man is. You may apply any of the inference methods described in this chapter. Why do you think that this riddle is difficult?

The first example we consider is the domain of family relationships, or kinship. This domain includes facts such as "Elizabeth is the most of Charles" and "Charles is the fatehr of William" and rules such as "One's grandmother is the mother of one's parent."

Clear, the objects in our domain are people. We have two unary predicates, Male and Female. Kinship relations-parenthood, brotherhood, marriage, and son on- are represented by binary predicates: Parent, sibling, brother, sister, child, daughter, son, spouse, wife, husband, grandparent, grandchild, cousin, aunt, and uncle. We use funtions for mother and father, because eevery person has exactly one of each of these (at least according to nature's design).

Explanation / Answer

Surprisingly, the hard part to represent is “who is that man.” We want to ask “what relationship does that man have to some known person,” but if we represent relations with predicates (e.g., Parent(x, y)) then we cannot make the relationship be a variable in first order logic. So instead we need to reify relationships. We will use Rel(r, x, y) to say that the family relationship r holds between people x and y.
Let Me denote me and MrX denote “that man.” We will also need the Skolem constants FM for the father of Me and FX for the father of MrX. The facts of the case (put into implicative normal form) are:
       (1) Rel(Sibling, Me, x) ? False
       (2) Male(MrX)
       (3) Rel(Father, FX, MrX)
       (4) Rel(Father, FM, Me)
       (5) Rel(Son, FX, FM )
We want to be able to show that Me is the only son of my father, and therefore that Me is father of MrX, who is male, and therefore that “that man” is my son. The relevant definitions from the family domain are:
       (6) Rel(Parent, x, y) ? Male(x) ? Rel(Father, x, y)
       (7) Rel(Son, x, y) ? Rel(Parent, y, x) ? Male(x)
       (8) Rel(Sibling, x, y) ? x = y ? ? p Rel(Parent, p, x) ? Rel(Parent, p, y)
       (9) Rel(Father, x1 , y) ? Rel(Father, x2 , y) ? x1 = x2
and the query we want is:
       (Q) Rel(r, MrX, y)
We want to be able to get back the answer {r/Son, y/Me}. Translating 1-9 and Q into INF (and negating Q and including the definition of =) we get:
      (6a) Rel(Parent, x, y) ? Male(x) ? Rel(Father, x, y)
      (6b) Rel(Father, x, y) ? M ale(x)
      (6c) Rel(Father, x, y) ? Rel(Parent, x, y)
      (7a) Rel(Son, x, y) ? Rel(Parent, y, x)
      (7b) Rel(Son, x, y) ? Male(x))
      (7c) Rel(Parent, y, x) ? Male(x) ? Rel(Son, x, y)
      (8a) Rel(Sibling, x, y) ? x = y
      (8b) Rel(Sibling, x, y) ? Rel(Parent, P (x, y), x)
      (8c) Rel(Sibling, x, y) ? Rel(Parent, P (x, y), y)
      (8d) Rel(Parent, P (x, y), x) ? Rel(Parent, P (x, y), y) ? x = y ? Rel(Sibling, x, y)
      (9) Rel(Father, x1 , y) ? Rel(Father, x2 , y) ? x1 = x2
      (N ) True ? x = y ? x = y
      (N ? ) x = y ? x = y ? F alse
      (Q? ) Rel(r, MrX, y) ? F alse
Note that (1) is non-Horn, so we will need resolution to be be sure of getting a solution. It turns out we also need demodulation to deal with equality. The following lists the steps of the proof, with the resolvents of each step in parentheses:
      (10) Rel(Parent, FM, Me)                                       (4, 6c)
      (11) Rel(Parent, FM, FX)                                       (5, 7a)
      (12) Rel(Parent, FM, y) ? Me = y ? Rel(Sibling, Me, y)        (10, 8d)
      (13) Rel(Parent, FM, y) ? Me = y ? False                      (12, 1)
      (14) Me = FX ? False                                           (13, 11)
      (15) Me = FX                                                    (14, N )
      (16) Rel(Father, Me, MrX)                                      (15, 3, demodulation)
      (17) Rel(Parent, Me, MrX)                                      (16, 6c)
      (18) Rel(Son, MrX, Me)                                          (17, 2, 7c)
      (19) False {r/Son, y/Me}                                        (18, Q? )

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.