Цена покрытия

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

Цена r-куба представляет собой количество несвязанных координат: S_r= n – r.

Принято использовать два вида цены покрытия:

1.

где N_r - количество r-кубов, входящих в покрытие, m - максимальная размерность кубов, входящих в покрытие. Цена S^a представляет собой сумму цен кубов, входящих в покрытие.

2.

где k - количество кубов, входящих в покрытие.

Определение. Минимальным покрытием называется покрытие, обладающее минимальной ценой S^a по сравнению с любым другим покрытием этой функции.

Можно показать, что покрытие, обладающее минимальной ценой S^a, обладает также и минимальной ценой S^b.

Пример:

C₀(f)=K⁰(f); S^a=5×3=15; S^b=S^a+5=20;

C₁(f)=K¹(f); S^a=4×2=8; S^b=S^a+4=12;

C_min(f) : S^a=3×2=6 ; S^b=9.

Цены покрытия S^a и S^b связаны с ДНФ, соответствующей этому покрытию, следующим образом:

- цена покрытия S^a представляет собой количество букв, входящих в ДНФ;

- цена S^b представляет для ДНФ сумму количества букв и количества термов.

Цена покрытия хорошо согласуется с ценой схемы по Квайну S_Q, которая строится по нормальной форме, соответствующей этому покрытию.

Для приведенной схемы цена по Квайну S_Q= 9 = S^b (9 - число входов в элементы).

В принципе, между S_Q и ценами S^a и S^b существует соотношение S^a £ S_Q £ S^b. Это неравенство имеет место при следующих допущениях:

1. Схема строится по нормальной форме (ДНФ или КНФ).

2. Схема строится на элементах булевого базиса (И, ИЛИ).

3. На входы схемы можно подавать как прямые, так и инверсные значения входных переменных, представляющие собой значения аргументов булевой функции (схема с парафазными входами). В соответствии с этим элементы НЕ (инверторы) в схеме отсутствуют.