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.