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