1. Сформулируйте алгоритм минимизации ФАЛ методом неопределённых коэффициентов.
2. Минимизировать ФАЛ, принимающую значение 1 на наборах:
1) 3,4,7.
2) 1,2,4.
3) 0,5,7.
4) 0,2,4,6.
5) 1,3,5,7.
6) 0,1,3,4.
7) 2,3,6,7.
8) 1,2,5,7.
9) 2,3,4,5.
10) 1,2,3,7.
11) 0,1,2,5.
12) 1,2,4,5.
13) 0,2,4,7.
14) 0,3,4,7.
15) 1,2,5,6.
16) 0,1,4,5.
17) 0,2,4,7.
18) 0,1,2,3,4
19) 0,3,4,6,7.
20) 0,2,4,6,7.
21) 1,2,3,6,7.
22) 1,2,4,5,6.
23) 1,2,3,4,5,6.
24) 0,1,3,4,6,7.
25) 1,2,3,5,6,7.
26) 0,2,3,4,6,7.
27) 0,2,3,4,5,7.
28) 0,1,2,5,6,7.
29) 2,3,5,6,7.
30) 0,3,4,5,6,7.
31) 0,2,4,5,6,7.
32) 1,2,3,5,6,7.
33) 0,1,2,3,4,5,6.
34) 0,1,2,3,5,6,7.
Сделать проверку, минимизировав функцию с помощью карт Карно и
законов логики.
Тема 6. Минимизация булевых функций в классе ДНФ. Метод Квайна
Минитермами ранга n называются элементарные конъюнкции ранга n, входящие в СДНФ минимизируемой функции.
Первичными импликантами называются элементарные конъюнкции произвольного ранга, которые получаются на заключительном этапе процесса склеивания.
1 Этап. Поиск первичных импликант.
а) все минтермы данной функции складыватся между собой попарно;
б) если два минтерма таковы, что они имеют вид и , то выписывается конъюнкция , являющаяся минитермом (n-1) –го ранга;
в) минитермы n-го ранга, для которых произошло склеивание, отмечаются;
г) после построения всех минитермов (n-1) –го ранга их вновь сравнивают попарно, выписывают минитрмы (n - 2) –го ранга, и отмечают склеивающиеся минитермы (n-1) –го ранга и т.д.;
д) этап склеивания заканчивается когда вновь полученные минитермы 1-го ранга уже не склеиваются между собой.
2 Этап. Расстановка меток.
а) составляется таблица, число строк которой равно числу полученных первичных импликант минимизируемой функции. Число столбцов совпадает с числом минитермов СДНФ.
б) если в некоторый минитерм СДНФ входит какой – либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка.
3 Этап. Нахождение существенных импликант.
Если в каком – либо из столбцов таблицы имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке называется существенной.
а) из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых этими существенными импликантами.
4 Этап. Вычёркивание лишних столбцов.
а) если в таблице меток, полученной на третьем этапе есть два столбца, в которых имеются метки в одинаковых строках, то один из столбцов вычёркивается.
5 Этап. Вычёркивание лишних импликант.
а) если в таблице появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам, исключаются из дальнейшего рассмотрения.
6 Этап. Выбор минимального покрытия.
а) выбираем такую совокупность первичных импликант, которая включает метки во всех столбцах (по крайней мере, по одной метке в каждом столбце);
б) при нескольких возможных вариантах предпочтение отдаётся варианту с минимальным суммарным числом переменных в первичных импликантах, образующих покрытие.
Минимальная форма заданной функции складывается из суммы существенных импликант и первичных, покрывающих оставшиеся термы.
Пример 6.1. Найти МДНФ функции, принимающей значение 1 на наборах: 3,4,5,7,9,11,12,13.
Решение.
Этап 1. Нахождение первичных импликант.
Выпишем термы для 1 значений функции и склеим все возможные:
Из таблицы видно, что наименьшей является импликанта .
Этап 2. Расстановка меток.
Первичные импликанты
Исходные термы
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Этап 3. Находим существенные импликанты.
Существенной импликантой является терм , т.к. во втором столбце стоит одна метка в последней строке. Вычёркиваем столбцы 2, 3,7,8, т.к. в них есть существенная импликанта .
Первичные импликанты
Исходные термы
*
*
*
*
*
*
*
*
Этап 4. Вычёркивание лишних столбцов.
В нашей задаче их нет.
Этап 5. Вычёркивание лишних первичных импликант.
В таблице нет строк, где нет ни одной метки, поэтому лишних импликант нет, и строки не вычёркиваются.
Этап 6. Выбор минимального покрытия.
.
Составив таблицу истинности, убеждаемся в том, что ФАЛ минимизирована верно.
