Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 55 >>> № 1 JANUARY — FEBRUARY 2019
UDC 519.714.7
A.I. Timoshkin1


1 National Metallurgical Academy of Ukraine, Dnipro, Ukraine

 timoshkin1964@gmail.com

ON AN ALGORITHM FOR CONSTRUCTING REDUCED DNF
OF ORDER-PROMINENT BOOLEAN FUNCTIONS

Abstract. The problem of building the reduced disjunctive normal forms of order-convex Boolean functions is considered. An algorithm of finding the reduced disjunctive normal forms of order-convex Boolean functions is proposed. The algorithm uses notions of partial order theory such as ideal and coideal and has much less time complexity than classical Quine and McCluskey’s algorithm.

Keywords: implicant, lattice, order-convex subset, ideal, coideal.



FULL TEXT

REFERENCES

  1. Aigner M. Combinatorial theory (Russian translation). Moscow: Mir, 1982. 558 p.

  2. Kovalev M.M. Matroids in discrete optimization. Minsk: Izd. «Universitetskoye», 1987. 222 p.

  3. Birkhoff G. Theory of lattices (Russian translation). Moscow: Nauka, 1984. 568 p.

  4. Yablonsky S.V. Introduction to discrete mathematics (Russian translation). Moscow: Nauka, 1986. 384 p.

Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2019 Kibernetika.org. All rights reserved.