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


Полезное:

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


Категории:

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






Минимизация ФАЛ и ограничения при ее рассмотрении





Покажем на примере, что СДНФ не является экономной формой записи:

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

на основании полного склеивания по Х2 мы видим, что запись стала короче, т.к. содержит меньшее число связок и букв. Физически это означает, что устройство, которое реализует эквивалентную, но более простую функцию, будет иметь в своем составе меньшее количество оборудования, а следовательно, будет работать надежнее.

Итак, задача синтеза устройства должна быть дополнена задачей уменьшения оборудования в нем. С математической точки зрения это задача построения минимальной ФАЛ.

Под минимальной ФАЛ понимается такая форма, в которой содержится меньшее количество букв и членов, чем в ее исходной форме.

Речь идет именно о буквах, а не о переменных, так в функции:

f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х2 имеется 6 букв и только 2 переменных.

Видно, что если какое-либо элементарное произведение входит в функцию, то при добавлении к нему новых сомножителей, полученное произведение так же будет входить в функцию.

Пример: если Х1Х2 входит в функцию от любого числа аргументов (>2), то в нее войдет, например, произведение Х1Х2Х3.

Это можно показать так:

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

Дадим ряд определений:

  1. Произведение одной или нескольких неповторяющихся переменных, взятых с отрицанием или без него, называют элементарным.

Например, Х1 Х2 Х3 – элементарное произведение, т.к. в него входят различные буквы Х1 Х2 Х3.

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

Обычно конституенты единицы выражают через произведение всех переменных, от которых зависит функция. СДНФ – дизъюнкция конституент единицы.

  1. Ранг произведения – число букв, входящих в него.
  2. Собственной частью называется произведение, полученное путем отбрасывания одной или нескольких переменных.

Например, Х1 Х2 Х3 Х4, где Х1, Х1 Х2, Х1 Х2 Х3 – некоторые собственные части.

  1. Если функция равна нулю на наборах аргументов, на которых обращается в нуль функция F, то говорят, что является импликантой функции F (т.е. нулей у импликанты не меньше, чем у функции).
  2. Простой импликантой называется произведение, которое само входит в выражение функции, но никакая его собственная часть в выражение функции не входит.

Например, Х1 Х1 Х2 Х3 Х1Х3=f: здесь Х1- простая импликанта, а Х1 Х2 Х3 и Х1 Х3 - не простые.

Понятие покрытия

Определение. Если на каком-либо наборе f принимает значение а1, а – значение а2, то говорят, что f своим значением а1 покрывает значение а2 функции .

При минимизации ФАЛ стремятся получить форму, в которой будет меньше букв, чем в исходной. По отношению к ДНФ эта форма называется сокращенной (Сок. ДНФ).

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

Так, каждое элементарное произведение, входящее в СДНФ, покрывает только одну единицу функции.

Например:

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

1 1 1

Эти единицы функции могут быть накрыты более короткими произведениями: Х1 накрывает две единицы: Х1Х2 и Х1Х2 и Х2, которое накрывает также две единицы: Х1Х2 и Х1Х2, т.е.

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

ТЕОРЕМА (без док-ва):

Любая ФАЛ может быть представлена единственным образом в Сок. ДНФ, т.е. записана в виде дизъюнкции простых импликант.

Сокращенная форма не означает, что это форма является минимальной. Однако для практической реализации эта форма более удобна, чем совершенная.

Рассмотрим метод получения Сок. ДНФ, предложенный Квайном. Этот метод, и, в частности, теорема Квайна в явном и неявном виде входит практически во все методы минимизации.

Исходная форма функции – совершенная ДНФ.

ТЕОРЕМА Квайна:

Если в СДНФ в начале произвести все операции неполного склеивания, а затем все операции поглощения, то в результате получится сокращенная ДНФ.

Покажем, что, применяя операцию неполного склеивания, получим все простые импликанты функции. Введем операцию развертывания, которая обратна операции склеивания: это есть умножение каждого произведения на выражение вида (Х X)=1.

Пусть Х1Х2 – простая импликанта некоторой f(Х1, Х2, Х3) трех переменных. Тогда:

Х1Х23 Х3)=Х1 Х2 Х3 Х1 Х2 Х3

получатся после многократного применения этой операции дизъюнкции конституент единицы исходной функции, т.е. ее СДНФ.

В эту форму, вообще говоря, могут входить несколько одинаковых членов, т.к. разные простые импликанты могут дать одинаковые конституенты единицы. Поэтому, отбросив в ДНФ лишние члены, получим ее СДНФ.

По отношению к СДНФ применяется операция неполного склеивания, т.к. одно и то же произведение, вообще говоря, может склеиваться с несколькими другими, давая различные импликанты, то чтобы не лишиться возможности провести все операции склеивания, приходится каждое произведение, которое участвовало в операции склеивания, оставить для других операций.

Пример:

f(Х1, Х2)= Х1Х2 Х1Х2 Х1Х2 = Х1Х2 Х1 или Х1Х2 Х2

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

Если теперь провести все операции поглощения, то в полученной форме функции f останутся только простые импликанты. Покажем это. Пусть в результате операций склеивания получится член x, не являющийся простой импликантой.

Тогда x=y*z, где z – простая импликанта, которая так же должна входить в f, т.к. в нее входит x. Но z будет поглощать х, поэтому х не может входить в f. Это и доказывает теорему Квайна.

Замечание: Заметим, что теорема Квайна применяется по отношению к функции СДНФ.

Порядок получения Сок. ДНФ может быть следующим:

  1. Провести все операции неполного склеивания конституент единицы исходной СДНФ. Получатся произведения (n-1) ранга; оставшиеся несклеенные конституенты единицы не могут участвовать в дальнейших склеиваниях.
  2. Провести покрытие всех полученных произведений и конституент единицы. Часть некоторых конституент единицы будет устранена.
  3. Продолжить, пока возможны операции 1) и 2).

Пример 1:

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

Если применим операцию полного склеивания, то получим:

или

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

или

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

т.е. у нас нет возможности далее провести операцию.

Применим теперь операцию неполного склеивания:

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

Простые импликанты: Х1, Х2

Конституенты единицы: Х1Х2, Х1Х2, Х1Х2

Теперь можем провести операции поглощения:

Х1 поглощает: Х1, Х1Х2, Х1Х2

Х2 поглощает: Х2, Х1Х2, Х1 Х2

Т.е. сокращенная ДНФ

f(Х1, Х2)= Х1 Х2 в данном случае она – минимальная форма.

Пример 2:

Пусть задана:

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

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

Получим СДНФ:

f= Х1Х32 Х2) Х1Х23 Х3) Х1Х2 Х3 = Х1Х2 Х3 Х1Х2 Х3 Х1Х2 Х3 Х1Х2 Х3 Х1Х2 Х3 = Х1Х2 Х3 Х1Х2 Х3 Х1Х2 Х3 Х1Х2 Х3

Теперь, имея СДНФ, можно получить сокращенную ДНФ:

f(X1,X2,X3)=X1X2X3 X2X3 X1X3

Пример 3:

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

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

Обычно произведение, содержащее 'n' букв, называется минтермом 'n'-ранга.

Date: 2016-05-14; view: 425; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



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