Open Information and Computer Integrated Technologies

The further development of the analytical method for minimizing Boolean functions (BF) in the class of disjunctive normal forms by the numbers of sets of argument values, called -minimization, is proposed. Such an approach allows to reduce the process of minimizing the BF to the use of an exclusively analytical description of all its steps using functions of the number of the set of the BF argument values. In general, the idea is to develop such a toolkit that allows at all stages of the minimization process to operate only with numerical objects – Boolean vectors, not involve a visual analysis of the results of the intermediate steps, and not resort to attracting letter objects. In the future, the implementation of this idea at the software level for computers is assumed. The article consists of two parts. The first part is about calculating the Hamming distance between two Boolean vectors. Its equality to unity is a necessary and sufficient condition for gluing together the constituents of unity (zero) or elementary conjunctions (disjunctions). The Hamming distance between two sets of variable values was calculated using the Zhegalkin operation (inversion of equivalence), the distance matrix was compiled, and the abbreviated disjunctive normal form (DNF) was determined from it. From the abbreviated DNF deadlock form, and among them the minimal ones, were obtained by sorting out subsets of the set of units of the distance matrix. Deadlock forms are found by the units to which the implicants, covering all units of the set of BF values, correspond. The final result is presented, of course, in letter form. The second part of the article is devoted to the formulation and solution of the problem of minimizing BF as a problem of linear integer mathematical programming. The goal function is the arithmetic sum of all implicants of the abbreviated DNF. The system of restrictions is based on the fact that among the set of simple implicants, it is necessary to choose the smallest number of them so that all constituents of the unit of the original BF are covered. Restrictions are based on how much the constituent of a unit is covered by one or another implicant, and they are written in the form of linear inequalities through the symbol "greater than or equal to" with the right-hand sides equal to unity. The solution of the mathematical programming problem requires the use of a distance matrix. Examples of -minimization of BF are given.

Boolean function; Hamming distance; matrix; minimization method; set; gluing; ab-breviated form; deadlock form

Sapozhenko, A. A., Chuhrov, I. P. Minimizacija bulevyh funkcij v klasse diz#junktivnyh normal'nyh form [Minimization of Boolean Functions in the Class of Disjunctive Normal Forms]. Itogi nauki i tehniki. Ser. Teor. verojatn. Mat. stat. Teor. kibernet. Moskva, VINITI Publ., 1987, vol. 25, pp. 68-116.

Lupanov, O. B. O realizacii funkcij algebry logiki formulami konechnyh klassov (formulami ogranichennoj glubiny) v bazise , , [About the realization of Boolean algebra functions by formulas of finite classes (formulas of bounded depth) in a basis , , ]. Problemy kibernetiki, Moskva, Fizmatgiz Publ., 1961, vol. 6, pp. 5-14.

Jablonskij, S. V. Funkcional'nye postroenija v k-znachnoj logike [Functional constructions in k -valued logic]. Tr. MIAN SSSR, Moskva, AN SSSR Publ., 1958, vol. 51, pp. 5-142.

Hamming, R. W. Error Detecting and Error Correcting Codes // Bell System Technical Journal, 1950, vol. 29, no. 2, pp. 147-160.

Senchukov, V. F., Denysova, T. V. Minimizatsiya bulevykh funktsiy za nomeramy naboriv znachen' arhumentiv [Minimize Boolean functions by argument set number numbers]. Otkrytye informacionnye komp'juternye integrirovannye tehnologii: sb. nauch. tr., Har'kov, Nac. ajerokosm. un-t ''HAI'' Publ., 2019, vol. 83, pp. 156-167. doi: 10.32620/oikit.2019.83.11.

Majstrova, T. L. Linejnoe programmirovanie i zadacha minimizacii normal'nyh form bulevyh funkcij [Linear programming and the problem of minimizing nor-mal forms of boolean functions]. Problemy peredachi informacii. Moskva, AN SSSR Publ., 1962, vol. 12, pp. 5-15.

Peskov, R. N., Shhennikov V. N. Sposob minimizacii diz#junktivnyh normal'n-yh form bulevyh funkcij [Method for minimizing disjunctive normal forms of boolean functions]. Vestnik Mordovskogo universiteta. Serija ''Fiz.-mat. nauki'', 2010, no. 4, pp. 26-29.

Pospelov, D. A. Logicheskie metody analiza i sinteza shem. Izd. 3rd, pererab. i dop. [Logical methods of analysis and synthesis of circuits]. Moskva, Jenergija, 1974, 368 p.