Метод минимизации ФАЛ по Квайну
Определение: Тупиковой ДНФ называется дизъюнкция простых импликант, ни одну из которых из выражения функции исключить нельзя.
Этот метод минимизации ФАЛ заключается в следующем:
- Находят Сок. ДНФ.
- Находят все возможные тупиковые ДНФ.
- Из найденных ТДНФ выбирают минимальную.
Иногда в Сок. ДНФ содержатся лишние импликанты. Как уже видели в сокращенной ДНФ:
f(Х1, Х2, Х3)= Х1Х3
импликанта Х2Х3 может быть исключена. Ни одной операции склеивания и поглощения к этой форме применить нельзя, т.к. это Сок. ДНФ, т.е. дизъюнкция простых импликант. Можно применить операцию развертывания по Х1:
f= Х1Х3
Т.к. Х1Х3 покрывает Х1Х2Х3
и Х1Х2 покрывает Х1Х2Х3, то f= Х1Х3
ТЕОРЕМА:
Всякая минимальная ДНФ является тупиковой. Обратное утверждение не справедливо. Доказательство очевидно.
Из этой теоремы вытекает важное следствие: Для того чтобы найти минимальную ДНФ, нужно найти все тупиковые формы и среди них взять минимальную.
Существует несколько различных способов отыскания тупиковых форм.
