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

       3.2 Построение таблицы покрытий матрицы Квайна

       Таблица покрытий строится следующим образом.
        Строки таблицы соответствуют простым импликантам (неотмеченным
кодам), полученным на первом шаге первого этапа, а столбцы – элементарным
конъюнкциям из СДНФ. На пересечение i-ой строки и j-ого столбца ставится
1, если i-я импликанта покрывает j-ю ЭК из СДНФ.

       3.3 Поиск минимального покрытия функции

       Для нахождения минимального покрытия функции необходимо удалить из
таблицы лишние простые импликанты (строки). Для этого в методе Квайна и
Мак-Класски применяется следующий алгоритм:
       1) если в каком-либо столбце таблицы покрытий имеется только
одна единица, то импликанта, стоящая в соответствующей строке является
существенной (обязательной) и должна входить в минимальное покрытие,
поскольку не используя еѐ, невозможно покрыть все конституенты;
       2) поглощение лишних столбцов (сжатие по столбцам). Из таблицы
удаляется тот столбец, в который полностью входит в любой другой столбец.
Если в таблице покрытий имеется такая пара столбцов ai и aj, что ai  a j , то
столбец aj удаляется, т.к. покрытие этого столбца может производиться путѐм
покрытия оставшегося столбца;
       3) поглощение лишних строк (сжатие по строкам). Если в таблице
покрытий имеется такая пара строк ai и aj, что a j  ai , то срока aj удаляется,
т.к. она поглощается строкой ai;
        4)   последовательное применение двух преобразований (сжатие по
столбцам и строкам).

       3.4 Получение минимальной формы ЛФ

       Простые импликанты, соответствующие строкам, которые входят в
минимальное покрытие, соединяются знаками дизъюнкции и образуют
минимальную дизъюнктивную нормальную форму булевой функции.
       Рассмотрим применение метода Квайна и Мак-Класски на примере.
Пусть ЛФ содержит восемь элементов четвѐртого ранга:

       Y  x1 x 2 x 3 x 4  x1 x 2 x 3 x 4  x1 x 2 x 3 x 4  x1 x 2 x 3 x 4 
        x1 x 2 x 3 x 4  x1 x 2 x 3 x 4  x1 x 2 x 3 x 4  x1 x 2 x 3 x 4

       Процесс склеивания кодов представлен в таблице 3.1


16