Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Упрощение логических функций




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

Алгоритм получения СНДФ из таблицы истинности, задающей функцию:

1. Выбрать из таблицы набор переменных (x1,x2,...,xn) для которого справедливо соотношение f(x1,x2,...,xn) = 1.

2. Сформировать из этого набора переменных и их отрицаний минтерм, т.е. произведение переменных или их отрицаний: если переменная набора имеет нулевое значение, то она берется с отрицанием; переменные, имеющие единичные значения в данном наборе не инвертируются.

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

4. Построить СДНФ путем логического суммирования полученных минтермов.

Аналогично определяется алгоритм для получения СКНФ:

1. Выбрать из таблицы набор переменных (x1,x2,...,xn), для которого справедливо соотношение f(x1,x2,...,xn) = 0.

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

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

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

Пример. По таблице истинности построить СДНФ и СКНФ.

СДНФ (f) = 000 Ú 010 Ú 100 Ú 101 Ú 110 = `X1`X2 `X3 Ú `X1 X2`X3 Ú

Ú X1 `X2 `X3 Ú X1 `X2 X3 Ú X1 X2 `X3.

 

 

___ ___ ___

СКНФ (f) = 001 Ù 011 Ù 111 = (X1 Ú X2 Ú `X3) (X1 Ú `X2 Ú `X3) (`X1 Ú `X2 Ú `X3).

 

 

X1X2X3 f (X1,X2…Xn)
0 0 0  
0 0 1  
0 1 0  
0 1 1  
1 0 0  
1 0 1  
1 1 0  
1 1 1  

 

 

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

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

Аналитические методы.

Наиболее эффективными приемами аналитических методов минимизации являются вынесение за скобки общих членов, а также применение двойного отрицания, теоремы де-Моргана, законов поглощения и склеивания. При этом, наряду с полным склеиванием, т.е. использованием зависимости AB Ú`AB = B или (A Ú B)(`A Ú B) = B (склеивание по A) часто применяют неполное склеивание – оба члена склеивания или один из них остаются и склеиваются с другими членами СДНФ. Неполное склеивание может рассматриваться как сочетание закона склеивания и идемпотентности. При преобразовании следует помнить, что логические операции имеют старшинство – в порядке убывания `, Ù, Ú.

Пример 1. Упростить выражение

f(x1, x2) = x1 Ú `x1x2 = 1x1 Ú `x1x2 = x1(`x2 Ú x2) Ú`x1x2 = x1`x2 Ú x1 x2 Ú x1 x2 Ú `x1x2 = x1(`x2 Ú x2) Ú x2 (x1 Ú `x1) = x1 Ú x2.

Пример. Минимизировать ФАЛ, заданную таблицей истинности.

СДНФ этой ФАЛ = `A`B C Ú`ABC Ú A`B`C Ú A`BC Ú AB`C Ú`AB`C Ú ABC = `AC(`B + B) + A`B (`C + C) + AB (`C + C) + ABC =`A (C + B`C) + A = A + B + C.

 

 

A B C f (ABC)
0 0 0  
0 0 1  
0 1 0  
0 1 1  
1 0 0  
1 0 1  
1 1 0  
1 1 1  

 

Пример 2. Дана таблица истинности. Найти СДНФ и минимизировать ее.

 

x1 x2 x3 f (x1 x2 x3) Проверка
0 0 0    
0 0 1    
0 1 0    
0 1 1    
1 0 0    
1 0 1    
1 1 0    
1 1 1    

 

fСДНФ (x1, x2, x3) = x1`x2 x3 Ú x1`x2`x3Ú x1 x2`x3 Ú `x1 x2`x3 = x1`x2 (x3 Ú `x3) Ú Ú x2`x3 (x1Ú `x1) = x1`x2 Ú x2`x3 = fминДНФ.

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

 




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


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


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



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




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