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

Задача минимизция булевых функций в классе ДНФ заключается в том, чтобы для данной булевой функции f найти ДНФ, представляющую эту функцию и имеющую наименьшую сложность L(f).

Читайте также:
  1. I. Использование функции Подбор параметра
  2. I. Основные функции и функциональные задачи управления фирмой.
  3. I. Переведите следующие предложения, обращая внимание на пе­ревод неличных форм глагола и их функцию.
  4. I. Переведите следующие предложения, обращая внимание на пе­ревод неличных форм глагола и их функцию.
  5. II. Логистические функции.
  6. III. Функции действующих лиц
  7. III. Функции и полномочия контрактной службы

 

Элементарным произведением называется конъюнкт, в который любая переменная входит не более одного раза.

Пример6. 2. Формула - элементарное произведение, а формула элементарным произведением не является.

 

Формула называется импликантой формулы , если - элементарное произведение и , т.е. для соответствующих формулам и функций справедливо неравенство .

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

Импликанта называется простой, если после отбрасывания любой литеры из не получается формула, являющаяся импликантой формулы .

Пример6.3. Найдем все простые импликанты для формулы . Всего имеется 8 элемен­тарных произведений с переменными х и у. Ниже приведены их таблицы истинности:

 

x y x y
   

 

Из таблиц истинности заключаем, что формулы , , , , y - все импликанты формулы , а из этих импликант простыми являются формулы и у (формула , например, не является простой импликантой, поскольку отбрасывая литеру , получаем импликанту ).

 

Дизъюнкция всех простых импликантданной формулы (функции) называется сокращенной ДНФ .

 

Теорема. Любая булева функция, не являющаяся константой 0, представима в виде сокращенной ДНФ.

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

Представление функции в виде тупиковой ДНФ в общем случае неоднозначно.

 

Выбор из всех тупиковых форм формы с наименьшим числом вхождений переменных дает минимальную ДНФ (МНДФ).

 

 

Рассмотрим метод Квайна для нахождения МДНФ, предста­вляющей данную булеву функцию.

Определим следующие три операции:

операция полного склеивания —

операция неполного склеивания

— операция элементарного поглощения

 

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

 

Пример6.4 . Пусть функция f(x,y.z) задана СДНФ

Тогда, произведя в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, имеем

 

Таким образом, сокращенной ДНФ функции f является формула .

 

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



 

Пример 6.5 . Пусть функция f(x,y.z) задана СДНФ

Тогда, произведя операции склеивания, а затем элементарного поглощения, имеем

 

 

Для получения минимальной ДНФ из сокращенной ДНФ используется матрица Квайна, которая строится следующим образом.

В заголовках столбцов таблицы записываются конституенты единицы совершенной ДНФ, а в заголовках строк — простые импликанты из полученной сокращенной ДНФ. B таблице звездочками отмечаются те пересечения строк и столбцов, для которых конъюнкт, стоящий в заголовке строки, входит в конституенту единицы, являющейся заголовком столбца.

 

 

Для примера 6.5. матрица Квайна имеет вид

 

 

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

Загрузка...

Минимальная ДНФ заданной функции есть .

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

 

 

 

 


Дата добавления: 2015-07-11; просмотров: 96 | Нарушение авторских прав


Читайте в этой же книге: Представление функций формулами. Равносильные формулы. | Принцип двойственности | Дизъюнктивные и конъюнктивные нормальные формы. | Совершенные ДНФ и КНФ. | Алгоритм нахождения СДНФ функции, заданной таблицей истинности. | Многочлены Жегалкина |
<== предыдущая страница | следующая страница ==>
Минимизция булевых функций в классе ДНФ| Замыкание множества булевых функций.

mybiblioteka.su - 2015-2018 год. (0.015 сек.)