Основные определения.
— конечный алфавит из переменных.
Рассмотрим слово:
Экспоненциальные обозначения:
— элемент конъюнкции.
S – длина элемента конъюнкции.
ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.
Любая булева функция может быть представлена как ДНФ
2.2.2 Теорема о совершенной ДНФ.
Любая булева функция тождественно не равная 0 может быть разложена в ДНФ следующего вида:
Опр: Носитель булевой функции
.
Лемма:
1) это элементарно
2) возьмем набор
а)
б)
Доказательство: , будем доказывать, что.
1) Докажем, что . Возьмем он попадает в число суммируемых наборов и по нему будет проводиться сумирование.
2) Докажем, что . Возьмем другой набор из
Следовательно
2.2.3 Некоторые другие виды ДНФ.
Опр: — называется минимальной ДНФ, если она имеет — наименьшую возможную длину из всех ДНФ данной функции.
Опр: — называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.
(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)
Опр: К-мерной гранью называется такое подмножество , которая является носителем некоторой элементарной конъюнкции длины: n-k.
Опр: Предположим дана функция и есть . Грань называется отмеченной, если она целиком содержится в носителе Т.
Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.
Предложение: Любую отмеченную грань можно вложить в максимальную грань.
Предложение:
(Носитель любой функции можно разложить в объединение нескольких граней разной размерностей)
Предложение: Носитель любой функции разлагается в объединение всех своих максимальных граней.
Опр: Элементарная конъюнкция называется минимальной, если её носитель является максимальной гранью. Следовательно всякая булева функция разлагается в дизъюнкцию всех своих элементарных конъюнкций.
Опр: Сокращенная ДНФ – разложение данной булевой функции в соответствующие ДНФ, которые соответствуют объединению её максимальных граней.
Теор: Минимальная ДНФ может быть получена из сокращенной отбрасыванием некоторого количества слагаемых, возможно пустого.