3 Derivative Operations for Classes C N of Boolean Functions
59
der
x 1
f 5 (x 1 , x 2 ) = x 2 ⊕ x 2 = 0,
der
x 2
f 5 (x 1 , x 2 ) = x 2 ⊕ x 2 = 1 = 0;
hence, the function f 5 (x 1 , x 2 ) and consequently also the function f 10 (x 1 , x 2 ) of the
class C N 3 depend on x 2 , but not on x 1 so that this class contains only 2 2−1 = 2 1 = 2
functions;
der
x 1
f 7 (x 1 , x 2 ) = (x 1 ∨ x 2 ) ⊕ (x 1 ∨ x 2 ) = x 2 = 0,
der
x 2
f 7 (x 1 , x 2 ) = (x 1 ∨ x 2 ) ⊕ (x 1 ∨ x 2 ) = x 1 = 0;
hence, the function f 7 (x 1 , x 2 ) and consequently all other functions of the class C N 5
depend on both x 1 and x 2 so that this class contains all 2 2−0 = 2 2 = 4 functions;
and
der
x 1
f 15 (x 1 , x 2 ) = 1 ⊕ 1 = 0,
der
x 2
f 15 (x 1 , x 2 ) = 1 ⊕ 1 = 0;
hence, the function f 15 (x 1 , x 2 ) of the class C N 6 is independent of both x 1 and x 2 so
that the number of functions of this class is equal to 2 2−2 = 2 0 = 1.
At the first glance the class C N 4 seems to be a counterexample to the rule that the
independence of the function f i (x) ∈ C N of one of the variables reduces the number
functions to the half of the maximal number of functions of an appropriate class. For
the function f 6 (x 1 , x 2 ) of the class C N 4 we get as result of the single derivatives:
der
x 1
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ x 2 ) = 1 = 0,
der
x 2
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ x 2 ) = 1 = 0;
hence, the function f 6 (x 1 , x 2 ) and consequently also the other function f 9 (x 1 , x 2 )
of the class C N 4 depend on both x 1 and x 2 . However, the class C N 4 does not contain
2 2−0 = 2 2 = 4, but only two functions. The reason for this property is that the
function f 6 (x 1 , x 2 ) is independent of the simultaneous change of x 1 and x 2 :
der
(x 1 ,x 2 )
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ x 2 )
= x 1 ⊕ x 2 ⊕ x 1 ⊕ 1 ⊕ x 2 ⊕ 1
= 0.
That means that both the function f 6 (x 1 , x 2 ) and f 9 (x 1 , x 2 ) can be split into pairs of
identical function values. Due to these pairs of identical function values only 2 n−1 of
the 2 n function values can arbitrarily be chosen; hence, this restriction has the same
effect as the independence of a single variable. However, the coefficient c i could
59
der
x 1
f 5 (x 1 , x 2 ) = x 2 ⊕ x 2 = 0,
der
x 2
f 5 (x 1 , x 2 ) = x 2 ⊕ x 2 = 1 = 0;
hence, the function f 5 (x 1 , x 2 ) and consequently also the function f 10 (x 1 , x 2 ) of the
class C N 3 depend on x 2 , but not on x 1 so that this class contains only 2 2−1 = 2 1 = 2
functions;
der
x 1
f 7 (x 1 , x 2 ) = (x 1 ∨ x 2 ) ⊕ (x 1 ∨ x 2 ) = x 2 = 0,
der
x 2
f 7 (x 1 , x 2 ) = (x 1 ∨ x 2 ) ⊕ (x 1 ∨ x 2 ) = x 1 = 0;
hence, the function f 7 (x 1 , x 2 ) and consequently all other functions of the class C N 5
depend on both x 1 and x 2 so that this class contains all 2 2−0 = 2 2 = 4 functions;
and
der
x 1
f 15 (x 1 , x 2 ) = 1 ⊕ 1 = 0,
der
x 2
f 15 (x 1 , x 2 ) = 1 ⊕ 1 = 0;
hence, the function f 15 (x 1 , x 2 ) of the class C N 6 is independent of both x 1 and x 2 so
that the number of functions of this class is equal to 2 2−2 = 2 0 = 1.
At the first glance the class C N 4 seems to be a counterexample to the rule that the
independence of the function f i (x) ∈ C N of one of the variables reduces the number
functions to the half of the maximal number of functions of an appropriate class. For
the function f 6 (x 1 , x 2 ) of the class C N 4 we get as result of the single derivatives:
der
x 1
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ x 2 ) = 1 = 0,
der
x 2
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ x 2 ) = 1 = 0;
hence, the function f 6 (x 1 , x 2 ) and consequently also the other function f 9 (x 1 , x 2 )
of the class C N 4 depend on both x 1 and x 2 . However, the class C N 4 does not contain
2 2−0 = 2 2 = 4, but only two functions. The reason for this property is that the
function f 6 (x 1 , x 2 ) is independent of the simultaneous change of x 1 and x 2 :
der
(x 1 ,x 2 )
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ x 2 )
= x 1 ⊕ x 2 ⊕ x 1 ⊕ 1 ⊕ x 2 ⊕ 1
= 0.
That means that both the function f 6 (x 1 , x 2 ) and f 9 (x 1 , x 2 ) can be split into pairs of
identical function values. Due to these pairs of identical function values only 2 n−1 of
the 2 n function values can arbitrarily be chosen; hence, this restriction has the same
effect as the independence of a single variable. However, the coefficient c i could