Разложение булевых функций по переменным.
Пусть G – параметр, равный 0 или 1. Введем обозначение:
Проверкой легко установить, что xG = 1, тогда и только тогда, когда
x = G. Отсюда следует, конъюнкция 
равна 1 (здесь G равен 0 или 1) тогда и только тогда, когда 
. Например, конъюнкция 
(в которой G2 = G1 = 0, G3 = G4 = 1) равна 1 только в случае, когда x1 = x2 = 0, x3 = x4 = 1.
Теорема 1Всякая булева функция f(x1,x2,…,xn) может быть представлена в следующей форме:
, (3.1)
где 1 ≤ k ≤ n, в дизъюнкции берется по всем наборам значений переменных.
Это представление носит название разложения функции по переменным 
. Например, при n = 4, k = 2 разложение (3.1) имеет вид:
.
Докажем справедливость разложения (3.1). Для этого возьмем произвольный набор значений переменных 
. Покажем, что левая и правая части соотношения (3.1) принимают при нем одно и то же значение. Действительно, так как xG = 1 тогда и только тогда, когда x = G, то среди 2К конъюнкции 
правой части (3.1) в единицу обращается только одна, в которой 
. Все остальные конъюнкции равны нулю.
Поэтому 
. В качестве следствия из разложения (3.1) получаем следующие два специальных разложения.
Разложение по переменной xn:
(3.2)
Если булева функция не есть константа 0, то справедливо разложение
Разложение по всем переменным:
, 
(3.3)
где дизъюнкция берется по всем наборам 
, при которых значение функции 
равно 1.
Разложение (3.3) называется совершенной дизъюнктивной нормальной формой (сокращенная запись СДНФ) функции.
Разложение (3.3) дает способ построения СДНФ. Для этого в таблице истинности отмечаем все строки , в которых . Для каждой такой строки образуем конъюнкцию 
и затем все полученные конъюнкции соединяем знаком дизъюнкции.
Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции и ее СДНФ. А это значит, что СДНФ для булевой функции единственна.
Единая булева функция, не имеющая СДНФ, есть константа 0.
Пример 1 Найти совершенную дизъюнктивную форму для функции 
.
Составим таблицу истинности для данной функции:
| 
| 
| 
| 
|
|
Отсюда получаем: = 
= 
.
Важную роль в алгебре логики играет следующее разложение булевых функций.
Теорема 2Всякая булева функция может быть представлена в следующей форме:
(3.4)
где 1≤k≤n, а конъюнкция берется по всем 2k наборам значений переменных.
Действительно, пусть – произвольный набор значений переменных. Покажем, что левая и правая части соотношения (3.4) принимают при нем одно и то же значение. Так как 
только тогда, когда 
, то среди 2k дизъюнкций 
правой части (3.4) в 0 обращается только одна, в которой . Все остальные дизъюнкции равны 1.
Поэтому 
= 
= .
Непосредственно из разложения (3.4) следуют разложения булевых функций:
(3.5)
, 
(3.6)
Последнее разложение носит название совершенной конъюнктивной нормальной формы (СКНФ). Разложение (3.6) дает способ построения СКНФ. Для этого в таблице истинности отмечаем все строки 
, в которых . Для каждой такой строки образуем дизъюнкцию 
и затем все полученные конъюнкции соединяем знаком конъюнкции. Таким образом, существует взаимно однозначное соответствие между таблицей истинности функции и ее СКНФ. А это значит, что СКНФ для булевой функции единственна.
Единственная булева функция, не имеющая СКНФ, есть константа 1.
Пример 2 Найти совершенную конъюнктивную нормальную форму для функции 
.
Составим таблицу истинности для данной функции.
|
|
|
| 
| 
|
|
Отсюда получаем СКНФ
.
Формула вида 
(краткая запись 
), где 
– конъюнкции 
называется дизъюнктивной нормальной формой (ДНФ).
В силу приведенного определения ДНФ будут, например, выражения: 
, 
.
Как отмечено в пункте 2.2, все логические операции можно свести к трем: конъюнкции, дизъюнкции и отрицания. Причем, ввиду закона
де Моргана, знак отрицания можно предполагать отнесенным только к переменным.
Теперь, используя дистрибутивный закон, раскрываем скобки и получаем дизъюнктивную нормальную форму. Итак, справедлива следующая теорема.
Теорема 3 Для любой формулы алгебры логики существует равносильная ей дизъюнктивная нормальная форма.
Доказательство данной теоремы дает способ построения дизъюнктивной нормальной формы для любой формулы алгебры логики.
Пример 3 Найти дизъюнктивную нормальную форму для следующей формулы: 
.
Исключая знак 
по закону 
и применяя законы де Моргана и двойного отрицания, получаем:
Затем, применяя закон дистрибутивности, раскроем скобки
Последнее выражение есть дизъюнктивная нормальная форма.
Форма вида 
(краткая запись 
), где 
- дизъюнкции 
называется конъюнктивной нормальной формой (КНФ).
Такими являются, например, выражения:
, 
.
Как показано выше, для любой формулы алгебры логики существует равносильная ей дизъюнктивная форма. Используя дистрибутивный закон 
, из данной ДНФ легко получить КНФ.
Итак, справедлива следующая теорема.
Теорема 4 Для любой формулы алгебры логики существует равносильная ей конъюнктивная нормальная форма.
Доказательство данной теоремы дает способ построения конъюнктивной нормальной формы для любой формулы алгебры логики.
Пример 4 Найти дизъюнктивную и конъюнктивную нормальные формы для следующей формулы: 
.
Используя закон 
, исключаем знак 
. Получаем формулу 
.
Используя закон де Моргана, получаем формулу 
. Раскрывая скобки, получаем дизъюнктивную нормальную форму
.
Чтобы получить конъюнктивную нормальную форму, применим к формуле дистрибутивный закон, получаем:
.
Последнее выражение является конъюнктивной нормальной формой. Так как 
и 
, то полученная КНФ равносильна следующей КНФ:
.
Среди всех нормальных формул данной формулы выделим совершенную нормальную форму как дизъюнктивную, так и конъюнктивную. Учитывая разложение (3), нетрудно заметить, что совершенная дизъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее дизъюнктивная нормальная форма, в которой:
1) все конъюнкции попарно различны;
2) каждая конъюнкция содержит ровно n переменных;
3) в каждой конъюнкции встречаются все n переменных.
На примере 1 мы рассмотрели один из способов построения СДНФ, основанный на составлении таблицы истинности. Следующий способ построения СДНФ основан на применении законов алгебры логики.
Пример 5 Найти совершенную дизъюнктивную форму формулы 
.
Используя, что , получаем 
. Ввиду законов
де Моргана и двойного отрицания имеем получили дизъюнктивную нормальную форму 
. Данная ДНФ равносильна формуле 
.
Раскрывая скобки, получаем: 
.
Используя закон идемпотентности, получаем требуемую СДНФ:
.
Учитывая разложение (3.6), нетрудно заметить, что совершенная конъюнктивная нормальная форма формулы алгебры логики, содержащей ровно n различных переменных, есть ее конъюнктивная нормальная форма, в которой:
1) все дизъюнкции попарно различны;
2) каждая дизъюнкция содержит ровно n членов;
3) в каждой дизъюнкции встречаются все n переменных.
На примере 2 мы рассмотрели один из способов построения СКНФ, основанный на составлении таблицы истинности. Следующий способ построения СКНФ основан на применении законов алгебры логики.
Пример 6 Найти совершенную конъюнктивную нормальную форму формулы 
.
Используя, , получаем 
.
Данная формула является конъюнктивной нормальной формой. Она равносильна формуле 
.
Используя закон дистрибутивности, получаем:
Применяя закон идемпотентности, получаем требуемую совершенную конъюнктивную нормальную форму
.
Формула алгебры логики называется тождественно истинной, если она при всех значениях входящих в нее переменных принимает значение истинно.
Примерами тождественно истинных формул являются формулы:
Формула алгебры логики называется тождественно ложной, если она при всех значениях, входящих в нее переменных, принимает значение ложь.
Примерами тождественно ложных формул являются формулы:
, 
Формула алгебры логики называется выполнимой, если она при некоторых значениях, входящих в нее переменных, принимает значение истинно.
Примерами выполнимых формул являются следующие формулы:
, 
.
В алгебре логики можно поставить следующую задачу: указать способ (алгоритм), позволяющий для каждой формулы алгебры логики выяснить, является она тождественно истинной или нет. Поставленная задача носит название проблемы разрешения.
Рассмотрим следующие два способа решения этой задачи.
Способ 1 (табличный) Для того, чтобы определить, является ли данная формула тождественно истинной или нет, достаточно составить ее таблицу истинности.
Однако данный способ, хотя и дает принципиальное решение проблемы разрешимости, он довольно громоздкий.
Способ 2 основан на приведении формул к нормальной форме.
Теорема 4Формула алгебры логики тогда и только тогда является тождественно истинной, когда каждая дизъюнкция в ее конъюнктивной нормальной форме содержит некоторую переменную вместе с ее отрицанием.
Действительно, если каждая дизъюнкция в конъюнктивной нормальной форме содержит переменную вместе с ее отрицанием, то все дизъюнкции равны 1, ибо , . Отсюда следует, что КНФ является тождественно истинной.
Пусть теперь данная формула является тождественно истинной, и пусть 
есть некоторая дизъюнкция в КНФ данной формулы. Допустим, что данная дизъюнкция не содержит переменной вместе с ее отрицанием. В таком случае мы можем каждой переменной, не стоящей под знаком отрицания, дать значение 0, а каждой переменной, стоящей под знаком отрицания – значение 1. После указанной подстановки все дизъюнкции станут равны 0, следовательно, формула не является тождественно истинной. Получили противоречие.
Пример 7 Выяснить, будет ли тождественно истинной формула
.
Используя, что , получаем 
.
Применяя закон дистрибутивности, получаем КНФ:
. Так как каждая дизъюнкция содержит некоторую переменную вместе с ее отрицанием, то формула тождественно истинна.
Аналогично предыдущей теореме доказывается теорема:
Теорема 5Формула алгебры логики тогда и только тогда является тождественно ложной, когда каждая конъюнкция в ее дизъюнктивной форме содержит некоторую переменную вместе с ее отрицанием.