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