Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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

⇐ ПредыдущаяСтр 11 из 32Следующая ⇒

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

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

  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

ТЕОРЕМА:

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

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

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

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
  1. Отбросим член x1x2:
fl = x1x3 x2x3 x1x2 = 1 => x1 = 0, x2 = 0 fl = 0*x3 1*x3 = x3 Т.к. x3 1 то x1x2 исключить нельзя
  1. Отбросим член x1x3:
fll = x1x2 x2x3 x1x3 = 1 => x1 = 1, x3 = 1 fll = 0*x2 x2 * 1 1 => x1x3 исключить нельзя.
  1. Отбросим член x2x3:
flll = x1x2 x1x3; x2x3 = 1 => x2 = 0, x3 = 1 flll = x1 x1 *1 = 1 => x2x3- член лишний. Если проверка показывает, что несколько импликант одновременно являются лишними, то исключить их одновременно из выражения ДНФ нельзя. Это можно выполнять лишь поочередно. Пример 2:

 

f(x1x2x3x4) = x1x3x4 x2x3x4 x1x2x4 x1x2x3 x2x3x4

  1. испытаем 1 член: x1x3x4 = 1; x1 = 0; x3 = 1; x4 = 1

f(x1x2x3x4) = x2 0 0 0=x2 Т.е. член x1x3x4 исключить нельзя.

  1. испытаем 2 член: x2x3x4 = 1; x2 = 0; x3 = x4 = 1

f(x1x2x3x4) = x1 x1 0 0 = 1 Т.е. член x2x3x4 лишний.

  1. испытаем 3 член: x1x2x4; x1 = 1; x2 = 0 x4 = 1

f(x1x2x3x4) = 0 x3 x3 0 = 1 Т.е. член x1x2x4 лишний.

  1. испытаем 4 член: x1x2x3; x1 = 1; x2 = x3 = 0

f(x1x2x3x4) = 0 0 x4 x4 = 1, Т.е. член x1x2x3 лишний.

  1. испытаем 5 член: x2x3x4; x2 = x3 = x4 = 0

f(x1x2x3x4) = 0 0 0 x1 = x1, Т.е. член x2x3x4 лишний.

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

f = x1x3x4 x2x3x4

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

x2x3x4; x1x2x4; x1x2x3; => x1x3x4 x2x3x4 x1x2x3

  • x2 = 0; x3 = x4 = 1 => f1 = x1 0
  • x1 = 1; x2 = 0; x4 = 1 => f2 = 0 0
  • x1 = 1; x2 = x3 = 0 => f3 = 0 x4

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

Исключим член x2x3x4, получим:

f(x1x2x3x4) = x1x3x4 x1x2x4 x1x2x3 x2x3x4

Проверим, не являются ли в этом выражении лишними те члены, которые оказались лишними в исходном выражении, т.е.: x1x2x4 и x1x2x3.

  1. проверим x1x2x4:

x1 = 1; x2 = 0; x4 = 1

f(x1x2x3x4) = 0 x3 0 = x3 т.е. член x1x2x4 не лишний

  1. проверим x1x2x3:

x1 = 1; x2 = x3 = 0

f (x1x2x3x4) = 0 x4 x4 = 1, т.е. член x1x2x3 лишний,

Поэтому f(x1x2x3x4) = x1x3x4 x1x2x4 x2x3x4 - тупиковая форма.

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

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



⇐ Предыдущая6789101112131415Следующая ⇒





Date: 2016-05-14; view: 386; Нарушение авторских прав


mydocx.ru - 2015-2024 year. (0.031 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию