Editing Disjunctive normal form (section)

== Maximum number of conjunctions ==
<span id="max_conjunctions"> <!-- is anker: do not delete --></span>
Any propositional formula is built from <math>n</math> variables, where <math>n \ge 1</math>.

There are <math>2n</math> possible literals: <math>L = \{ p_1, \lnot p_1, p_2, \lnot p_2, \ldots, p_n, \lnot p_n\}</math>.

<math>L</math> has <math>(2^{2n} -1)</math> non-empty subsets.<ref><math>\left|\mathcal{P}(L)\right| = 2^{2n}</math></ref>

This is the maximum number of conjunctions a DNF can have.<ref name="noreps" />

A full DNF can have up to <math>2^{n}</math> conjunctions, one for each row of the truth table.

'''Example 1'''

Consider a formula with two variables <math>p</math> and <math>q</math>.

The longest possible DNF has <math>2^{(2 \times 2)} -1 = 15</math> conjunctions:<ref name= "noreps" />
:<math> 
\begin{array}{lcl}
(\lnot p) \lor (p) \lor (\lnot q) \lor (q) \lor \\
(\lnot p \land       p) \lor
\underline{(\lnot p \land \lnot q)} \lor
\underline{(\lnot p \land       q)} \lor
\underline{(      p \land \lnot q)} \lor
\underline{(      p \land       q)} \lor
(\lnot q \land       q) \lor \\
(\lnot p \land       p \land \lnot q) \lor	
(\lnot p \land       p \land       q) \lor	
(\lnot p \land \lnot q \land       q) \lor	
(      p \land \lnot q \land       q) \lor \\
(\lnot p \land       p \land \lnot q \land q)
\end{array}</math>

The longest possible full DNF has 4 conjunctions: they are underlined.

This formula is a [[Tautology (logic)|tautology]]. It can be simplified to <math>(\neg p \lor p)</math> or to <math>(\neg q \lor q)</math>, which are also tautologies, as well as valid DNFs.

'''Example 2'''

Each DNF of the e.g. formula <math>(X_1 \lor Y_1) \land (X_2 \lor Y_2) \land \dots \land (X_n \lor Y_n)</math> has <math>2^n</math> conjunctions.