3 Derivative Operations for Classes C N of Boolean Functions
81
Fig. 3.6 Karnaugh-map of
the representative function
g re (x) and the independence
matrix IDM(C N (g(x))) that
specify the two Boolean
functions of the calculated
twofold derivative with regard
to (x 2 , x 4 )
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
0
0
1
0
1
1
0
1 x1
x2
0
0
1
0
1
1
0
1
x3 x4
g
re (x)
1
2
3
4
1 2 3 4
i
j
1 0 1 0
0 1 0 0
0 0 0 0
0 0 0 1
IDM(CN (g(x)))
3.4 Conclusion
This contribution extends the theory of derivative operations of the Boolean
differential calculus to classes C N
f re (x), f id (x)
of Boolean functions, where
f re (x) is a representative function of this equivalence class and the independence
function f id (x) indicates the directions of change all functions of this class are
independent of. It has been shown that all derivative operations transform such a
class into another class C N
g re (x), g id (x)
of the same type. If a direction of change
is used for a vectorial derivative operation (which include the single derivative
operations) the given class is depending on, the number of Boolean function of the
resulting class is reduced to one halve of the given functions.
A vectorial derivative of the different Boolean functions of a class C N has in
general different Boolean functions as result. However, if the result of a vectorial
derivative of one Boolean function of a class C N is equal to 0, then the results
of the same vectorial derivatives of all other Boolean functions of this class C N
are also equal to 0. The proof of the associated theorem is a remarkable result of
this contribution that significantly decreases the effort to calculate all derivative
operations for classes C N of Boolean functions.
Based on the provided theory it is not necessary to calculate the derivative
operation for each function of the class separately; it is sufficient to calculate the
required derivative operation for a representative function of the given class and
adjust the associated independence matrix. Algorithms that uniquely determine the
directions of change all functions of the class are not depending on could be reused
from the theory of derivative operations of lattices of Boolean function.
References
1. Posthoff, C., Steinbach, B.: Logic Functions and Equations – Binary Models for Computer
Science, 2nd edn. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-02420-8
2. Stankovi´ c, R. S., Astola, J., Steinbach, B.: Former and recent work in classification of switching
functions. In: Steinbach, B. (ed.) Proceedings of the 8th International Workshops on Boolean
Problems, September 18–19, 2008, pp. 115–126. Freiberg University of Mining and Technology,
Freiberg (2008). ISBN 978-3-86012-346-1
3. Steinbach, B.: Generalized Lattices of Boolean Functions Utilized for Derivative Operations.
Materialy konferencyjne KNWS13, Lagów, pp. 1–17 (2013). https://doi.org/10.13140/2.1.1874.
3680
81
Fig. 3.6 Karnaugh-map of
the representative function
g re (x) and the independence
matrix IDM(C N (g(x))) that
specify the two Boolean
functions of the calculated
twofold derivative with regard
to (x 2 , x 4 )
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1
0
0
1
0
1
1
0
1 x1
x2
0
0
1
0
1
1
0
1
x3 x4
g
re (x)
1
2
3
4
1 2 3 4
i
j
1 0 1 0
0 1 0 0
0 0 0 0
0 0 0 1
IDM(CN (g(x)))
3.4 Conclusion
This contribution extends the theory of derivative operations of the Boolean
differential calculus to classes C N
f re (x), f id (x)
of Boolean functions, where
f re (x) is a representative function of this equivalence class and the independence
function f id (x) indicates the directions of change all functions of this class are
independent of. It has been shown that all derivative operations transform such a
class into another class C N
g re (x), g id (x)
of the same type. If a direction of change
is used for a vectorial derivative operation (which include the single derivative
operations) the given class is depending on, the number of Boolean function of the
resulting class is reduced to one halve of the given functions.
A vectorial derivative of the different Boolean functions of a class C N has in
general different Boolean functions as result. However, if the result of a vectorial
derivative of one Boolean function of a class C N is equal to 0, then the results
of the same vectorial derivatives of all other Boolean functions of this class C N
are also equal to 0. The proof of the associated theorem is a remarkable result of
this contribution that significantly decreases the effort to calculate all derivative
operations for classes C N of Boolean functions.
Based on the provided theory it is not necessary to calculate the derivative
operation for each function of the class separately; it is sufficient to calculate the
required derivative operation for a representative function of the given class and
adjust the associated independence matrix. Algorithms that uniquely determine the
directions of change all functions of the class are not depending on could be reused
from the theory of derivative operations of lattices of Boolean function.
References
1. Posthoff, C., Steinbach, B.: Logic Functions and Equations – Binary Models for Computer
Science, 2nd edn. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-02420-8
2. Stankovi´ c, R. S., Astola, J., Steinbach, B.: Former and recent work in classification of switching
functions. In: Steinbach, B. (ed.) Proceedings of the 8th International Workshops on Boolean
Problems, September 18–19, 2008, pp. 115–126. Freiberg University of Mining and Technology,
Freiberg (2008). ISBN 978-3-86012-346-1
3. Steinbach, B.: Generalized Lattices of Boolean Functions Utilized for Derivative Operations.
Materialy konferencyjne KNWS13, Lagów, pp. 1–17 (2013). https://doi.org/10.13140/2.1.1874.
3680