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

UptoLike

ВУЗ: 

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

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

Рубрика: 

D o k a z a t e l ~ s t v o . Esli f
(x
1
,
. . . , x
n
) =
g(x
1
, . . . , x
n
), to po
opredeleni 1.3
f
∗
(x
1
,
. . . , x
n
) =
g
∗
(x
1
,
. . .
, x
n
)
. Obratno, esli
f
∗
(
x
1
, . . .
, x
n
) = g
∗
(
x
1
, . . . , x
n
), to f
∗∗
(
x
1
, . . . , x
n
) = g
∗∗
(
x
1
, . . . , x
n
) i
po sledstvi 1
f
(x
1
, . . . , x
n
) =
g(
x
1
, . . . , x
n
).
J
Tablica 3
Dvo$istvennye funkcii
n peremennyh pri
n
= 0,
1,
2
f
= f
∗∗
1 x x x
∧y
x
|y
x
→ y
x
∼ y
f
∗
0 x x x
∨
y x
↓
y y
\
x x
⊕
y
Teorema 1.2 (Dvo$istvenna k slono$i funkcii).
Pust~ f
1
,
. . .
, f
k
— bulevy funkcii
n peremennyh, g
— buleva funkci
k pere-
mennyh, F (
x
1
,
. . . , x
n
) =
g(f
1
(
x
1
, . . . , x
n
)
,
. . .
, f
k
(
x
1
,
. . .
, x
n
))
. Togda
F
∗
(x
1
,
. . .
, x
n
) = g
∗
(
f
∗
1
(x
1
, . . . , x
n
)
, . . . , f
∗
k
(
x
1
, . . .
, x
n
))
,
t. e. dl poluqeni dvo$istvenno$i k slono$i funkcii
F nuno
vse funkcii, vhodwie v F , zamenit~ na dvo$istvennye.
D o k a z a t e l ~ s t v o . Iz opredeleni otricani sleduet for-
mula x
= x
. Uqityva ee, poluqim
F
∗
(x
1
,
. . . , x
n
) =
F
(
x
1
, . . .
, x
n
) =
g
(
f
1
(
x
1
, . . .
, x
n
),
. . .
, f
k
(
x
1
, . . .
, x
n
)) =
= g(f
1
(x
1
,
. . .
, x
n
) . . . f
k
(x
1
,
. . .
, x
n
)) =
g
∗
(f
1
(x
1
,
. . .
, x
n
) . . . f
k
(x
1
,
. . .
, x
n
)) =
=
g
∗
(f
∗
1
(x
1
,
. . . , x
n
)
, . . .
, f
∗
k
(x
1
, . . .
, x
n
))
. J
V sleduwe$i teoreme privodts ravenstva dl bulevyh
funkci$i, neobhodimye pri uprowenii logiqeskih formul. V
silu principa dvo$istvennosti v kado$i stroke formul nado
dokazat~ tol~ko odno ravenstvo.
Primer 1.1 (Tabliqnye dokazatel~stva ravenstv).
Razvernuty$i
variant dokazatel~stva
a
∨ b
= a
∧
b
priveden v tablice, pome-
wenno$i v ramki, a kompaktny$i variant v tablice bez ra-
mok, v kotoro$i rezul~taty operaci$i pixuts pod ih znaka-
mi (potomu dl otricani ispol~zuets znak
¬
vmesto ).
a b a ∨
b
a ∨
b
a b a∧b
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0
¬
(
a
∨
b
) = (
¬a
) ∧
(
¬
b )
1 0 0 0 1 0 1 1 0
0 0 1 1 1 0 0 0 1
0 1 1 0 0 1 0 1 0
0 1 1 1 0 1 0 0 1
7

Страницы