3 Derivative Operations for Classes C N of Boolean Functions
63
The independence matrix IDM(C N ) uniquely determines the directions of change
all functions of the class C N are independent of by a value 1 in the main diagonal.
Each such direction of change halves the number of functions of the class C N and
increases the value of rank(IDM(C N )) by 1. If the functions of the class C N do not
depend on k uniquely specified directions of change, then there are 2 n−k functions
in the class C N , the rank(IDM(C N )) = k, and we get
n f (C N ) = 2
n−k .
Theorem 3.5 If one Boolean function f (x 0 , x 1 ) of a class C N satisfies
der
x 0
f (x 0 , x 1 ) = 0,
(3.6)
then also all other Boolean functions f (x 1 ⊕ c 1 , x 2 ⊕ c 2 , . . . , x n ⊕ c n ) of this class
satisfy
der
x 0
f (x 1 ⊕ c 1 , x 2 ⊕ c 2 , . . . , x n ⊕ c n ) = 0.
(3.7)
Proof The Shannon decomposition of (3.6) with regard to the variables
x 1 = (x 11 , x 12 , . . . , x 1j )
results in
der
x 0
f (x 0 , x 1 ) = x 11 x 12 . . . x 1j der
x 0
f (x 0 , 0, 0, . . . , 0)∨
x 11 x 12 . . . x 1j der
x 0
f (x 0 , 1, 0, . . . , 0) ∨ · · · ∨
x 11 x 12 . . . x 1j der
x 0
f (x 0 , 1, 1, . . . , 1) = 0 ;
hence, this vectorial derivative is equal to 0 for all subspaces x 1 = c 1 so that
all possible assignments of values to c 1 lead to the same result 0 of this vectorial
derivative.
It remains the proof for x 0 = (x 01 , x 02 , . . . , x 0k ) and x 1 = c 1 that if
der
x 0
f (x 0 , c 1 ) = 0,
(3.8)
then
der
x 0
f (x 01 ⊕ c 01 , x 02 ⊕ c 02 , . . . , x 0k ⊕ c 0k , c 1 ) = 0.
(3.9)