Минимизация функций в базисах И-НЕ и ИЛИ-НЕ


 

Функции " стрелка Пирса" (ИЛИ-НЕ) и "штрих Шеффера" (И-НЕ) обладают функциональной полнотой; для двух переменных:

Для n переменных:

Эти соотношения позволяют свести задачу минимизации булевой функции в рассматриваемых базисах к задаче минимизации ДНФ и КНФ.

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

КНФ функции можно представить в общем виде:

где – элементарные дизъюнкции : ;

Используя операцию для n переменных, получим:

Таким образом, минимизацию функции можно осуществлять в базисе , а затем перейти к операции . Операция с помощью реализуется таким образом:

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

 

 
 

Пример: рассмотрим функцию, заданную диаграммой Вейча:

 
 

МКНФ:

Переходя к двухместным операциям, получаем:

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

Пример:

МДНФ:

 

 



Дата добавления: 2016-07-18; просмотров: 2893;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

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

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.