Which one of the following is true ?
2015
Which one of the following is true ?
- A.
The resolvent of two Horn clauses is not a Horn clause
- B.
The resolvent of two Horn clauses is a Horn clause
- C.
If we resolve a negated goal G against a fact or rule A to get clause C then C has positive literal or non-null goal
- D.
If we resolve a negated goal G against a fact or rule A to get clause C then C has positive literal or null goal
Attempted by 48 students.
Show answer & explanation
Correct answer: B
Correct answer: The resolvent of two Horn clauses is a Horn clause.
Reasoning:
Definition: A Horn clause is a clause with at most one positive literal.
When resolving two clauses, you remove a complementary pair of literals (one positive and one negative) and form the disjunction of the remaining literals from both clauses.
Case analysis shows the resolvent cannot have more than one positive literal:
If both parent clauses have zero positive literals, the resolvent has zero positive literals.
If one parent clause has one positive literal and the other has zero, the resolvent has at most one positive literal.
If both parent clauses have one positive literal each, resolution removes at least the complementary literal pair and cannot create two new positive literals, so the resolvent still has at most one positive literal.
Therefore, in all cases the resolvent of two Horn clauses has at most one positive literal and is itself a Horn clause.
Simple example:
Clause 1: p ∨ ¬q (Horn: one positive literal p)
Clause 2: ¬p ∨ r (Horn: one positive literal r)
Resolvent on p and ¬p: ¬q ∨ r (Horn: at most one positive literal)