Совершенная дизъюнктивная нормальная форма.

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

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

Пусть зафиксирован набор булевых переменных x_1,x₂, ..., x_n.

Определение 1 . Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Если число переменных равноn, то такая элементарная конъюнкция называется полной.

В примере 1 - полные элементарные конъюнкции.

Определение 2. Дизъюнкция полных элементарных конъюнкций называется совершенной дизъюнктивной нормальной формой (СДНФ).

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

Приведение формулы к СДНФ.

Способ перехода от табличного задания к булевой формуле: для каждого набора переменных x₁, x₂, ... x_n , для которого функция f(x₁, x₂, ... x_n) равна 1, выписывается конъюнкция всех переменных: над теми переменными, которые на этом наборе равны 0, ставятся отрицания; все такие конъюнкции соединяются знаком дизъюнкции.

Полученная таким образом формула является совершенной дизъюнктивной нормальной формой ( СДНФ) логической функции f(x₁, x₂, ..., x_n).

СДНФ из таблицы примера 1 предыдущего параграфа имеет вид

(Для удобства восприятия символ конъюнкции представлен в виде ∙).

Пример 1 0 0 1

0 1 1

1 0 0

1 0 0

П р и ме р 2. f(x₁, x₂) ≡ x₁ ~ x₂x₁ x₂ x₁ ~ x₂f(x) ≡

0 0 1

0 1 0

1 0 0

1 1 1

<== предыдущая лекция | следующая лекция ==>

Равносильность формул. | Совершенная конъюнктивная нормальная форма.