58
B. Steinbach and C. Posthoff
All functions of a class C N can be calculated using Definition (3.1) which will get
the form
f
(c 1 ,c 2 ) (x 1 , x 2 ) = f j (x 1 ⊕ c 1 , x 2 ⊕ c 2 )
(3.4)
for all Boolean functions of f (x 1 , x 2 ) : B 2 → B and all (c 1 , c 2 ) ∈ B 2 .
Due to the two coefficients (c 1 , c 2 ) a class C N of Boolean functions of two
variables can contain up to 2 2 = 4 functions. The calculation of the related functions
of two variables of a class C N using (3.4) results in seven classes C N of Boolean
functions f (x 1 , x 2 ) : B 2 → B:
C N 0 = {f 0 (x 1 , x 2 )} ,
C N 1 = {f 1 (x 1 , x 2 ), f 2 (x 1 , x 2 ), f 4 (x 1 , x 2 ), f 8 (x 1 , x 2 )} ,
C N 2 = {f 3 (x 1 , x 2 ), f 12 (x 1 , x 2 )} ,
C N 3 = {f 5 (x 1 , x 2 ), f 10 (x 1 , x 2 )} ,
C N 4 = {f 6 (x 1 , x 2 ), f 9 (x 1 , x 2 )} ,
C N 5 = {f 7 (x 1 , x 2 ), f 11 (x 1 , x 2 ), f 13 (x 1 , x 2 ), f 14 (x 1 , x 2 )} ,
C N 6 = {f 15 (x 1 , x 2 )} .
The complete exploration of all functions of two variables results in classes C N
of one, two, or four Boolean functions. We noticed already for the functions of one
variable that the independence of a variable reduces the number functions to the half
of the maximal number of functions of such a class. This property can be confirmed
for the classes C N 0 , C N 1 , C N 2 , C N 3 , C N 5 , and C N 6 as follows:
der
x 1
f 0 (x 1 , x 2 ) = 0 ⊕ 0 = 0,
der
x 2
f 0 (x 1 , x 2 ) = 0 ⊕ 0 = 0;
hence, the function f 0 (x 1 , x 2 ) of the class C N 0 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;
der
x 1
f 1 (x 1 , x 2 ) = x 1 x 2 ⊕ x 1 x 2 = x 2 = 0,
der
x 2
f 1 (x 1 , x 2 ) = x 1 x 2 ⊕ x 1 x 2 = x 1 = 0;
hence, the function f 1 (x 1 , x 2 ) and consequently all other functions of the class C N 1
depend on both x 1 and x 2 so that this class contains all 2 2−0 = 2 2 = 4 functions;
der
x 1
f 3 (x 1 , x 2 ) = x 1 ⊕ x 1 = 1 = 0,
der
x 2
f 3 (x 1 , x 2 ) = x 1 ⊕ x 1 = 0;
hence, the function f 3 (x 1 , x 2 ) and consequently also the function f 12 (x 1 , x 2 ) of the
class C N 2 depend on x 1 , but not on x 2 so that this class contains only 2 2−1 = 2 1 = 2
functions;
B. Steinbach and C. Posthoff
All functions of a class C N can be calculated using Definition (3.1) which will get
the form
f
(c 1 ,c 2 ) (x 1 , x 2 ) = f j (x 1 ⊕ c 1 , x 2 ⊕ c 2 )
(3.4)
for all Boolean functions of f (x 1 , x 2 ) : B 2 → B and all (c 1 , c 2 ) ∈ B 2 .
Due to the two coefficients (c 1 , c 2 ) a class C N of Boolean functions of two
variables can contain up to 2 2 = 4 functions. The calculation of the related functions
of two variables of a class C N using (3.4) results in seven classes C N of Boolean
functions f (x 1 , x 2 ) : B 2 → B:
C N 0 = {f 0 (x 1 , x 2 )} ,
C N 1 = {f 1 (x 1 , x 2 ), f 2 (x 1 , x 2 ), f 4 (x 1 , x 2 ), f 8 (x 1 , x 2 )} ,
C N 2 = {f 3 (x 1 , x 2 ), f 12 (x 1 , x 2 )} ,
C N 3 = {f 5 (x 1 , x 2 ), f 10 (x 1 , x 2 )} ,
C N 4 = {f 6 (x 1 , x 2 ), f 9 (x 1 , x 2 )} ,
C N 5 = {f 7 (x 1 , x 2 ), f 11 (x 1 , x 2 ), f 13 (x 1 , x 2 ), f 14 (x 1 , x 2 )} ,
C N 6 = {f 15 (x 1 , x 2 )} .
The complete exploration of all functions of two variables results in classes C N
of one, two, or four Boolean functions. We noticed already for the functions of one
variable that the independence of a variable reduces the number functions to the half
of the maximal number of functions of such a class. This property can be confirmed
for the classes C N 0 , C N 1 , C N 2 , C N 3 , C N 5 , and C N 6 as follows:
der
x 1
f 0 (x 1 , x 2 ) = 0 ⊕ 0 = 0,
der
x 2
f 0 (x 1 , x 2 ) = 0 ⊕ 0 = 0;
hence, the function f 0 (x 1 , x 2 ) of the class C N 0 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;
der
x 1
f 1 (x 1 , x 2 ) = x 1 x 2 ⊕ x 1 x 2 = x 2 = 0,
der
x 2
f 1 (x 1 , x 2 ) = x 1 x 2 ⊕ x 1 x 2 = x 1 = 0;
hence, the function f 1 (x 1 , x 2 ) and consequently all other functions of the class C N 1
depend on both x 1 and x 2 so that this class contains all 2 2−0 = 2 2 = 4 functions;
der
x 1
f 3 (x 1 , x 2 ) = x 1 ⊕ x 1 = 1 = 0,
der
x 2
f 3 (x 1 , x 2 ) = x 1 ⊕ x 1 = 0;
hence, the function f 3 (x 1 , x 2 ) and consequently also the function f 12 (x 1 , x 2 ) of the
class C N 2 depend on x 1 , but not on x 2 so that this class contains only 2 2−1 = 2 1 = 2
functions;