4-Variable Boolean Functions Representations Classification in the Form of Nonlinearity Minimal Degree Separating Surfaces
( Pp. 56-92)

In this paper, a classification study was carried out on the construction of 4-variable Boolean functions representations classification in the form of nonlinearity minimal degree separating surfaces. To construct these surfaces was used an adaptive ellipsoid algorithm based on the Khachiyan algorithm for solving systems of linear inequalities with integer coefficients. To define Boolean functions, we used its graphical representation on the projection of a four-dimensional cube. The classification study carried out was not limited only to the search for a separating surface of the minimum degree of nonlinearity. Additionally, the task was set to find the surface with the smallest number of non-zero nonlinear terms in accordance with a given lexicographic order. Based on the results of the study, a catalog of separating surfaces of the nonlinearity minimum degree with the smallest number of nonlinear terms for Boolean functions of 4 variables is constructed, and it is also determined that 15 classes of geometric equivalence functions have a minimum degree of nonlinearity of 1, 166 - degree 2, 40 - degree 3, and 1 function degree 4.

Lapikov I.I., Nikonov V.G., Kasyanenko K.V., (2022), 4-VARIABLE BOOLEAN FUNCTIONS REPRESENTATIONS CLASSIFICATION IN THE FORM OF NONLINEARITY MINIMAL DEGREE SEPARATING SURFACES. Computational Nanotechnology, 1 => 56-92.

Balakin G.V., Nikonov V.G. Methods of reducing Boolean equations to systems of threshold relations. Review of the appl. Industrial. Math. 1994. Vol. 1. No. 3. Pp. 389-401. (In Rus.)
Ivanescu P.L., Rudeanu S. Boolean methods in operator research and related areas. Berlin; Heidelberg; New York: Springer Verlag, 1968. 331 p.
Khachiyan L.G. Polynomial algorithms in linear programming. ZHVMIMF. 1980. Vol. 20. No. 1. Pp. 51-68. (In Rus.)
Lapikov I.I. On the possibility of constructing a spatial decomposition algorithm based on geometric parallelization of an adaptive ellipsoid algorithm. Computational Nanotechnology. 2018. No. 1. Pp. 140-145. (In Rus.)
Harisson M.A. Introduction to switching and automata theory. NY: McGraw-Hill, 1964. 499 p.
Ninomiya I. A study of the structures of Boolean functions and its application to the synthesis of switching circuits // Mem. Faculty Engineering, Nagoya Univ. 1961. Vol. 13. No. 2. Pp. 149-363.
Nikonov V.G. Classification of minimal basic representations of all Boolean functions from four variables. Review of the Appl. Industrial. Math. 1994. Vol. 1. No. 3. Pp. 458-545. (In Rus.)

Boolean functions, Khachiyan algorithm, adaptive ellipsoid algorithm, Boolean functions classification.