Лекции.Орг


Поиск:




Категории:

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

 

 

 

 


Дизъюнктивная и конъюнктивная нормальные формы булевой функции (дизъюнкция конъюнкций и конъюнкция дизъюнкций)




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

 

Пример

­­– дизъюнктивная нормальная форма

­­– конъюнктивная нормальная форма

 

Формулы приводятся к нормальной форме следующим путем:

1) с помощью законов де Моргана формула преобразуется к такому виду, чтобы знаки отрицания относились только к отдельным переменным;

2) на основе первого (второго) дистрибутивного закона формула сводится к дизъюнкции конъюнкций (конъюнкции дизъюнкций);

3) полученные выражения упрощаются в соответствии с тождествами ()

 

Пример

Привести к дизъюнктивной и конъюнктивной нормальным формам функцию .

Решение

В соответствии с законом де Моргана преобразуем .

.

На основе законов дистрибутивности раскроем скобки:

.

В соответствии с законом идемпотентности . Откуда

.

Полученное выражение является дизъюнктивной нормальной формой.

Аналогичным образом представим заданную функцию в конъюнктивной нормальной форме:

.

Конъюнктивная нормальная форма получена.

 

Члены дизъюнктивной (конъюнктивной) нормальной формы, представляющие собой элементарные конъюнкции (дизъюнкции) k букв, называются минитермами (макситермами) k- го ранга. Так, например, – минитерм третьего ранга, а – макситерм второго ранга.

Совершенной дизъюнктивной (конъюнктивной) нормальной формой называется дизъюнктивная (конъюнктивная) нормальная форма, каждый минитерм (макситерм) которой содержит все переменные (либо в прямом, либо в инверсном виде).

Например, минитерм функции четырех переменных (х 1, х 2, х 3, х 4) в совершенной дизъюнктивной нормальной форме будет представлен дизъюнкцией двух минитермов: .

 

Вопросы и задания

6.1. Может ли одной и той же дизъюнктивной нормальной форме соответствовать несколько различных совершенных дизъюнктивных нормальных форм?

6.2. Может ли одной и той же совершенной дизъюнктивной нормальной форме соответствовать несколько различных дизъюнктивных нормальных форм?

6.3. Представьте функцию трех переменных

а) в дизъюнктивной нормальной форме;

б) в совершенной дизъюнктивной нормальной форме;

в) в конъюнктивной нормальной форме;

г) в совершенной конъюнктивной нормальной форме.

6.4. Схема, представленная на рис.4.4 соответствует дизъюнктивной нормальной форме. Каждая ветвь цепи соответствует одному минитерму. Какая цепь соответствует макситерму? Каков общий вид схемы, соответствующей конъюнктивной нормальной форме?

 





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


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 514 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Лаской почти всегда добьешься больше, чем грубой силой. © Неизвестно
==> читать все изречения...

4285 - | 4123 -


© 2015-2026 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.