Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

5: Минимизация неполностью определенных функций

Лекция



Привет, Вы узнаете о том , что такое минимизация неполностью определенных функций, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое минимизация неполностью определенных функций , настоятельно рекомендую прочитать все из категории Цифровые устройства. Микропроцессоры и микроконтроллеры. принципы работы ЭВМ.

Аннотация: В лекции представлена минимизация неполностью определенных функций , дан синтез функций в базисах штрих Шеффера и стрелка Пирса, даны подходы к минимизации конъюнктивных форм.

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

 

Определение. Неполностью определенной функцией является такая переключательная функция, значения которой на некоторых наборах аргументов могут быть произвольными (т.е. равными " 0 " или " 1 ").

 

Определение. Пусть функция f(x1,x2,...xn) не определена на " р " наборах аргументов. Тогда полностью определенную функцию  5: Минимизация неполностью определенных функций будем считать эквивалентной к f(x1,x2,...xn), если ее значения на тех наборах, на которых f(x1,x2,...xn)определена, совпадают.

 

Очевидно, существует 2р различных функций, эквивалентных f(x1,x2,...xn).

 

Задача минимизации f(x1,x2,...xn) состоит в выборе такой эквивалентной  5: Минимизация неполностью определенных функций, которая имеет простейшую форму.

 

Введем две вспомогательные эквивалентные функции  5: Минимизация неполностью определенных функций 5: Минимизация неполностью определенных функций, которые принимают на запрещенных наборах аргументов значения 0 и 1 соответственно.

 

ТЕОРЕМА. СДНФ неполностью определенной f(x1,x2,...xn) совпадает с дизъюнкцией самых коротких импликант  5: Минимизация неполностью определенных функций, которые совместно накрывают все конституенты единицы  5: Минимизация неполностью определенных функций, и ни одна из которых не является лишней.

 

Пример:

 

Пусть задана f(x1,x2,...xn) в виде следующей таблицы:

 
f(x1,x2,...xn) 1 - - - 0 1 0 0 1 0 - 0 1 - - 1
Числовые эквиваленты наборов 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
 

Тогда

 

 5: Минимизация неполностью определенных функций,

 

а

 

 5: Минимизация неполностью определенных функций

 

Найдем простые импликанты  5: Минимизация неполностью определенных функций

 
Конституенты единицы  5: Минимизация неполностью определенных функций 1Отметки о склейкеИмпликантыОтметки о склейкеИмпликанты
0000
 
*
000-
00-0
-000
 
*
00- -
00- -
-0-0
 
0001
0010
1000
 
* *
* *
*
00-1
0-01
001-
-010
1-00
 
*
0011
0101
1010
1100
 
* -
* *
1- -0
 
* *
* *
1101
1110
 
*
 
-101
1-10
110-
11-0
 
-
*
*
 
-
11- -
 
-
1111
 
*
111-
 
*
 

Простые импликанты  5: Минимизация неполностью определенных функций

 

 5: Минимизация неполностью определенных функций

 

Построим импликантную матрицу.

 
Конституенты единицы  5: Минимизация неполностью определенных функций00000101100011001111
Простые импликанты  5: Минимизация неполностью определенных функций
0-01   +      
-101   +      
110-       +  
11-0       +  
00-- +        
-0-0 +   +    
1--0     + +  
11--       + +
 

Выполним оптимальное покрытие конституент единицы  5: Минимизация неполностью определенных функций простыми импликантами  5: Минимизация неполностью определенных функций и получаем минимальную форму функцииf(x1x2 x3 x4)

 

 5: Минимизация неполностью определенных функций

 

 5: Минимизация неполностью определенных функций

 

Минимизация с помощью диаграмм Вейча неполностью определенных функций в наглядной и удобной форме позволяет отыскать минимальные формы.

 

Пример:

 

Рассмотрим функцию f(x1x2 x3 x4) и найдем ее минимальную форму. Об этом говорит сайт https://intellect.icu . Заполнить диаграмму Вейча по следующим правилам: в клетки диаграммы поставим единицы, которые соответствуют конституентам единицы, нули – для отсутствующих конституент и символ неопределенности – " * " (звездочка) – в остальные.

 
 5: Минимизация неполностью определенных функций
 

Видно, что в клетки для конституент: x1x2x3x4, x1x2x3x4, x1x2x3x4 целесообразно "поставить" единицы вместо символов неопределенности, так как в этом случае образуется правильная конфигурация 2-го ранга, которая покрывается произведением x2x3.

 

Аналогично и в клетку x1x2x3x4 нужно "поставить" единицу.

 

Итак,  5: Минимизация неполностью определенных функций.

 

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

 

В этом случае необходимо отыскивать правильные конфигурации, образованные нулями

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

Операция (стрелка) Пирса

f
8
(x
1
,x
2
)
 
x1 0 0 1 1
x2 0 1 0 1
f8 1 0 0 0
 

Эту функцию можем представить, записав по "единицам":

 

 5: Минимизация неполностью определенных функций

 

или

 

 5: Минимизация неполностью определенных функций

 

На основе принципа суперпозиции:

 

 5: Минимизация неполностью определенных функций

 

Применяя правило де Моргана:

 

 5: Минимизация неполностью определенных функций

 

или:

 

 5: Минимизация неполностью определенных функций

 

т.е.

 

 5: Минимизация неполностью определенных функций

 

Рассмотрим некоторые соотношения для операции Пирса:

 

 5: Минимизация неполностью определенных функций

 

 5: Минимизация неполностью определенных функций

 

 5: Минимизация неполностью определенных функций,

 

т.е. операция Пирса не обладает свойством ассоциативности

 

 5: Минимизация неполностью определенных функций

 

 5: Минимизация неполностью определенных функций

 

При этом порядок выполнения операций в формулах, где есть операции Пирса такой:

 
  1. раскрываются скобки
  2. выполняются операции инверсии
  3. выполняются операции Пирса
 

Синтез логических функций в базисе Пирса удобно производить, имея запись функции в КНФ.

 

Допустим, что ФАЛ задана в конъюктивной форме

 

f = Q1Q2Q3 . . . Qn

 

Подставим член Qi в виде:

 

 5: Минимизация неполностью определенных функций

 

Возьмем двойное отрицание от обеих частей этого равенства, применив правило де Моргана

 

 5: Минимизация неполностью определенных функций

 

Применяя соотношение, полученное на основе принципа суперпозиции:

 

 5: Минимизация неполностью определенных функций

 

Или, применяя это преобразование к исходной форме, получим:

 

 5: Минимизация неполностью определенных функций

 

Итак: чтобы от КНФ перейти к базису Пирса и инверсии необходимо:

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

Пример:

 

 5: Минимизация неполностью определенных функций

 

Замечание. Так как в этих произведениях число букв не увеличивается, и если исходная форма функции была минимальной, то вновь полученная также будет минимальной (в действительности дело обстоит сложнее, поскольку мы рассматриваем не базис "  5: Минимизация неполностью определенных функций ", а другой, то есть "  5: Минимизация неполностью определенных функций " и " - " - операцию Пирса и инверсию).

 

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

Операция штрих Шеффера

x1 0 0 1 1
x2 0 1 0 1
f14 1 1 1 0
 

Заметим, что эта функция дуальна по отношению к f8, поэтому все свойства являются по существу дуально вытекающими из рассмотренных.

 

 5: Минимизация неполностью определенных функций (запись функций по нулям)

 

 5: Минимизация неполностью определенных функций

 

на основе принципа суперпозиции:

 

x1 | x2 | . . . | xn = x1x2...xn

 

Рассмотрим некоторые эквивалентности:

 

 5: Минимизация неполностью определенных функций

 

x1 | x2 | x3 = (x1 x2)| x3 = x1| (x2 x3)

 

x1 | x2 | x3| x4 = (x1 x2)| (x3 x4)

 

Сформулируем правила перехода от ДНФ функции к выражению с использованием операции " Штрих Шеффера ".

 
  1. заменить все операции дизъюнкции на операции Шеффера
  2. заменить все операции конъюнкции на операции Шеффера
  3. группы букв, которые соответствуют дизъюнктивным членам, заключить в скобки.
 

Пример:

 

 5: Минимизация неполностью определенных функций

 

То же самое можно утверждать относительно минимальной формы.

 

В заключение необходимо отметить, что в настоящее время вопросы синтеза функций в одноэлементном базисе приобретают большое значение, так как соответствующие элементы используют операцию Пирса и Шеффера. Однако в полной мере теоретически методы синтеза разработаны не столь детально, как это сделано в базисе "и", "или", "инверсия".

 

Минимальные конъюнктивные нормальные формы

Как было отмечено, для получения минимальной формы функции нужно построить как МДНФ так и МКНФ.

 

Рассмотрим построение МКНФ.

 

В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:

 
  1. Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:

     5: Минимизация неполностью определенных функций,

     

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

     
  2. При задании функции в произвольной конъюктивной форме, применяя

    формулы развертывания:

     

     5: Минимизация неполностью определенных функций

     

    . . . . . . . . . . . .,

     

    получить СКНФ.

     
  3. Выполнить все операции неполного склеивания:

     5: Минимизация неполностью определенных функций

     

    и поглощения:  5: Минимизация неполностью определенных функций, получить сокращенную КНФ.

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

      По возможности отбросить одновременно несколько членов, поступить как и при минимизации функции ДНФ.

       
    • При использовании диаграмм Вейча ищутся правильные конфигурации, образованные нулями.
    • При применении метода импликантных матриц поступают как и в случае ДНФ, только колонкам присваивают имена конституент" 0 " функции, записанной в СКНФ, а горизонтальным рядам – простых импликант. Далее ищут оптимальное покрытие.

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

Из статьи мы узнали кратко, но содержательно про минимизация неполностью определенных функций

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.

создано: 2016-04-15
обновлено: 2021-03-13
132460



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Цифровые устройства. Микропроцессоры и микроконтроллеры. принципы работы ЭВМ

Термины: Цифровые устройства. Микропроцессоры и микроконтроллеры. принципы работы ЭВМ