Об одном алгоритме построения сокращенных ДНФ порядково-выпуклых булевых функцій / Тимошкин А. И. (2019)
Ukrainian

інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0000947553
  Кибернетика и системный анализ      А - 2019  /     Випуск (2019, Т. 55, № 1)

Тимошкин А. И.
Об одном алгоритме построения сокращенных ДНФ порядково-выпуклых булевых функцій

Рассмотрена проблема построения сокращенных дизъюнктивных нормальных форм порядково-выпуклых булевых функций. Предложен оригинальный алгоритм нахождения этих форм. Алгоритм использует такие понятия теории упорядоченных множеств как идеал и коидеал и имеет существенно меньшую временную сложность, чем классический алгоритм Квайна - Мак-Класки.

 https://doi.org/10.1007/s10559-019-00109-8
 Scopus

Бібліографічний опис:
Тимошкин А. И.  Об одном алгоритме построения сокращенных ДНФ порядково-выпуклых булевых функцій. Кибернетика и системный анализ. 2019. Т. 55, № 1. С. 39-43. doi: https://doi.org/10.1007/s10559-019-00109-8 URL: http://jnas.nbuv.gov.ua/article/UJRN-0000947553

English  Cybernetics and Systems Analysis   /     Issue (2019, 55 (1))

Timoshkin A.I.
On an algorithm for constructing reduced DNF of order-prominent boolean functions

This paper considers the problem of constructing reduced disjunctive normal forms of order-convex Boolean functions. An original algorithm is proposed for finding these forms. The algorithm uses concepts of the theory of ordered sets such as an ideal and a coideal and has a substantially lower time complexity than the classical Quine–McCluskey algorithm. © 2019, Springer Science+Business Media, LLC, part of Springer Nature.

Keywords: coideal, ideal, implicant, lattice, order-convex subset, Computer science, Cybernetics, coideal, ideal, implicant, lattice, order-convex subset, Boolean functions

Cite:
Timoshkin A.I. (2019). On an algorithm for constructing reduced DNF of order-prominent boolean functions. Cybernetics and Systems Analysis, 55 (1), 39-43. doi: https://doi.org/10.1007/s10559-019-00109-8 http://jnas.nbuv.gov.ua/article/UJRN-0000947553 [In Russian].

 

Інститут інформаційних технологій НБУВ

+38 (044) 525-36-24
libnas@nbuv.gov.ua
Голосіївський просп., 3, к. 209
м. Київ, 03039, Україна