Аннотация:
Обзор посвящен проблеме минимизации булевых функций в классе дизъюнктивных нормальных форм (д. н. ф.) и охватывает литературу с 1953 по 1986 годы. Основное внимание в обзоре уделено математическому направлению исследований в области минимизации булевых функций: оценки параметров булевых функций и алгоритмические трудности синтеза минимальных д. н. ф. Кроме того, в обзоре дана классификация алгоритмов минимизации, приведены примеры эвристических алгоритмов минимизации и оценки их эффективности.
Библ. 217.
Образец цитирования:
А. А. Сапоженко, И. П. Чухров, “Минимизация булевых функций в классе дизъюнктивных нормальных форм”, Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет., 25, ВИНИТИ, М., 1987, 68–116; J. Soviet Math., 46:4 (1989), 2021–2052
\RBibitem{SapChu87}
\by А.~А.~Сапоженко, И.~П.~Чухров
\paper Минимизация булевых функций в классе дизъюнктивных нормальных форм
\serial Итоги науки и техн. Сер. Теор. вероятн. Мат. стат. Теор. кибернет.
\yr 1987
\vol 25
\pages 68--116
\publ ВИНИТИ
\publaddr М.
\mathnet{http://mi.mathnet.ru/intv68}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=927297}
\zmath{https://zbmath.org/?q=an:0666.06010|0684.06012}
\transl
\jour J. Soviet Math.
\yr 1989
\vol 46
\issue 4
\pages 2021--2052
\crossref{https://doi.org/10.1007/BF01096022}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/intv68
https://www.mathnet.ru/rus/intv/v25/p68
Эта публикация цитируется в следующих 13 статьяx:
L. Aslanyan, “Logic Separation: Discrete Modelling of Pattern Recognition”, Pattern Recognit. Image Anal., 33:4 (2023), 902
И. П. Чухров, “О свойствах булевых функций с экстремальным числом простых импликант”, Дискретн. анализ и исслед. опер., 29:1 (2022), 74–93
I. P. Chukhrov, “Properties of Boolean Functions with Extremal Number of Prime Implicants”, J. Appl. Ind. Math., 16:1 (2022), 8
И. П. Чухров, “Связные булевы функции с локально экстремальным числом простых импликант”, Дискретн. анализ и исслед. опер., 28:1 (2021), 68–96; I. P. Chukhrov, “Connected Boolean functions with a locally extremal number of prime implicants”, J. Appl. Industr. Math., 15:1 (2021), 17–38
K. N. Petrov, V. G. Gitis, A. B. Derendyaev, Lecture Notes in Computer Science, 12252, Computational Science and Its Applications – ICCSA 2020, 2020, 405
И. П. Чухров, “О сложности минимизации квазициклических булевых функций”, Дискретн. анализ и исслед. опер., 25:3 (2018), 126–151; I. P. Chukhrov, “On the complexity of minimizing quasicyclic Boolean functions”, J. Appl. Industr. Math., 12:3 (2018), 426–441
И. П. Чухров, “Минимальные комплексы граней случайной булевой функции”, Дискретн. анализ и исслед. опер., 21:5 (2014), 76–94
Ю. В. Максимов, “Реализация булевых функций с ограниченным числом нулей в классе дизъюнктивных нормальных форм”, Ж. вычисл. матем. и матем. физ., 53:9 (2013), 1569–1588; Yu. V. Maximov, “Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms”, Comput. Math. Math. Phys., 53:9 (2013), 1391–1409
И. П. Чухров, “О мерах сложности комплексов граней в единичном кубе”, Дискретн. анализ и исслед. опер., 20:6 (2013), 77–94; I. P. Chukhrov, “On complexity measures for complexes of faces in the unit cube”, J. Appl. Industr. Math., 8:1 (2014), 9–19
А. Д. Коршунов, “Сложность вычислений булевых функций”, УМН, 67:1(403) (2012), 97–168; A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165
И. П. Чухров, “О соотношении тупиковых и минимальных комплексов граней в единичном кубе”, Дискрет. матем., 24:2 (2012), 46–74; I. P. Chukhrov, “On the relation between the irredundant and minimal complexes of faces in the unit cube”, Discrete Math. Appl., 22:3 (2012), 273–306
И. П. Чухров, “О тупиковых комплексах граней в единичном кубе”, Дискрет. матем., 23:1 (2011), 132–158; I. P. Chukhrov, “On irredundant complexes of faces in the unit cube”, Discrete Math. Appl., 21:2 (2011), 243–274
И. П. Чухров, “О ядровых и кратчайших комплексах граней в единичном кубе”, Дискретн. анализ и исслед. опер., 18:2 (2011), 75–94; I. P. Chukhrov, “On kernel and shortest complexes of faces in the unit cube”, J. Appl. Industr. Math., 6:1 (2012), 42–55
Цитирование в формате AMSBIB
Обратная связь: