V | V | ||||||
V | V | ||||||
V | V | ||||||
V | V | ||||||
V | V | ||||||
V | V | V | V |
Шаг 4 пропускаем.
Шаг 5.
Выбираем те min-термы, при записи которых, МДНФ функции минимальна.
Шаг 6.
Недостаток метода Квайна – необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант.
Идея модификации метода Квайна – метод Квайна-Мак-Класки. (1.4)
1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.
2. Вся совокупность номеров наборов разбивается на группы в зависимости от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа и.т.д.).
3. Сравниваются две группы, отличающиеся на одну единицу.
4. В результате сравнения в номере набора, имеющего большее число единиц на позиции, где обнаружится разница на одну единицу ставится прочерк.
5. В процессе преобразования возникают новые сочетания (n-группы).
6. Процесс преобразования длится до тех пор, пока возможна операция склеивания.
7. Элементы преобразованных групп являются первичными импликантами, которые вместе с номерами исходных наборов образуют таблицы разметок.
8. В остальном эти методы совпадают с единственным уточнением – если в результате таблицы разметок ни одна из строк не покрывает единицу столбца, то надо выбрать номер столбца набора из предыдущей группы преобразований.
Определение: n-группа – это такой набор аргументовфункции, что число всех аргументов равных единице равно n, причем значении функции равно 1.
Пример:
Составим таблицу истинности:
0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 |
Запишем n-группы:
0-Группа: 0000
1-Группа: 0001, 0010, 0100, 1000
2-Группа: 0011, 0101, 0110, 1001
3-Группа: 0111,1011
4-Группа: 1111
Теперь сравним группы с номерами n и n+1:
0-Группа: 000-, 00-0, 0-00, -000
1-Группа: 00-1, 0-01, -001, 001-, 0-10, 010-,01-0, 100-
2-Группа: 0-11, -011, 01-1, 011-, 10-1
3-Группа: -111, 1-11
Еще раз сравним (при этом прочерки должны быть на одинаковых позициях):
0-Группа: 00--, 0-0-, -00-
1-Группа: 0--1, -0-1, 0-1-, 01—
2-Группа: --11
И еще раз сравним:
0-Группа: 0---
Запишем таблицу исходных min-термов, где функция равна 1:
0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1011 | 1111 |
V | V | V | V | V | V | V | V | 0--- |
Выделим минимальное число групп, покрывающих
Для проверки составим таблицу истинности
1000 | 1001 | 1011 | 1111 |
-00- | V | V | |
-0-1 | V | V | |
-111 | V | V |
Метод минимизирующих карт (для ДСНФ и КСНФ). (1.5)
Одним из способов графического представления булевых функций от небольшого числа переменных являются карты Карно. Их разновидность – карты Вейча, которые строятся как развертки кубов на плоскости, при этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба.
Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на котором значение функции равно единице, а ноль не ставится, а для КСНФ – наоборот.
Диаграмма для двух логических переменных (для ДСНФ):
Для трех переменных:
Карты Карно используются для ручной минимизации функций алгебры логики при небольшом количестве переменных. Правило минимизации: склеиванию подвергаются 2,4,8,16,
клеток и клетки, лежащие на границе карты.При числе переменных 5 и больше отобразить графически функцию в виде единой плоской карты невозможно. Тогда строят комбинированные карты, состоящие из совокупности более простых карт. Процедура минимизации заключается тогда в том, что сначала находится минимальная форма 4-х мерных кубов (карт), а затем, расширяя понятие соседних клеток, отыскивают min-термы для совокупности карт. Причем соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.
Пример: Минимизировать ФАЛ от двух переменных:
1 | 1 | |
1 |
Минимизировать функцию:
1 | 1 | 1 | ||
1 | ||||