54
B. Steinbach and C. Posthoff
The reason that the classes C N 0 = {0(x 1 )} and C N 2 = {1(x 1 )} contain only a
single function is that all functions (here the single function) of these classes are
independent of the change of the variable x 1 .
Another observation of Example 3.1 is that all functions of the class C N 1 could
be generated from both f 1 (x 1 ) and f 2 (x 1 ). These two Boolean functions belong to
the same class C N 1 and are in the sense of Definition (3.1) equivalent to each other.
For that reason we consider the equivalence relation.
Definition 3.2 (Relation R of Boolean Functions) Two Boolean functions f i (x)
and f j (x) belong to the relation f i (x)Rf j (x) if and only if f i (x) = f j (x ⊕ c) for
any c.
Theorem 3.2 All Boolean functions defined by (3.1) satisfy all three properties of
an equivalence relation; hence, each class C N of Boolean functions defined by (3.1)
is an equivalence class of the relation R.
Proof The vector c = (c 1 , c 2 , . . . , c n ) ∈ B n determines the chosen Boolean
function of the class C N .
Reflexivity: For each function of the class C N the same function is determined
for c = (0, 0, . . . , 0); hence, we have
∀f i (x) ∈ C N : f i (x) R f i (x).
Symmetry: Using any function f i (x) ∈ C N , another function f j (x) ∈ C N is
specified by an arbitrary vector of coefficients c j :
f j (x) = f i (x ⊕ c j ) .
Using the same vector of coefficients c j , we get based on the function f j (x):
f i (x) = f j (x ⊕ c j ) = f i (x ⊕ c j ⊕ c j ) .
Hence, we have
∀f i (x), f j (x) ∈ C N : (f i (x) R f j (x)) ⇔ (f j (x) R f i (x)).
Transitivity: Using any function f i (x) ∈ C N , then another function f j (x) ∈ C N
is specified by an arbitrary vector of coefficients c j :
f j (x) = f i (x ⊕ c j ) .
Using the function f j (x) ∈ C N , another function f k (x) ∈ C N is specified by a vector
of coefficients c k = c j :
f k (x) = f j (x ⊕ c k ) .
B. Steinbach and C. Posthoff
The reason that the classes C N 0 = {0(x 1 )} and C N 2 = {1(x 1 )} contain only a
single function is that all functions (here the single function) of these classes are
independent of the change of the variable x 1 .
Another observation of Example 3.1 is that all functions of the class C N 1 could
be generated from both f 1 (x 1 ) and f 2 (x 1 ). These two Boolean functions belong to
the same class C N 1 and are in the sense of Definition (3.1) equivalent to each other.
For that reason we consider the equivalence relation.
Definition 3.2 (Relation R of Boolean Functions) Two Boolean functions f i (x)
and f j (x) belong to the relation f i (x)Rf j (x) if and only if f i (x) = f j (x ⊕ c) for
any c.
Theorem 3.2 All Boolean functions defined by (3.1) satisfy all three properties of
an equivalence relation; hence, each class C N of Boolean functions defined by (3.1)
is an equivalence class of the relation R.
Proof The vector c = (c 1 , c 2 , . . . , c n ) ∈ B n determines the chosen Boolean
function of the class C N .
Reflexivity: For each function of the class C N the same function is determined
for c = (0, 0, . . . , 0); hence, we have
∀f i (x) ∈ C N : f i (x) R f i (x).
Symmetry: Using any function f i (x) ∈ C N , another function f j (x) ∈ C N is
specified by an arbitrary vector of coefficients c j :
f j (x) = f i (x ⊕ c j ) .
Using the same vector of coefficients c j , we get based on the function f j (x):
f i (x) = f j (x ⊕ c j ) = f i (x ⊕ c j ⊕ c j ) .
Hence, we have
∀f i (x), f j (x) ∈ C N : (f i (x) R f j (x)) ⇔ (f j (x) R f i (x)).
Transitivity: Using any function f i (x) ∈ C N , then another function f j (x) ∈ C N
is specified by an arbitrary vector of coefficients c j :
f j (x) = f i (x ⊕ c j ) .
Using the function f j (x) ∈ C N , another function f k (x) ∈ C N is specified by a vector
of coefficients c k = c j :
f k (x) = f j (x ⊕ c k ) .