По отношению к СДНФ применяется операция неполного склеивания, т.к. одно и то же произведение, вообще говоря, может склеиваться с несколькими другими, давая различные импликанты, то чтобы не лишиться возможности провести все операции склеивания, приходится каждое произведение, которое участвовало в операции склеивания, оставить для других операций.
Пример:
f(Х1, Х2)= Х1Х2
Таким образом после выполнения операции неполного склеивания получится не только дизъюнкция простых импликант, но и часть конституент единицы.
Если теперь провести все операции поглощения, то в полученной форме функции f останутся только простые импликанты. Покажем это. Пусть в результате операций склеивания получится член x, не являющийся простой импликантой.
Тогда x=y*z, где z – простая импликанта, которая так же должна входить в f, т.к. в нее входит x. Но z будет поглощать х, поэтому х не может входить в f. Это и доказывает теорему Квайна.
Замечание: Заметим, что теорема Квайна применяется по отношению к функции СДНФ.
Порядок получения Сок. ДНФ может быть следующим:
Пример 1:
f(Х1, Х2)= Х1Х2
Если применим операцию полного склеивания, то получим:
или
f(Х1, Х2)= Х1
или
f(Х1, Х2)= Х1Х2
т.е. у нас нет возможности далее провести операцию.
Применим теперь операцию неполного склеивания:
f(Х1, Х2)= Х1
Простые импликанты: Х1, Х2
Конституенты единицы: Х1Х2, Х1Х2, Х1Х2
Теперь можем провести операции поглощения:
Х1 поглощает: Х1, Х1Х2, Х1Х2