diskr_edit (1023554), страница 12
Текст из файла (страница 12)
AVA&B A (2- ой закон поглощения).
4.5. Булева алгебра (алгебра логики). Полные системы булевых функций
Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества.
Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания.
Система булевых функций {f1, f2, … , fn} называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {, &, V} является полной. Также полными являются следующие системы функций:
а){, V}; б) {, &}; в) {, }.
Полнота систем {, V} и {, &} следует из полноты системы {, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A&B(AVB); AVB (A&B).
Поэтому система {, &, V} может быть сокращена на одну функцию:
Полнота системы {, } следует из полноты системы {, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию:
AB AVB.
4.6. Нормальные формы
Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.
Пример 4.6.
x, y, x&y, x1&x2&(x3) – элементарные конъюнкции.
xVy, x1&x2 Vx1&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 – СДНФ функции двух переменных.
xVx&y, xVy – не СДНФ.
Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных.
Пример 4.9.
x, y, xVy, x1Vx2V(x3) – элементарные дизъюнкции.
x&y, (x1Vx2) & (x1Vx2) – не элементарные дизъюнкции.
Определение 4.8. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций (в вырожденном случае это может быть одна дизъюнкция).
Пример 4.10.
x, x&y, x & x&(y), (x1Vx2)&(x3)&(x1Vx2Vx3) – КНФ.
x&y V x – не КНФ.
Определение 4.9. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания.
Пример 4.11.
xVy, (xVy) &(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) или на (AVB)&(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 Vx3) ~(x1Vx2).
2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим:
(x2&x3) ~ (x1Vx2).
3. Устранив эквивалентность, получим:
(x2&x3) & (x1Vx2) V (x2&x3) & (x1Vx2).
4. Применив закон де Моргана ко второму члену дизъюнкции, получим
(x2&x3) & (x1Vx2) V (x2Vx3) & (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) & (x2Vx2) & (x3Vx1) & (x3Vx2).
Учитывая, что. x2Vx2 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).
После применения шага 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б). В соответствии с этим законом:
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
