2 1. INTRODUCTION
1.2 BOOLEAN FUNCTIONS OF ONE VARIABLE
ere exist only four Boolean functions f .A/ of a single Boolean variable A. Table 1.1 shows
the four corresponding truth tables. However, two of these functions are not really dependent
of A. ey are constants:
f .A/ D 0 (Table 1.1a)
f .A/ D 1 (Table 1.1b) :
We thus have only two true functions (or proper functions) of A :
f .A/ D A (Table 1.1c)
f .A/ D A (Table 1.1d) :
e former is called the IDENTITY function, the latter is called the NOT function. Here, we have
introduced the following short-hand notation for the NOT function:
X D NOT X :
Whereas X is called a letter, both X and X are called a literal.
Table 1.1: Truth table of the four Boolean functions f .A/: (a) the constant function 0, (b) the
constant function 1, (c) the IDENTITY function, and (d) the NOT function
A f A f A f A f
0
1
0
0
0
1
1
1
0
1
0
1
0
1
1
0
(a) (b)
(c) (d)
1.3 BOOLEAN FUNCTIONS OF TWO VARIABLES
ere exist 2
4
D 16 different Boolean functions of two variables.
1
Table 1.2 shows them all.
However, some of these functions f .A; B/ are not truly functions of A and B. Two functions
are independent of both A and B. ey are constants:
f
0
.A; B/ D 0
f
15
.A; B/ D 1 :
1
Besides using the notation A
1
, A
2
, …, A
n
for the variables, we will also use the letters A, B, C , …, whenever this is more
convenient.
1.3. BOOLEAN FUNCTIONS OF TWO VARIABLES 3
Another four functions are in fact functions of a single variable: f
3
and f
12
are independent
of B, whereas both f
5
and f
10
are independent of A :
f
3
.A; B/ D A
f
5
.A; B/ D B
f
10
.A; B/ D B
f
12
.A; B/ D A :
is leaves only 16 2 4 D 10 functions, which are truly dependent on both A and B. We
call them “true functions” of A and B.
Table 1.2: Truth table of all 16 Boolean functions f
j
.A; B/
ree out of the ten true functions of two variables (i.e., f
1
, f
7
, and f
6
) are well known:
the AND function, the OR function, and the XOR function (a.k.a. the EXCLUSIVE OR). Table 1.3
gives the corresponding truth tables. We will use the following short-hand notations for these
basic Boolean functions:
XY D X AND Y
X C Y D X OR Y
X ˚ Y D X XOR Y :
Table 1.3: Truth table of three basic Boolean functions: (a) the AND function, (b) the OR function,
and (c) the
XOR
function
AB f AB f AB f
0 0
0
1
1
0
1 1
0
0
0
1
0 0
0 1
1 0
1 1
0
1
1
1
0 0
0 1
1 0
1 1
0
1
1
0
(a) (b) (c)
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset