3 Derivative Operations for Classes C N of Boolean Functions
75
Example 3.9 We use the resulting class C N (g(x)) of Example 3.8, rename this class
to C N (f (x)), and calculate the single derivative with regard to x 2 .
The renamed independence matrix IDM(C N (f (x))) is not empty (see Fig. 3.3)
so that it must be verified whether Condition (3.21) is satisfied. The binary vector
of x 2 for functions of four variables is BV (x 2 ) = (0100). The result calculated
by Algorithm 1 (MIDC) for x 2 and IDM(C N (f (x))) is s min = (0001), so that
Condition (3.21) is satisfied and the representative function of all single derivatives
of the class
C N
(x 1 (x 2 ⊕ x 4 )) ∨ x 3 , der
(x 2 ,x 4 )
f (x)
with regard to x 2 can be calculated using (3.22):
g
re (x) = der
x 2
f
re (x) = x 1 x 3 .
Due to (3.21) Algorithm 2 (UM) must be used to adjust the resulting independence
matrix of this single derivative of the class C N (f ). Algorithm 2 determines in
line 2 s min = (0001) so that the condition of line 3 is satisfied and the index of
the most significant bit is assigned in line 4: j = 4. In the second swap of the
while-loop of lines 6–11 the condition of line 7 is satisfied so that the ⊕-operation
removes rightmost 1 in the second row of the independence matrix IDM(C N (g(x))).
No other changes occur in the while-loop, and s min is stored into the last row of
IDM(C N (g(x))) in line 12 of Algorithm 2 (UM).
The independence function g id (x) associated with the resulting independence
matrix IDM(C N (g(x))) is
g
id (x) = der
x 2
g(x) ∨ der
x 4
g(x).
This independence function contains two single derivatives; hence, the associated
independence matrix contains two values 1 in the main diagonal, the rank of this
independence matrix is
rank(IDM(C N (g(x)))) = 2,
so that the class
C N
x 1 x 3 , der
x 2
g(x) ∨ der
x 4
g(x)
contains 2 n−rank(IDM(C N (g))) = 2 4−2 = 2 2 = 4 functions g(x) of four variables.
This confirms that each vectorial (and also single) derivative with regard to a
direction of change the class is depending on divides the number of functions of
the given class in halves.
75
Example 3.9 We use the resulting class C N (g(x)) of Example 3.8, rename this class
to C N (f (x)), and calculate the single derivative with regard to x 2 .
The renamed independence matrix IDM(C N (f (x))) is not empty (see Fig. 3.3)
so that it must be verified whether Condition (3.21) is satisfied. The binary vector
of x 2 for functions of four variables is BV (x 2 ) = (0100). The result calculated
by Algorithm 1 (MIDC) for x 2 and IDM(C N (f (x))) is s min = (0001), so that
Condition (3.21) is satisfied and the representative function of all single derivatives
of the class
C N
(x 1 (x 2 ⊕ x 4 )) ∨ x 3 , der
(x 2 ,x 4 )
f (x)
with regard to x 2 can be calculated using (3.22):
g
re (x) = der
x 2
f
re (x) = x 1 x 3 .
Due to (3.21) Algorithm 2 (UM) must be used to adjust the resulting independence
matrix of this single derivative of the class C N (f ). Algorithm 2 determines in
line 2 s min = (0001) so that the condition of line 3 is satisfied and the index of
the most significant bit is assigned in line 4: j = 4. In the second swap of the
while-loop of lines 6–11 the condition of line 7 is satisfied so that the ⊕-operation
removes rightmost 1 in the second row of the independence matrix IDM(C N (g(x))).
No other changes occur in the while-loop, and s min is stored into the last row of
IDM(C N (g(x))) in line 12 of Algorithm 2 (UM).
The independence function g id (x) associated with the resulting independence
matrix IDM(C N (g(x))) is
g
id (x) = der
x 2
g(x) ∨ der
x 4
g(x).
This independence function contains two single derivatives; hence, the associated
independence matrix contains two values 1 in the main diagonal, the rank of this
independence matrix is
rank(IDM(C N (g(x)))) = 2,
so that the class
C N
x 1 x 3 , der
x 2
g(x) ∨ der
x 4
g(x)
contains 2 n−rank(IDM(C N (g))) = 2 4−2 = 2 2 = 4 functions g(x) of four variables.
This confirms that each vectorial (and also single) derivative with regard to a
direction of change the class is depending on divides the number of functions of
the given class in halves.