Реферат: Минимизация функций алгебры логики

Недостаток метода Квайна – необходимость полного по парного сравнения всех 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