Читайте также:
|
Переменная или ее отрицание называется литерой. Каждая формула имеет конечное число вхождений литер. Под вхождением литеры будем понимать место, которое она занимает в формуле. Количество вхождений литер, которые образуют форму, задающую булеву функцию f(x1,…, хn), называется сложностью L(f) этой формы. |
Пример 6.1.
Сложность совершенной ДНФ функции f(x1, х2, х3), (голосования «комитета трех») равна 12.
f(x1, х2, х3) = 
Уменьшим сложность этой функции, используя основные тождества алгебры Буля. Согласно свойствам идемпотентности дизъюнкции,
f(x1, х2, х3) = 
Используя свойства коммутативности, ассоциативности и дистрибутивности, получаем
f(x1, х2, х3) = 
Окончательно имеем
f(x1, х2, х3) = 
В результате получаем сложность L(f) функции равную 5.
Дата добавления: 2015-07-11; просмотров: 99 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Алгоритм нахождения СДНФ функции, заданной таблицей истинности. | | | Задача минимизция булевых функций в классе ДНФ заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшую сложность L(f). |