Метод Квайна

Метод применим к СДНФ и основывается на применении двух основных соотношений:

1. склеивание

2. поглощение

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

Для получения МДНФ необходимо убрать из СкДНФ все лишние простые импликанты с помощью импликантной матрицы Квайна. В строках матрицы отмечаются простые импликанты, а в столбцах – конституэнты "1" булевой функции. Минимальные ДНФ строятся по импликантной матрице таким образом:

1) ищутся столбцы матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют ядро булевой функции. Ядро обязательно входит в МДНФ.

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

Пример: .

1) Избавимся от отрицаний и скобок:

2) Восстановим СДНФ, применяя развертывание:

3) Найдем СкДНФ, произведя все возможные склеивания:

4) Ищем МДНФ:

Ядро:

МДНФ: