Minimization of Boolean functions in the class of orthogonal disjunctive normal forms
https://doi.org/10.37661/1816-0301-2021-18-2-33-47
Abstract
The orthogonal disjunctive normal forms (DNFs) of Boolean functions have wide applications in the logical design of discrete devices. The problem of DNF orthogonalization is to get for a given function such a DNF that any two its terms would be orthogonal, i. e. the conjunction of them would be equal identically to zero. An approach to solve the problem using the means of graph theory is suggested. The approach is proposed by representation of the function as perfect DNF. Obtaining all the intervals of the Boolean space where the given function has value 1 is supposed, and the intersection graph of those intervals is considered. Two methods to obtain a minimum orthogonal DNF are considered. One of them reduces the problem toward finding out the smallest dominating set in the graph by covering its vertices with their closed neighborhoods, the other - to obtain the maximum independent set by lexicographic enumeration. It is shown how the suggested approach can be extended on incompletely specified Boolean functions.
About the Author
Yu. V. Pottosin
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Russian Federation
Russian Federation
Yuri V. Pottosin - Cand. Sci. (Phys.-Math.), Leading Researcher, The United Institute of Informatics Problems of the National Academy of Sciences of Belarus.
st. Surganova, 6, Minsk, 220012.
References
1. Kuznetsov O. P. Orthogonal systems of Boolean functions and their applications in analysis and synthesis of logical networks. Avtomatika i telemehanika [Automatics and Remote Control], 1970, no. 10, pp. 117-128 (In Russ.).
2. Baranov S. I. Sintez mikroprogrammnyh avtomanov. Synthesis of Microprogrammed Automata. Leningrad, Energia, 1979, 232 p. (In Russ.).
3. Zakrevskij A. D. Logicheskij sintez kaskadnyh shem. Logical Synthesis of Cascaded Circuits. Moscow, Nauka, 1981, 416 p. (In Russ.).
4. Zakrevskij A. D., Balaklej L. I., Eliseeva N. A., Oranov A. M., Pottosin Yu. V., Jankovskaja A. E. Sintez asinhronnyh avtomatov na EVM. Synthesis of Asynchronous Automata in a Computer. Minsk, Nauka i tehnika, 1975, 184 p. (In Russ.).
5. Bibilo P. N. Sintez kombinatsionnyh PLM-struktur dl'a SBIS. Synthesis of Combinational PLA-structures for VLSI. Minsk, Navuka i tehnika, 1992, 323 p. (In Russ.).
6. Zakrevskij A. D., Pottosin Yu. V. Calculation of engineering system reliability when the critical set of events is given. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Akademii nauk Belarusi, 1996, pp. 123-131 (In Russ.).
7. Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals of Discrete Devices Design. Moscow, Fizmatlit, 2007, 592 p. (In Russ.).
8. Matrosova A. Yu. On probabilistic simulation of discrete devices. Avtomatika i telemehanika [Automatics and Remote Control], 1995, no. 3, pp. 156-164 (In Russ.).
9. Gavrilov M. A., Devjatkov V. V., Pupyrev E. I. Logicheskoe proektirovanie diskretnyh avtomatov (jazyki, metody, algoritmy). Logical Design of Discrete Automata (Languages, Methods, Algorithms). Moscow, Nauka, 1977, 352 p. (In Russ.).
10. Bibilo P. N., Enin S. V. Sintez kombinatsionnyh shem metodom funkcional'noj dekompozicii. Synthesis of Combinational Circuits by the Method of Functional Decomposition. Minsk, Nauka i tehnika, 1987, 189 p. (In Russ.).
11. Kardash S. N. Orthogonalization of a DNF system of Boolean functions. Informacionnye tehnologii i sistemy 2020 (ITS 2020): materialy Mezhdunarodnoj nauchnoj konferencii, Minsk, Belarus', 18 nojabrja 2020 g. [Informational Technologies and Systems 2020 (ITS 2020): Proceedings of International Scientific Conference, Minsk, Belarus, 18 November 2020], Minsk, Belorusskij gosudarstvennyj universitet informatiki i radiojelektroniki, 2020, pp. 41-42 (In Russ.).
12. Pottosin Yu. V. Metody diskretnoj matematiki v proektirovanii cifrovyh ustrojstv. Discrete Mathematics Methods in Digital Devices Design. Saarbrucken, LAP LAMBERT Academic Publishing, 2017, 176 p. (In Russ.).
13. Pottosin Yu. V., Shestakov E. A. Orthogonalization of a system of completely specified Boolean functions. Logicheskoe proektirovanie [Logical Design]. Minsk, Institut tehnicheskoj kibernetiki Nacional'noj akademii nauk Belarusi, 2000, pp. 107-115 (In Russ.).
14. Parshina N. A. Minimization of partial Boolean functions in the class of orthogonal DNFs. Novye informacionnye tehnologii v issledovanii diskretnyh struktur: doklady Vtoroj Vserossijskoj konferencii [Novel Information Technologies in the Research of Discrete Structures: Proceedings of the Second All-Russian Conference]. Ekaterinburg, Ural'skoe otdelenie Rossijskoi akademii nauk, 1998, pp. 181-184 (In Russ.).
15. Pottosin Yu. V. Orthogonalization of a system of incompletely specified Boolean functions. Voprosy sinteza logiki CVM [The Problems of Digital Computer Logic Synthesis]. Kaunas, KPI, 1976, part III, pp. 39-42 (In Russ.).
16. Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I. Lekcii po teorii grafov. Lectures on Graph Theory. Moscow, Nauka, 1990, 384 p. (In Russ.).
Review
For citations:
Pottosin Yu.V. Minimization of Boolean functions in the class of orthogonal disjunctive normal forms. Informatics. 2021;18(2):33-47. (In Russ.) https://doi.org/10.37661/1816-0301-2021-18-2-33-47
Views: 515
Email this article 