Минимизация КНФ

По аналогии с ДНФ производится в два этапа:

· нахождение сокращенной КНФ – конъюнкции всех простых имплициент;

· нахождение минимальной КНФ – удаление лишних простых имплициент.

Поиск сокращенной КНФ основан на операциях:

1. неполного склеивания: (А Ú х) (А Ú ù х) = (А Ú х) (А Ú ù х) А,

где А – любая элементарная дизъюнкция;

2. поглощения: (А Ú ) A = A, где Î { x, ù x }.

Пример: Дана функция трех переменных:

Таблица 2.27 – Логическая функция трех переменных

х1	х2	х3	F

СКНФ: F = (x₁ Ú x₂ Ú x₃) (x₁ Ú ù x₂ Ú x₃) (x₁ Ú ù x₂ Ú ù x₃).

После склеек и поглощений имеем: F = (x₁ Ú x₃) (x₁ Ú ù x₂ ).

То же по картам Карно:

Таблица 2.28 – Минимизация КНФ по карте Карно

x1 \ x2 x3
				0

x₁ Ú ù x₂ x₁ Ú x₃

Возможен другой подход к минимизации КНФ. Записывают как бы СДНФ для нулевых значений функции и получают инверсную функцию:

ù F = ù x₁ ù x₂ ù x₃ Ú ù x₁ x₂ ù x₃ Ú ù x₁ x₂ x₃.

После склеек и поглощений получаем:

ù F = ù x₁ ù x₃ Ú ù x₁ x₂ .

Откуда: F = ù (ù x₁ ù x₃ Ú ù x₁ x₂) = ù (ù x₁ ù x₃) ù (ù x₁ x₂) = (x₁ Ú x₃) (x₁ Ú ù x₂ ).

Дата добавления: 2014-01-06