Теория автоматов. Аралбаев Т.З - 15 стр.

     3. Практическое занятие №3. Метод минимизации Квайна и
Мак-Класски

       Метод получения тупиковых дизъюнктивных нормальных форм ЛФ,
разработанный Квайном и усовершенствованный Мак-Класски, включает четыре
основных этапа:
       1) нахождение всех простых импликант;
       2) построение таблицы покрытий матрицы Квайна;
       3) поиск минимального покрытия функции;
       4) отыскание минимальной формы логической функции.

       3.1 Нахождение всех простых импликант

       Поиск     простых   импликант      осуществляется    последовательным
применением операции склеивания к элементарным конъюнкциям СДНФ с целью
понижения ранга.
       Для удобства склеивания обычно все элементарные конъюнкции ДНФ
кодируются n – разрядным троичным кодом: если переменная входит в ЭК в
прямом виде, то в коде ей соответствует 1, в инверсном – 0, если переменная
отсутствует – Z (или прочерк “-”). Число единиц и нулей в коде определяет его
ранг.
       Каждый этап выполняется последовательно по шагам.

       1. На первом шаге исходное множество ЭК разбивается на группы с
одинаковым числом единиц. Нулевая группа включает код, не содержащей
единиц (если такой имеется). Первая группа включает коды, содержащие по
одной единице, вторая – по две и т.д.
       2. Затем попарно сравниваются между собой все коды соседних групп, т.е.
коды нулевой группы “склеиваются” с кодами первой группы, коды первой
группы – с кодами второй группы и так далее. Операция “склеивания” возможна
лишь для пары кодов, различающихся только в одном разряде: пара
“склеиваемых” кодов заменяется одним кодом меньшего ранга, имеющим Z
(или прочерк “ - ” ) в этом разряде.
       Например пара кодов 0 1 0 Z и 1 1 0 Z заменяется интервалом Z 1 0 Z.
       3 Все коды, участвующие в операции “склеивания”, отмечаются
(например звездочкой “*” или буквой n), так как они поглощаются полученным
кодом. Один и тот же код можно “склеивать” несколько раз. В результаты
операции “склеивания”, проведенных над кодами групп r-ого ранга получаем
производные группы (r - 1) - ого ранга, коды которых подвергаются аналогично
операции склеивания до тех пор, пока не останутся коды, не допускающие
операции “склеивания”, т.е. неотмеченные коды. Совокупность неотмеченных
кодов, соответствует совокупности простых импликант, образующих
сокращенную дизъюнктивную нормальную форму ЛФ.


                                                                           15