1.4. BOOLEAN FUNCTIONS OF n VARIABLES 5
1.4.1 THE MINTERM EXPANSION
From the truth table, one can immediately deduce the Boolean formula called the minterm
expansion. For example, Table 1.4 immediately yields:
f .A; B; C /
D
A B C
C
A B C
C
A B C
C
AB C :
It consists of the OR of different terms. ere are between 0 and 2
n
different terms present. Each
term is called a minterm and consists of the AND of exactly n literals.
e algorithm for translating the truth table into the minterm expansion is straightfor-
ward: each row of the truth table with a 1 in the rightmost column (i.e., the output column) yields
one minterm; the latter consists of an AND of all input letters, overlined if in the corresponding
column appears a 0, not overlined if in the corresponding column appears a 1.
In the literature such an expansion is sometimes referred to as a “sum of products” because
an OR in some way “resembles a sum” and an AND in a way “resembles a product.” Also the
abbreviation SOP is often used.
1.4.2 THE REED–MULLER EXPANSION
A fundamentally different expansion is the Reed–Muller expansion. It is obtained as follows:
we apply to the minterm expansion the two identities
X D 1 ˚ X
X C Y D X ˚ Y ˚ XY : (1.1)
is leads to a XOR of ANDs. e result is subsequently simplified by applying the identities
X ˚ X D 0
0 ˚ X D X :
In case of our example (Table 1.4), we obtain
f .A; B; C / D A ˚ B ˚ C ˚ AB : (1.2)
A Reed–Muller expansion is an example of an ESOP expansion, in other words, an
“EXCLUSIVE-OR sum of products.” us, just like the OR, the XOR function also is considered
“a kind of sum.”
In many respects, a Reed–Muller expansion of a Boolean function resembles the well-
known Taylor expansion of ordinary calculus. Let us assume a function f of the real numbers x,
y, and z. en, the Taylor expansion around the point .x; y; z/ D .0; 0; 0/ looks like
f .x; y; z/ D c
000
C c
100
x C c
010
y C c
001
zC
c
110
xy C c
101
xz C c
011
yz C c
200
x
2
C c
020
y
2
C c
002
z
2
C
c
111
xyz C c
210
x
2
y C :
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.