Логические и арифметические основы и принципы работы ЭВМ


Понятие покрытия - часть 2


разные простые импликанты могут дать одинаковые конституенты единицы. Поэтому, отбросив в ДНФ лишние члены, получим ее СДНФ.

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

Пример:

f(Х1, Х2)= Х1Х2

Х1Х2
Х1Х2 = Х1Х2
Х1 или Х1Х2
Х2

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

Если теперь провести все операции поглощения, то в полученной форме функции f останутся только простые импликанты. Покажем это. Пусть в результате операций склеивания получится член x, не являющийся простой импликантой.

Тогда x=y*z, где z – простая импликанта, которая так же должна входить в f, т.к. в нее входит x. Но z будет поглощать х, поэтому х не может входить в f. Это и доказывает теорему Квайна.

Замечание: Заметим, что теорема Квайна применяется по отношению к функции СДНФ.

Порядок получения Сок. ДНФ может быть следующим:

  1. Провести все операции неполного склеивания конституент единицы исходной СДНФ. Получатся произведения (n-1) ранга; оставшиеся несклеенные конституенты единицы не могут участвовать в дальнейших склеиваниях.
  2. Провести покрытие всех полученных произведений и конституент единицы. Часть некоторых конституент единицы будет устранена.
  3. Продолжить, пока возможны операции 1) и 2).

Пример 1:

f(Х1, Х2)= Х1Х2

Х1Х2
Х1Х2

Если применим операцию полного склеивания, то получим:

или

f(Х1, Х2)= Х1

Х1Х2

или

f(Х1, Х2)= Х1Х2

Х2

т.е. у нас нет возможности далее провести операцию.

Применим теперь операцию неполного склеивания:

f(Х1, Х2)= Х1

Х1Х2
Х1Х2
Х1Х2
Х2 = Х1
Х2
Х1Х2
Х1Х2
Х1Х2

Простые импликанты: Х1, Х2

Конституенты единицы: Х1Х2, Х1Х2, Х1Х2

Теперь можем провести операции поглощения:

Х1 поглощает: Х1, Х1Х2, Х1Х2




- Начало -  - Назад -  - Вперед -