lec04

Носитель элементарной конъюнкции K ранга r называется

интервалом NK ранга r.

Интервал NK ранга r содержит n-r векторов (вершин в Bn). | NK |= 2n-r. Т.е. все те вектора на r местах на которых сомножители в элементарной конъюнкции будут равны 1.

12

Утверждение 4.1. Для n переменных (x1,x2, … xi, … xn) интервал для конъюнкции K ранга r - грань в Bn, размерность которой равна:

n – r, (количество вершин в интервале).

Совокупность интервалов N1, N2, … Ni, … NS образует покрытие для функции , если выполняется условие:

Nf = N1 N2 … Ni … NS

в частности отсюда вытекает, что целиком содержится Ni Nf.

Интервал Ni называется допустимым, если Ni Nf.

14

Теорема о покрытии БФ интервалами конъюнктов.

Теорема 4.1.

Если D = K1 K2 … KS есть некоторая ДНФ для булевой функции, то соответствующие интервалы для конъюнктов

1, 2 , … ,

образуют покрытие для функции .

Доказательство.

Следует из определения покрытия.

15

Из теоремы 4.1 следует:

Утверждение 4.2.

Nf g = Nf Ng

т.е. фактически наблюдаем связь между операциями над носителями с операциями для функций.

Пусть Вn – вершина булева куба, Вn в точке, где

g( ) = 1 ( ) = 1 или g( ) = 1 Nf или Ng

Nf Ng. Показано, что левая часть лежит в правой

Nf g Nf Ng

Аналогично справа налево показывается и обратное включение:

Nf Ng Nf g Nf g = Nf Ng

16

Рассмотрим (x1,x2, … xn) представленную суммой ДНФ. Минимизируем ее ранг. Имеет смысл рассматривать покрытие

Nf = 1 2 …

которое будет соответствовать

Dmin = 1 2 …

Для булевой функции интервал NK называется максимальным, если:

NK Nf ; NK': NK NK' Nf

(т.е. другого допустимого интервала целиком содержащего в себе исходный).

Логическая сумма всех конъюнкций, отвечающей максимальным интервалам NK для функции называется сокращенной ДНФ - DC.

18

Теорема о равенстве БФ ее сокращенной ДНФ.

Теорема 4.2.

Имеет место = DC.

Доказательство.

Совокупность всех интервалов покрывает ДНФ, что очевидно.

19