Логические и арифметические основы и принципы работы ЭВМ

       

Метод минимизации ФАЛ по Квайну


Определение: Тупиковой ДНФ называется дизъюнкция простых импликант, ни одну из которых из выражения функции исключить нельзя.

Этот метод минимизации ФАЛ заключается в следующем:

  1. Находят Сок. ДНФ.
  2. Находят все возможные тупиковые ДНФ.
  3. Из найденных ТДНФ выбирают минимальную.

Иногда в Сок. ДНФ содержатся лишние импликанты. Как уже видели в сокращенной ДНФ:

f(Х1, Х2, Х3)= Х1Х3

Х2Х3
Х1Х2

импликанта Х2Х3 может быть исключена. Ни одной операции склеивания и поглощения к этой форме применить нельзя, т.к. это Сок. ДНФ, т.е. дизъюнкция простых импликант. Можно применить операцию развертывания по Х1:

f= Х1Х3

Х2Х3 (Х1
Х1)
Х1Х2 = Х1Х3
Х1Х2 Х3
Х1Х2 Х3
Х1Х2

Т.к. Х1Х3 покрывает Х1Х2Х3

и Х1Х2 покрывает Х1Х2Х3, то f= Х1Х3

Х1Х2

ТЕОРЕМА:

Всякая минимальная ДНФ является тупиковой. Обратное утверждение не справедливо. Доказательство очевидно.

Из этой теоремы вытекает важное следствие: Для того чтобы найти минимальную ДНФ, нужно найти все тупиковые формы и среди них взять минимальную.

Существует несколько различных способов отыскания тупиковых форм.



Содержание раздела