Spring ‘22 AI Homework 5: solutions
Let D be the domain of people and animals. Let L be the first-order language over D with the following primitives:
● ● ● ● ● ●
A(a) – a is an animal
Copyright By PowCoder代写 加微信 powcoder
L(x, y) – person x loves y H(x, y) – person x hates y D(a)-aisadog
Jane, Jim: people
points) Represent the following sentences in L:
1. Everyone who loves all animals is loved by someone
2. Jane or Jim hates the dog, who is named Fido
3. Anyone who hates an animal is loved by no one.
4. A dog is an animal
5. Jane loves all animals
6. Jim hates Fido
B) (4 points) Convert the sentences from A into CNF. Show all steps including Skolemization. A
1 ∀x [∀a A(a) => L(x, a)] => [∃y L(y,x)]
2 [H(Jane, Fido) v H(Jim, Fido)] ^ D(Fido)
3 ∀x [∃a A(a) ^ H(x, a)] => [∀y ¬L(y,x)]
4 ∀a D(a) => A(a)
5 ∀a A(a) => L(Jane, a)
6 H(Jim, Fido)
1 ∀x [∀a A(a) => L(x, a)] => [∃y L(y,x)] 2 [H(Jane, Fido) v H(Jim, Fido)] ^ D(Fido) 3 ∀x [∃a A(a) ^ H(x, a)] => [∀y ¬L(y,x)] 4 ∀a D(a) => A(a)
5 ∀a A(a) => L(Jane, a)
6 H(Jim, Fido)
No <=> skip to Step 2: important to get the ¬ in the right place
1 ∀x ¬ [∀a ¬ A(a) v L(x, a)] v [∃y L(y,x)] 2 [H(Jane, Fido) v H(Jim, Fido)] ^ D(Fido) 3 ∀x ¬[∃a A(a) ^ H(x, a)] v [∀y ¬L(y,x)] 4 ∀a ¬ D(a) v A(a)
5 ∀a ¬ A(a) v L(Jane, a) 6 H(Jim, Fido)
Update Step 3 to include quantifiers
1 ∀x [∃a A(a) ^ ¬ L(x, a)] v [∃y L(y,x)] 2 [H(Jane, Fido) v H(Jim, Fido)] ^ D(Fido) 3 ∀x[∀a ¬ A(a) v ¬ H(x, a)] v [∀y ¬L(y,x)] 4 ∀a ¬ D(a) v A(a)
5 ∀a ¬ A(a) v L(Jane, a)
6 H(Jim, Fido)
4.a: eliminate existential quantifiers via Skolemization
1 ∀x [ A(Sk0(x)) ^ ¬ L(x, Sk0(x))] v [ L(Sk1(x),x)] 2 [H(Jane, Fido) v H(Jim, Fido)] ^ D(Fido)
3 ∀x[∀a ¬ A(a) v ¬ H(x, a)] v [∀y ¬L(y,x)]
4 ∀a ¬ D(a) v A(a)
5 ∀a ¬ A(a) v L(Jane, a) 6 H(Jim, Fido)
Step 4.b drop existential
1 [ A(Sk0(x)) ^ ¬ L(x, Sk0(x))] v [ L(Sk1(x),x)] 2 [H(Jane, Fido) v H(Jim, Fido)] ^ D(Fido)
3 [¬ A(a) v ¬ H(x, a)] v [¬L(y,x)]
4 ¬ D(a) v A(a)
5 ¬ A(a) v L(Jane, a) 6 H(Jim, Fido)
Step 5/6: distribution and splitting
1.a A(Sk0(x)) v L(Sk1(x),x)
1.b ¬L(x, Sk0(x)) v L(Sk1(x),x) 2.a H(Jane, Fido) v H(Jim, Fido) 2.b D(Fido)
3 ¬A(a) v ¬H(x, a) v ¬L(y,x)
4 ¬D(a) v A(a)
5 ¬A(a) v L(Jane, a)
6 H(Jim, Fido)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com