Булева алгебра (алгебра логики). Полные системы булевых функций
Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества.
Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.
Система булевых функций {f1, f2, … , fn} называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {Ø, &, V} является полной. Также полными являются следующие системы функций:
а) {Ø, V}; б) {Ø, &}; в) {Ø, É}.
Полнота систем {Ø, V} и {Ø, &} следует из полноты системы {Ø, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A&B ºØ(ØAVØB); AVB º Ø(ØA&ØB).
Поэтому система {Ø, &, V} может быть сокращена на одну функцию:
Полнота системы {Ø, É} следует из полноты системы {Ø, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию:
AÉB ºØAVB.
Нормальные формы
Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.
Пример 4.6.
x, y, x&y, Øx1&x2&(Øx3) – элементарные конъюнкции.
xVy, x1&Øx2 VØx1&x2 – не элементарные конъюнкции.
Определение 4.5. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций (в вырожденном случае это может быть одна конъюнкция).
Пример 4.7.
x, x&y, x V Øx&(Øy), Øx1&x2&(Øx3) V x1&(Øx2)&x3 V x1&x2&(Øx3) – ДНФ.
(xVy)&Øx – не ДНФ.
Определение 4.6. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, каждый конъюнктивный член которой содержит все переменные, либо их отрицания.
Пример 4.8.
x&y, x&Øy V Øx&y – СДНФ функции двух переменных.
xVØx&y, xVy – не СДНФ.
Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.
Пример 4.9.
x, y, xVy, Øx1Vx2V(Øx3) – элементарные дизъюнкции.
x&y, (x1VØx2) & (Øx1Vx2) – не элементарные дизъюнкции.
Определение 4.8. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций (в вырожденном случае это может быть одна дизъюнкция).
Пример 4.10.
x, x&y, x & Øx&(Øy), (Øx1Vx2)&(Øx3)&(x1VØx2Vx3) – КНФ.
x&y V Øx – не КНФ.
Определение 4.9. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания.
Пример 4.11.
xVy, (xVØy) &(ØxVy) – СКНФ функции двух переменных.
x &(ØxVy), x&y – не СКНФ.
Теорема 4.2. Для каждой формулы булевой функции A имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).
Доказательство теоремы состоит просто в указании алгоритмов нахождения для любой формулы A равносильных ей ДНФ и КНФ. Процесс нахождения этих форм называется приведением формулы A соответственно к ДНФ и КНФ. Для каждой формулы A имеется, вообще говоря, бесконечное множество ДНФ и КНФ, но для решения задач, в которых эти формы нужны, требуется, как правило, найти по крайней мере одну из них.
Алгоритм 4.1 (Алгоритм приведения формул булевых функций к ДНФ (КНФ)).
Шаг 1. Все подформулы A вида B É C (т.е. содержащие импликацию) заменяем на ØBVC или на Ø(B&ØC) (в соответствии с равносильностью 12 раздела 4.3).
Шаг 2. Все подформулы A вида B ~ C (т.е. содержащие эквивалентность) заменяем на (A&B) V (ØA&ØB) или на (AVØB)&(ØAVB) (в соответствии с равносильностью 13).
Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20).
Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8).
Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18).
Шаг 6. для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11.
Очевидно, что в результате всех указанных операций формула имеет вид ДНФ или КНФ. Указанные операции, вообще говоря, могут осуществляться в любом порядке, однако целесообразно придерживаться изложенного выше, за исключением снятия двойных отрицаний (шаг 4), от которых следует избавляться по мере их появления.
Пример 4.12.
Приведем к ДНФ и КНФ рассмотренную ранее в примере 4.4 формулу f(x1, x2, x3) = Ø(x2 
Øx3) ~(Øx1Vx2).
1. Устранив импликацию, получим:
Ø(Øx2 VØx3) ~(Øx1Vx2).
2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим:
(x2&x3) ~ (Øx1Vx2).
3. Устранив эквивалентность, получим:
(x2&x3) & (Øx1Vx2) V Ø(x2&x3) & Ø(Øx1Vx2).
4. Применив закон де Моргана ко второму члену дизъюнкции, получим
(x2&x3) & (Øx1Vx2) V (Øx2VØx3) & (x1& Øx2).
5. Применив закон дистрибутивности 3а, получим
(x2&x3&Øx1 V x2&x3&x2) V (Øx2&x1&Øx2 V Øx3&x1&Øx2).
6. Применив законы идемпотентности 5а и 5б, и располагая переменные по возрастанию индексов, получим:
Øx1&x2&x3 V x2&x3 V x1&Øx2 V x1&Øx2&Øx3.
7. Применив 2–ой закон поглощения (6б), вместо Øx1&x2&x3.V x2&x3 запишем x2&x3, а вместо x1&Øx2 V x1&Øx2&Øx3 запишем x1&Øx2 и в результате получим ДНФ нашей формулы:
f(x1, x2, x3) º x2&x3 V x1&Øx2
При приведении к КНФ применим закон дистрибутивности 3б и получим:
x2&x3 V x1&Øx2 º ( x2Vx1) & (x2VØx2) & (x3Vx1) & (x3VØx2).
Учитывая, что. x2VØx2 º 1 (равносильность 11), и применив свойство 9а, получим окончательно КНФ для f(x1, x2, x3)
f(x1, x2, x3) º ( x1Vx2) & (x1Vx3) & (Øx2Vx3).
Приведение некоторой формулы к ДНФ и КНФ не является однозначным. Количество равносильных ДНФ и КНФ, вообще говоря, бесконечно. Однако, совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) или не существуют или единственны.
Теорема 4.3. Каждая формула A, не равная тождественно нулю, может быть приведена к СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов.
Теорема 4.4. Каждая формула A, не равная тождественно единице, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.
Доказательство этих теорем состоит в указании алгоритма приведения формулы А к СДНФ и СКНФ.
Алгоритм 4.2. (Алгоритм приведения формулы булевой функции к СДНФ)
Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А.
Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями:
A&ØA º 0, B&0 º 0, СV0 º С.
Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&A º A.
Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание Øx, то на основании 1- го закона расщепления (равносильность 7а) заменяем С на (С&x) V (C&Øx).
Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1, ..., n) на i-ом месте была либо переменная xi, либо ее отрицание Øxi.
Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС º С.
Пример 4.13.
Найдем СДНФ формулы из примера 4.4:
f(x1, x2, x3) = Ø(x2 Øx3) ~(Øx1Vx2).
1. Найденная ранее в примере 4.12 ДНФ формулы f(x1, x2, x3) имеет вид:
x2&x3 V x1&Øx2.
2. Шаги 2 и 3 алгоритма не требуются (они уже выполнены), поэтому переходим к шагу 4 и применяем 1-ый закон расщепления. В результате вместо каждого из двух конъюнктивных членов получим две элементарных конъюнкции (всего их будет четыре):
f(x1, x2, x3) º x2&x3&x1 V x2&x3&Øx1V x1&Øx2&x3 V x1&Øx2&Øx3).
3. После применения шага 5 получим:
f(x1, x2, x3) º x1&x2&x3 V Øx1&x2&x3 V x1&Øx2&x3 V x1&Øx2&Øx3.
4. Шаг 6 не требуется. Найденное выражение формулы f(x1, x2, x3) является СДНФ этой формулы.
Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на V и V на &.
Пример 4.14.
Найдем СКНФ формулы из примера 4.4:
f(x1, x2, x3) = Ø(x2 Øx3) ~(Øx1Vx2).
1. Найденная в примере 4.12 КНФ формулы f(x1, x2, x3) имеет вид:
f(x1, x2, x3) º (x1Vx2) & (x1Vx3) & (Øx2Vx3).
2. Шаги 2 и 3 алгоритма не требуются, поэтому переходим к шагу 4 и применяем 2-ой закон расщепления (равносильность 7б). В соответствии с этим законом:
x1Vx2 º ( x1Vx2Vx3) & (x1Vx2VØx3).
x1Vx3 º (x1Vx3Vx2)&(x1Vx3VØx2).
Øx2 Vx3 º(Øx2Vx3Vx1) & (Øx2Vx3VØx1).
Поэтому имеем:
f(x1, x2, x3) = (x1Vx2Vx3)&(x1Vx2VØx3)&(x1Vx3Vx2)&(x1Vx3VØx2)&(Øx2Vx3Vx1)&(Øx2 V x3VØx1).
3. Применив шаг 5, получим:
f(x1, x2, x3) º (x1Vx2Vx3)&(x1Vx2VØx3)&(x1Vx2Vx3)&(x1VØx2Vx3)&(x1VØx2Vx3)&(Øx1 VØx2Vx3).
4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f(x1, x2, x3):
f(x1, x2, x3) º (x1Vx2Vx3)&(x1Vx2VØx3)&(x1VØx2Vx3)&(Øx1VØx2Vx3).