Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введём обозначения: . Пусть параметр, равный 0 или 1. Тогда , если , и , если .

Теорема 8.1. Всякая логическая функция может быть представлена в следующем виде:

,

где , а дизъюнкция берётся по всем наборам значений переменных .

Равенство (1) называется разложением по переменным . Формула (1) достаточно громоздка на вид, однако её несложно использовать при небольших значениях и . Например, при значениях , разложение (1) имеет вид:

.

Практический смысл такого разложения очевиден: оно позволяет заменять функцию нескольких переменных суперпозицией конечного числа функций с меньшим количеством переменных. Особенно важен частный случай , когда разложение производится по всем переменным. При этом все переменные в правой части равенства (1) получают фиксированные значения, и функции в конъюнкциях правой части становятся равными 0 или 1, что даёт:

,

где дизъюнкция берётся по всем наборам , на которых . Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции . СДНФ содержит ровно только конъюнкций, сколько единиц в таблице функции ; каждому единичному набору соответствует дизъюнкция всех переменных, в которых взято с отрицанием, если и без отрицания, если . Таким образом, существует взаимно однозначное соответствие между таблицей функции и её СДНФ. Следовательно, для каждой логической функции СДНФ является единственной (с точностью до порядка переменных и конъюнкций).

Пример 1. Составить СДНФ для функции, заданной таблицей:

Поскольку данная таблица (уже встречавшаяся ранее) содержит три единичных набора, СДНФ будет конъюнкцией трёх дизъюнкций. В свою очередь, каждая дизъюнкция включает три переменных – по числу их в функции .

Получим: .

Напомним, что, подобно знаку умножения, знак дизъюнкции в логических формулах часто опускают. Тогда полученное выражение примет более компактный вид:

.

Единственная функция, которая не имеет СДНФ – это константа .

Формулы, содержащие кроме переменных и скобок, только знаки дизъюнкции, конъюнкции и отрицания, будем называть булевыми формулами.

Теорема 8.2. Всякая логическая функция может быть представлена булевой функцией, то есть как суперпозиция дизъюнкции, конъюнкции и отрицания.