Минимизация функций алгебры логики (стр. 2 из 7)

	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