Суть минимизации методом Квайна

3.1 Минимизируемая функция представляется в СДНФ и к ней применяются все возможные операции неполного склеивания:

1)

а затем поглощения

2) KV KX₀=K(1V X₀)=K, где

3.2 Эта пара операций может применятся многократно:

y= (x_2,x_1,x₀)= Σ(3,4,5,6,7)=V(011,100,101,110,111)

+ + ;

.

4. Суть минимизации методом кубических форм.

4.1. -включает k кубов разных рангов(j).

- покрытие К(Z).

.

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

Ц_n= ΣЦ_k= Σ(n-r)_k,

где – n - число переменных куба;

r - ранг куба.

Ц_k=(n-r)_k - цена k-куба, входящего в покрытие.

4.2. Суть минимизации ФАЛ сводится к поиску покрытия П(Z) кубического комплекса К(Z), имеющего минимальную цену Ц_n= ΣЦ_k ® min.

4.3. Покрытие П(Z) комплекса К(Z), имеющее минимальную цену, называется покрытием Квайна, а соответствующая этому покрытия ДНФ называется минимальной ДНФ (МДНФ).

Пример:

K(Z)=(011,100,101,110,111,-11,11-,1-1,10-,1-0,1- -)

П₁(Z)=(011,100,101,110,11)=K₀; ;

П₂(Z)=(-11,11-,1-1,10-,1-0)=K₁; .

Перебирая сочетания кубов различных рангов можно получить следующее покрытия

П₃(Z)=(011,11-,10-)=K₂, ;

П₄(Z)=(-11,1-1,1-0)=K₃, ;

П₅(Z)=(011,1- -)=K₄ , Ц_n= =3+1=4;

П₆(Z)=(-11,1- -) и т.д. Ц_n= =2+1=3.

Соответствующие ДНФ имеют

,

,

, ,

; .

Дата добавления: 2015-07-02