Бинарный граф решений: различия между версиями

Понятие [[булева функция|булевой функции]] – функции с областью определения {0,1}<math>^n</math> и областью значений {0,1} – является одним из базовых понятий для любых вычислений. Булевы функции используются в основополагающих работах по вычислительной сложности [7, 9], а также при проектировании и анализе логических схем [4, 13]. Булева функция может быть представлена в виде таблицы истинности – перечисления значений, принимаемых функцией на каждом элементе {0,1}<math>^n</math>. Поскольку для представления в виде таблицы истинности требуется экспоненциальный относительно n объем памяти, для большинства приложений оно оказывается непрактичным. Следовательно, существует потребность в структурах данных и соответствующих алгоритмах для эффективного представления и обработки булевых функций.

Булевы функции могут быть представлены различными способами. Одним из естественных представлений является схема булевых комбинаций, или просто булева схема [6, глава 34]. Схема состоит из булевых комбинационных элементов, соединенных проводами. Булевыми комбинационными элементами являются вентили и первичные входы. Существуют три типа вентилей: NOT, AND и OR. Вентильная функция NOT работает следующим образом: она принимает одно булево значение-вход и вычисляет одно булево значение-выход, которое принимает значение 0, если вход равен 1, и 1 – если вход равен 0. Вентиль AND принимает два булевых значения-входа и вычисляет одно значение-выход, равное 1, если оба входа имеют значение 1, и 0 в противном случае. Вентиль OR похож на AND, за тем исключением, что выходное значение равно 1 в случае, если одно или оба входных значения равны 1, и 0 в противном случае.

Схемы должны быть бесконтурными; отсутствие контуров обеспечивает возможность однозначным образом протягивать булево присваивание первичным входам по вентилям в топологическом порядке. Из этого следует, что схема на n упорядоченных первичных входах с выделенным вентилем, называемым первичным выходом, соответствует булевой функции на {0,1}<math>^n</math>. Каждая булева функция может быть представлена схемой – например, путем построения схемы, воспроизводящей таблицу истинности.