Could someone explain me why is there for each formula one and only one equivalent canonical conjunctive normal form? Like, I understood how to derive one by using the truth tables but I'm still asking myself how to prove this statement in a formal way.
Asked
Active
Viewed 1,330 times
1 Answers
4
Think about it this way: two statements are equivalent if and only if they have the same truth table, and there is exactly one canonical conjunctive form for every truth-table.
It follows that there is exactly one canonical conjunctive form that is equivalent to a given statement.
The key then, if you want to prove it formally, is to do the following two things:
- for an arbitrary truth-table, find a canonical conjunctive normal form with that truth table
- given that two canonical conjunctive normal forms have the same truth table, show that the expressions must be identical.
Ben Grossmann
- 225,327
-
thanks, it makes a lot of sense! – ZouZou Nov 11 '14 at 19:12
-
@Omnomnomnom, can I convert two boolean expressions into their canonical SOP/POS form to prove their equivalence? If canonical form is unique they should match, right? – Samik Oct 12 '15 at 05:48
-
@Samik correct.${}{}{}$ – Ben Grossmann Oct 12 '15 at 11:18
-
@Omnomnomnom - Do you have a reference for the uniqueness? It seems to me this post contradicts the uniqueness. What am I missing? Thanks in advance! – Pierre-Yves Gaillard Apr 12 '17 at 11:28
-
I don't see how the first is in CNF – Ben Grossmann Apr 12 '17 at 12:23
-
Thanks for your answer! I haven't been alerted and saw it by chance. (It might be more prudent to use the @ sign.) If I understand correctly, you're saying that you don't see how $A\land B$ is in CNF. This is the fourth example in this Wikipedia subentry. – Pierre-Yves Gaillard Apr 12 '17 at 15:31
-
You can also look at this WolframAlpha link. – Pierre-Yves Gaillard Apr 12 '17 at 15:43
-
@Pierre-YvesGaillard my apologies for leaving it out the @. In any case, it seems that (according to your links) I misunderstood the definition of CNF back when I answered this; my understanding was that the CNF was necessarily was expanded to include all "maxterms". That is, I would have said that $A \wedge B$ is in a conjunctive form but not in the canonical conjunctive form as neither $A$ nor $B$ are maxterms. That is, was thinking of CCNF, i.e. canonical conjunctive form. – Ben Grossmann Apr 12 '17 at 16:19
-
@Pierre-YvesGaillard in fact, looking at the question, he is indeed asking specifically about the canonical CNF, so I was accidentally right. – Ben Grossmann Apr 12 '17 at 16:20
-
@Pierre-YvesGaillard It is well known that CNFs are not unique. In fact, the problem of finding a minimal CNF (i.e. with the fewest terms) is important in electrical engineering and can be solved using Karnaugh diagrams. – Ben Grossmann Apr 12 '17 at 16:23
-
I also missed the "canonical". Sorry! Now everything is clear. Thanks! – Pierre-Yves Gaillard Apr 12 '17 at 17:17