Минимизация высказываний методом Квайна

 

1. Выражение из произвольной формы приводится к СДНФ.

2. Выполнив в СДНФ все возможные неполные склеивания, а затем все возможные поглощения мы получим Сокращенную ДНФкДНФ). Конъюнкции в СкДНФ называются импликантами.

 
 


Примечание: Склеивание: X×Y Ú X×Y ≡ X

Неполное склеивание: X×Y Ú X×Y ≡ X Ú X×Y Ú X×Y

 

3. На основании СкДНФ и СДНФ строим импликантную матрицу и путем нахождения минимального покрытия этой матрицы получаем минимальную дизъюнктивную нормальную форму (МДНФ).

 

 

Пример 1:

           
   
     
 


f = X×Y×Z Ú X×Y×Z Ú X×Y×Z Ú X×Y×Z Ú X×Y×Z

(I) (II) (III) (IV) (V)

 

I-II : X×Y (VI)

I-III : Y×Z (VII)

I-V : X×Z (VIII )

III-IV : X×Z (IX)

IV-V : Y×Z (X)

VII-X : Z

VIII-IX:Z

 

Импликантная матрица.

  _ _ _ X×Y×Z _ _ X×Y×Z _ _ X×Y×Z _ X×Y×Z _ _ X×Y×Z
_ _ X×Y + +      
_ Z +   + + +

 

СкДНФ(f) = X×Y Ú Z = МДНФ.

 

Пример 2:

                                   
           
           
 


X×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×ZÚX×Y×Z

1 2 3 4 5 6

 

                       
   
           
 
 


1-2 : X×Y СкДНФ = ХYÚY×ZÚX×ZÚY×Z×ÚX×ZÚX×Y

1-4 : Y×Z

2-3 : X×Z

3-6 : Y×Z

4-5 : X×Z

5-6 : X×Y

 

 

Импликантная матрица.

 

  X×Y×Z _ X×Y×Z _ _ X×Y×Z _ X×Y×Z _ _ X×Y×Z _ _ _ X×Y×Z
  X×Y * + * +
  Y×Z # + # +
_ X×Z # + # +
_ _ Y×Z * + * +
_ X×Z * + * +
_ _ X×Y # + # +

МДНФ1 = X×Y Ú Y×Z Ú X×Z

 

МДНФ2 = Y×Z Ú X×Y Ú X×Z