L. X Xn = {(x1,,xn): xi X 1 i n}.
. (, , , ), :
1) , , ;
2) , , ;
3) , ;
4) , .
F1,F2,,Fn, (F1,F2,,Fn,) r, r . :
, r = {X1,X2,,Xk} :
1, 2,,n = ,
, , 1 i n, i , i , i j {A1, A2,,Ai-1}. , , :
T .
, = Æ, .
T , = {X1,X2,,Xk}, ,
X1,X2,,Xk T A.
T T , .
1 2 , 1 2, 1 2.
, ,
, , , &, (,), ,
: , , , ( ), ( ), (&) ,
:
(1) ( ),
(2) ( ( )) (( ) ( )),
(3) & ,
(4) & ,
(5) ( (&)),
(6) ( ),
(7) ( )
(8) ( ) (( ) (( ) )),
(9) ( ) (( ) ),
(10)
:
MP
e: {0,1}, , :
e( A)= , e(A B)=e(A) e(B), e(A&B)=e(A)&e(B), e(A B)=e(A) e(B).
. L .
. , L. (. .3.3, ). (10) . (5) , K &. (3) (4) : & K & K . L :
( ( )).
:
L ( ( )).
:
, L ( ).
(3) (4), : & K ( ). , ( ) ( ) :
|
|
( ) L ( ) L .
, & ( ). .
, L : & ( ), . L. (1) (10) L. L. , L. L , L. .
. .
3.5.
L P. S. , . . 3.4, .
å Í S . å , e: S I,
e(q) = 1 q Î å. å , . å , q q, Øq. q Øq å .
. å , q Î S, åÈ{q}, åÈ{Øq} .
. , å È {q} . A1, A2, , Am Î å, {A1, A2, , Am, q} . e: S I, e(Ai) = 1 1 £ i £ m, e(q) 0. , e(A1& A2&& &Am&q) = 0, Ø(A1& A1&&Am&q),
A1& &A2&&AmØq, .
A1& &&AmØq . B1,,Bn Î å {B1,,Bn, Øq} :
L B1 & B2 && Bn, q.
, B1&B2&&Bn Lq A1 & A2 && An L Øq :
A1, , Am, B1, , Bn L q & Øq,
{ A1, , Am, B1, , Bn }, å. , {B1,,Bn,Øq} B1,, Bn Î å. , å È {q} , å È {Øq} . .
. å , A Î å ØA å, {A, ØA} .
|
|
( ). å L. å , å .
. , å , . . å¢ Í S, å. Í. å¢ Ê å å. - å¢ Ê S, . q Î S q, Øq å¢, å¢ È {q}, å¢ È {Øq} . å¢. , å¢ .
¢: S I, ¢(q) = 1 q Î å¢, ¢(q) = 0 . , ¢ , å¢. , A, B Î å¢. å¢ , Ø(A & B) Î å¢,
A & B Î å¢. Ø(A & B) Î å¢, å¢ ¢¢, ¢¢(A) = ¢¢(B) = ¢¢(Ø(A & B)) = 1. ¢¢(A & B) = 1 ¢¢(A & B) = 0, Ø(A & B) å¢. , A Î å¢ B Î å¢
A & B Î å¢. ¢(A & B) = ¢(A) & ¢(B). A B :
Ø(A & ØB), (¢(A B)) = (¢(A) ¢(B)). , , ¢ . e | å = 1, å . .
.................................................................................................................................................................................. 3
1. .......................................................................................................................................... 4
1.1. ..................................................................................................................................... 4
1.2. -............................................................................................................................................ 5
1.3. ............................................................................................................................................. 7
1.4. -.......................................................................................................... 8
1.5. .......................................................................................................................................................... 8
1.6. ................................................................................................................................................. 9
1.7. .......................................................................................................................................................... 10
1.8. ........................................................................................................................................................ 10
|
|
1.9. ....................................................................................................................... 11
1.10. ....................................................................................................................................................... 11
1.11. ............................................................................................................................................................. 12
2. ........................................................................................................................................................... 13
2.1. ........................................................................................................................... 13
2.2. ...................................................................................................... 13
2.3. ........................................................................................................................................ 15
2.4. .................................................................................................................................... 15
2.5. ........................................................................................................... 16
2.6. ................................................................................................................................. 17
3. .................................................................................................................................. 19
3.1. L........................................................................................................................................... 19
3.2. ........................................................................................................................................................ 20
3.3. ..................................................................................................................... 21
3.4. .............................................................................................................. 23
3.5. .................................................................................................. 24