Лекции по математической логике и теории алгоритмов (стр. 5 из 10)
Пример 2.3.2. Пусть функция f(x,y,z) задана совершенной ДНФ f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Тогда, производя в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, имеем
f
Таким образом, сокращенной ДНФ функции f является формула y¤x·z.
На практике при выполнении операций неполного склеивания на каждом этапе можно не писать члены, участвующие в этих операциях, а писать только результаты всевозможных полных склеиваний и конъюнкты, не участвующие ни в одном склеивании.
Пример 2 . 3 . 3 . Пусть функция f{x,y,z) задана совершенной ДНФ f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Тогда, производя операции склеивания, а затем элементарного поглощения, имеем
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
Для получения минимальной ДНФ из сокращенной ДНФ используется матрицаКвайна, которая строится следующим образом. В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. В таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.
Для примера 2.3.3. матрица Квайна имеет вид
| импликанты | x ⋅ y⋅ z | x ⋅ y⋅z | x ⋅ y⋅z | x ⋅ y⋅z |
 | * | * | ||
| * | * | |||
| * | * |
В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет все конституенты единицы, т. е. каждый столбец матрицы Квайна содержит звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. В качестве минимальной ДНФ выбирается тупиковая, которая имеет наименьшее число вхождений переменных.
В примере 2.3.3 по матрице Квайна находим, что минимальная ДНФ заданной функции есть x ⋅ y ¤ x ⋅ z .
Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем 
использовать f =f и законы де Моргана.§ 2.4. Карты Карно.
Другой способ получения простых импликант формул с малым числом переменных (и, значит, нахождения минимальной ДНФ) основан на использовании так называемых карт Карно.
Карта Карно - это специального вида таблица, которая позволяет упростить процесс поиска минимальных форм и успешно применяется, когда число переменных не превосходит шести. Карты Карно для функций, зависящих от n переменных, представляет собой прямоугольник, разделенный на 2n клеток. Каждой клетке диаграммы ставится в соответствие двоичный n-мерный набор. Значения заданной функции f из таблицы истинности вносятся в нужные квадраты, однако если клетке соответствует 0, то обычно она остается пустой.
В таб.2.4.1. показан пример разметки карты Карно для функции, зависящей от трех переменных. Нижние четыре клетки карты соответствуют двоичным наборам, в которых переменная x принимает значение 1, четыре верхние клетки соответствуют наборам, в которых переменная x принимает значение 0. Четырем клеткам составляющим правую половину карты, соответствуют наборы, в которых переменная y; принимает значение 1 и т.д. В таб.2.4.2. приведена разметка карты Карно для n=4 переменных.
| y z x | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 | 000 | 001 | 011 | 010 |
| 1 | 100 | 101 | 011 | 010 |
таблица 2.4.1. таблица 2.4.2.
Z w x y | 0 0 | 0 1 | 1 1 | 1 0 |
| 00 | 0000 | 0001 | 0011 | 0010 |
| 01 | 0100 | 0101 | 0011 | 0010 |
| 11 | 1100 | 1101 | 1111 | 1110 |
| 10 | 1000 | 1001 | 1011 | 1010 |
Для построения минимальной ДНФ производится процедура склеивания "1". Склеивающимся значениям "1" соответствуют соседние клетки, т.е. клетки отличающиеся лишь значением одной переменной (на графическом изображении разделенных вертикальной или горизонтальной линией с учетом соседства противоположных крайних клеток).
Процесс склеивания "1" сводится к объединению в группы единичных клеток карты Карно, при этом необходимо выполнять следующие правила;
1. Количество клеток, входящих в одну группу, должно выражаться числом кратным 2, т.е. 2m где m=0,1,2,...
2. Каждая клетка, входящая в группуиз 2m клеток, должна иметь m соседних в группе.
3. Каждая клетка должна входить хотя бы в одну группу.
4. В каждую группу должно входить максимальное число клеток, т.е. ни одна группа не должна содержаться в другой группе.
5. Число групп должно быть минимальным.
Считывание функции f по группе склеивания производится следующим образом: переменные, которые сохраняют одинаковые значения в клетках группы склеивания, входят в конъюнкцию, причем значениям 1 соответствуют сами переменные, а значениям 0 их отрицания.
Приведем шаблоны, которые помогают строить покрытия 1 (переменные считаем теми же, но их писать не будем). Для упрощения записи мы не будем отмечать переменные, хотя сохраним их обозначения как и в таблицах 2.4.1,2.4.2.
А) n=3
F=z f=Ÿx F=Ÿy
| 1 | 1 |
| 1 | 1 |
| F=Ÿy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
B) n=4
F=w f=Ÿy F=Ÿz
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Пример 2.4.1. Построить МДНФ.
Сначала смотрим, есть ли покрытия_1 из 16 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 8 клеток. Смотрим, есть ли покрытия 1 из 8 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий нет. Переходим к покрытиям из 4 клеток. Смотрим, есть ли покрытия 1 из 4 клеток покрывающих хотя бы одну непокрытую 1. Таких покрытий два. Переходим к покрытиям из 2 клеток. Такое покрытие одно. Таким образом, все 1 стали покрытыми. Далее, смотрим можно ли убрать некоторые покрытия, так чтобы все единицы остались покрытыми. В конце выписываем МДНФ: f =x⋅z∨y⋅w∨y⋅z⋅w.
Замечание. Для построения минимальной КНФ функции f, достаточно построить минимальную ДНФ для функции f , а затем 
использовать f =f и законы де Моргана.Глава III. Алгебра Жегалкина.
Множество булевых функций, заданный в базисе Жегалкина S4={∆,&,1} называется алгеброй Жегалкина.
Основные свойства.
1. коммутативность
H1∆H2=H2∆H1, H1&H2=H2&H1;
2. ассоциативность
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)&H3;
3. дистрибутивность
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. свойства констант H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Утверждение 3.1.1. Через операции алгебры Жегалкина можно выразить все другие булевы функции:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y=1∆xy.
Определение. Полиномом Жегалкина (полиномом по модулю 2) от n переменных x1,x2,…,xn называется выражение вида c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, где постоянные скмогут принимать значения 0 ли 1.
Если полином Жегалкина не содержит произведений отдельных переменных, то он называется линейным ( линей ная функция).
Например, f=x∆yz∆xyz и f1=1∆x∆y∆z–полиномы, причем второй является линейной функцией.
Теорема 3.1.1. Каждая булева функция представляется в виде полинома Жегалкина единственным образом.
Приведем основные методы построения полиномов Жегалкина от заданной функции.
1. Метод неопределенных коэффициентов. Пусть P(x1,x2,…,xn) - искомый полином Жегалкина, реализующий заданную функцию f(x1,x2,…,xn). Запишем его в виде
P= c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn.