, , ?
I
:
: n 2n
II
. .
III
, @1 , 7(@1). , .
.1 Û .
.2 Û .
.1 Û .
.2 Û .
IV
: ( ) F(X1, X2, , Xn) . , , .
.?╞ F(X,Y,Z) @ (X(YZ))(Y(XZ))
1) X=0: F(0,Y,Z) @ (0(YZ))(Y(0Z)) @ 1(Y1) @ 11 @ 1.
, (0,Y,Z) F 1.
2) X=1: F(1,Y,Z) @ (1(YZ))(Y(1Z)) @ (YZ)(YZ) @ 1.
, (1,Y,Z) F 1.
 X
| 
| 7X |
  Y
|  7Y Y
| 7Y 
|
 
|    
|  
|
| Z 7Z | Z 7Z Z | 7Z Z 7Z |
, , F , :
| X
|
| 7X |
1 1
()
1
() n
f: {0, 1}n {0, 1}
: , ,
. 
n .
(?)
f: {0, 1} {0, 1}
| x | f(x) | f0(x) | f1(x) | f2(x) | f3(x) |
| f(0) | |||||
| f(1) |
f0(x)=0 , f1(x)=x ,
f2(x)=x¢ , f3(x)=1 .
f: {0, 1}2 {0, 1}
| x | y | f(x, y) | f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 |
| f(0, 0) | ||||||||||||||||||
| f(0, 1) | ||||||||||||||||||
| f(1, 0) | ||||||||||||||||||
| f(1, 1) |
f0(x,y)=0 ,
|
|
|
f1(x,y)=x×y ,
f2(x,y)=(xy)¢
f3(x,y)=x
f4(x,y)=(yx)¢
f5(x,y)=y
f6(x,y)= (xy)¢=x+y ( 2, XOR, Ȼ)
f7(x,y)=xÚy
f8(x,y)=(xÚy)¢=x¯y
f9(x,y)=xy
f10(x,y)=y¢
f11(x,y)=yx
f12(x,y)=x¢
f13(x,y)=xy
f14(x,y)=(x×y)¢=x½y
f15(x,y)=1
2
xi f(x1, x2, , xn):
f(a1, a2, , ai-1, 0, ai+1, , an) ¹ f(a1, a2, , ai-1, 1, ai+1, , an)
(a1, a2, , ai-1, ai+1, , an) (x1, x2, , xi-1, xi+1, , xn)
()
 x
| y | z | f(x,y,z) |
 1
| |||
 1
| |||
 1
| |||
| 1
|
:
1) ,
2) , ,
3) , ,
4) ,
,
5)
6)
7)
8) 0 1
9)
10) ,
3
x1, x2, x3, , xk
(1)
(2)
,
n ,
.
| x | y | z | f(x, y, z) | - | - |
| xÚyÚz | |||||
| xÚyÚz′ | |||||
| x′yz′ | |||||
| x′yz | |||||
| xy′z′ | |||||
| xy′z | |||||
| x′Úy′Úz | |||||
| xyz |
f(x, y, z): x′yz′ Ú x′yz Ú xy′z′ Ú xy′z Ú xyz
f(x, y, z): (xÚyÚz) (xÚyÚz′) (x′Úy′Úz)
|
|
|
f(x, y, z): x′yz′ + x′yz + xy′z′ + xy′z + xyz =
= x′y (z′ + z)+ xy′(z′ + z) + xyz = (x+1)y + x(y+1) +xyz = xy + y + xy + x + xyz =
= xyz + x + y
4
( 1- ) f1, f2, , fm
={f1, f2, f3, , fm} ,
f1, f2, f3, , fm
. = {f1, f2, f3, , fm} , f1, f2, f3, , fm g1, g2, g3, , gk . {g1, g2, g3, , gk } . (!)
M ,
={f1, f2, f3, , fm} ,
[M] = M.
T0 = {fÎP2| f (0, 0, 0, , 0)=0} , .
T1 = {fÎP2| f (1, 1, 1, , 1)=1} , .
TS = {fÎP2| f = f*} .
f = f* Û f′ (x1, x2, x3, , xn) = f(x1′, x2′, x3′, , xn′),
.. f , .
a 
Î{0, 1}n, b 
Î{0, 1}n,
a b, ai≤ bi i=1, , n
TM = {fÎP2| a, bÎ{0, 1}n a ≤ b Þ f(a) ≤ f(b)} .
TL = {fÎP2| f = a0+a1x1+a2x2++anxn, ai Î{0, 1}, i = 0, , n} .
T0, T1, TS, TM . TL .
T0, T1, TS, TM, TL , ,
. () M , T0, T1, TS, TM, TL.
5
- () .
:
f(x1, x2, x3, , xn) ,
f(x1, x2, x3, , xn) = 
.
x f (x) = x
x′ f (x) = x′
x y f (x, y) = xy
x
f (x,y) = xÚy
y
.
.
.
| x | y | z | f(x, y, z) | - |
| x′yz | ||||
| xy′z | ||||
| xyz′ | ||||
| xyz |
f (x, y, z) = x′yz Ú xy′z Ú xyz′ Ú xyz 1
f (x, y, z) = yz Ú xz Ú xy 2
f (x, y, z) = y(zÚx) Ú xz 3
6
, .
j(x1, x2, x3, , xn) f, j , f.
j , j .
|
|
|
Þ Þ
| x1 | x2 | xn | x1x2 | x1x3 | xn-1xn | x1x2 x3 | xn-2xn-1 xn | x1x2 xn | ||||
| x1′ | x2 | xn | x1′x2 | x1′x3 | xn-1xn | x1′x2 x3 | xn-2xn-1 xn | x1′x2 xn | ||||
| x1 | x2′ | xn | x1x2′ | x1x3 | xn-1xn | x1x2′x3 | xn-2xn-1 xn | x1x2′ xn | ||||
| x1 | x2 | xn′ | x1x2 | x1x3 | xn-1xn′ | x1x2 x3 | xn-2xn-1 xn′ | x1x2 xn′ | ||||
| x1′ | x2′ | xn | x1′x2′ | x1′x3 | xn-1xn | x1′x2′x3 | xn-2xn-1 xn | x1′x2′ xn | ||||
| x1′ | x2′ | xn′ | x1′x2′ | x1′x3′ | xn-1′xn′ | x1′x2′x3′ | xn-2′xn-1′xn′ | x1′x2′ xn′ |
. i- f(x1, x2, x3, , xn), , .
) : j × x Ú j × x′ = j
) : j × x Ú j × x′ = j Ú j × x Ú j × x′
) ) : j ×x Ú j =j, j × x′ Ú j = j
. () , , .
 x
|  x′
| ||
 y
| z′ | ||
| 
| z | |
| |||
| y′ | z′ |
f (x, y, z) = xyz′ Ú xyz Ú xy′z Ú x′yz′ Ú x′yz = y Ú xz
()
1
. . , .
A, B ╞ C
 |  |
()
n - , M1× M2× M3×× Mn, , x1, x2, x3,..., xn, x1, x2, x3,..., xn M1× M2× M3×× Mn
P(x1, x2, x3,..., xn)
Q, R, S, T,
P(x1, x2, x3,..., xn)
I(P) = {(a 1, a 2, a 3, , a n)| λ(P(a 1, a 2, a 3, , a n) = 1)}
I(P) = M1× M2× M3×× Mn
I(P) = Æ
I(P) ¹ Æ
I(P) ¹ M1× M2× M3×× Mn
"x P(x) () x P(x) ( )
$x P(x) () x , P(x) ( )
2
:
- x, y, z, xi, yi (iÎ N)
- P, Q, R,
- n- (n≥1)
|
|
|
- P1(n)(,, ,), P2(n)(,, ,), , Q(n)(,, ,) R(n)(,, ,)
-
-
-
1
2 P(n)(,, ,) - n- (n≥1) x1, x2, , xn , P(x1, x2, , xn) , x1, x2, , xn
3 F , 7F , , F
4 F1, F2 , , (F1*F2), * Ù, Ú, , , . () , () F1, F2
5 F x , ("x F) ($x F) , x
6
, .. 1, 2,
:
;
;
. (, 1936) , ,
