1. -
, (. ). -, , . . . , , . , - . - , . . , , . . .
, - , - . - .
- , . , , . L.
1. L. :
(1) x, y, z, - ( , , 1, 2, y5, z* ..)
(2) 1, 2, -
(3) f, g, h, - ( )
(4) P, Q, R, - ( )
(5) ù, Ú, $ -
(6) (,) -
(1), (4), (5) (6). . , .. , . , f 2 , +. 1 ( ), , .. , , .
|
|
, . - , , . . , f , , - . , , , , - . . , , - , .
2. L. L. . , . . L*, L. :
a, b, c, -
x, y, z, - ( L*) ( L)
, e 1, e 2, e 3, -
f, g, h, -
P, Q, R, -
A, B, C, -
, Y, Z, - L
, L, b L, .. , y, z, L. L* , . L .
2.1. L. :
1) : L .
2) : 1, 2, , a n L, f n L, f ( 1, 2, , a n) L.
3) : L .
, L L, .
2.2. L. :
1) : 1, 2, , a n L, n L, ( 1, 2, , a n) ( ) L.
2) :
2.1) L, ù L,
2.2) , L, Ú L,
2.3) , L, $ - L.
|
|
3) : L .
, L , , , (ù), (Ú) ($) L.
3. L. L , L. . , . - , . , L. , , L ( . ). L.
L 1, 2, , n L,
- n
- 1, 2, , n-1
- L,
- , 1, 2, , n-1.
L L, L.
1, B 2, , B m L.
1, B 2, , B m L 1, 2, , n L,
- n
- 1, 2, , n-1
- L,
- 1, B 2, , B m,
- , 1, 2, , n-1.
, 1, B 2, , B n, . L.
, L L. , L. , , . - . - .
4. L. -. - , . L S = <M,F,P>, , F .
-, S L , , L , S . , L, . Sem(e) . , f n, P m L, Sem(f) - n, Sem(P) - m S. . L S. L S , L, , . , L. , L. , , L. . , . , , g, S. g , L - g() S. g . , g, . , , L S.
|
|
, L. g Sem(X,g) g. S. L .
1. .
1) :
- , Sem(e,g) = Sem(e)
- , Sem(,g) = g(x)
, . .
2) : Sem(a 1,g), Sem(a 2,g), , Sem(a n,g) 1, 2, , a n , f ( 1, 2, , a n) :
Sem(f ( 1, 2, , a n), g) = Sem(f)(Sem(a 1,g), Sem(a 2,g), , Sem(a n,g))
, f ( 1, 2, , a n), Sem(f) Sem(a 1,g), Sem(a 2,g), , Sem(a n,g) 1, 2, , a n.
2. .
1) . Sem(a 1,g), Sem(a 2,g), , Sem(a n,g) 1, 2, , a n , ( 1, 2, , a n) :
Sem( ( 1, 2, , a n), g) = 1 Sem()(Sem(a 1,g), Sem(a 2,g), , Sem(a n,g)) .
, ( 1, 2, , a n) Sem() Sem(a 1,g), Sem(a 2,g), , Sem(a n,g) 1, 2, , a n. ( 1, 2, , a n) 1 , Sem() Sem(a 1,g), Sem(a 2,g), , Sem(a n,g).
|
|
Fù FÚ, :
Fù(1) = 0 Fù(0) = 1 Fù , , .
FÚ(1, 1) = 1,FÚ(0, 1) = 1,
FÚ(1, 0) = 1,FÚ(0, 0) = 0
FÚ , . .
2) .
2.1) Sem(A,g), ù Sem(ù A, g) = Fù(Sem(A,g))
2.2) Sem(A,g) Sem(,g), Ú : Sem( Ú , g) = FÚ(Sem(A,g), Sem(,g)).
$ . , . g - , g[a/ x ] , g , S.
2.3) Sem(A,g), $ :
Sem($ ,g) = 1 S, , Sem(,g[a/ x ]) = 1
L S, Sem(A,g) = 1 g. , L , .
S L, L S ( ) S.
L S.
2. -
- , - , , - ( , ).
, : , [21]. , , , : , 2 ., . : , , . , , , , . , , 1.5 . 2 ., , .
L, . S L . S L1,L2, , Ln C1, C2,,Cm, . :
L1,L2, , Ln
C1, C2,,Cm
( L1,L2, , Ln C1, C2,,Cm) (, ), (, ).
3.
, - , . , . .
|
|
. , , , , . , , , , , . . , , , , , ().
.. .. [22] : , -, , , , , , 1575 . , ? . . , . , . . . , , , - . , , , . - . [23]. , , , . , : , . [24]. .
, . .
- , . , (). :
S
S ,
S
, ( . - ) , . , () , () .
, . , , , .
4.
, , . , , . , , 20 . . - , - . , , , . , , . . . , , . , .
, , . , , .
1. . - . , - . ( ) - , , , . , , . : () , . . , , , . , , - . , , , . , , . , - . , , , . .
2. . . , . 2 1. , 2 1 - (: 2 () 1). - -. - , 1 L1 - 2 L2,
1) L1 L2,
2) 1 2.
, L1 L2, 1 2. , 2 1 . , L1, L2. L1 L2. , 1 2. - , L1 L2. , . - - , , .
3. . ( ) , . - , .. . , , , , . .
, . , , . -, ( , , ).
, , , . .
.. :
1) - . :
- ( ),
- ,
- ( - , ( : , ), ).
2) . :
- ,
- , .
() () . - , () , - . < ( : ¯ ---, .. (¯ ----), ¯). , , , , . < ( ¯ ---, (¯), ). :
- ( ). , , , , . (<) .
- , , (<), .
, , ... , , , - . , , ( , , ..) , , .. , ( , , , ). , :
- ,
- ,
- , .
, , , . (<) , (<) . .