Краткий курс лекций по Дискретной математике (стр. 8 )

Отметим, что в общем случае решений может быть несколько.

4.Метод Карно.

в

Этот метод минимизации функции производится посредством таблицы, которая называется картой Карно. Карта Карно – это таблица, содержащая 2n ячеек. Каждой ячейке соответствует определенный набор переменных и указывается какое значение на этом наборе принимает функция. Причем соседние ячейки отличаются значением только одной переменной, что позволяет минимизировать ДНФ, используя закон склеивания, объединяя ячейки по 2n в прямоугольники, которые называются контурами. Соседними являются крайние верхние и крайние слева и справа. Необходимо стремиться к тому, чтобы контуры содержали как можно больше ячеек. А количество контуров должно быть минимально возможным. При создании контуров одну и туже ячейку (конъюнкцию) можно включать в несколько контуров в соответствии закона идемпотентности. Каждому контуру соответствует конъюнкция. При соединении двух ячеек исключается одна переменная, четырех – две, восьми – три и т. д. При объединении ячеек исключаются, согласно закона склеивания, переменные, которые входят в конъюнкции с разными значениями. Покажем карты Карно для функций от двух, трех и четырех переменных:

00	01
10	11

000	010	011	001
100	110	111	101

0000	0010	0011	0001
0100	0110	0111	0101
1100	1110	1111	1101
1000	1010	1011	1001

По карте можно составить СДНФ и СКНФ, как по таблице истинности. Мы показали, какие наборы соответствуют каждой ячейке. Для задания функции по карте в ячейке указывается значение функции на данном наборе. Вернемся к примеру из предыдущего пункта и минимизируем функцию с помощью карты.

b   0	c   1	0	d   0
0	1	1	1
a   1	1	0	1
0	1	0	0

Получим такую же ДНФ:

5.Постановка задачи минимизации в геометрической форме.

Обозначим через Еn множество всех наборов из 0 и 1. Это множество будем рассматривать как множество всех вершин единичного n –мерного куба. Само множество Еn будем называть единичным n – мерным кубом. Количество вершин куба Еn равно 2n.

0-мерный куб – это одна вершина или точка.

Одномерный куб – Е1 , множество вершин {(0), (1)}:

Двухмерный куб – Е2 , множество вершин {(00), (01), (10), (11)}:

Трехмерный куб – Е3 , множество вершин {(000), (001), (010), (001), (110), (011), (101), (111)}:

Четырехмерный единичный куб – Е4 :

Пятимерный единичный куб – Е5 :

Заметим, что наборы , соответствующие соседним вершинам куба, т. е. вершинам, которые соединяются ребром, отличаются значением только какой –либо одной координаты, как соседние ячейки карты Карно.

Далее введем понятие грани куба.

Пусть si1 , si2, si3,…, sir фиксированная система чисел из 0 и 1 такая, что Множество всех вершин куба Еп таких, что ai1= si1 , ai2 =si2, ai3= si3,…, air= sir называется (n –r) – мерной гранью.

Введем в рассмотрение множество Nf всех вершин куба таких, что По этому множеству можно однозначно восстановить саму функцию.

Пример: Функции f(x, y, z) соответствует множество Nf = {(000), (100), (101), (110), (111)}.

По данному множеству восстановим булеву функцию:

Графическое представление множества Nf :

Рассмотрим какую –либо элементарную конъюнкцию К из ДНФ функции n –переменных, состоящую из r множителей. Сопоставим ей множество таких наборов, при которых эта конъюнкция равна 1. Обозначим это множество Nk. Полученное таким образом множество называется (n –r) –мерной гранью куба Еn. Количество множителей – r в конъюнкции называется ее рангом. Ранг конъюнкции является и рангом соответствующей грани.

Пример: Дана ДНФ каrой-либо фукнции f(x, y, z) :

Составим для каждой конъюнкции множество Nki:

Nk1= {(100), (101)} – это 3-2=1 – одномерная грань трехмерного куба, ранг равен 2;

Nk2= {(010), (110), (011), (111)} – это 3-1 = 2 – одномерная грань трехмерного куба, ранг - 1;

Nk3= {(011)} – это 3-3=0 – нольмерная грань трехмерного куба, ранг -3.

Легко заметить, что чем меньше ранг конъюнкции. Тем больше мерность соответствующей грани.

Свойства соответствия между f и Nf:

Если f(x1, x2, …, xn) = g(x1, x2, …, xn)Vh(x1, x2, …, xn), то:

1.  Ng Í Nf, Nh Í Nf;

2.  Nf = Ng È Nh.

В частности следует. Что если f – есть ДНФ: f = К1V К2 V…VКs, то из указанных свойств следут, что Nki Í Nf, т. е. Nki – это грань расположенная внутри множества Nf и :

Nf = Nk1È Nk2 È…ÈNks, т. е. множество Nf покрывается гранями Nk1, Nk2 ,…,Nks.

Если грани Nki имеют ранги ri (i = 1-s), то ранг всего покрытия равен

Теперь сформулируем задачу минимизации в геометрической форме (задача о покрытии):

Найти для данного множества Nf такое покрытие гранями Nki, чтобы его ранг был наименьшим.

Пример:

Составим множество Nf ={(000), (100), (101), (110), (100)}

Данное множество имеет точечное покрытие, соответствующее СДНФ, состоящее из 5 нольмерных граней. Используя закон склеивания можно минимизировать СДНФ. Графически эту задачу можно решить так: объединить вершины из множества Nf по возможности в грани большей мерности, а значит меньшего ранга. Покажем это на рисунке:

 

Вершины нижнего основания можно объединить в одну двухмерную грань {(100), (110), (010), (000)}, которой соответствует конъюнкция ; соседние вершины (100) и (101) соединим в одну одномерную грань {(100), (101)}, которой соответствует конъюнкция

Значит, данное множество имеет еще одно покрытие одной двухмерной и одной одномерной гранями, а СДНФ равносильна ДНФ: v

6.Сокращенная ДНФ.

Познакомимся с сопутствующими понятиями.

Максимальная грань: Nk называется максимальной гранью, если не существует Nk’ такая, что:

1.  Nk ÍNf ÍNk’ ;

2.  размерность грани Nk’ больше размерности Nk.

Пример:

для каждой конъюнкции найдем грани и выявим максимальные:

Nk1 ={(000), (100)}- одномерная, максимальная,

Nk2 ={(100), (101)}- одномерная, является подмножеством Nk3, или, покрывается гранью Nk3, поэтому не является максимальной.

Nk3 ={(100), (110), (101), (111)}- двухмерная, максимальная.

Конъюнкции, соответствующие максимальным граням, называются простыми импликантами.

В нашем примере простыми импликантами будут К1 и К3.

ДНФ, являющаяся дизъюнкцией всех простых импликант функции f, называется сокращенной ДНФ.

Алгоритм построения сокращенной ДНФ:

1.  составить какую-либо КНФ функции (можно СКНФ);

2.  раскрыть скобки;

3.  удалить нулевые члены, поглащаемые и дублирующие, т. е. К1К2VK1º K1, K1VK1º K1.

Полученная ДНФ состоит только из простых импликант и является сокращенной.

Пример: Для функции построить сокращенную ДНФ.

Путем равносильных преобразований составим какую-либо КНФ и, выполняя пункты 2 и 3 алгоритма, получим сокращенную ДНФ:

Найдем грани конъюнкций:

Nk1 = {(000), (010)}- одномерная, максимальная,

Nk2 = {(100), (101)}- одномерная, максимальная,

Nk3 = {(000), (100)}- одномерная, максимальная.

Соответствующий рисунок:

 

7.Тупиковая ДНФ. ДНФ Квайна.

Построение сокращенной ДНФ является первым шагом в процессе получения минимальной ДНФ. Следующий шаг минимизации – это построение, так называемых, тупиковых ДНФ.

Дадим определение тупиковой ДНФ:

Покрытие множества Nf максимальными гранями называется неприводимым, если совокупность этих граней, получающаяся из исходной путем выбрасывания какой-либо грани, не будет уже покрытием Nf.

ДНФ, которая соответствует неприводимому покрытию, называется тупиковой ДНФ.

Минимальная ДНФ содержится среди тупиковых.

Тупиковые ДНФ получаются путем выбрасывания из сокращенной ДНФ некоторых простых импликант.

Существуют алгоритмы, при помощи которых получаются единственные для данной функции тупиковые ДНФ. К таким тупиковым ДНФ относится ДНФ Квайна.

Введем сопутствующие понятия.

Ядровая грань: максимальная грань называется ядровой, если ей принадлежит вершина, принадлежащая покрытию Nf только этой грани и не принадлежащая никакой другой максимальной грани.

Множество всех ядровых граней покрытия Nf, называется ядром Nf .

Теперь познакомимся с определением ДНФ Квайна:

ДНФ, которую получают путем выбрасывания всех простых импликант, соответствующих максимальным граням, которые покрываются ядром, называется ДНФ Квайна.

Алгоритм построения ДНФ Квайна:

1.  получить сокращенную ДНФ;

2.  найти ядровые грани;

3.  удалить импликанты, покрываемые ядром.

Полученная ДНФ, является ДНФ Квайна.

В предыдущем примере Nk3 – не является ядровой гранью, т. к. каждая вершина принадлежит другим граням. Тогда сокращенную ДНФ можно еще раз минимизировать, выбросив конъюнкцию , получим ДНФ Квайна : .

Оставшиеся грани Nk1 и Nk2 покрывают Nf. Продемонстрируем это на рисунке:

Отметим справедливость следующего утверждения:

Для любой не тождественно ложной функции существует единственная ДНФ Квайна.

Задачи для самостоятельного решения.

1.  Минимизировать функцию, принимающую значение 1, если большинство переменных равны 1, методом минимизирующих карт.

2.  Для формулы составить множество Nf и изобразить его вершинами куба. Минимизировать методом Карно. Составить сокращенную ДНФ. Определить ядровые грани. Составить ДНФ Квайна.

3.  Графически представлено нольмерное покрытие множества Nf. Составить СДНФ и СКНФ. Составить покрытие ядровыми гранями и записать соответствующую ДНФ Квайна. По данному рисунку составить карту Карно и минимизировать функцию. Сравнить результаты.

4.  Дана функция f(). Составить множество Nf и изобразить его графически.

5.  Для функции из задания 4 составить СКНФ и сокращенную ДНФ. Изобразить сокращенную ДНФ. Найти ядровые грани и построить ДНФ Квайна.

6.  Функция представлена картой Карно. Построить минимальную ДНФ с помощью этой карты.

 

b   0	1	1	0
0	0	1	1
а   0	0	1	1
0	1	1	0

7. Дана функция от четырех переменных f(2,3,6,7,11,13,14,15)=1. Минимизировать ее методом Квайна и методом Карно.

Контрольные вопросы

1.  Определение минимальной ДНФ.

2.  Что собой представляет минимизирующая карта?

3.  Сформулировать утверждение, которое используется в методе минимизирующих карт.

4.  Алгоритм построения минимальной ДНФ с помощью минимизирующей карты.

5.  Этапы минимизации СДНФ при применении метода Квайна.

6.  Что представляет собой карта Карно?

7.  Сколько ячеек можно включать в контуры и почему?

8.  Что представляет собой единичный n-мерный куб?

9.  Какие наборы входят в множество Nf?

10.  Что называется (n-r)- мерной гранью? Как определяется ранг конъюнкции и ранг ДНФ?

11.  Задача минимизации в геометрической форме.

12.  Какая грань называется максимальной? Что такое простая импликанта? Какая ДНФ называется сокращенной?

13.  Методика построения сокращенной ДНФ.

14.  Какое покрытие называется неприводимым? Какие ДНФ называются тупиковыми?

15.  Алгоритм построения ДНФ Квайна.

ЛЕКЦИЯ 9

ТЕМА: ПОЛИНОМ ЖЕГАЛКИНА.

1.  Некоторые логические операции. Двоичное сложение.

2.  Полином Жегалкина.

Главная

1.  Некоторые логические операции. Двоичное сложение.

Пополним список уже известных логических операций, а именно, познакомимся со штрихом Шеффера, стрелкой Пирса и операцией двоичного сложения. На последней остановимся более подробно.

Штрих Шеффера – это новое высказывание, обозначаемое х|y, ложное тогда и только тогда, когда оба высказывания х и у истинны. Приведем таблицу истинности:

х	у	x|у
0	0	1
0	1	1
1	0	1
1	1	0

Легко заметить, что штрих Шеффера – это отрицание конъюнкции или дизъюнкция отрицаний х и у: Следовательно, штрих Шеффера можно прочесть следующим образом: не х или не у.

Используя основные равносильности, можно эту операцию выразить и через другие, например:

Отрицание высказывания можно представить в виде :

Стрелка Пирса – это новое высказывание, обозначаемое х¯ у, истинное тогда и только тогда, когда оба высказывания ложны. Приведем таблицу истинности:

х	у	х¯у
0	0	1
0	1	0
1	0	0
1	1	0

Стрелка Пирса – это отрицание дизъюнкции или конъюнкция отрицаний х и у:

Стрелку Пирса можно прочесть так: не х и не у.

Отрицание высказывания выражается через стрелку Пирса:

Пример: составить КНФ и ДНФ для формулы

Используя новые равносильности и основные равносильности, преобразуем формулу:

Полученная формула является одновременно ДНФ и КНФ.

Двоичное сложение – это новое высказывание, обозначаемое х+у, ложное тогда и только тогда. Когда оба высказывания имеют одинаковые логические значения. Приведем таблицу истинности: