Эта публикация цитируется в
7 статьях
Сложность вычислений булевых функций
А. Д. Коршунов Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Булевы функции являются одним из основных объектов дискретной математики, в особенности тех ее разделов, которые входят в математическую логику и математическую кибернетику. Язык булевых функций удобен для описания функционирования многих дискретных систем, например, контактных схем, булевых схем, ветвящихся программ и некоторых других. Важным параметром таких дискретных систем является их сложность. Эта характеристика активно изучается, начиная с работ К. Шеннона. Опубликовано много научных статей, в которых содержится большое число результатов. Цель обзора – изложение основных результатов по сложности вычислений (реализации) булевых функций контактными схемами, булевыми схемами и булевыми схемами без ветвлений, которые получены за последние шестьдесят лет.
Библиография: 165 названий.
Ключевые слова:
базис, булевы схемы, булева функция, глубина и задержка булевой схемы, дизъюнктивная нормальная форма, инвариантные классы булевых функций, клеточная схема, контактная схема без нулевых цепей, логическая формула, нижние оценки сложности схем, параллельно-последовательная контактная схема, симметрическая булева функция, сложность схемы, частичная булева функция.
УДК:
519.95+
519.7
MSC: Primary
06E30,
68Q30,
94C10; Secondary
06E99 Поступила в редакцию: 04.10.2011
DOI:
10.4213/rm9459
Полный текст:
PDF файл (1086 kB)
