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

More about authors
Lapikov Igor I. Cand. Sci. (Eng.); аssociate professor at the Cybersecurity and Digital Technologies Institute of the Russian Technological
MIREA - Russian Technological University
Moscow, Russian Federation Nikonov Vladimir G. Dr. Sci. (Eng.), Professor, Member at the Presidium of the Russian Academy of Natural Sciences
Russian Academy of Natural Sciences
Moscow, Russian Federation Kasyanenko Kristina V. lecturer
S.M.Kirov Military Medical Academy
Saint-Petersburg, Russian Federation
For read the full article, please, register or log in
Abstract:
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.
How to Cite:
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. DOI: 10.33693/2313-223X-2022-9-1-56-92
Reference list:
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.)
Keywords:
Boolean functions, Khachiyan algorithm, adaptive ellipsoid algorithm, Boolean functions classification.