Совершенная дизъюнктивная нормальная форма.
Как уже отмечалось, система операций булевой алгебры функционально полна, это означает, что для любой логической формулы переход к булевской формуле всегда возможен. .
Пусть зафиксирован набор булевых переменных x1, x2, ..., xn.
Определение 1 . Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Если число переменных равно n, то такая элементарная конъюнкция называется полной.
В примере 1
- полные элементарные конъюнкции.
Определение 2. Дизъюнкция полных элементарных конъюнкций называется совершенной дизъюнктивной нормальной формой (СДНФ).
Теорема. Любая булева формула может быть представлена и притом единственным образом в виде СДНФ.
Приведение формулы к сднф.
Способ перехода от табличного задания к булевой формуле: для каждого набора переменных x1, x2, ... xn , для которого функция f(x1, x2, ... xn) равна 1, выписывается конъюнкция всех переменных: над теми переменными, которые на этом наборе равны 0, ставятся отрицания; все такие конъюнкции соединяются знаком дизъюнкции.
Полученная таким образом формула является совершенной дизъюнктивной нормальной формой ( СДНФ) логической функции f(x1, x2, ..., xn).
СДНФ из таблицы примера 1 предыдущего параграфа имеет вид
(Для удобства восприятия символ конъюнкции представлен в виде ∙).
Пример 1
0 0 1
0 1 1
1 0 0
1 0 0
П р и ме р 2. f(x1,
x2) ≡ x1
~ x2 x1
x2 x1
~ x2 f(x)
≡
0 0 1
0 1 0
1 0 0
1 1 1
Совершенная конъюнктивная нормальная форма.
Пусть зафиксирован набор булевых переменных x1, x2, ..., xn.
Определение 1 . Элементарной дизъюнкцией называется дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза. Если число переменных равно n, то такая элементарная дизъюнкция называется полной.
В примере 2
- полные элементарные дизъюнкции.
Определение 2. Конъюнкция полных элементарных дизъюнкций называется совершенной конъюнктивной нормальной формой (СКНФ).
Теорема. Любая булева формула может быть представлена и притом единственным образом в виде СКНФ.
Приведение формулы к скнф.
Способ перехода от табличного задания к булевой формуле: для каждого набора переменных x1, x2, ... xn , для которого функция f(x1, x2, ... xn) равна 0, выписывается дизъюнкция всех переменных: над теми переменными, которые на этом наборе равны 1, ставятся отрицания; все такие дизъюнкции соединяются знаком конъюнкции.
Полученная таким образом формула является совершенной конъюнктивной нормальной формой ( СКНФ) логической функции f(x1, x2, ..., xn).
П р и м е р 1.
0 0 1
0 1 1
1 0 0
1 1 1
П р и м е р 2. . f(x1,
x2) ≡ x1
~ x2 x1
x2 x1
~ x2 f(x)
≡
0 0 1
0 1 0
1 0 0
1 1 1