ВУЗ:
Составители:
Рубрика:
21
n
1
n1
n1
n1
1f
n1
xxxxf
δ
δ
δδ
δδ
=
∨=
),...,(
,...,
),...,(
- СДНФ
т.е. булевой формулой для f(x
1
,…,x
n
) может служить ее
СДНФ.
Если же f(x
1
,…,x
n
)
≡
0, то f(x
1
,…,x
n
) = x
1
1
x .
Сформулируем изложенные результаты в виде
Теоремы 5.1.
Всякая логическая функция может быть
представлена булевой формулой.
Совершенная конъюнктивная нормальная форма (СКНФ).
Определение. Выражение вида
12
12
...
n
n
x
xx
δδ
δ
∨∨∨ называется
элементарной дизъюнкцией.
Членами дизъюнкции являются либо
1
,...,
n
x
x , либо их
отрицания.
Пример 5.2.
.,,
54214321
xxxxxxxx ∨∨∨∨∨
Определение.
Элементарная дизъюнкция, в которую включены
все переменные, называется основной элементарной дизъюнкцией.
Пример 5.3.
5432154321
xxxxxxxxxx5n ∨∨∨∨∨∨∨∨= ,;.
Определение.
Формула
m21
DDD
⋅
=
Φ
, где D
i
- элементарные
дизъюнкции, называется конъюнктивной нормальной формой
(КНФ). Если все D
i
являются основными элементарными
дизъюнкциями, то КНФ называется совершенной
(СКНФ).
Пример 5.4.
n=3;
−
∨∨∨ ))()((
323121
xxxxxx КНФ,
))((
321321
xxxxxx ∨∨∨∨ -СКНФ.
Спрашивается, нельзя ли произвольную функцию алгебры
логики представить в виде СКНФ? Покажем, что при 1f ≡
/
это
возможно.
Пусть 1xxf
n1
≡
/
),...,(. Разложим функцию f
*
(x
1
,…,x
n
) (очевидно
0xxf
n1
≡
/
),...,(
*
) в СДНФ:
Страницы
- « первая
- ‹ предыдущая
- …
- 19
- 20
- 21
- 22
- 23
- …
- следующая ›
- последняя »
