, : , .
, (18151864), , . 1879 (18481925) , , .
, .
. :
1. .
2. .
3. .
4. .
1.
( ) , , , , , .
, :
- ( );
- , ;
- , ;
- , .
, , . . , . .
, ; . . , , , . : ( ) ( ).
|
|
|
R A , R A, , A R.
, , - .
, , .
, , , , ; .
, , .
, :
() () ;
( , );
T ( ).
:
1. . , ( , ), . . . , , , .
2. . , F F, . , (, , ), .
3. . , . , . , .
4. . , , (), , .
( ) , , , .
, :
1)
, 
, 
, ↔, →;
", $;
: .
2)
, , P(n), Q(m), , P1(n), P2(n);
X, Y, Z, , X1, X2, ( , );
|
|
|
x, y, z, , x1, x2,;
a, b, c, , a 1, a 2,
n- P (x1, x2,, xn) P: M1M2ׅMn → {1,0}, n M= M1M2ׅMn {1,0}. , .
P(x1, x2,, xn), M1M2ׅMn P(x1, x2,, xn), , (a 1, a 2,, a n) 
M1M2ׅMn
P(x1, x2,, xn), M1M2ׅMn, Q(y1, y2,, ym), N1N2ׅNm, P Q(x1, x2,, xn, y1, y2,, ym) c M1M2ׅMnN1N2ׅNn, (a 1, a 2,, a n, b 1, b 2,, b m) M1M2ׅMnN1N2ׅNn
P(x1, x2,, xn), M1M2ׅMn, Q(y1, y2,, ym), N1N2ׅNm, P Q(x1, x2,, xn, y1, y2,, yn) c M1M2ׅMnN1N2ׅNn, (a 1, a 2,, a n, b 1, b 2,, b m) M1M2ׅMnN1N2ׅNn
P(x1, x2,, xn), M1M2ׅMn, Q(y1, y2,, ym), N1N2ׅNm, P → Q(x1, x2,, xn, y1, y2,, yn) c M1M2ׅMnN1N2ׅNn, (a 1, a 2,, a n, b 1, b 2,, b m) M1M2ׅMnN1N2ׅNn
P(x1, x2,, xn), M1M2ׅMn, Q(y1, y2,, ym), N1N2ׅNm, P(x1, x2,, xn) ↔ Q (y1, y2,, yn) c M1M2ׅMnN1N2ׅNn, (a 1, a 2,, a n, b 1, b 2,, b m) M1M2ׅMnN1N2ׅNn
xi n- P(x1, x2,, xn)), M1M2ׅMn, , n-1- " xi P(x1, x2,, xi-1, xi+1,, xn), x1 = a 1, , xi-1 = a i-1, xi-1 = a i-1, , xn = a n , xi = a i P(a 1, a 2,, a n) .
xi n- P(x1, x2,, xn) , n-1- $ xi P(x1, x2,, xi-1, xi+1,, xn), x1 = a 1, , xi-1 = a i-1, xi-1 = a i-1, , xn = a n , xi = a i P(a 1, a 2,, a n) .
- , , .
:
;
P(n) (x1, x2,, xn), P(n) n- , x1, x2,, xn ;
F, F ;
F1 F2, F1 F2, F1 ↔ F2, F1 → F2, F1 F2 , ;
" xi P(x1, x2,, xi-1, xi+1,, xn) $ xi P(x1, x2,, xi-1, xi+1,, xn), P(x1, x2,, xn) , xi
.
1) ;
2) , ;
3) 1 () 0 ();
4) .
|
|
|
:
) () , () ;
) - (-) , ();
) (), , ();
) (), - (-).
P(x1, x2,, xn), M1M2ׅMn, (a 1, a 2, a n), a 1 M1 a 2 M2,, a n Mn, , (a 1, a 2, a n) x1 = a 1 x2 = a 2,, xn = a n. P+.
n- (x1, x2,, xn) Q(x1, x2,, xn), M1M2ׅMn , a 1 M1 a 2 M2,, a n Mn (a 1, a 2, a n) , . (x1, x2,, xn) Q(x1, x2,, xn) .
(x1, x2,, xn), M1M2ׅMn Q(x1, x2,, xn), , Q(x1, x2,, xn).
() , . , , , , .. , , .
1) A={ a 0, a 1, , a n};
2) Q={ q 1, q 2,, q m} ;
3) {, , }
4) , , ;
5) ,
0.
q 1, , ( ) q 0, .
, A. ,
q i a j → a pX q k
: q i, a j, (1) a j a p, (2) , , = , , = , , = , (3) q k.
, , q, , q i a j . , . A={ a 0, a 1, , a n} Q={ q 1, q 2,, q m} m (n+ 1) .
|
|
|
Q, A 
Q . k- , k- ( , k- ), , . , .. , , , , , . , , , .
- , , ( ) , . , .
, \ { 0} = { a 1, , a n} , , , , . (), , , q 1 ( q 0).
, , , ( )
:
= {0, 1} ( 0 ), Q = { q 0, q 1, q 2} ():
q 1 0 → 1 q 2;
q 1 1 → 0 q 2;
q 2 0 → 0 q 0;
q 2 1 → 1 q 1;
| q 1 | 1 q 2 | 0 q 2 |
| q 2 | 0 q 0 | 1 q 1 |
, 110, :
q 1
: q 1 0 → 1 q 2 ( q 1, 0, 0 1, , q 2), :
q 2
: q 2 1 → 1 q 1 :
q 1
: q 1 1 → 0 q 2. :
q 2
, q 2 0 → 0 q 0
q 0
, q 0.
, 110 101.
( , ):
11 q 10 => 1 q 211 => 1 q 111 => 1 q 201 => 10 q 01
, () A Q, .. . , , , .
, . , , , q i a j q 0, .
|
|
|
, q i a j, (.. ) , , .
.
, , .
.
, . , . 0, q 0* , q 0, :
q 0 a 1→ a 1 q 0 (1)
q 0 a 2→ a 2 q 0 (2)
q 0 a n→ a n q 0 * (n)
T0.
M . M , q 1 a i T q 0 a 1, (1), T0 . M , q 1 a i T q 0 a n, (n), T0 .
, T0 .
T0 q 1 a i. T0 , . T0 , , q 1 a i, . T0 , , , q 1 a j, . , , .
, . . , .
