Метод квайна (Куайна)

• Определение. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.
• Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.
• Всякий импликант функции f есть часть функции f.
• Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.
• Определение.Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.
• Утверждение. Всякая функция f реализуется своей  сокращенной ДНФ.
• Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
• Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.

Алгоритм Куайна построения сокращенной ДНФ
1.    Получить СДНФ функции.
2.    Провести все операции неполного склеивания.
3.    Провести все операции поглощения.

Пример. Минимизировать функцию f=1111010010101111.
Решение.
1.    Строим таблицу значения для данной функции (табл.). Строим СДНФ функции. При этом слагаемые нумеруем и записываем в столбец (табл.).

2.    Проводим все операции неполного склеивания.
Первый этап склеивания (табл.):

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

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15 (табл.).
Второй этап склеивания:

В процедуре склеивания на втором этапе не принимали участие слагаемые № 5, 8 с предыдущего шага, поэтому после второго этапа склеивания и последующих поглощений получаем, что

Поскольку дальнейшее склеивания невозможны, то это и будет сокращенная ДНФ исходной функции.