Нахождение минимальных КНФ ФАЛ

Для нахождения минимальных КНФ можно рекомендовать два метода:

1.Метод Квайна, в основу которого берется операция склеивания конституент нуля функции. Конституентам нуля на карте Карно соответствуют пустые клетки (или клетки, содержащие нули). Правила склеивания конституент нуля аналогичны правилам склеивания конституент единицы.

2. Минимизация функции, инверсной заданной, и преобразование полученной минимальной ДНФ функции по законам инверсии и де Моргана в минимальную КНФ.

Пример 8. Найти минимальную КНФ ФАЛ, приведенной в примере 7.

Решение.

1. По первому методу выполняем склеивание конституент нуля функции, которая нанесена на карту Карно (рис. 4,б). Склеивание конституент нуля функции, которые на рис. 4,б отмечены точками, образуют три простых дизъюнкции третьего ранга. На карте ясно видно, что эти простые дизъюнкции являются так же существенными, т.е. должны обязательно войти в минимальную КНФ функции. Другими простыми дизъюнкциями третьего ранга являются . Так как полученные простые дизъюнкции третьего ранга не склеиваются , то простых дизъюнкций второго ранга нет.

2. Составляем таблицу (табл.6), столбцы которой отмечаем конституентами нуля и ∨ , а строки - простыми дизъюнкциями ∨ и расставляем метки.

Таблица 6

		˅
	*
˅	*	*
		*

3. Находим тупиковые и минимальные КНФ.

Составляем конъюнкцию простых дизъюнкций отдельных столбцов (по способу Петрика): (A ∨ B)(B ∨ C).

Применяя распределительный закон (раскрытие скобок в данном случае происходит одновременно), получим (A ∨ B)(B ∨ C) = B ∨ AC. Учитывая существенные дизъюнкции

D= , E = получим:

(B ∨ AC)DEF = BDEF ∨ ACDEF. (12)

Из выражения (12) следует, что функция имеет две тупиковых формы:

f_туп1(х₄, х₃, х₂, х₁) = BDEF =

˅ ;

f_туп2(х₄, х₃, х₂, х₁) = ACDEF = =( .

Минимальной является первая тупиковая форма:

f_мин(х₄, х₃, х₂, х₁) = ˅ .

Примечание: минимальную КНФ функции можно сразу найти, анализируя карту Карно на рис. 4,б. Оставшиеся неотмеченными точками две конституенты нуля склеиваются по переменной ˅ Конъюнкция последней и существенных дизъюнкций и есть минимальная КНФ.

Минимальную КНФ можно найти вторым способом, минимизируя функцию (х₄, х₃, х₂, х₁), карта Карно которой показана на рис. 4,в:

_мин(х₄, х₃, х₂, х₁) = ∨ (13)

Инвертируя левую и правую части выражения (13) и применяя правило де Моргана , получим минимальную КНФ:

f_мин (х₄, х₃, х₂, х₁) = =

∨ . (14)

Преобразование минимальных ДНФ и КНФ в базисы функций И-НЕ и ИЛИ-НЕ

Дважды инвертируя правые части выражений (10) и (14) и применяя правило де Моргана, получим минимальные формы функции f_мин (х₄, х₃, х₂, х₁) в базисах функций И-НЕ и ИЛИ-НЕ:

f_мин (х₄, х₃, х₂, х₁) = ∨ ∨ ∨ =

= ; (15)

f_мин (х₄, х₃, х₂, х₁) = ˅ =

= . (16)