IV. ..
( ) 1854. , .
1938. , , , .
- , .
, , ( ).
, .
, .
(True) 1, (False) 0.
.
, .
.
1. (Ż, NOT) .
.
, , .
2. (Ȼ, OR) .
|
1 2 , .
1 | 2 | 1 2 |
3. (Ȼ, AND) .
&
1 2 , .
1 | 2 | 1 2 |
4. .
→
1 → 2 , 1 = 1, 2 = 0, .
1 | 2 | 1 → 2 |
5. .
~ ↔
1 ↔ 2 , 1 2 = 0 1, .
1 | 2 | 1 ↔ 2 |
|
|
6. mod 2 .
1 2 , , .
1 | 2 | 1 2 |
:, , , →, ↔,
.
:
1. n , .
2. 2n + 2( )
3. k .
4. n + k.
5.
1- 2n/21
2- 2n/22 ..
6. .
:
F(A, B, C) = ((B A) C) A
n = 3. = 23 + 2 = 10
k = 4. = n + k = 7
:
2n/21 = 8/2 = 4 4 4 .
B 2n/22 = 8/4 = 2 2 2 .
2n/23 = 8/8 = 1 1 1 .
B (2 1) | (B A) C (4 3) | A (1) | F(A, B, C) ((B A) C) A (5 6) | |||
() F(X1, X2,,Xn) , 0- 1- .
n .
2- :
1 | ||||||
2 | ||||||
F0 | F(X1, X2)=0 | |||||
F1 | F(X1, X2)= 1 2 | |||||
F2 | 2 | F(X1, X2)= 1 ∆ 2 | ||||
F3 | 1 | F(X1, X2)= 1 | ||||
F4 | 1 | F(X1, X2)= 2 ∆ 1 | ||||
F5 | 2 | F(X1, X2)= 2 | ||||
F6 | mod 2 | F(X1, X2)= 1 2 | ||||
F7 | F(X1, X2)= 1 2 | |||||
F8 | F(X1, X2)= 1 ↓ 2= | |||||
F9 | F(X1, X2)= 1 ↔ 2 | |||||
F10 | 2 | F(X1, X2)= 2 | ||||
F11 | 2 1 () | F(X1, X2)= 2 → 1 | ||||
F12 | 1 | F(X1, X2)= 1 | ||||
F13 | 1 2 | F(X1, X2)= 1 → 2 | ||||
F14 | F(X1, X2)= 1 | 2= | |||||
F15 | F(X1, X2)=1 |
|
|
, n . .
. .
. , X Y, X Y, X Y. (). , F()= (X Y) (X Y).
. , X Y, X Y, X Y. (). , (X Y) (X Y).
. .
() , , ( ). , (X1 X2 X3) (X1 X2 X3).
() , , ( ). , (X1 X2 X3) (X1 X2 X3).
, 1. , 0, (), 1 .
:
1. , f(X1, X2,Xn)=1.
2. () . Xi 1, , 0, .
3. ().
:
X1 | X2 | f(X1,X2) |
, 0. , 1, (), 0 .
:
1. , f(X1, X2,Xn)=0.
2. () . Xi 0, , 1, .
3. ().
:
X1 | X2 | f(X1,X2) |
:
X1 | X2 | X3 | f(X1, X2, X3) |
:
:
.
:
X1 | X2 | f(X1, X2) |
, :
|
|
:
:
, 2n.
, , z , (.. ) (2n-z).
, 0 1, , .
:
, 0 1, . .
:
:
1. ():
2. ():
3. ():
4. ( ):
5. :
6. :
7. :
, (). , .
, Ż, Ȼ, Ȼ.
:
:
1. .
2. .
, . , .
:
Y | ||
X | ||
:
X | ||||
Z | ||||
Y |
, ( ).
:
1. 1 , , ( , ).
2. , , ( , ).
3. , , .
:
F(X, Y, Z)
X | Y | Z | F(X, Y, Z) |
:
:
X | ||||
Z | ||||
Y |
:
X | ||||
Z | ||||
Y |
, , .. .
|
|
, .
: