3 Derivative Operations for Classes C N of Boolean Functions
61
change of single variables) there are 2 n − 1 different directions of change for
Boolean functions of n variables. However, only n of these directions of change are
independent of each other. Hence, for a unique representation of classes C N a unique
specification of the directions of change is needed for which the functions of the
class are independent. This unique specification can be reached by the independence
matrix [3, 6, 8] which has already been used for the unique specification of lattices
of Boolean functions.
Definition 3.3 (Independence Matrix) The independence matrix IDM(f ) of a
Boolean function f (x 1 , x 2 , . . . , x n ) is a Boolean matrix of n rows and n columns.
The columns of the independence matrix are associated with the n variables of the
Boolean space in the fixed order (x 1 , x 2 , . . . , x n ). The independence matrix has the
shape of an echelon; all elements below the main diagonal are equal to 0. Values 1 in
a row of the independence matrix indicate a set of variables for which the vectorial
derivative of the function f (x 1 , x 2 , . . . , x n ) is equal to 0. The following rules ensure
the uniqueness of the independence matrix:
1. values 1 can only occur to the right of a value 1 in the main diagonal of the
independence matrix; and
2. all values above a value 1 in the main diagonal of the independence matrix are
equal to 0.
Example 3.6 Both functions of the class C N 4 are independent of the simultaneous
change of the variables x 1 and x 2 ; hence, it holds:
f 6 (x 1 , x 2 ) = x 1 ⊕ x 2 ,
f 9 (x 1 , x 2 ) = x 1 x 2 = (x 1 ⊕ x 2 ) = x 1 ⊕ x 2 ⊕ 1,
der
(x 1 ,x 2 )
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ 1 ⊕ x 2 ⊕ 1)
= 0,
der
(x 1 ,x 2 )
f 9 (x 1 , x 2 ) = (x 1 ⊕ x 2 ⊕ 1) ⊕ (x 1 ⊕ 1 ⊕ x 2 ⊕ 1 ⊕ 1)
= 0.
Based on Definition 3.3 we get the independence matrix IDM(f 6 (x 1 , x 2 )) of Fig. 3.1
which is also the independence matrix of the class C N 4 : IDM(C N 4 ).
Fig. 3.1 Independence
matrix of the class C N 4
1 1
0 0
1
2
i 1 2
j
61
change of single variables) there are 2 n − 1 different directions of change for
Boolean functions of n variables. However, only n of these directions of change are
independent of each other. Hence, for a unique representation of classes C N a unique
specification of the directions of change is needed for which the functions of the
class are independent. This unique specification can be reached by the independence
matrix [3, 6, 8] which has already been used for the unique specification of lattices
of Boolean functions.
Definition 3.3 (Independence Matrix) The independence matrix IDM(f ) of a
Boolean function f (x 1 , x 2 , . . . , x n ) is a Boolean matrix of n rows and n columns.
The columns of the independence matrix are associated with the n variables of the
Boolean space in the fixed order (x 1 , x 2 , . . . , x n ). The independence matrix has the
shape of an echelon; all elements below the main diagonal are equal to 0. Values 1 in
a row of the independence matrix indicate a set of variables for which the vectorial
derivative of the function f (x 1 , x 2 , . . . , x n ) is equal to 0. The following rules ensure
the uniqueness of the independence matrix:
1. values 1 can only occur to the right of a value 1 in the main diagonal of the
independence matrix; and
2. all values above a value 1 in the main diagonal of the independence matrix are
equal to 0.
Example 3.6 Both functions of the class C N 4 are independent of the simultaneous
change of the variables x 1 and x 2 ; hence, it holds:
f 6 (x 1 , x 2 ) = x 1 ⊕ x 2 ,
f 9 (x 1 , x 2 ) = x 1 x 2 = (x 1 ⊕ x 2 ) = x 1 ⊕ x 2 ⊕ 1,
der
(x 1 ,x 2 )
f 6 (x 1 , x 2 ) = (x 1 ⊕ x 2 ) ⊕ (x 1 ⊕ 1 ⊕ x 2 ⊕ 1)
= 0,
der
(x 1 ,x 2 )
f 9 (x 1 , x 2 ) = (x 1 ⊕ x 2 ⊕ 1) ⊕ (x 1 ⊕ 1 ⊕ x 2 ⊕ 1 ⊕ 1)
= 0.
Based on Definition 3.3 we get the independence matrix IDM(f 6 (x 1 , x 2 )) of Fig. 3.1
which is also the independence matrix of the class C N 4 : IDM(C N 4 ).
Fig. 3.1 Independence
matrix of the class C N 4
1 1
0 0
1
2
i 1 2
j