3 Derivative Operations for Classes C N of Boolean Functions
53
Example 3.1 There are 2 2 1 = 2 2 = 4 Boolean functions of one variable x 1 :
f 0 (x 1 ) = x 1 ∧ x 1 = 0(x 1 ),
f 1 (x 1 ) = x 1 ,
f 2 (x 1 ) = x 1 ,
f 3 (x 1 ) = x 1 ∨ x 1 = 1(x 1 ).
All functions of a class C N can be calculated using Definition (3.1) which get the
form
f
c 1 (x 1 ) = f j (x 1 ⊕ c 1 )
for all Boolean functions f (x 1 ) : B 1 → B and all c 1 ∈ B 1 .
It can be assumed that these classes C N contain two functions due to the two
possible values 0 and 1 of c 1 . However, a complete exploration reveals that this
assumption is not true:
f
0
0 (x 1 ) = (x 1 ⊕ 0) ∧ (x 1 ⊕ 0) = x 1 ∧ x 1 = 0(x 1 ) = f 0 (x 1 ),
f
1
0 (x 1 ) = (x 1 ⊕ 1) ∧ (x 1 ⊕ 1) = x 1 ∧ x 1 = 0(x 1 ) = f 0 (x 1 ),
f
0
1 (x 1 ) = x 1 ⊕ 0 = x 1 = f 1 (x 1 ),
f
1
1 (x 1 ) = x 1 ⊕ 1 = x 1 = f 2 (x 1 ),
f
0
2 (x 1 ) = x 1 ⊕ 0 = x 1 = f 2 (x 1 ),
f
1
2 (x 1 ) = x 1 ⊕ 1 = x 1 = f 1 (x 1 ),
f
0
3 (x 1 ) = (x 1 ⊕ 0) ∨ (x 1 ⊕ 0) = x 1 ∨ x 1 = 1(x 1 ) = f 3 (x 1 ),
f
1
3 (x 1 ) = (x 1 ⊕ 1) ∨ (x 1 ⊕ 1) = x 1 ∨ x 1 = 1(x 1 ) = f 3 (x 1 ).
Hence, there are three classes C N of Boolean functions f (x 1 ) : B 1 → B:
C N 0 = {f 0 (x 1 )} ,
C N 1 = {f 1 (x 1 ), f 2 (x 1 )} ,
C N 2 = {f 3 (x 1 )} .
Example 3.1 confirms that there are classes C N containing less than 2 1 = 2
Boolean functions of one variable; these are the classes C N 0 and C N 2 . These classes
satisfy
f
0
i (x 1 ) = f
1
i (x 1 ) = f i (x 1 ) .