Методические рекомендации по изучению дисциплины (стр. 8 )

Таким образом,

.

Следуя пунктам 1), 2), 3), 4), находим:

.

1.9 Минимизация булевых функций.

Элементарная конъюнкция () называется импликантом булевой функции , если - тождественно истинная формула.

Упражнение1.9.1 Проверить, что каждая элементарная конъюнкция, входящая в приведённую К. Н.Ф. А, является её импликантой.

Упражнение1.9. 2 Элементарная конъюнкция над множеством переменных является импликантом булевой функции , если и только если

.

Импликант функции называется простым имтликантом, если удаление любой переменной (или её отрицания) из приводит к элементарной конъюнкции, не являющейся простым импликантом этой функции.

Пример1.9.1 Элементарные конъюнкции являются импликантами Д. Н.Ф.

,

(смотри упражнение 1).

а) импликанта не является простой, так как удаление переменной z даёт элементарную конъюнкцию x, которая также является импликантой Д.

Действительно,

;

б) импликанта также не является простой, так как элементарная конъюнкция , полученная из этой импликанты удалением , является импликантой. Действительно,

в) импликанта у является простой, т. к. удаление переменной у из этой импликанты приводит к константе 1, но формула не равносильна 1.

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

Упражнение1.9.3 Доказать, что сокращённая Д. Н.Ф. функции f представляет эту функцию.

Н.Ф. можно получить одним из методов:

а) методом Квайна;

б) геометрическим методом;

в) методом Блейка.

а) Алгоритм метода Квайна применим для любой, не тождественно равной нулю, функции :

1) находим С. Д.Н. Ф. , представляющую функцию ;

2) применяем к последовательно равносильности (если это возможно):

(неполное склеивание по переменной u);

(поглощение),

где и - две элементарные конъюнкции ранга n, входящие в , в качестве логических слагаемых ().

Пример1.9.2 Найдём методом Квайна сокращённую Д. Н.Ф. функции .

Переходя от векторного задания к табличному будем иметь:

0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Таблица

Отсюда

.

Здесь операции неполного склеивания применимы к следующим парам полных элементарных конъюнкций:

и (по переменной )

и (по переменной ).

Применяя к ним операцию полного склеивания, получим:

.

Применяя далее операцию поглощения к тем полным элементарным конъюнкциям, к которым были применены все возможные операции неполного склеивания, получим:

.

К операция неполного склеивания уже применима, т. е. является сокращённой Д. Н.Ф.

Упражнение1.9.4 Проверить, что ; ; - простые импликанты функции

На данном шаге алгоритма операцию поглощения можно осуществлять параллельно с выполнением операции неполного склеивания. А именно, элементарную конъюнкцию К (начиная с первой) пытаемся склеивать с каждой последующей. Осуществив все возможные склеивания К с последующими, записываем только результаты склеиваний, а конъюнкцию К удаляем (при условии, что хотя бы одно склеивание оказалось возможным).

Пример 1.9.2 Найдём сокращённую Д. Н.Ф. функции

.

Переходя к С. Д.Н. Ф., получим:

.

Номерами элементарных дизъюнкций, входящих в будут: 4; 5; 7; 10; 12; 13; 14; 15. Двигаясь справа налево, начиная с элементарной конъюнкции номера 4, выписываем пары номеров элементарных дизъюнкций, которые удаётся склеить:

4 и 5 по переменной ;

4 и 12 по переменной ;

5 и 7 по переменной ;

5 и 13 по переменной ;

7 и 15 по переменной ;

10 и 14 по переменной ;

12 и 13 по переменной ;

12 и 14 по переменной ;

13 и 15 по переменной ;

14 и 15 по переменной .

Так как каждая из элементарных конъюнкций склеивается хотя бы с одной из других элементарных конъюнкций, то выписываем только результаты склеиваний, т. е.

.

Группируем элементарные конъюнкции от одного и того же набора переменных, получим четыре группы элементарных конъюнкций

.

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

Первая группа: 1 и 2 по переменной ;

2 и 3 по переменной .

Вторая группа: 1 и 2 по переменной ;

2 и 3 по переменной .

Третья группа: 1 и 3 по переменной ;

2 и 3 по переменной .

В результате получим:

.

Далее операция склеивания не применима, т. е. полученная Д. Н.Ф. является сокращённой.

Упражнение1.9.5 Применяя метод Квайна найти сокращенные Д. Н.Ф., представляющие функции:

а) ;

б) .

б) Множество двоичных наборов длины п можно рассматривать, как множество вершин n- мерного куба:

- если n=1, то - одномерный куб, т. е. отрезок (2 вершины);

- если n=2, то - двумерный куб, т. е. квадрат (4вершины);

- если n=3, то - трехмерный куб, т. е. обычный куб (8 вершины);

- если n=4, то - четырехмерный куб, (16 вершин) и т. д.

Пусть; . Множество

называется гранью n – мерного куба ; число t называется рангом этой грани, а - её размерностью.

Пример1.9. 4 Найдём грань пятимерного куба .

Согласно определения эту грань составляют те наборы из ,у которых вторая координата равна 1, а четвёртая – нулю. Следовательно:

Упражнение1.9. 6 Найти грани:

а) ; б) ; в) .

Грани n-мерного куба поставим в соответствие элементарную конъюнкцию над множеством переменных .

Упражнение1.9. 7 Доказать, что указанное выше соответствие между множеством граней ранга t n – мерного куба и множеством элементарных конъюнкций над является биективным.

Для каждой функции определим множество

.

Упражнение1.9. 8 Доказать, что элементарная конъюнкция над множеством переменных импликант функции тогда и только тогда, когда

.

Грани n – мерного куба, соответствующие импликантам функции , называются интервалами этой функции. Интервал функции , не содержащийся ни в каком другом её интервале, называется максимальным интервалом.

Упражнение1.9. 8 Доказать, что импликант К над функции является простым тогда и только тогда, когда интервал функции , соответствующий этому импликанту, является максимальным.

Пример1.9. 5 Найдём максимальные интервалы функции

.

Выписываем множество :

(смотри пример 3).

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

Данная функция имеет три максимальных интервала ранга 2 и один максимальный интервал ранга 1:

;

;

;

.

Этим максимальным интервалам соответствуют пустые импликанты: ; ; ; . Следовательно, сокращенной Д. Н.Ф. данной функции является Д. Н.Ф.:

.

Этот же результат был получен в примере 3.

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

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

Упражнение 1.9. 11 Доказать, что если формула

представляет функцию (константу 1), то .

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

1) есть функция простых импликаций функции ;

2) удаление из любого дизъюнктивного члена приводит к Д. Н.Ф., которая не равносильна .

Упражнение 1.9.12 Доказать, что всякая минимальная Д. Н.Ф. является тупиковой.

Ф., представляющую функцию , можно найти согласно следующим предписаниям:

) находим сокращённую Д. Н.Ф., представляющую ;

) строим две тупиковые Д. Н.Ф. функции , удаляя из полученной в ) сокращённой Д. Н.Ф. дизъюнктивные члены, основываясь на упражнении 11;

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

Пример1.9. 6 Найдём минимальную Д. Н.Ф., представляющую функцию из примера 3.

) Н.Ф., представляющая эту функцию получена ранее:

) 1) выясним, можно ли исключить из И дизъюнктивный член . Для этого, следуя упражнению 11, проверяем, представляет ли формула (1)

функцию-константу 1. Нетрудно видеть, что система

не имеет решений, т. е. формула (1) ни на одном наборе из не принимает значение равное 0. Таким образом, формула (1) представляет константу 1 и

.

Д. Н.Ф. может оказаться ещё не тупиковой. Проверим, можно ли из удалить хотя бы один из её дизъюнктивных членов равносильным образом. Рассмотрим формулы:

; (2)

; (3)

. (4)

Формула (2) равна 0 на наборе ; формула (3) равна 0 на наборе ; формула (4) равна 0 на наборе . Следовательно, из (не нарушая равносильности) нельзя удалить ни один из дизъюнктивных членов, т. е. - тупиковая Д. Н.Ф.

) 2) Выясним, можно ли из И исключить дизъюнктивный член .

Формула

равна 0 на наборе , т. е. дизъюнктивный член нельзя исключить из И.

) 3) Формула

равна 0 на наборе , т. е. дизъюнктивный член нельзя исключить из И.

) 4) Формула

равна 0 на наборе , т. е. дизъюнктивный член нельзя исключить из И.

) Выше была только одна тупиковая Д. Н.Ф., представляющая функцию :

,

т. е. она и будет минимальной.

Пример 1.9.7 Найдем минимальную Д. Н.Ф. функции

.

Н.Ф. функции найдём исходя из геометрических соображений.

.

Отметим на трёхмерном кубе вершины, соответствующие наборам из и выделим максимальные интервалы (смотри рисунок 3)

Как видно из рисунка 3, данная функция имеет 1 максимальный интервал ранга два и 2 максимальных интервала ранга один ;

;

.

Находим простые импликанты, соответствующие этим интервалам: ; ; . Таким образом, сокращённая Д. Н.Ф. имеет вид:

.

Следуя предписаниям - ) имеем:

Формулы

;

;

принимают значения 0 на наборах ; ; соответственно, т. е. ни один из дизъюнктивных членов из И удалить нельзя. Следовательно, полученная сокращённая Д. Н.Ф.

будет единственной тупиковой, а значит и минимальной.