[Math] Disjunctive normal form (BOTH dnf and cnf) example help

conjunctive-normal-formdiscrete mathematicsdisjunctive-normal-formproof-writingpropositional-calculus

Consider
$$T \vee ( \neg x \wedge y ) \vee ( x \wedge y )\tag{1}$$

In class we went over examples of how many things can be both DNF and CNF… e.g.,

  • $(\neg z) \vee y$

can be thought of as both

  1. $(\neg z) \vee y\qquad\quad\,$ DNF
  2. $((\neg z) \vee y) \wedge T\quad$ CNF

Can someone explain why example (1) cannot work like that, i.e., as in being one large conjunction of a disjunction as in (2)?

$$T \wedge (T \vee ( \neg x \wedge y ) \vee ( x \wedge y ))\tag{2}$$

Is it due to having more than one disjunction inside?

Best Answer

For DNF :

a formula is a disjunctive normal form if and only if it is a disjunction of one or more conjunctions of one or more literals.

Tus, the formula :

$(\lnot z) \lor y$

is in DNF beacuse is the disjunction of two "degenerate" conjunctions : $\lnot z$ and $y$.

For CNF, we have that :

a formula is a conjunctive normal form (CNF) if and only if it is a conjunction of clauses, where a clause is a disjunction of literals.

Thus :

$((\lnot z) \lor y) \land T$

is in CNF, because we have the disjunction of the two literals : $\lnot z$ and $y$ that makes the clause : $(\lnot z) \lor y$; then a second clause : $T$ (a "degenerate" disjunction) and the two disjunctions are conjoined into : $((\lnot z) \lor y) \land T$.

Regarding the formula :

$T \land [T \lor (\lnot x \land y ) \lor ( x \land y )]$

we have three conjunctions : $(\lnot x \land y )$ and $( x \land y )$ and the "degenerate" : $T$, and they are disjoined into :

$T \lor (\lnot x \land y ) \lor ( x \land y )$;

this formula is in DNF; but adding the part : $T \land \ldots$, the resulting formula is nor more a DNF.

With the formula :

$T \land [T \lor (\lnot x \land y ) \lor ( x \land y )]$

we can apply Distributivity to its subformula:

$$[(\lnot x \land y ) \lor ( x \land y )] \equiv [y \land (x \lor \lnot x)] \equiv (y \land T) \equiv y$$

to get the equivalent :

$[T \land (T \lor y)] \equiv (T \land T) \equiv T$

which is both a CNF and a DNF equivalent to the original formula.

Related Question