Читайте также:
|
Как уже отмечалось, система операций булевой алг ебры функционально полна, это означает, что для любой логической формулы переход к булевской формуле всегда возможен..
Пусть зафиксирован набор булевых переменных 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
Дата добавления: 2015-07-20; просмотров: 56 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Равносильность формул. | | | Совершенная конъюнктивная нормальная форма. |