Студопедия

КАТЕГОРИИ:


Архитектура-(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) есть функция алгебры логики.

1. Построим СДНФ функции f, и пусть P 1, P 2, …, Pn есть ее коституенты единицы).

2. Построим сокращенную ДНФ функции, f и пусть K 1, K 2, …, Km – ее простые импликанты.

3. Построим матрицу покрытий простых импликант функции f ее конституентами единицы (табл. 3.4), полагая, что

+, если каждый множитель в Ki является множителем в Pj; (Pj есть aij = часть для Ki);

Æ в противном случае.

 

Таблица 3.4

N P 1 P 2PjPn
K 1 K 2 Ki Km a 11 a 12 … a 1 j …a 1 n a 21 a 22 … a 2 j … a 2 n ai 1 ai 2 … aij … ain am 1 am 2 … amj … amn

 

4. Для каждого столбца j (1 £ j £ n) найдем множество Ej всех тех номеров I строк, для которых aij = 1. Пусть Составим выражение Назовем его решеточным выражением. Это выражение можно рассматривать как формулу, построенную в свободной дистрибутивной решетке с образующими 1, 2, …, m и с операциями & и Ú.

5. В выражении A раскроем скобки, приведя выражение A к равносильному выражению где перечислены все конъюнкции элементы которой взяты из скобок 1,2,…, n соответственно в выражении A.

6. В выражении B проведем все операции удаления дублирующих членов и все операции поглощения. В результате получим дизъюнкцию элементарных конъюнкций C.

Утверждение. Каждая элементарная конъюнкция i 1& i 2&…& ir в С дает ТДНФ для f. Все ТДНФ для функции f исчерпываются элементарными конъюнкциями в выражении С.

Пример 5. Сокращенная ДНФ для функции f = (1111010010101111) имеет вид

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

1. Строим матрицу покрытий (таблица 3.5).

Таблица 3.5

    Конституенты единицы функции f
  N ПИ x ` x ` x ` x ` x x x x x x x y ` y ` y ` y y ` y ` y y y y y z ` z z z ` z ` z z ` z ` z z z t t ` t t t ` t ` t ` t t t t
  x y ` x ` y ` y ` t x ` t ` x ` z t y ` z t + + + + + + + + + + + + + + + + + + + +

 

2. Строим решеточное выражение (по столбцам таблицы).

E = (2Ú3)(2Ú5)(2Ú3)2(5Ú6)(3Ú4)(3Ú4)(1Ú4)(1Ú6)(1Ú4)(1) = (2Ú3)(2Ú5)(5Ú6)(3Ú4)(1Ú4)(1Ú6)12 = (5Ú6)(3Ú4)(1)(2) = 1235Ú1245Ú1236Ú1246.

3. Строим все тупиковые ДНФ функции f:

простые импликанты 1,2,3,5;

простые импликанты 1,2,4,5;

простые импликанты 1,2,3,6;

простые импликанты 1,2,4,6.

4. Все найденные ТДНФ являются минимальными ДНФ.

 

Алгоритм минимизации функций в классе ДНФ

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

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

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

4. Среди построенных ТДНФ выбираем все минимальные дизъюнктивные нормальные формы функции f.

 

Алгоритм минимизации функций в классе КНФ

Чтобы построить все минимальные КНФ (МКНФ) функции f, следует построить все МДНФ функции ` f и взять от каждой из них отрицание, для чего заменить знаки & на Ú, а Ú на & (сохранив первоначальное распределение скобок) и над каждой буквой поставить знак отрицания. Полученные КНФ для функции f будут минимальными. В самом деле, если бы для f существовала КНФ с меньшим числом букв, то ее отрицание дало бы для ` f ДНФ с меньшим числом букв, чем в любой из минимальных ДНФ для ` f. Противоречие с их минимальностью.

 

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

Пусть f – функция алгебры логики.

1. Строим все МДНФ функции f.

2. Строим все МКНФ функции f.

3. Из построенных минимальных форм выбираем простейшие (по числу букв).

Пример 6. В классе нормальных форм минимизировать функцию f =(01011110).

1. Строим СДНФ для функции f:

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

3. Строим матрицу покрытий (таблица 3.6).

Таблица 3.6

  N   ПИ   ` x ` y z ` x y z x ` y ` z x ` y z x y ` z
    ` x z ` y z x ` y x ` z   + + + + + + + +

 

Решеточное выражение E = (1 Ú 2) 1 (3 Ú 4) 4 = 134 Ú 124.

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

5. Обе построенные ТДНФ являются минимальными.

6. Повторяем эти этапы для функции ` f.

СДНФ:

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

Строим матрицу покрытий (таблица 3.7).

Таблица 3.7

  N   ПИ   x`y`z `x y`z x y z
    `x`z x y z   + + +

 

Решеточный многочлен E = 112 = 12. Единственная тупиковая ДНФ (она же минимальная) для функции Минимальная КНФ функции Из построенных МДНФ и МКНФ выбираем простейшую

Пример 7. В классе нормальных форм минимизировать функцию f =(11011011).

1. СДНФ:

2. Сокращенная ДНФ: =

3. Строим матрицу покрытий (таблица 3.8).

 

Таблица 3.8

  N   ПИ   ` x ` y ` z ` x ` y z ` x y z x ` y ` z x y ` z x y z
  x y x`z y ` z ` x z y z ` x ` y + + + + + + + + + + + +

 

E = (3 Ú 6) (4 Ú 6) (4 Ú 5) (2 Ú 3) (1 Ú 2) (1 Ú 5) = 1246 Ú 1356 Ú 134 Ú 256 Ú 2345.

4. Тупиковые ДНФ функции f:

5. Минимальные ДНФ функции f:

6. Повторяем указанные выше этапы для функции ` f.

СДНФ:

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

Построенная сокращенная ДНФ функции ` f является для нее тупиковой и минимальной.

Минимальная КНФ функции

Построенные МДНФ и МКНФ имеют одно и то же число букв; все они составляют минимальные формы для f:

 




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


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


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



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




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