Лекции по дискретной математике. Математическая логика. Зарипова Э.Р - 18 стр.

UptoLike

ВУЗ: 

РУДН | Москва

Составители: 

Рубрика: 

18
Совершенная дизъюнктивная нормальная форма (СДНФ).
Введем обозначения x
o
=
x
, x
1
=x. Пусть
δ∈{
0,1
}
. Тогда
⎩
⎨
⎧
=
=
=
.,
,
0x
1x
x
δ
δ
δ
Очевидно, что x
δ
=1
⇔
x=
δ
.
Определение.
Выражение вида
12
12
...
n
n
x
xx
δ
δδ
называется
элементарной конъюнкцией.
Членами конъюнкции являются либо сами переменные x
1
,…,x
n
,
либо их отрицания.
Пример 4.3.
.,,
54214321
xxxxxxxx
Определение.
Элементарная конъюнкция, в которую включены
все переменные, называется основной элементарной конъюнкцией.
Пример 4.4.
.,;
5432154321
xxxxxxxxxx5n =
Лемма 4.1.
⎩
⎨
⎧
≠
==
=
.,
,,...,
...
iодногодлябыхотяxесли0
xxесли1
xxx
ii
nn11
n21
n
21
δ
δδ
δ
δδ
Доказательство
Пусть
δ
1
=x
1
,…,
δ
n
=x
n
. Тогда
.111xxxx
n1n1
x
n
x
1n1
===
δδ
Пусть ,
kk
x≠
δ
для некоторого k: nk1
≤
≤
. Тогда
.011011xxxxxx
nk
1
nk
1
x
n
x
k
x
1nk1
=⋅⋅==
δδ
δ
Определение.
Формула
m21
kkk ∨∨∨
=
Φ
... , где k
i
-
элементарные конъюнкции, называется дизъюнктивной
нормальной формой (ДНФ). Если все k
i
являются основными
элементарными конъюнкциями, то ДНФ называется совершенной
(СДНФ).
Пример 4.5.
.
,;
СДНФxxxxxx
ДНФxxxxxx3n
321321
323121
−∨
−
∨∨=

Страницы