Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм минимизации частично определенных функций




Алгоритм минимизации частично определенных функций

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

Пусть функция f (x 1,…, xn) частично (не всюду) определена. Если f не определена на p наборах из 0 и 1, то существует 2 p возможностей для доопределения функции f. Полностью определенная функция g (x 1,…, xn) есть доопределение функции f, если g совпадает с f на тех наборах из 0 и 1, на которых f определена.

Задача минимизации частично определенной функции f сводится к отысканию такого доопределения g функции f, которое имеет простейшую (по числу букв) минимальную форму.

Обозначим через f 0(x 1,…, xn) и f 1(x 1,…, xn) доопределения нулями и единицами соответсвенно частично определенной функции f (x 1,…, xn).

Теорема. Минимальная ДНФ частично определенной функции f (x 1,…, xn) есть дизъюнкция самых коротких импликант в сокращенной ДНФ доопределения f 1(x 1,…, xn), которые в совкупности накрывают все конституенты единицы доопределения f 0(x 1,…, xn).

Доказательство. Рассмотрим СДНФ некоторого доопределения g (x 1,…, xn) функции f (x 1,…, xn). Конституенты единицы, входящие в эту форму, войдут и в СДНФ доопределения f 1. Поэтому любой простой импликант функции g будет совпадать с некоторым импликантом функции f 1 или накрываться им. Самые короткие импликанты, накрывающие единицы функции f, есть импликанты функции f 1. Доопределение f 0 имеет минимальное количество конституент единицы в своей СДНФ, следовательно, и количество простых импликант функции f 1, потребных для накрытия этих конституент, будет наименьшим. ДНФ, составленная из самых коротких простых импликант в сокращенной ДНФ функции f 1 , накрывающих все конституенты единицы функции f 0, будет самой короткой ДНФ, доопределяющей функцию f.

Так как единицы функции f 1 составлены из единиц функции f и единиц на наборах, на которых f не определена, то построенная ДНФ, накрывая все единицы функции f 0 (а, следовательно, и все единицы функции f), совпадает с минимальной ДНФ некоторого доопределения g функции f.

 

в классе ДНФ

1. Строим СДНФ функции f 0 .

2. Строим сокращенную ДНФ функции f 1 .

3. С помощью матрицы покрытий коституент единицы функции f 0 простыми импликантами функции f 1 и решеточного выражения строим все тупиковые ДНФ (для некоторых доопределений функции f).

4. Среди полученных ТДНФ выбираем простейшие, они являются минимальными ДНФ (для некоторых доопределений функции f).

 

в классе КНФ

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

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

Пример 1. В классе нормальных форм минимизировать частично определенную функцию f (x, y, z, t) = (1---010010-01--1)

Решение. Минимизируем функцию f в классе ДНФ.

1. Строим сокращенную ДНФ для доопределения единицами f 1 функции f по таблице 3.9.

Таблица 3.9

x y z t f f 0 f 1 ` f h 0 h 1
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 - 0 1 - 0 1 - 0 1 - 0 1 - 0 1 - 0 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 - 0 1 - 0 1 0 0 0 1 1 1 1 1 1 1 1 1 - 0 1 - 0 1 - 0 1 - 0 1 1 1 1 0 0 0

2. Строим матрицу покрытий коституент единицы в СДНФ для доопределения нулями f 0 функции f с помощью построенной сокращенной ДНФ для f 1 (таблица 3.10).

Таблица 3.10

N ПИ
        + +
  +        
      + +  
  +   +    
    +      
    +      

3. По таблице строим решеточный многочлен

E = (2Ú4)(5Ú6)(3Ú4)(1Ú3)1 = 145 Ú 125 Ú 146 Ú 1236.

4. Строим все тупиковые ДНФ:

5. Из построенных тупиковых ДНФ выбираем минимальные:

Функции g 1 и g 3 есть минимальные доопределения функции f в классе ДНФ.

Минимизируем теперь функцию f в классе КНФ. Для этого проведем минимизацию функции ` f в классе ДНФ Пусть h 0 и h 1 есть доопределение нулями и единицами соответственно функции ` f.

Сокращенная ДНФ для

Матрица покрытия конституент единицы в СДНФ для h 0 с помощью простых импликант в сокращенной ДНФ для h 1 приведена в таблице 3.11.

Таблица 3.11

N ПИ
        + +
    + +    
    +      
        +  
  + +      
          +

 

3. Решеточное выражение E =5 (2 Ú 3 Ú5) 2 (1Ú 4)(1Ú 6) = 25(1Ú 46) = 125 Ú 2446.

4. Строим две тупиковые ДНФ:

и

Минимальная.

5. Функция есть минимальное доопределение функции f в классе КНФ.

Найденные МДНФ g 1, g 3 и МКНФ являются минимальными доопределениями функции f в классе нормальных форм.

Техническая реализация минимальных форм для функции часто проще, а потому дешевле реализации ее СДНФ (СКНФ). Следовательно, этап минимизации при конструировании логических схем является одним из важнейших.

 




Поделиться с друзьями:


Дата добавления: 2014-12-27; Просмотров: 771; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.018 сек.