Реферат: Математическая Логика

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

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

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

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

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

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

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

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

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

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

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

.

Лемма :

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

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

а)

б)

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

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

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

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

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

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

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

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