Элементы дискретной математики. Часть I - 24 стр.

UptoLike

ВУЗ: 

ЯрГУ | Ярославль

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

Рубрика: 

f(x
1
,...,x
n
)
ϕ(x
1
,...,x
n
,y
1
,y
2
) (¬y
2
) [ϕ(x
1
,...,x
n
,y
1
,y
2
)] ⊆ L = P
2
f(x
1
,...,x
n
) (ε
1
,...,ε
n
)
f(ε
1
,...,ε
n
)=1
{ϕ(x
1
,...,x
n
,y
1
,y
2
)}
ϕ(0,...,0, 0, 0) = 1 ϕ(1,...,1, 1, 1) = 0 ϕ(x
1
,...,x
n
,y
1
,y
2
) /∈ C
0
ϕ(x
1
,...,x
n
,y
1
,y
2
) /∈ C
1
ϕ(x
1
,...,x
n
,y
1
,y
2
) ∈ L
ϕ(x
1
,...,x
n
,y
1
,y
2
)=a
0
⊕ a
1
x
1
⊕ ...⊕ a
n
x
n
⊕ b
1
y
1
⊕ b
2
y
2
.
ϕ(ε
1
,...,ε
n
,y
1
,y
2
)=a
0
⊕ a
1
ε
1
⊕ ...⊕ a
n
ε
n
⊕ b
1
y
1
⊕ b
2
y
2
,
y
1
|y
2
= b
0
⊕ b
1
y
1
⊕ b
2
y
2
.
|
ϕ(x
1
,...,x
n
,y
1
,y
2
) /∈ L
ϕ(ε
1
,...,ε
n
, 0, 0) = 1,ϕ(ε
1
,...,ε
n
, 1, 1) = 0,
ϕ(x
1
,...,x
n
,y
1
,y
2
) /∈ M
ϕ(x
1
,...,x
n
,y
1
,y
2
) ∈ S
ϕ(¬x
1
,...,¬x
n
, ¬y
1
, ¬y
2
)=¬ϕ(x
1
,...,x
n
,y
1
,y
2
),
(f(¬x
1
,...,¬x
n
)&y
1
) ∨y
2
= (f(x
1
,...,x
n
)&¬y
1
) ∨ (¬y
2
)=
=(
f(x
1
,...,x
n
) ∨ y
1
)&y
2
).
(x
1
,...,x
n
):=(¬ε
1
,...,¬ε
n
) ε := f(¬ε
1
,...,¬ε
n
)
(y
1
∨ y
2
)=(ε ∨ y
1
)&y
2
.
y
1
ε y
2
¬ε 1=0
ϕ(x
1
,...,x
n
,y
1
,y
2
) /∈ S
[ϕ(x
1
,...,x
n
,y
1
,y
2
)] = P
2
[ϕ(x
1
,...,x
n
,y
1
,y
2
)] = P
2
|∈[ϕ(x
1
,...,x
n
,y
1
,y
2
)] |
[ϕ(x
1
,...,x
n
,y
1
,y
2
)] NP
L M S
f(x
1
,...,x
n
)
f(x
1
,...,x
n
)&(y
1
&y
2
) /∈ L,

Страницы