How to prove that a given disjunctive or conjuctive normal form is minimal?

139 Views Asked by At

what is the argument that a given canonical normalform cannot be reduced any further?
For example have a look at this $dnf(f) = (\neg a \wedge b \wedge c) \vee (a \wedge \neg b \wedge c) \vee(a \wedge b \wedge \neg c)$?
Every term in this $dnf(f)$ is complete (there are only variables $a,b,c$).
Link to wolfram alpha

Can somebody help?

1

There are 1 best solutions below

0
On BEST ANSWER

The statement being in canonical disjunctive normal form means that every one of its disjuncts makes reference to each of the variables exactly once. And, since that disjunct is in fact a conjunction of those variables or negations thereof, that disjunct is true for exactly one truth-assignment of those variables. Finally, since the disjuncts are all different from each other, they will all 'pick out' a different truth-assignment. That is, any two different disjuncts $\phi$ and $\psi$ from the CDNF cannot be true at the same time. Therefore, removing any one of its disjuncts will mean that the resulting formula is no longer true for the truth-assignment 'picked out' by that very disjunct, meaning that the resulting formula is not equivalent to the original. So that is why it can not be reduced any further while still in CDNF.

Of course, it is perfectly possible for statements in CDNF to be reduced to 'smaller' statements, but the result will no longer in CDNF.