 |
Булева алгебра (алгебра логики). Полные системы булевых функций
|
|
|
|
Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества.
Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.
Система булевых функций { f 1, f 2, …, fn } называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {Ø, &, V} является полной. Также полными являются следующие системы функций:
а) {Ø, V}; б) {Ø, &}; в) {Ø, É}.
Полнота систем {Ø, V} и {Ø, &} следует из полноты системы {Ø, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A & B ºØ(Ø A VØ B); A V B º Ø(Ø A &Ø B).
Поэтому система {Ø, &, V} может быть сокращена на одну функцию:
Полнота системы {Ø, É} следует из полноты системы {Ø, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию:
A É B ºØ A V B.
Нормальные формы
Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.
Пример 4.6.
x, y, x & y, Ø x 1& x 2&(Ø x 3) – элементарные конъюнкции.
x V y, x 1&Ø x 2 VØ x 1& x 2 – не элементарные конъюнкции.
Определение 4.5. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций (в вырожденном случае это может быть одна конъюнкция).
|
|
|
Пример 4.7.
x, x & y, x V Ø x &(Ø y), Ø x 1& x 2&(Ø x 3) V x 1&(Ø x 2)& x 3 V x 1& x 2&(Ø x 3) – ДНФ.
(x V y)&Ø x – не ДНФ.
Определение 4.6. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, каждый конъюнктивный член которой содержит все переменные, либо их отрицания.
Пример 4.8.
x & y, x &Ø y V Ø x & y – СДНФ функции двух переменных.
x VØ x & y, x V y – не СДНФ.
Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.
Пример 4.9.
x, y, x V y, Ø x 1V x 2V(Ø x 3) – элементарные дизъюнкции.
x & y, (x 1VØ x 2) & (Ø x 1V x 2) – не элементарные дизъюнкции.
Определение 4.8. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций (в вырожденном случае это может быть одна дизъюнкция).
Пример 4.10.
x, x & y, x & Ø x &(Ø y), (Ø x 1V x 2)&(Ø x 3)&(x 1VØ x 2V x 3) – КНФ.
x & y V Ø x – не КНФ.
Определение 4.9. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания.
Пример 4.11.
x V y, (x VØ y) &(Ø x V y) – СКНФ функции двух переменных.
x &(Ø x V y), x & y – не СКНФ.
Теорема 4.2. Для каждой формулы булевой функции A имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).
Доказательство теоремы состоит просто в указании алгоритмов нахождения для любой формулы A равносильных ей ДНФ и КНФ. Процесс нахождения этих форм называется приведением формулы A соответственно к ДНФ и КНФ. Для каждой формулы A имеется, вообще говоря, бесконечное множество ДНФ и КНФ, но для решения задач, в которых эти формы нужны, требуется, как правило, найти по крайней мере одну из них.
|
|
|
Алгоритм 4.1 (Алгоритм приведения формул булевых функций к ДНФ (КНФ)).
Шаг 1. Все подформулы A вида B É C (т.е. содержащие импликацию) заменяем на Ø B V C или на Ø(B &Ø C) (в соответствии с равносильностью 12 раздела 4.3).
Шаг 2. Все подформулы A вида B ~ C (т.е. содержащие эквивалентность) заменяем на (A & B) V (Ø A &Ø B) или на (A VØ B)&(Ø A V B) (в соответствии с равносильностью 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 (x 1, x 2, x 3) = Ø(x 2 
Ø x 3) ~(Ø x 1V x 2).
1. Устранив импликацию, получим:
Ø(Ø x 2 VØ x 3) ~(Ø x 1V x 2).
2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим:
(x 2& x 3) ~ (Ø x 1V x 2).
3. Устранив эквивалентность, получим:
(x 2& x 3) & (Ø x 1V x 2) V Ø(x 2& x 3) & Ø(Ø x 1V x 2).
4. Применив закон де Моргана ко второму члену дизъюнкции, получим
(x 2& x 3) & (Ø x 1V x 2) V (Ø x 2VØ x 3) & (x 1& Ø x 2).
5. Применив закон дистрибутивности 3а, получим
(x 2& x 3&Ø x 1 V x 2& x 3& x 2) V (Ø x 2& x 1&Ø x 2 V Ø x 3& x 1&Ø x 2).
6. Применив законы идемпотентности 5а и 5б, и располагая переменные по возрастанию индексов, получим:
Ø x 1& x 2& x 3 V x 2& x 3 V x 1&Ø x 2 V x 1&Ø x 2&Ø x 3.
|
|
|
7. Применив 2–ой закон поглощения (6б), вместо Ø x 1& x 2& x 3.V x 2& x 3 запишем x 2& x 3, а вместо x 1&Ø x 2 V x 1&Ø x 2&Ø x 3 запишем x 1&Ø x 2 и в результате получим ДНФ нашей формулы:
f (x 1, x 2, x 3) º x 2& x 3 V x 1&Ø x 2
При приведении к КНФ применим закон дистрибутивности 3б и получим:
x 2& x 3 V x 1&Ø x 2 º (x 2V x 1) & (x 2VØ x 2) & (x 3V x 1) & (x 3VØ x 2).
Учитывая, что. x 2VØ x 2 º 1 (равносильность 11), и применив свойство 9а, получим окончательно КНФ для f (x 1, x 2, x 3)
f (x 1, x 2, x 3) º (x 1V x 2) & (x 1V x 3) & (Ø x 2V x 3).
Приведение некоторой формулы к ДНФ и КНФ не является однозначным. Количество равносильных ДНФ и КНФ, вообще говоря, бесконечно. Однако, совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) или не существуют или единственны.
Теорема 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 (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~(Ø x 1V x 2).
1. Найденная ранее в примере 4.12 ДНФ формулы f (x 1, x 2, x 3) имеет вид:
x 2& x 3 V x 1&Ø x 2.
2. Шаги 2 и 3 алгоритма не требуются (они уже выполнены), поэтому переходим к шагу 4 и применяем 1-ый закон расщепления. В результате вместо каждого из двух конъюнктивных членов получим две элементарных конъюнкции (всего их будет четыре):
f (x 1, x 2, x 3) º x 2& x 3& x 1 V x 2& x 3&Ø x 1V x 1&Ø x 2& x 3 V x 1&Ø x 2&Ø x 3).
3. После применения шага 5 получим:
f (x 1, x 2, x 3) º x 1& x 2& x 3 V Ø x 1& x 2& x 3 V x 1&Ø x 2& x 3 V x 1&Ø x 2&Ø x 3.
4. Шаг 6 не требуется. Найденное выражение формулы f (x 1, x 2, x 3) является СДНФ этой формулы.
Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на V и V на &.
Пример 4.14.
Найдем СКНФ формулы из примера 4.4:
f (x 1, x 2, x 3) = Ø(x 2 Ø x 3) ~(Ø x 1V x 2).
1. Найденная в примере 4.12 КНФ формулы f (x 1, x 2, x 3) имеет вид:
f (x 1, x 2, x 3) º (x 1V x 2) & (x 1V x 3) & (Ø x 2V x 3).
2. Шаги 2 и 3 алгоритма не требуются, поэтому переходим к шагу 4 и применяем 2-ой закон расщепления (равносильность 7б). В соответствии с этим законом:
x 1V x 2 º (x 1V x 2V x 3) & (x 1V x 2VØ x 3).
x 1V x 3 º (x 1V x 3V x 2)&(x 1V x 3VØ x 2).
Ø x 2 V x 3 º(Ø x 2V x 3V x 1) & (Ø x 2V x 3VØ x 1).
Поэтому имеем:
f (x 1, x 2, x 3) = (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1V x 3V x 2)&(x 1V x 3VØ x 2)&(Ø x 2V x 3V x 1)&(Ø x 2 V x 3VØ x 1).
3. Применив шаг 5, получим:
f (x 1, x 2, x 3) º (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1V x 2V x 3)&(x 1VØ x 2V x 3)&(x 1VØ x 2V x 3)&(Ø x 1 VØ x 2V x 3).
4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f (x 1, x 2, x 3):
f (x 1, x 2, x 3) º (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1VØ x 2V x 3)&(Ø x 1VØ x 2V x 3).
|
|
|
