Artificial Intelligence: Knowledge Representation And Reasoning Week 5 NPTEL Assignment Answers 2025

NPTEL Artificial Intelligence: Knowledge Representation And Reasoning Week 5 Assignment Answers 2024

Q1. Select the formulas that are in CNF (Conjunctive Normal Form):

a. A ∧ B ∧ C
b. A ∨ B ∨ C
c. ¬A
d. (¬A ∨ B ∨ C) ∧ (¬C ∨ ¬D ∨ E)
e. ¬(A ∨ B ∨ C) ∧ (C ∨ D ∨ E)

✅ Answer: a, b, c, d
📘 Explanation:

• CNF is a conjunction of disjunctions.
• a: (A ∧ B ∧ C) — each literal is a clause. ✔
• b: (A ∨ B ∨ C) — single disjunctive clause. ✔
• c: (¬A) — single literal clause. ✔
• d: Two OR-clauses combined by AND → valid CNF ✔
• e: ¬(A ∨ B ∨ C) → becomes (¬A ∧ ¬B ∧ ¬C) after De Morgan → CNF only if transformed, not as-is ❌

---

Q2. Convert this formula to CNF:

∀x∀y{ ( A(x,y) ⊃ [B(x) ⊃ C(y)] ) ⊃ ( D(x) ⊃ [A(x,y) ⊃ C(y)] ) }

a. ∀x∀y[¬A(x,y) ∧ B(x) ∧ C(y) ∧ ¬D(x)]
b. ∀x∀y{[C(y) ∨ ¬D(x)] ∧ [¬A(x,y) ∨ B(x) ∨ C(y) ∨ ¬D(x)] ∧ [¬A(x,y) ∨ ¬D(x)]}
c. ∀x∀y[¬A(x,y) ∨ B(x) ∨ C(y) ∨ ¬D(x)]
d. ∀x∀y[¬A(x,y) ∨ ¬B(x) ∨ C(y) ∨ D(x)]

✅ Answer: c
📘 Explanation: After removing implications and applying CNF transformation step by step, the correct conjunctive form is option c.

---

Q3. Convert to Skolem form:

∀x[(∃y(P(x) ⊃ R(x,y))) ⊃ (Q(x) ∧ ∃z R(x,z))]

a. ∀x∀y[(P(x) ⊃ R(x,y)) ⊃ (Q(x) ∧ R(x,sk(x)))]
b. ∀x[(P(x) ⊃ R(x,sk(x))) ⊃ (Q(x) ∧ R(x,sk(x)))]
c. ∀x∀y[(P(x) ∧ ¬R(x,y)) ∨ (Q(x) ∧ R(x,sk(x)))]
d. ∀x[(P(x) ∧ ¬R(x,sk(x))) ∨ (Q(x) ∧ R(x,sk(x)))]

✅ Answer: a, c
📘 Explanation:

• Skolemization removes existential quantifiers using Skolem functions.
• a and c are both valid Skolem forms depending on distribution.

---

Q4. Convert the above to clause form:

a. [P(?t) ∨ Q(?t)] ∧ [P(?w) ∨ R(?w,sk(?w))] ∧ [¬R(?x,?y) ∨ Q(?x)] ∧ [¬R(?u,?v) ∨ R(?u,sk(?u))]
b. [P(?t) ∨ Q(?t)] ∧ [P(?w) ∨ R(?w,sk(?w))] ∧ [¬R(?x,sk(?x)) ∨ Q(?x)] ∧ [¬R(?u,sk(?u)) ∨ R(?u,sk(?u))]
c. { {P(?t) Q(?t)}; {P(?w), R(?w,sk(?w))}; {¬R(?x,?y), Q(?x)}; {¬R(?u,?v), R(?u,sk(?u))} }
d. { {P(?t), Q(?t)}; {P(?w), R(?w,sk(?w))}; {¬R(?x,sk(?x)), Q(?x)}; {¬R(?u,sk(?u)), R(?u,sk(?u))} }

✅ Answer: a, c
📘 Explanation: Options a and c represent the correct breakdown into CNF clauses and clause-set representation.

---

Q5. Unifiers for pair of clauses:

1. { R(f(a), g(b)) }
2. { ¬R(?x, ?y); ¬R(f(?x), g(?y)); Q(f(?x)); }

a. { x -> a; y -> b }
b. { x -> f(a); y -> b }
c. { x -> f(a); y -> g(b) }
d. None of the above

✅ Answer: a, c
📘 Explanation:

• a matches R(f(a), g(b)) directly with ¬R(x, y)
• c matches R(f(a), g(b)) with ¬R(f(x), g(y)) by x = a, y = b

---

Q6. For the pair of clauses in the previous question, select the most general unifier.

• { x -> a; y -> b }
• { x -> f(a); y -> b }
• { x -> f(a); y -> g(b) }
• None of the above because clauses with multiple unifiers cannot be unified.

✅ Answer: a, c
📘 Explanation: a is a more general match for ¬R(x, y); c is for ¬R(f(x), g(y)). Both valid depending on which literal is unified.

---

Q7. Resolution on KB1:

KB1 = { (A ∧ B) ⊃ C; Q ⊃ (P ⊃ B); D ⊃ (P ∧ Q); ¬(A ⊃ ¬D) }

Which of the following are resolvents?

a. ¬A ∨ ¬B ∨ C
b. B ∨ ¬P ∨ ¬Q
c. ¬B ∨ Q
d. C ∨ ¬P ∨ ¬Q
e. C ∨ ¬Q

✅ Answer: d, e
📘 Explanation: Using resolution on transformed CNF clauses leads to d and e. Others are not direct resolvents.

---

Q8. Is KB1 consistent?

• Yes
• No
• Cannot be determined

✅ Answer: Yes
📘 Explanation: No contradiction is derived during resolution → so KB1 is consistent.

---

Q9. Does KB1 entail (B ∧ C ∧ P ∧ Q)? Use the Resolution Refutation Method to prove/disprove it.

• Yes
• No
• Cannot be determined

✅ Answer: Yes
📘 Explanation: Using resolution refutation (negating conclusion and deriving contradiction) proves entailment.

---

Q10. From KB2, which follow?

KB2:

1. ¬A(?x) ∨ S(?x)
2. ¬B(?u) ∨ R(?u,?v)
3. ¬P(?y,?z) ∨ Q(?y,?z)
4. ¬S(?t) ∨ B(?t) ∨ P(?t,?w)
5. A(Foo)
6. B(Foo)

Options:

a. S(Foo) ∧ S(Bar)
b. R(Foo,Bar) ∨ Q(Foo,Bar)
c. ∃t∃x∃y (R(t,x) ∨ Q(t,y))
d. ∃t∃x∃y (R(t,x) ∧ Q(t,y))

✅ Answer: b, c
📘 Explanation:

• From A(Foo) and 1 → S(Foo)
• Then via 4 + 6, derive P(Foo,?) → resolve with 3 → Q(Foo,?)
• Hence we can get R or Q in disjunction for arbitrary terms.

---

Q11. Can Resolution Refutation Method be used to prove the following?

∀t∃x∃y [ A(t) ⊃ (R(t,x) ∨ Q(t,y)) ]

• Yes
• No

✅ Answer: Yes
📘 Explanation:

• Resolution can handle universal to existential quantifiers by Skolemization and clause transformation.