1

So i tried to convert this

(ABCD+AB¬C¬D+¬A¬CD+¬AC¬D+¬B¬CD+¬BC¬D) into CNF form but im stuck at

(¬A+¬B+¬C+D).(¬A+¬B+C+¬D).(A+¬B+C+D).(A+¬B+¬C+¬D).(A+C+D).(A+¬C+¬D).(B+C+D).(B+¬C+¬D)

and the right answer should be (¬A+¬B+¬C+D).(¬A+¬B+C+¬D).(A+C+D).(A+¬C+¬D).(B+C+D).(B+¬C+¬D).

Any help would be great.

KusKus
  • 13

1 Answers1

0

Your answer is logically equivalent, but has some redundant terms

Your answer:

$(\neg A \lor \neg B \lor \neg C \lor D) \land (\neg A \lor \neg B \lor C \lor \neg D) \land (A \lor \neg B \lor C \lor D) \land (A \lor \neg B \lor \neg C \lor \neg D) \land (A \lor C \lor D) \land (A \lor \neg C \lor \neg D) \land (B \lor C \lor D) \land (B \lor \neg C \lor \neg D)$

The book's answer:

$(\neg A \lor \neg B \lor \neg C \lor D) \land (\neg A \lor \neg B \lor C \lor \neg D) \land (A \lor C \lor D) \land (A \lor \neg C \lor \neg D) \land (B \lor C \lor D) \land (B \lor \neg C \lor \neg D)$

Note the only difference between your answer are the two terms below:

$(A \lor \neg B \lor C \lor D) \land (A \lor \neg B \lor \neg C \lor \neg D)$

These terms are made redundant by

$(A \lor C \lor D)$ and $(A \lor \neg C \lor \neg D)$ respectively

Do you see how $(A \lor C \lor D)$ is equivalent to $(A \lor \neg B \lor C \lor D) \land (A \lor B \lor C \lor D)$? This means it is equivalent and redundant to an extra term you included.

jwc845
  • 661