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

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

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

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

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

f(Х₁, Х₂, Х₃)= Х₁Х₃ Х₂Х₃ Х₁Х₂

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

f= Х₁Х₃ Х₂Х₃ (Х₁ Х₁) Х₁Х₂ = Х₁Х₃ Х₁Х₂ Х₃ Х₁Х₂ Х₃ Х₁Х₂

Т.к. Х₁Х₃ покрывает Х₁Х₂Х₃

и Х₁Х₂ покрывает Х₁Х₂Х₃, то f= Х₁Х₃ Х₁Х₂

ТЕОРЕМА:

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

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

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

4. Лекция: Метод проб
Страницы: 1 | 2 | 3 | 4 | вопросы |»	| учебники | для печати и PDA | ZIP
Если Вы заметили ошибку - сообщите нам, или выделите ее и нажмите Ctrl+Enter
В данной лекции представлены способы минимизации на основе метода проб, метода Квайна-Мак-Класки, на основе минимизирующих диаграмм для функции 2-х, 3-х, 4-х переменных (диаграммы Вейча).
Рассмотрим произвольную ДНФ. Если в ней выбросить любое произведение, то оставшееся выражение будет принимать нулевое значение на тех наборах, что и исходная форма, т.к. x1 1 x2 2... xi i = 0 только тогда все члены x1 1 x2 2... xi i = 0. Однако, если отброшенное произведение (импликанта) обращалось в единицу, и функция принимала единичное значение на этом единственном наборе, то оставшееся выражение может уже не принять единичное значение на данном наборе. Это означает, что импликанта не была лишней. Если же с помощью проверки установить, что оставшееся выражение обращается в единицу, импликанта – лишняя, и ее можно отбросить. Пример 1: Пусть дана f(x1x2x3) = x1x2 x1x3 x2x3 Отбросим член x1x2: fl = x1x3 x2x3 x1x2 = 1 => x1 = 0, x2 = 0 fl = 0*x3 1*x3 = x3 Т.к. x3 1 то x1x2 исключить нельзя Отбросим член x1x3: fll = x1x2 x2x3 x1x3 = 1 => x1 = 1, x3 = 1 fll = 0*x2 x2 * 1 1 => x1x3 исключить нельзя. Отбросим член x2x3: flll = x1x2 x1x3; x2x3 = 1 => x2 = 0, x3 = 1 flll = x1 x1 *1 = 1 => x2x3- член лишний. Если проверка показывает, что несколько импликант одновременно являются лишними, то исключить их одновременно из выражения ДНФ нельзя. Это можно выполнять лишь поочередно. Пример 2:

f(x₁x₂x₃x₄) = x₁x₃x₄ x₂x₃x₄ x₁x₂x₄ x₁x₂x₃ x₂x₃x₄

1. испытаем 1 член: x₁x₃x₄ = 1; x₁ = 0; x₃ = 1; x₄ = 1

f(x₁x₂x₃x₄) = x₂ 0 0 0=x₂ Т.е. член x₁x₃x₄ исключить нельзя.

1. испытаем 2 член: x₂x₃x₄ = 1; x₂ = 0; x₃ = x₄ = 1

f(x₁x₂x₃x₄) = x₁ x₁ 0 0 = 1 Т.е. член x₂x₃x₄ лишний.

1. испытаем 3 член: x₁x₂x₄; x₁ = 1; x₂ = 0 x₄ = 1

f(x₁x₂x₃x₄) = 0 x₃ x₃ 0 = 1 Т.е. член x₁x₂x₄ лишний.

1. испытаем 4 член: x₁x₂x₃; x₁ = 1; x₂ = x₃ = 0

f(x₁x₂x₃x₄) = 0 0 x₄ x₄ = 1, Т.е. член x₁x₂x₃ лишний.

1. испытаем 5 член: x₂x₃x₄; x₂ = x₃ = x₄ = 0

f(x₁x₂x₃x₄) = 0 0 0 x₁ = x₁, Т.е. член x₂x₃x₄ лишний.

Исключим одновременно члены 2, 3, 4

f = x₁x₃x₄ x₂x₃x₄

Проверим значения f одновременно на тех наборах, на которых обращаются в единицу все отброшенные члены.

x₂x₃x₄; x₁x₂x₄; x₁x₂x₃; => x₁x₃x₄ x₂x₃x₄ x₁x₂x₃

• x₂ = 0; x₃ = x₄ = 1 => f₁ = x₁ 0
• x₁ = 1; x₂ = 0; x₄ = 1 => f₂ = 0 0
• x₁ = 1; x₂ = x₃ = 0 => f₃ = 0 x₄

т.е. видно, что во всей совокупности этого сделать нельзя

Исключим член x₂x₃x₄, получим:

f(x₁x₂x₃x₄) = x₁x₃x₄ x₁x₂x₄ x₁x₂x₃ x₂x₃x₄

Проверим, не являются ли в этом выражении лишними те члены, которые оказались лишними в исходном выражении, т.е.: x₁x₂x₄ и x₁x₂x₃.

1. проверим x₁x₂x₄:

x₁ = 1; x₂ = 0; x₄ = 1

f(x₁x₂x₃x₄) = 0 x₃ 0 = x₃ т.е. член x₁x₂x₄ не лишний

1. проверим x₁x₂x₃:

x₁ = 1; x₂ = x₃ = 0

f (x₁x₂x₃x₄) = 0 x₄ x₄ = 1, т.е. член x₁x₂x₃ лишний,

Поэтому f(x₁x₂x₃x₄) = x₁x₃x₄ x₁x₂x₄ x₂x₃x₄ - тупиковая форма.

Проверяя затем, начав с исключения третьего члена, получим другую тупиковую форму. Затем выберем из них минимальную.

Недостаток метода заключается в том, что при большом числе членов он становится громоздким, поскольку связан с перебором различных вариантов. Машинная реализация данного метода вследствие этого сложна. При автоматизации поиска минимальных форм метод практически не используется.