For every Boolean function, there exists a corresponding disjunctive normal form. As stated by Footprints, the form only uses negation ( ¬ ), disjunction ( ∨ ), and conjunction ( ∧ ). Because of this, the set S of logical connectives {¬, ∧, ∨} is functionally complete.
In general, a set of logical connectives L is said to be functionally complete if every Boolean function in any number of variables can be expressed by a sentence containing logical connectives only from L.
Here is a step-by-step process for constructing a disjunctive normal form from any Boolean function.
For example, let a Boolean function f(p, q, r) be defined by the truth table below:
p q r | f(p,q,r)
----------+----------
0 0 0 | 1
0 0 1 | 1
0 1 0 | 0
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 0
1 1 1 | 0
For the first row with f = 1, variables p, q, and r are all equal to 0. For this row and only for this row is ¬p, ¬q, and ¬r all true. This can be expressed as (¬p ∧ ¬q ∧ ¬r). Add this next to row 1:
p q r | f(p,q,r)
----------+----------
0 0 0 | 1 (¬p ∧ ¬q ∧ ¬r)
0 0 1 | 1
0 1 0 | 0
0 1 1 | 0
1 0 0 | 1
1 0 1 | 0
1 1 0 | 0
1 1 1 | 0
Continue analysis in this fashion for all rows with f = 1:
p q r | f(p,q,r)
----------+----------
0 0 0 | 1 (¬p ∧ ¬q ∧ ¬r)
0 0 1 | 1 (¬p ∧ ¬q ∧ r)
0 1 0 | 0
0 1 1 | 0
1 0 0 | 1 ( p ∧ ¬q ∧ ¬r)
1 0 1 | 0
1 1 0 | 0
1 1 1 | 0
Compound these terms into one formula with disjunctions:
(¬p ∧ ¬q ∧ ¬r) ∨
(¬p ∧ ¬q ∧ r) ∨
(p ∧ ¬q ∧ ¬r)
This formula is true iff the list of values (p, q, r) corresponds to a row with f = 1.
∴ The formula is logically equivalent to f. This form of formula is called the
disjunctive normal form, which every Boolean function has. Since the form consists only of connectives from set S, S is functionally complete.
Other examples of functionally complete sets include
{¬, ∨},
{¬, ∧},
{↑}, and
{↓}.
Here are some logical equivalents to other common connectives in disjunctive normal form:
(p ⇒ q) ≡ (¬ p ∨ q)
(p ⇔ q) ≡ ((p ∧ q) ∨ (¬ p ∧ ¬ q))
| 
