Метод Квайна

Метод Квайна основан на применении двух соотношений.

а) соотношение склеивания: ;

б) соотношение поглощения: .

1 Этап. Получение сокращенной днф.

Рассмотрим некоторый импликант функции , являющийся конъюнкцией. Для удобства будем считать, что в него входят первые переменных, т.е., импликант имеет вид .

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

Осуществив склеивания по переменной ,

из них можно получить всевозможные конъюнкции вида . Затем, произведя склеивания по переменной , придем к всевозможным конъюнкциям и т.д., пока не получим .

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

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

Пример 4.1. Пусть функция задана в СДНФ

Получим все простые импликанты функции . Для этого необходимо произвести все возможные склеивания сначала конституент, а затем всех производных конъюнкций более низкого ранга и выполнить все возможные поглощения. Этот процесс иллюстрирует табл. 4.8. Таблица состоит из трех колонок, которые заполняются последовательно. В колонке 1 помещены конституенты единицы. Каждая конституента помечена номером (1-7). В колонке 2 содержатся конъюнкции ранга 3 (номера 8-13), полученные в результате проведения всех возможных склеиваний конституент. Если и конституенты склеились, используется запись , где – результат склеивания. Конституенты, поглощаемые конъюнкциями колонки 2, помечаются значком . В колонке 3 находятся конъюнкции ранга 2, полученные путем проведения всех возможных склеиваний конъюнкций из колонки 2. Поглощаемые ими конъюнкции из колонки 2 отмечаются значком . Конъюнкции из колонки 3 не склеиваютя. Конституенты и конъюнкции более низкого ранга, не участвовавшие в склеивании (не отмеченные значком ), являются простыми импликантами, образующими сокращенную ДНФ функции