Лекции по математической логике и теории алгоритмов (стр. 4 из 10)
Решение.
Таблица 2.2
| x | y | z | основные конъюнкции | f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Основные конъюнкции (или конституенты_1), включенные в таблицу, соответствуют конкретному набору нулей и единиц, которые принимают переменные x,y,z. Строятся конституенты_1 по следующему правилу: переменная входит в произведение сама, если на данном наборе она принимает значение 1, в противном случае в произведение входит ее отрицание. Так, например, на наборе (0,0,1) переменные x,y принимают значение 0 и поэтому в произведение входят их отрицания, а переменная z принимает значение 1 и поэтому входит в произведение сама. Для данного набора (0,0,1) конституента_1 равнаx ⋅ y ⋅ z .
Очевидно, что конъюнкция x ⋅ y ⋅ z равна 1 только на наборе
(0,0,0), а x ⋅ y ⋅ z равна 1 на наборе (0,0,1) и т.д. (см. по таблице). Далее, заметим, что дизъюнкция двух основных конъюнкций равна 1 ровно на двух наборах, которые соответствуют данным основным конъюнкциям. Например, функция x ⋅ y ⋅ z¤x ⋅ y ⋅ z равна 1 только на двух наборах – (0,0,0) и (0,0,1), а на всех других наборах она равна 0. Аналогично, дизъюнкция трех основных конъюнкций равна 1 ровно на трех наборах, которые соответствуют данным основным конъюнкциям и т.д.
Т.о. получаем правило: для построения СДНФ следует выбрать строки, в которых функция равна 1, а затем взять дизъюнкцию соответствующих основных конъюнкций, получим искомую СДНФ. Так для нашего примера, имеем x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Задача.По данной таблице истинности построить СКНФ.
Конституента_0 для набора нулей и единиц (которые принимают переменные x,y,z) строится следующим образом: переменная входит в дизъюнкцию сама, если на данном наборе она принимает значение 0, в противном случае в произведение входит ее отрицание.
Правило для построения СКНФ: следует выбрать строки, в которых функция равна 0, а затем взять конъюнкцию соответствующих конституент_0. В результате получится искомая СКНФ. Так для нашего примера, имеем f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Замечание. Для построения совершенной КНФ функции f, достаточно построить совершенную ДНФ для функции f , а затем 
использовать f =f и законы де Моргана.Построим СКНФ для нашего примера на основании замечания. 1. Строим СДНФ для отрицания.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Используем законы де Моргана f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z == (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .Описанный способ нахождения СДНФ (и СКНФ) по таблице истинности бывает часто более трудоемким, чем следующий алгоритм.
1. Для нахождения СДНФ данную формулу приводим сначала к ДНФ.
2. Если в некоторый конъюнкт К (т.е. К это произведение некоторого числа переменных или их отрицаний) не входит скажем переменная у, то этот конъюнкт заменяем на эквивалентную формулу K&(y ∨ y) и, применяя закон дистрибутивности, приводим полученную формулу к ДНФ; если недостающих переменных несколько, то для каждой из них к конъюнкту добавляем соответствующую формулу вида (y ∨ y) .
3. Если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них. В результате получается СДНФ.
Замечание: Для построения СКНФ в дизъюнкт не содержащий скажем переменную у добавляем формулу вида y⋅ y, т.е. этот дизъюнкт заменяем на эквивалентную формулу D ∨ y⋅ y и, применяя 2-й закон дистрибутивности.
Пример 2 . 2 . 2 . Построить СДНФ для функции f при помощи эквивалентных преобразований.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) =
= x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =ОТСТУПЛЕНИЕ.
Вычисление СДНФ имеет не только теоретическое, но и большое практическое значение. Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется наглядный бланк в виде таблицы: в клетках записываются условия, причем клетки одного столбца считаются соединенными конъюнкцией, а столбцы — дизъюнкцией, то есть образуют ДНФ (или наоборот, в таком случае получается КНФ). В частности, так устроен графический интерфейс QBE (Query-byExample), применяемый для формулировки логических условий при запросе к СУБД.
Алгоритм 2.2.1. Построение СДНФ
Вход: вектор Х: array [l..n] of string - идентификаторов переменных, матрица V: array [1..2n, l..n] of 0..1 всех различных наборов значений переменных,
вектор F: array [1..2n] of 0..1 соответствующих значений функции.
Выход: последовательность символов, образующих запись формулы СДНФ для заданной функции.
f:= false{ признак присутствия левого операнда дизъюнкции }for i from 1 to 2n do
if F[i] = 1 then if f then
yield '¤' { добавление в формулу знака дизъюнкции; оператор yield m выводит на печать
символ m}else f:=true
end if g:=false{ признак присутствия левого операнда конъюнкции }for j from 1 to n do if g then
yield '⁄' {добавление в формулу знака конъюнкции }
elseg: =true
end if if V[i,j}=0 then
yield 'Ÿ' { добавление в формулу знака отрицания }
end ifyield X[j] { добавление в формулу идентификатора переменной
}
end for
end if
end for
§2.3. Минимизация ДНФ методом Квайна.
Каждая формула имеет конечное число вхождений переменных. Под вхождением переменной понимается место, которое переменная занимает в формуле. Задача заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшее число вхождений переменных.
Если х - логическая переменная, а σœ{0,1} то выражение xσ =xx еслиеслиσσ== 10 .
называется литерой. Конъюнктом называется конъюнкция литер. Например, формулы x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x являются конъюнктами. Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза (либо сама либо ее отрицание).
Формула f1 называется импликантой формулы f, если f1 — элементарное произведение и f 1 ⁄ f = f 1 ,т. е. для соответствующих формулам функций справедливо неравенство f 1 § f . Импликанта f1 формулы f называется простой, если после отбрасывания любой литеры из f1 не получается формула, являющаяся импликантой формулы f.
Пример2.3.1. Найдем все импликанты и простые импликанты для формулы f=xØy. Всего имеется 8 элементарных произведений с переменными х и у. Ниже, для наглядности, приведены их таблицы истинности:
| x | y | xØy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | x | y | x | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Из таблиц истинности заключаем, что формулы x ⋅ y , x ⋅ y , x ⋅ y , x ,y— все импликанты формулы xØy, а из этих импликант простыми являются формулы x и у (формула x ⋅ y , например, не является простой импликантой, поскольку, отбрасывая литеру y , получаем импликанту x ).
Сокращенной ДНФ называется дизъюнкция всех простых импликант данной формулы (функции).
Теорема 2.3.1. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.
В примере 2.3.1 функция, соответствующая формулe xØy представима формулой x ∨ y которая является ее сокращенной ДНФ.
Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если из сокращенной ДНФ удалить все лишние импликанты, то получается ДНФ, называемая тупиковой.
Заметим, что представление функции в виде тупиковой ДНФ в общем случае неоднозначно. Выбор из всех тупиковых форм, формы с наименьшим числом вхождений переменных дает минимальную ДНФ {МДНФ).
Рассмотрим метод Квайна, для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие три операции:
1. операция полного склеивания: f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. операция неполного склеивания:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. операция элементарного поглощения f ⋅ x σ ∨ f = f , σ ∈ {0,1} .
Теорема 2.3.2 (теорема Квайна). Если исходя из СДНФ функции произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т. е. дизъюнкция всех простых импликант.