Метод Куайна

Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.

Преобразование функции можно разделить на два этапа:

-на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращённой форме;

-на втором этапе — переход от сокращённой формы к минимальной форме.

Первый этап (получение сокращённой формы):

Представим, что заданная функция представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия: Операция склеивания; Операция поглощения.

Операция склеивания сводится к нахождению пар членов, соответствующих виду или , и преобразованию их в следующие выражения: . Результаты склеивания w теперь играют роль дополнительных членов.

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

Члены сокращённой формы называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ.

Второй этап(табличный) (получение минимальной формы):

Как и на первом этапе, в полученном равенстве могут содержаться члены, устранение которых никаким образом не повлияет на конечный результат. Следующий этап минимизации — удаление таких переменных. Конечное выражение достигается за счёт повторного использования операций склеивания и поглощения.

Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.

Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами (их отмечают) Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой. Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра.

Использование метода для получения минимальной КНФ:

Для получения Минимальной Конъюнктивной Нормальной Формы (МКНФ), используя метод Куайна, вводятся следующие критерии:

1.для минимизации берётся не СДНФ, а СКНФ функции;

2.склеиваемые пары членов меняются на: или ;

3.правило операции поглощения выглядит следующим образом: