52
B. Steinbach and C. Posthoff
3.2 Classes C N of Boolean Functions
Several approaches for classifications of Boolean Functions are given in [2]. One
type of these classes is C N . A class C N contains all functions which can be created
from an arbitrary Boolean function by replacing the variable x i , i = 1, . . . , n, by
the negated variable x i .
Definition 3.1 (Functions of a Class C N ) A Boolean function f i (x) =
f i (x 1 , x 2 , . . . , x n ) that satisfies
f i (x 1 , x 2 , . . . , x n ) = f (x 1 ⊕ c 1 , x 2 ⊕ c 2 , . . . , x n ⊕ c n )
(3.1)
for a given c = (c 1 , c 2 , . . . , c n ) ∈ B n and a given f (x) is an element of the class
C N (f (x)) of Boolean functions.
Sets of Boolean functions that satisfy Condition (3.1) of a class C N are the
solution of Boolean differential equations in which only the function f (x) and all
its vectorial derivatives occur [5]. Such Boolean differential equations (BDE) have
the general form:
D 1
f (x), der
x 1
f (x), . . . , der
x
f (x)
= D 2
f (x), der
x 1
f (x), . . . , der
x
f (x)
.
(3.2)
D 1 , D 2 mean any Boolean function (expression) depending on functions and
vectorial (including single) derivatives.
The knowledge that all other derivative operations can be expressed using only
the function f (x) and all its vectorial derivatives reveals the universality of this
Boolean differential equation. In [5] the following theorem and the associated proof
are given:
Theorem 3.1 If the Boolean function
f (x) = f (x 1 , x 2 , . . . , x n )
is a solution function of the BDE (3.2), then all functions
f (x 1 , x 2 , . . . , x n ) = f (x 1 ⊕ c 1 , x 2 ⊕ c 2 , . . . , x n ⊕ c n )
for c = (c 1 , . . . , c n ) ∈ B n are solution functions of (3.2) too.
Due to this relevance we explore in this contribution the classes C N of Boolean
functions and their derivative operations. It might be assumed that each class C N
contains 2 n Boolean functions f (x 1 , x 2 , . . . , x n ), because there are n coefficients
c i ∈ B in (3.1). However, already the exploration of all Boolean functions of a
single variable x 1 rebuts this assumption.
B. Steinbach and C. Posthoff
3.2 Classes C N of Boolean Functions
Several approaches for classifications of Boolean Functions are given in [2]. One
type of these classes is C N . A class C N contains all functions which can be created
from an arbitrary Boolean function by replacing the variable x i , i = 1, . . . , n, by
the negated variable x i .
Definition 3.1 (Functions of a Class C N ) A Boolean function f i (x) =
f i (x 1 , x 2 , . . . , x n ) that satisfies
f i (x 1 , x 2 , . . . , x n ) = f (x 1 ⊕ c 1 , x 2 ⊕ c 2 , . . . , x n ⊕ c n )
(3.1)
for a given c = (c 1 , c 2 , . . . , c n ) ∈ B n and a given f (x) is an element of the class
C N (f (x)) of Boolean functions.
Sets of Boolean functions that satisfy Condition (3.1) of a class C N are the
solution of Boolean differential equations in which only the function f (x) and all
its vectorial derivatives occur [5]. Such Boolean differential equations (BDE) have
the general form:
D 1
f (x), der
x 1
f (x), . . . , der
x
f (x)
= D 2
f (x), der
x 1
f (x), . . . , der
x
f (x)
.
(3.2)
D 1 , D 2 mean any Boolean function (expression) depending on functions and
vectorial (including single) derivatives.
The knowledge that all other derivative operations can be expressed using only
the function f (x) and all its vectorial derivatives reveals the universality of this
Boolean differential equation. In [5] the following theorem and the associated proof
are given:
Theorem 3.1 If the Boolean function
f (x) = f (x 1 , x 2 , . . . , x n )
is a solution function of the BDE (3.2), then all functions
f (x 1 , x 2 , . . . , x n ) = f (x 1 ⊕ c 1 , x 2 ⊕ c 2 , . . . , x n ⊕ c n )
for c = (c 1 , . . . , c n ) ∈ B n are solution functions of (3.2) too.
Due to this relevance we explore in this contribution the classes C N of Boolean
functions and their derivative operations. It might be assumed that each class C N
contains 2 n Boolean functions f (x 1 , x 2 , . . . , x n ), because there are n coefficients
c i ∈ B in (3.1). However, already the exploration of all Boolean functions of a
single variable x 1 rebuts this assumption.