Дизъюнктивные нормальные формы.

 Основные определения.

 — конечный алфавит из переменных.

Рассмотрим слово:

Экспоненциальные обозначения:

 — элемент конъюнкции.

S – длина элемента конъюнкции.

ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.

Любая булева функция может быть представлена как ДНФ

2.2.2  Теорема о совершенной ДНФ.

Любая булева функция  тождественно не равная 0 может быть разложена в ДНФ следующего вида:

Опр: Носитель булевой функции

.

Лемма:

1)                        это элементарно 

2)                        возьмем набор

а) 

б) 

Доказательство: , будем доказывать, что.

1)                       Докажем, что . Возьмем  он попадает в число суммируемых наборов и по нему будет проводиться сумирование.

2)                       Докажем, что . Возьмем другой набор из

Следовательно

2.2.3  Некоторые другие виды ДНФ.

Опр:  — называется минимальной ДНФ, если она имеет  — наименьшую возможную длину из всех ДНФ данной функции.

Опр:  — называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.

 (Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

Опр: К-мерной гранью называется такое подмножество , которая является носителем некоторой элементарной конъюнкции длины: n-k.

Опр: Предположим дана функция  и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.

Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

Предложение:

 (Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)

Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.

Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.

Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.

Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.

 

Логика - доступно для всех