. . , . . ,
.
, .
, 23010062 .
, , . , .
-
, 2009
.. 4
1. .. 4
1.1. . 4
1.2. . . 5
1.3. . 7
1.4. . . 10
1.5. . . 11
1.6. . 12
. 12
2. .. 15
2.1. . . . 15
2.2. .. 18
2.3. . 19
2.4. . 20
3. .. 22
3.1. . 22
3.2. . . 25
3.3. . 27
4. .. 30
4.1. . 30
4.2. . 31
4.3. . 33
5. .. 33
5.1. . 33
5.2. . 34
5.3 . 37
.. 38
, , , . (computer science). :
;
|
|
|
, , ;
;
;
- ;
, .
1.
, , , . .
, {0, 1}:
l (P) P.
λ . , , . 0, 1 λ () = 0 λ () = 1 = 0 = 1.
( ), :
1) Ø P ( " P ");
2) P Ù Q P & Q ( " P Q ");
3) P Ú Q ( " P Q ");
4) P Q ( " P, Q " " P Q ");
5) P Q ( " P Q " " P , Q ").
: P , Ø P . 1 ( ).
1
| P | Q | P Ù Q | P Ú Q | P Q | P Q |
, P Ù Q , P Q , . .
P Ú Q , P Q , . .
P Q , P = 1, Q = 0. . ( ) , - . , , . .
P Q , P Q .
, .
|
|
|
1.2. .
, .
() :
1) ;
2) F1 F2 , Ø F, (F1 Ù F2), (F1 Ú F2), (F1 F2), (F1 F2) ;
3) , , .
. , .
F (X1, X2,, Xn) , X1, X2,, Xn, A1, A2,, An , , , F (A1, A2,, An).
F (X1, X2,, Xn) (), A1, A2,, An, () F (A1, A2,, An).
, ( , ), () . : ⊨ F (X1, X2,, Xn).
: P P, P Ú P, (P Ù P), P P, - (P Ù Q) (Ø P Ú ØQ), (P Ú Q) (Ø P Ù ØQ) .
.
() . .
G (X1, X2,, Xn) F1 (X1, X2,, Xn), , Fm (X1, X2,, Xn), , F1 , ,Fm. F1 , ,Fm ⊨ G.
, . F G : F º G. , . . .
P, Q, R :
1. .
) P Ù Q º Q Ù P ( );
) P Ú Q º Q Ú P ( ).
2. .
) P Ù(Q Ù R) º (P Ù R)Ù R ( );
) P Ú(Q Ú R) º (P Ú Q)Ú R ( ).
3. .
) P Ù(Q Ú R) º (P Ù Q)Ú(P Ù R) ( );
) P Ú(Q Ù R) º (P Ú Q)Ù(P Ú R) ( ).
4. .
) Ø(P Ù Q) ºØ P ÚØ Q ( );
) Ø(P Ú Q) º Ø P ÙØ Q ( ).
5. .
) P Ù P º P ( );
) P Ú P º P ( ).
6. .
|
|
|
) P Ù(P Ú Q) º P (1- );
) P Ú(P Ù Q) º P (2- ).
7. ().
) (P Ù Q)Ú(P ÙØ Q) º P (1- );
) (P Ú Q) Ù (P ÚØ Q) º P (2- ).
8. .
Ø(Ø P) º P.
9. .
) P Ù1 º P; ) P Ù0 º 0; ) P Ú1 º 1;
) P Ú0 º P; ) Ø0 º 1; ) Ø1 º 0.
10. .
P ÙØ P º 0.
11. .
P ÚØ P º 1.
12. P Q ºØ P Ú Q º Ø(P ÙØ Q).
13. P Q º (P Q)Ù(Q P) º (P Ù Q) Ú (Ø P ÙØ Q) º (P ÚØ Q)Ù(Ø P Ú Q).
, , º.
