1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ ok let me make sure I understand this. so because T and (T or ( not x and y ) or ( x and y )) would be a conjunction of disjunctions of conjunctions(rather than factors or degenerates) that makes it neither in this case right? because there are too many levels of junctions rather than (x, T, F, not x) $\endgroup$ – Maximus12793 Feb 6 '15 at 4:01
  • $\begingroup$ @Maximus12793 - $T$ and $(T \lor ( \lnot x \land y ) \lor ( x \land y ))$ is not a CNF because it is a conjunction of $T$ and $(T \lor ( \lnot x \land y ) \lor ( x \land y ))$ but this one is not a clause, i.e. a disjunction of literals : we have e.g. $( x \land y )$ that is not a literal, i.e. a boolean variable or a negated boolean variable, but a "complex" formula. $\endgroup$ – Mauro ALLEGRANZA Feb 6 '15 at 7:21

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.