56
B. Steinbach and C. Posthoff
Table 3.1 Decimal
equivalents e d (f i (x 1 )) of all
functions of B 1
x 1
f 0 (x 1 ) f 1 (x 1 ) f 2 (x 1 ) f 3 (x 1 ) Weights
0
0
0
1
1
2 1 = 2
1
0
1
0
1
2 0 = 1
e d (f i (x 1 )) 0
1
2
3
The selection of f 1 (x 1 ) = x 1 with the smallest e d (f 1 (x 1 )) = 1 as representative
function f re (x 1 ) for C N 1 is an arbitrary decision that results in the unique
representative function f re (x 1 ) = f 1 (x 1 ) = x 1 .
The exploration of all Boolean functions of one variable in Example 3.1 has
shown that not all classes C N contain the maximal number of 2 1 = 2 functions.
The reason that the classes C N 0 and C N 2 contain only a single function is that all
functions (here the single function) of these classes are independent of the change
of the variable x 1 :
der
x 1
f 0 (x 1 ) = der
x 1
(x 1 ∧ x 1 )
der
x 1
f 3 (x 1 ) = der
x 1
(x 1 ∨ x 1 )
= (x 1 ∧ x 1 ) ⊕ (x 1 ∧ x 1 )
= (x 1 ∨ x 1 ) ⊕ (x 1 ∨ x 1 )
= 0 ,
= 0 .
Therefore, the coefficient c 1 of (3.1) can be omitted in the specification of the classes
C N 0 and C N 2 .
This observation can be generalized as follows:
– if the representative function f re (x) is independent of x i , i.e.,
der
x i
f
re (x) = 0 ,
then all functions f j (x) of the class C N satisfy der x i f j (x) = 0;
– der x i f (x) can be used to indicate that all functions of the class C N are
independent of x i ;
– in the case of the independence of x i all functions of the class C N satisfy f j (x i =
0, x 0 ) = f j (x i = 1, x 0 ) so that the coefficient c i of (3.1) can be omitted;
– a class C N of Boolean functions f j (x 1 , x 2 , . . . , x n ) with der x i f j (x) = 0 and
der
x 0
f j (x) = 0, ∀ x 0 ⊆ x \ x i
contains 2 n−1 functions.
We use for the function on the left-hand side of an equation like der x i f (x) = 0
the name independence function f id . A comprehensive definition of the independence function f id (x) will be given at the end of this section. The independence
function f id (x) can be used together with the representative function f re (x) to
specify all 2 n (or less) functions of a class C N without an enumeration of all the
functions of the class in the form
B. Steinbach and C. Posthoff
Table 3.1 Decimal
equivalents e d (f i (x 1 )) of all
functions of B 1
x 1
f 0 (x 1 ) f 1 (x 1 ) f 2 (x 1 ) f 3 (x 1 ) Weights
0
0
0
1
1
2 1 = 2
1
0
1
0
1
2 0 = 1
e d (f i (x 1 )) 0
1
2
3
The selection of f 1 (x 1 ) = x 1 with the smallest e d (f 1 (x 1 )) = 1 as representative
function f re (x 1 ) for C N 1 is an arbitrary decision that results in the unique
representative function f re (x 1 ) = f 1 (x 1 ) = x 1 .
The exploration of all Boolean functions of one variable in Example 3.1 has
shown that not all classes C N contain the maximal number of 2 1 = 2 functions.
The reason that the classes C N 0 and C N 2 contain only a single function is that all
functions (here the single function) of these classes are independent of the change
of the variable x 1 :
der
x 1
f 0 (x 1 ) = der
x 1
(x 1 ∧ x 1 )
der
x 1
f 3 (x 1 ) = der
x 1
(x 1 ∨ x 1 )
= (x 1 ∧ x 1 ) ⊕ (x 1 ∧ x 1 )
= (x 1 ∨ x 1 ) ⊕ (x 1 ∨ x 1 )
= 0 ,
= 0 .
Therefore, the coefficient c 1 of (3.1) can be omitted in the specification of the classes
C N 0 and C N 2 .
This observation can be generalized as follows:
– if the representative function f re (x) is independent of x i , i.e.,
der
x i
f
re (x) = 0 ,
then all functions f j (x) of the class C N satisfy der x i f j (x) = 0;
– der x i f (x) can be used to indicate that all functions of the class C N are
independent of x i ;
– in the case of the independence of x i all functions of the class C N satisfy f j (x i =
0, x 0 ) = f j (x i = 1, x 0 ) so that the coefficient c i of (3.1) can be omitted;
– a class C N of Boolean functions f j (x 1 , x 2 , . . . , x n ) with der x i f j (x) = 0 and
der
x 0
f j (x) = 0, ∀ x 0 ⊆ x \ x i
contains 2 n−1 functions.
We use for the function on the left-hand side of an equation like der x i f (x) = 0
the name independence function f id . A comprehensive definition of the independence function f id (x) will be given at the end of this section. The independence
function f id (x) can be used together with the representative function f re (x) to
specify all 2 n (or less) functions of a class C N without an enumeration of all the
functions of the class in the form