4 1. INTRODUCTION
e remaining 10 3 D 7 functions are considered a combination of the NOT, AND, OR,
and XOR functions. For example,
f
2
.A; B/ D A AND .NOT B/ D AB :
We observe that all three functions AND, OR, and XOR are commutative:
A AND B D B AND A
and similar identities for the other two functions. is is not the case for any function f .A; B/.
For example, the function f
2
is not commutative:
f
2
.A; B/ ¤ f
2
.B; A/ but f
2
.A; B/ D f
4
.B; A/ :
1.4 BOOLEAN FUNCTIONS OF n VARIABLES
ere exist 2
2
n
different Boolean functions of n variables. Each is represented by a truth table,
consisting of n C1 columns and 2
n
rows. Table 1.4 gives an example for n D 3. e function
is one out of the 2
8
D 256 possibilities. Among them, only 218 are true functions of the three
variables A, B, and C . Among the 256 functions, 70 are so-called balanced functions, in other
words, functions which have an equal number of 1’s and 0’s in the output column. e function
of Table 1.4 is both true and balanced.
A truth table can be summarized by a single Boolean formula. However, as mentioned in
Section 1.1, there are multiple ways to write a given table as a Boolean expression [3]. We will
now present three of them.
Table 1.4: Truth table of a function f .A; B; C / of three variables
ABC f
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0
1
1
0
1
0
1
0
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.