I was not able to find or come up with two formulae which are equivalent but have different CNF. All my ideas reduce to the same formula after applying transformations. The requirements are the following:

Give an example which shows that proving equivalence of two formulas by bringing them into conjunctive normal form is incomplete. By incompleteness, we mean that there are examples of formulas which are equivalent but their conjunctive normal form is not the same.


It depends on the algorithm for obtaining CNF of a formula. A simple truth table-based method will always produce syntactically the same CNFs for equivalent formulas, since it in a sense just gives you the rows of the truth table for which the formula evaluates to false.

A trivial example of equivalent formulas, which are both in CNF:

$$A \wedge B$$ $$(A \vee B) \wedge (A \vee \neg B) \wedge (\neg A \vee B).$$

Non-uniqueness of CNF means that one can build an algorithm, which returns essentially different CNFs for equivalent formulas. For example, as a first step the conversion algorithm can check if a formula already in CNF and return it immediately.

  • $\begingroup$ Yes,the second is CNF based on truth table but wouldn't it reduce to the same formula if we apply distribution? $\endgroup$ Mar 30 '16 at 17:04
  • $\begingroup$ (1) I didn't specify the exact conversion algorithm. The simple truth table-based algorithm will give you the same formulas, since it essentially just gives you the rows of the truth table for which the formula evaluates to false. $\endgroup$ Mar 30 '16 at 17:25
  • $\begingroup$ (2) We need to decide which formulas are 'the same'. The CNF formulas $A \wedge B$ and $B \wedge A$ are not the same syntactically. $\endgroup$ Mar 30 '16 at 17:27
  • $\begingroup$ I know, the requirements got me confused. And I thought at the exact same thing as you did. Thanks for your help :) $\endgroup$ Mar 30 '16 at 17:37
  • $\begingroup$ I just had a discussion with my teacher who game me the exercise. Apparently even (A and not A ) equivalent to | (bottom) would have been enough. My expectations were to high... $\endgroup$ Mar 30 '16 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.