is the maximum number of conjunctions a DNF can have.

A full DNF can have up to conjunctions, one for each row of the truth table.

Example 1

Consider a formula with two variables and .

The longest possible DNF has conjunctions:
:

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

This formula is a tautology. It can be simplified to or to , which are also tautologies, as well as valid DNFs.

Example 2

Each