Метод Квайна – Мак-Класки

Метод Квайна – Мак-Класки представляет собой модернизацию метода Квайна для нахождения простых импликант.

Основная идея метода заключается в том, что поиск склеивающихся аргументов следует вести среди конъюнкций, отличающихся друг от друга только одним аргументом.

Этапы поиска простейших импликант методом Квайна - Мак-Класки:

1. Закрепить за аргументами определенные места в конъюнкции.

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

3. Получающиеся в результате такой перекодировки двоичные числа разбиваются на группы по числу единиц.

4. Склеивающиеся аргументы нужно искать только между соседними группами.

5. На месте склеивающихся аргументов будем ставить прочерк, а склеившиеся конъюнкции будем помечать *.

6. Повторять шаги 3-5 до тех пор, пока среди конъюнкций не останется склеивающихся между собой.

Пример. Минимизировать функцию

= 0000 + 0001 + 0010 + 0011 + 0100 + 0110 + 0111 + +1000 + 1001 + 1011 + 1111

0 группа: 0000 *

1: 0001 * 0010 * 0100 * 1000 *

2: 0011 * 0110 * 1001 *

3: 0111 * 1011 *

4: 1111 *

0 группа: 000- * 00-0 * 0-00 * -000 *

1: 00-1 * 001- * 0-10 * 01-0 * -001 * 100- *

2: 0-11 * 011- * -011 * 10-1 *

3: -111 * 1-11 *

0 группа: 00-- 00-- 0--0 0--0 -00- -00-

1: 0-1- 0-1- -0-1 -0-1

2: --11 --11

= 00-- + 0--0 + -00- + 0-1- + -0-1 + --11

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

Таблица 3.

Метод импликантных матриц

МДНФ = 0--0 + -00- + --11 =