3 Derivative Operations for Classes C N of Boolean Functions
55
The function f k (x) ∈ C N can also be determined by f i (x) ∈ C N using the vector of
coefficients c j ⊕ c k :
f k (x) = f j (x ⊕ c k ) = f i (x ⊕ c j ⊕ c k ).
Hence, we have
∀f i (x), f j (x), f k (x) ∈ C N : (f i (x) R f j (x))∧(f j (x) R f k (x)) ⇔ (f i (x) R f k (x)) .
All functions of the class C N satisfy the three properties of an equivalence relation;
hence, the theorem holds.
Due to Theorem 3.2 it is not necessary to enumerate all Boolean functions of a
class C N ; knowing that C N is an equivalence class defined by (3.1) it is enough to
know one representative function f re (x); all the other functions of the class C N can
be generated by means of (3.1) using all c = 0.
Such a simplified representation of a class C N confronts us with the question:
which function should be used as representative function f re (x)? Due to the
property that C N is an equivalence class each of the Boolean functions of a given
class can be used as representative function f re (x). Sometimes it can be desired
that the representative function f re (x) of n variables is uniquely specified. One easy
method to select a uniquely specified function of the class C N is the following:
1. prepare a function table for all functions of the class C N using a fixed lexicographic order of the argument vectors from 0 to 1;
2. calculate the decimal equivalent e d (f i (x)) of each vector of the function values
such that the function value of f (0) is weighted by 2 n and f (1) by 2 0 = 1;
3. use the function with the smallest decimal equivalent e d (f i (x)) as representative
function f re (x) of the class C N .
Example 3.2 Table 3.1 shows the calculation of the decimal equivalents e d (f i (x 1 ))
for all functions of B 1 . Using the decimal equivalents e d (f i (x 1 )) the unique
representative function f re (x 1 ) of the classes C Ni determined in Example 3.1 we
get
C N 0 :
f
re (x 1 ) = 0(x 1 )
e d (f
re (x 1 )) = 0,
C N 1 :
f
re (x 1 ) = x 1
e d (f
re (x 1 )) = 1,
C N 2 :
f
re (x 1 ) = 1(x 1 )
e d (f
re (x 1 )) = 3.
Only for C N 1 there is a choice between the functions
f 1 (x 1 ) = x 1 with e d (f 1 (x 1 )) = 1 and
f 2 (x 1 ) = x 1 with e d (f 2 (x 1 )) = 2.
55
The function f k (x) ∈ C N can also be determined by f i (x) ∈ C N using the vector of
coefficients c j ⊕ c k :
f k (x) = f j (x ⊕ c k ) = f i (x ⊕ c j ⊕ c k ).
Hence, we have
∀f i (x), f j (x), f k (x) ∈ C N : (f i (x) R f j (x))∧(f j (x) R f k (x)) ⇔ (f i (x) R f k (x)) .
All functions of the class C N satisfy the three properties of an equivalence relation;
hence, the theorem holds.
Due to Theorem 3.2 it is not necessary to enumerate all Boolean functions of a
class C N ; knowing that C N is an equivalence class defined by (3.1) it is enough to
know one representative function f re (x); all the other functions of the class C N can
be generated by means of (3.1) using all c = 0.
Such a simplified representation of a class C N confronts us with the question:
which function should be used as representative function f re (x)? Due to the
property that C N is an equivalence class each of the Boolean functions of a given
class can be used as representative function f re (x). Sometimes it can be desired
that the representative function f re (x) of n variables is uniquely specified. One easy
method to select a uniquely specified function of the class C N is the following:
1. prepare a function table for all functions of the class C N using a fixed lexicographic order of the argument vectors from 0 to 1;
2. calculate the decimal equivalent e d (f i (x)) of each vector of the function values
such that the function value of f (0) is weighted by 2 n and f (1) by 2 0 = 1;
3. use the function with the smallest decimal equivalent e d (f i (x)) as representative
function f re (x) of the class C N .
Example 3.2 Table 3.1 shows the calculation of the decimal equivalents e d (f i (x 1 ))
for all functions of B 1 . Using the decimal equivalents e d (f i (x 1 )) the unique
representative function f re (x 1 ) of the classes C Ni determined in Example 3.1 we
get
C N 0 :
f
re (x 1 ) = 0(x 1 )
e d (f
re (x 1 )) = 0,
C N 1 :
f
re (x 1 ) = x 1
e d (f
re (x 1 )) = 1,
C N 2 :
f
re (x 1 ) = 1(x 1 )
e d (f
re (x 1 )) = 3.
Only for C N 1 there is a choice between the functions
f 1 (x 1 ) = x 1 with e d (f 1 (x 1 )) = 1 and
f 2 (x 1 ) = x 1 with e d (f 2 (x 1 )) = 2.