Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Минимизция булевых функций в классе ДНФ

Читайте также:
  1. А. Вспомогательные элементы для связи функций между собой
  2. Анатомо-морфологическая база высших психических функций
  3. Анатомо-морфологическая база высших психических функций.
  4. В 9 классе
  5. В то же время, старение тела - это прогрессирую­щий ожог химическими веществами, который приводит к повреждению желез и нарушению их функций, вплоть до их полой дисфункции.
  6. Вопрос № 8. Культурно-историческая концепция психического развития. Понятие высших психических функций.
  7. Вычисление пределов степенно-показательных функций

 

 

 

Переменная или ее отрицание называется литерой. Каждая формула имеет конечное число вхождений литер.

Под вхождением литеры будем понимать место, которое она занимает в формуле. Количество вхождений литер, которые образуют форму, задающую булеву функцию 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).

mybiblioteka.su - 2015-2024 год. (0.006 сек.)