URN: http://vtn.chdtu.edu.uaurn:2306:44553.2018.162695

DOI: https://doi.org/10.24025/2306-4412.3.2018.162695


S. V. Burmistrov, O. M. Panasco, D. V. Vakulenko


The article describes a matrix method for obtaining the full composition of the groups of relativ-ity of Boolean functions on the basis of a universal permutation matrix. This method makes it possible to obtain the full composition of the group of relativity on the ba-sis of one Boolean function of its composition, the name of the group of relativity (the smallest binary number of Boolean function in the group), to construct the minimal form for any of Boolean functions of the group without the process of minimization if at least one function from the group of relativity is already minimized. The phenomenon of the groups of relativity in symbolic logic is due to the problem of numerology. It is due to the fact that all arguments of Boolean function are absolutely equal, but when constructing a truth table, columns must be put in a certain order. As a result, there are large groups of functions hav-ing the same properties, because they have the same internal structure. The advantage of group data is that they completely cover the full range of Boolean functions without overlapping one another. This makes it possible to significantly reduce the number of objects studied within the complete set L(n) of all Boolean functions f(n) by examining only one Boolean function from the whole group. The full composition of the group of relativity based on the truth table of the function can be formed by performing two equivalence operations – by rearranging columns of arguments in places or by replacing the arguments columns with their inverses, without changing in both cases the values in the column of the result. It is these actions that underlie the implementation of the method. To simplify the implementation of the method, recursive procedures are replaced by cyclic ones. This method is developed as a working tool for studying the relationships between the groups of relativity in terms of the decomposition of Boolean functions in order to find new effective methods of minimization.

Ключові слова

Boolean function; groups of relativity; universal matrix of permutations.

Повний текст:


Пристатейна бібліографія ГОСТ

1. Bibilo, P. N. (2009) Decomposition of Bool-ean functions based on solving logical equa-tions. Minsk: Belarussian Nuclei. 211 p. ISBN 978-985-08-1072-4

2. Kochkarev, Yu. A., Panteleev, N. N., Kazari-nova, N. L. (1999) Classical and alternative minimal forms of logical functions: Catalog – reference book: monograph. G. E. Pukhov Institute for Modeling Problems in the Ener-gy, Cherkasy Institute of Management. Cher-kasy. 195 p.

3. Bibilo, P. N., Pottosin, Yu. V., Cheremisino-va, L. D. (2017) On the scientific heritage of Corresponding Member A. D. Zakrevsky. In-formatics. Joint Institute for Informatics Problems of the National Academy of Scienc-es of Belarus. No. 1 (53). January-March. P. 112–124.

4. Filippov, V. M., Manokhina, T. V., Evdo-kimov, A. A., Sajats, D. S. (2016) Minimiza-tion of functions of the algebra of logic by the method of a non-directed graph. International Journal of Applied and Fundamental Re-search. Technical sciences. No. 8. Р. 509–511.

5. Alekseychuk, A. N., Konyushok, S. N. (2014) The algebraically degenerate approx-imation of Boolean functions. Cybernetics and system analysis. No. 6. P. 112–124.

6. Bibilo, P. N. (2014) Application of binary selection diagrams in the synthesis of logic circuits. Minsk: Belarussian Nuclear. 231 p.

7. Pottosin, Yu. V. (2015) Energy-saving anti-convoy coding of states of asynchronous au-tomaton. PDM Annex. No. 8. Р. 120–123.

8. Cheremisinova, L. D., Novikov, D. Ya. (2008) Verification of the scheme realization of partial Boolean functions. Bulletin of Tomsk State University. Management, Computing and In-formatics. No. 4 (5). Р. 102–111.

9. Zakrevsky, A. D., Toropov, N. R. (2009) Minimization of Boolean functions of many variables in the DNF class-iterative method and program realization. PDM. Annex. No. 1 (3). Р. 5–14.

Copyright (c) 2018 S. V. Burmistrov, O. M. Panasco, D. V. Vakulenko