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

Более эффективным является выписывание для функции n переменных не всех возможных конъюнкций, а только тех, которые могут присутствовать в ДНФ, эквивалентной минимизируемой функции. Этот прием позволяет уменьшить таблицу и перебор, который мы проводим с целью нахождения МДНФ.

Предположим, что минимизируемая функция задана в СДНФ. Для простоты будем называть элементарные конъюнкции ранга n, входящие в СДНФ минимизируемой функции, минитермами ранга n. Метод состоит из последовательного выполнения следующих этапов.

1. Нахождение первичных импликант. Все минитермы данной функции сравнивают между собой попарно. Если минитермы m_i и m_j таковы, что они имеют вид ax_i и a`x<sub>i</sub>, то вписывается конъюнкция a, являющаяся минитермом (n-1)-го ранга. Будем говорить, что минитерм a покрывает минитерм ax и `ax (покрывается ими). Минитермы n-го ранга, для которых произошло склеивание, отмечаются. После построения всех минитермов (n-1)-го ранга вновь сравнивают их попарно, выписывают минитермы (n-2)-го ранга, отмечают склеивающиеся минитермы (n-1)-го ранга и т.д. Этап заканчивается, когда вновь полученные минитермы i-го ранга уже не склеиваются между собой. Все неотмеченные минитермы называются первичными или простыми импликантами.

ПримерПример 6

f(x₁,x₂,x₃,x₄)=`x<sub>1</sub>`x₂x₃x₄Ú`x<sub>1</sub>x<sub>2</sub>`x₃`x<sub>4</sub>Ú`x₁x₂`x₃x₄Ú

Ú`x<sub>1</sub>x<sub>2</sub>x<sub>3</sub>x<sub>4</sub>Úx<sub>1</sub>`x₂`x<sub>3</sub>x<sub>4</sub>Úx<sub>1</sub>`x₂x₃x₄Úx₁x₂`x<sub>3</sub>`x₄Úx₁x₂x₄`x₃.

Минитермы 4-го ранга:

x₁`x<sub>2</sub>x<sub>3</sub>x*<sub>4</sub>, `x₁x₂`x<sub>3</sub>`x*₄, `x<sub>1</sub>`x₃x₂x*₄, `x₁x₂x₃x*₄,

x₁`x<sub>2</sub>`x₃x*₄, x₁`x<sub>2</sub>x<sub>3</sub>x*<sub>4</sub>, x<sub>1</sub>x<sub>2</sub>`x₃`x*<sub>4</sub>, x<sub>1</sub>x<sub>2</sub>`x₃x*₄.

Образуем минитермы 3-го ранга:

`x<sub>1</sub>x<sub>3</sub>x<sub>4</sub>, `x₂x₃x₄, `x<sub>1</sub>x<sub>2</sub>`x*₃, x₂`x<sub>3</sub>`x*₄,

`x<sub>1</sub>x<sub>2</sub>x<sub>4</sub>, x<sub>2</sub>`x₃x*₄, x₁`x<sub>2</sub>x<sub>4</sub>, x<sub>1</sub>`x₃x₄, x₁x₂`x*₃.

Теперь находим минитермы 2-го ранга: x₂`x₃.

Дальнейшее склеивание невозможно, этап получения простых импликант закончен. Простыми импликантами являются минитермы:

`x<sub>1</sub>x<sub>3</sub>x<sub>4</sub>, `x₂x₃x₄, `x<sub>1</sub>x<sub>2</sub>x<sub>4</sub>, x<sub>1</sub>`x₂x₄, x₁`x<sub>3</sub>x<sub>4</sub>, x<sub>2</sub>`x₃.

2. Расстановка меток. Для данной функции f(x₁,x₂,...,x_n)=Ú_il_i, где l_i - простые импликанты, полученные нами на первом этапе. Для нахождения МДНФ нужно найти минимальное подмножество из l_i, покрывающее конъюнкции исходной СДНФ, для чего необходимо выбросить некоторое количество первичных импликант. На данном этапе составляется таблица, число строк которой равно числу полученных первичных импликант минимизируемой функции, число столбцов совпадает с числом минитермов. Если в некоторый минитерм входит какая-либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка.

Продолжение примера 6. Составим таблицу (табл.9) с метками для рассматриваемой функции, в которой будет 6 строк и 8 столбцов.

Таблица 9

3. Нахождение существенных импликант. Если в каком-либо из столбцов составленной таблицы имеется только одна метка, то первичная импликанта, стоящая в соответствующей строке, называется существенной импликантой. Существенная импликанта не может быть исключена из правой части, так как без нее не будет получено покрытие всего множества T1 данной функции. Поэтому из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов, покрываемых этими существенными импликантами.

Продолжение примера 6. Для нашей функции существенной импликантой является x₂`x<sub>3</sub>. Она покрывает минитермы `xx₁xx₂`xx<sub>3</sub>`xx₄, `xx<sub>1</sub>xx<sub>2</sub>`xx₃`xx<sub>4</sub>, xx<sub>1</sub>xx<sub>2</sub>`xx₃`xx<sub>4</sub>, xx<sub>1</sub>xx<sub>2</sub>xx<sub>4</sub>`xx₃. При переходе к следующему этапу эти минитермы будут вычеркнуты.

4. Вычеркивание лишних столбцов. Исследуется таблица, полученная после третьего этапа. Если в ней есть два столбца, в которых используются метки в одинаковых строках, то один из них вычеркивается. Это можно сделать в силу того, что покрытие оставшегося столбца будет осуществлять покрытие выброшенного минитерма.

Продолжение примера 6. После вычеркивания существенной импликанты и минитермов, которые она покрывает, таблица меток принимает вид, как в табл.5.10:

Таблица 10

В данном случае одинаковых столбцов нет.

5. Вычеркивание лишних первичных импликант. Если после выбрасывания некоторых столбцов на четвертом этапе в таблице появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам, исключаются из дальнейших рассмотрений, так как они не покрывают оставшиеся в рассмотрении минитермы.

6. Выбор минимального покрытия максимальными интервалами. Выбирается такая совокупность первичных импликант, которая включает метки во всех столбцах (по крайней мере, по одной в каждом столбце). При нескольких возможных вариантах отдается предпочтение варианту с минимальным суммарным числом букв в простых импликантах, образующих покрытие.

Окончание примера 6. Для рассматриваемой функции выбираем покрытие из импликант `xx<sub>1</sub>xx<sub>3</sub>xx<sub>4</sub> и xx<sub>1</sub>`xx₂xx₄, так как они совместно покрывают все оставшиеся после четвертого этапа минитермы. Минимальная ДНФ для этой функции имеет вид

f(xx₁,xx₂,xx₃,xx₄)=`xx<sub>1</sub>xx<sub>3</sub>xx<sub>4</sub>Úxx<sub>1</sub>`xx₂xx₄Úxx₂`xx₃.