Question

Q1) Given the following sentences:

1. All hounds howl at night.
2. Anyone who has any cats will not have any mice.
3. Light sleepers do not have anything which howls at night.
4. John has either a cat or a hound.
5. (Conclusion) If John is a light sleeper, then John does not have any mice.

Part 1:

1. Translate into propositional logic sentences
2. Convert the propositional sentences into Conjunctive Normal Form (CNF)
3. Negate the conclusion
4. Use resolution to prove the conclusion

Part 2:

1. Translate into FOL (First Order Logic) sentences
2. Convert the FOL (First Order Logic) sentences from a into Conjunctive Normal Form (CNF)
3. Negate the conclusion
4. Use resolution to prove the conclusion

Answer 1

1. ∀ x (HOUND(x) → HOWL(x))
2. ∀ x ∀ y (HAVE (x,y) ∧ CAT (y) → ¬ ∃ z (HAVE(x,z) ∧ MOUSE (z)))
3. ∀ x (LS(x) → ¬ ∃ y (HAVE (x,y) ∧ HOWL(y)))
4. ∃ x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))
5. LS(John) → ¬ ∃ z (HAVE(John,z) ∧ MOUSE(z))

PART 1;

1. ∀ x (HOUND(x) → HOWL(x))

   ¬ HOUND(x) ∨ HOWL(x)

2. ∀ x ∀ y (HAVE (x,y) ∧ CAT (y) &rarr ¬ ∃ z (HAVE(x,z) ∧ MOUSE (z)))

   ∀ x ∀ y (HAVE (x,y) ∧ CAT (y) &rarr ∀ z ¬ (HAVE(x,z) ∧ MOUSE (z)))

   ∀ x ∀ y ∀ z (¬ (HAVE (x,y) ∧ CAT (y)) ∨ ¬ (HAVE(x,z) ∧ MOUSE (z)))

   ¬ HAVE(x,y) ∨ ¬ CAT(y) ∨ ¬ HAVE(x,z) ∨ ¬ MOUSE(z)

3. ∀ x (LS(x) &rarr ¬ ∃ y (HAVE (x,y) ∧ HOWL(y)))

   ∀ x (LS(x) → ∀ y ¬ (HAVE (x,y) ∧ HOWL(y)))

   ∀ x ∀ y (LS(x) → ¬ HAVE(x,y) ∨ ¬ HOWL(y))

   ∀ x ∀ y (¬ LS(x) ∨ ¬ HAVE(x,y) ∨ ¬ HOWL(y))

   ¬ LS(x) ∨ ¬ HAVE(x,y) ∨ ¬ HOWL(y)

4. ∃ x (HAVE (John,x) ∧ (CAT(x) ∨ HOUND(x)))

   HAVE(John,a) ∧ (CAT(a) ∨ HOUND(a))

5. ¬ [LS(John) → ¬ ∃ z (HAVE(John,z) ∧ MOUSE(z))] (negated conclusion)

   ¬ [¬ LS (John) ∨ ¬ ∃ z (HAVE (John, z) ∧ MOUSE(z))]

   LS(John) ∧ ∃ z (HAVE(John, z) ∧ MOUSE(z)))

   LS(John) ∧ HAVE(John,b) ∧ MOUSE(b)

The set of CNF clauses for this problem is thus as follows:

1. ¬ HOUND(x) ∨ HOWL(x)
2. ¬ HAVE(x,y) ∨ ¬ CAT(y) ∨ ¬ HAVE(x,z) ∨ ¬ MOUSE(z)
3. ¬ LS(x) ∨ ¬ HAVE(x,y) ∨ ¬ HOWL(y)
4. 1. HAVE(John,a)
   2. CAT(a) ∨ HOUND(a)
5. 1. LS(John)
   2. HAVE(John,b)
   3. MOUSE(b)