. ,
( ). ,
. , ,
.
, .
1. "x P(x) º $x P(x) 2.$x P(x) º "x P(x) 3. "x P(x) º $x P(x)
4. $x P(x) º "x P(x) 5. "x P(x) Ú Q) ( Q x.)
6. "x P(x) & Q º "x (P(x) & Q) 7. $x P(x) Ú Q º $x (P(x) Ú Q)
8. $x P(x) & Q º $x (P(x) & Q) 9. "x Q º Q
10. $x Q º Q 11. "xP(x) & "xR(x) º "x (P(x) & R(x)) 12. $xP(x) Ú $xR(x) º $x (P(x) Ú R(x))
13. "xP(x) Ú "xR(x) "x (P(x) Ú R(x)) 14. $x (P(x) & R(x)) $xP(x) & $xR(x)
15. "x P(x) º "yP(y) (, - ) 16. $x P(x) º $y P(y)
17. "x$y P(x, y) º $x"y P(x, y) 18. "x"y P(x, y) º "x"y P(x, y)
19. $x$y P(x, y) º $x$y P(x, y)
. , ,
.
:
1. .
2. .
3. .
. . .
1. ()
2.
3.
Vx(ƎyP(x,y v ƎyR(y) -> Q(x) v ƎyF(y))
Vx(⌐ƎyP(x,y) & ⌐ƎyR(y) v Q(x) v ƎyF(y))
Vx(Vy⌐P(x,y) & Vy⌐R(y) v Q(x) v Ǝy F(y)) y z ( 2 )
VxVyƎz(⌐P(x,y) & ⌐R(y) v Q(x) v F(z))
, , , ,
. .
1. : , , ..
2.
3..
4. ( )
: (ƎxP(x)vVyQ(y) & (Vx,yR(x,y)vƎyL(y))= (ƎxP(x)vVyQ(y)& (Vz,qR(z,q)vƎdL(d) =
ƎxVyVzVqƎd(P(ac)vq(y) & (R(z,q)vL(fc(y,z,q))
ƎxP(x) P(ac)
C
VxƎyP(x,y)=P(x,fc(x))
|
|
8. .
,
.
:
) ,
( , ): A, B, C,..., Z
: (,), ,
) .
, AB (B , ,
(A B) (B)
, :
) (A... Z) .
) , - , (), A, A B - .
:
A (A B)
(A (B C)) ((A B) (A C))
(A B) (B A)
A, B, C .
.
: (
) modus ponens
( ) - mp. , ,
.
A, A B ½¾ B
½¾ "".
A A B B B .
( ) 1, 2,..., n,
, .
.
. , , ,
() : , , ..
, , .
:
: ½¾ A A
1: 2 = , = , = , :
(A ((A A) A)) ((A (A A)) (A A))
2: 1, = , = , :
( (( ) ))
1,2 m.p. 3: (A (A A)) (A A)
4: 1, = , = , :
( ( ))
3, 4 m.p. 5: A A
.
- G = <VN,VT, P, S >,
VN - ( );
VT - ( );
P - ;
S Î VN - .
- , :
::= - ;
| - ;
<... > - ;
[ ] - ;
, - .
: G1:
<>::=<> | <>; <>
<>::=<>:= <>
<>::=a | b | c
<>::=<> | <> <> <>
<>::= + | - | * | /
V = VN È VT - .
V* - (, ) ;
V*N - (, ) ;
V*T - (, ) .
|
|
e Î V - , .
a b : a Þ b,
a = vxw b = vyw p: x::= y,
v,w, Î V*, Î VN, = V* \ {e}
a b a Þ* b, a b
.
:
<> Þ <>; <> Þ <>; <> Þ <>:= <>; <> Þ*
a:= b + c; c:= a + b - c;
, () .
b a : a Ü b,
a = vxw b = vyw p: x::= y,
v,w, Î V*, Î VN, = V* \ {e}
b a a *Ü b, b a
.
, () .
, ,
.
L, G - ,
.
.
L(G) = { x Î V*N | S Þ* x }
L .
L(G) = { x Î V*N | S *Ü x }
.
::= , ()
, () .
.
. .