Логика. Множества. Вероятность. Лексаченко В.А. - 10 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

1.2. Polnye mnoestva bulevyh funkci$i. Bazisy
Iz teoremy 1.3 sleduet, qto nekotorye iz bulevyh funkci$i
mono vyrazit~ qerez drugie i potomu mnoestvo funkci$i,
predstavlennyh v tabl. 2 izbytoqno.
Opredelenie 1.4 (Polnye mnoestva funkci$i, bazisy). Mno-
estvo bulevyh funkci$i nazyvaets polnym, esli lba buleva
funkci moet byt~ vyraena qerez funkcii togo mnoes-
tva. Minimal~noe polnoe mnoestvo nazyvaets bazisom.
Opredelenie 1.5 (lementarnye konnkcii, diznkcii).
lementarno$i konnkcie$i
(
diznkcie$i)
nazyvaets funkci
c
a
(x)
V
n
i
=1
x
a
i
i
,
d
a
(x
)
c
a
(
x) =
W
n
i=1
x
a
i
i
, gde
a
, x
∈
B
n
.
Teorema 1.4 (Svo$istva funkci$i
c
a
(
x), d
a
(x
)).
1) c
a
(x) =
1
pri x=a
0 pri
x6=
a
,
2)
d
a
(x) =
0 pri x =a
1 pri x
6
=
a
,
3) esli a
6= b
, to
c
a
(x)
∧
c
b
(
x
)=0
, c
a
(
x)
∨
c
b
(
x
)=
c
a
(
x)
⊕
c
b
(x
)
.
D o k a z a t e l ~ s t v o . 1. Iz ravenstva c
a
(
x
) =
V
n
i=1
(
x
i
∼ a
i
)
sle-
duet, qto c
a
(x) = 1
pri x
=
a
i c
a
(
x) = 0
pri x 6
=
a
.
2. Formula dl d
a
(x) sleduet iz opredeleni i svo$istva 1.
3. Iz 1 i
a 6= b sleduet
c
a
(x)∧c
b
(
x
)=0, otkuda po osnovnomu
sootnoxeni 42 poluqim
c
a
(
x)
∨
c
b
(
x
)=
c
a
(x
)⊕c
b
(
x
)
.
J
Opredelenie 1.6 (DNF, KNF, SDNF, SKNF). Pust~ b
ij
— bu-
leva peremenna ili ee otricanie. Vyraenie
W
m
i
=1
V
n
i
j
=1
b
ij
nazyvaets diznktivno$i normal~no$i formo$i
(
DNF
)
funkcii,
kotoru ono predstavlet. Vyraenie
V
m
i=1
W
n
i
j
=1
b
ij
nazyva-
ets konnktivno$i normal~no$i formo$i (
KNF
) funkcii, koto-
ru ono predstavlet. DNF (KNF
)
nazyvaets soverxenno$i ili
SDNF (
SKNF
)
, esli kada peremenna vhodit v kadu le-
mentarnu konnkci
(diznkci
) odin raz.
Teorema 1.5 (Predstavleni bulevyh funkci$i). Vska funkci
f
(
x) predstavlets formulami:
1) f
(
x) =
_
a ∈{f
=1
}
c
a
(x
)
(
SDNF
f)(x)
,
2) f
(x
) =
^
a ∈{
f=0}
d
a
(
x
)
(
SKNF f)(
x
)
,
3)
f(x) =
_
a
∈{f
=1}
d
a
(
x
) =
^
a
∈{f=0}
c
a
(
x
) =
M
a
∈{f=1}
n
^
i
=1
(x
i
⊕
a
i
⊕
1) ,
10

Страницы