3 Derivative Operations for Classes C N of Boolean Functions
67
Based on the given set x 0 of the needed vectorial derivative operation, Algorithm 1 determines which vector s min must be included into the independence matrix
IDM(C N ) belonging to the result of the vectorial derivative operation with regard to
x 0 . The function BV (x 0 ) in line 2 maps the variables x 0 into a binary vector, where
the bit s min [ j ] = 1 indicates that the variable x j belongs to x 0 . The initial vector
s min is modified in line 5 if both the bit s min [ j ] and the bit in the main diagonal
IDM(f )[ j, j ] are equal to 1. The result of Algorithm 1 is a uniquely specified
vector s min that must be included into the independence matrix IDM(f ) such that
the most significant bit belongs to the main diagonal. If s min = 0, then all Boolean
functions of the class C N are independent of the simultaneous change of all variables
of x 0 :
der
x 0
f (x 0 , x 1 ) = 0,
(3.12)
and case 1 of the above enumeration applies. Due to the dependence of certain
direction of change it is possible that BV (x 0 ) does not occur in the independence
matrix IDM(C N ) but s min = 0.
Algorithm 2 realizes the unique inclusion of a given direction of change specified
by x 0 into the independence matrix IDM(f ). Initial steps copy IDM(f ) to IDM(g)
and calculate the unique vector s min for the given variables x 0 using Algorithm 1.
The copied independence matrix IDM(g) must be changed only in the case that
s min > 0. The index of the most significant bit j of s min indicates within IDM(g)
both the column which must be evaluated and the row where s min must be stored.
All rows of IDM(g) must be equal to 0 in the column j except in the main diagonal.
The operations within the while-loop in lines 6–11 perform the needed changes by
Algorithm 2 IDM(g) = UM(IDM(f ), x 0 ): unique merge
Input : x 0 ⊆ x: subset of variables that satisfy (3.12) to merge with IDM(f ),
Input : IDM(f ): unique independence matrix of n rows and n columns of f (x)
Output : IDM(g): unique independence matrix of the same size of g(x) with der x 0 g(x) = 0
1: IDM(g) ← IDM(f )
2: s min = MIDC(IDM(f ), x 0 )
3: if s min > 0 then
4:
j ← IndexOfMostSignificantBit(s min )
5:
i ← 1
6:
while i < j do
7:
if IDM(g)[ i, j ] = 1 then
8:
IDM(g)[ i ] ← IDM(g)[ i ] ⊕ s min
9:
end if
10:
i ← i + 1
11:
end while
12:
IDM(g)[ j ] ← s min
13: end if
67
Based on the given set x 0 of the needed vectorial derivative operation, Algorithm 1 determines which vector s min must be included into the independence matrix
IDM(C N ) belonging to the result of the vectorial derivative operation with regard to
x 0 . The function BV (x 0 ) in line 2 maps the variables x 0 into a binary vector, where
the bit s min [ j ] = 1 indicates that the variable x j belongs to x 0 . The initial vector
s min is modified in line 5 if both the bit s min [ j ] and the bit in the main diagonal
IDM(f )[ j, j ] are equal to 1. The result of Algorithm 1 is a uniquely specified
vector s min that must be included into the independence matrix IDM(f ) such that
the most significant bit belongs to the main diagonal. If s min = 0, then all Boolean
functions of the class C N are independent of the simultaneous change of all variables
of x 0 :
der
x 0
f (x 0 , x 1 ) = 0,
(3.12)
and case 1 of the above enumeration applies. Due to the dependence of certain
direction of change it is possible that BV (x 0 ) does not occur in the independence
matrix IDM(C N ) but s min = 0.
Algorithm 2 realizes the unique inclusion of a given direction of change specified
by x 0 into the independence matrix IDM(f ). Initial steps copy IDM(f ) to IDM(g)
and calculate the unique vector s min for the given variables x 0 using Algorithm 1.
The copied independence matrix IDM(g) must be changed only in the case that
s min > 0. The index of the most significant bit j of s min indicates within IDM(g)
both the column which must be evaluated and the row where s min must be stored.
All rows of IDM(g) must be equal to 0 in the column j except in the main diagonal.
The operations within the while-loop in lines 6–11 perform the needed changes by
Algorithm 2 IDM(g) = UM(IDM(f ), x 0 ): unique merge
Input : x 0 ⊆ x: subset of variables that satisfy (3.12) to merge with IDM(f ),
Input : IDM(f ): unique independence matrix of n rows and n columns of f (x)
Output : IDM(g): unique independence matrix of the same size of g(x) with der x 0 g(x) = 0
1: IDM(g) ← IDM(f )
2: s min = MIDC(IDM(f ), x 0 )
3: if s min > 0 then
4:
j ← IndexOfMostSignificantBit(s min )
5:
i ← 1
6:
while i < j do
7:
if IDM(g)[ i, j ] = 1 then
8:
IDM(g)[ i ] ← IDM(g)[ i ] ⊕ s min
9:
end if
10:
i ← i + 1
11:
end while
12:
IDM(g)[ j ] ← s min
13: end if