Совершенная дизъюнктивная нормальная форма.
Как уже отмечалось, система операций булевой алгебры функционально полна, это означает, что для любой логической формулы переход к булевской формуле всегда возможен. .
Пусть зафиксирован набор булевых переменных 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
Как уже говорилось, одна и та же логическая
формула может быть представлена с
помощью различных наборов логических
операций. Существуют наборы логических
операций, с помощью которых можно
выразить любую логическую формулу.
Такие наборы называют функционально
полными системами или базисами.
Примером, базиса является набор
Этот базис обозначается буквой B.
Формулы алгебры высказываний, при образовании которых не использовались операции, отличные от , называют булевыми формулами алгебры высказываний.
Множество всех булевых формул называют логической оболочкой базиса В и обозначают P2(B).