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))