.
1) . , , . , , R , ( ).
2) . ( :
, (.. ) , (i,j- , ).
.
R , .
3) . , ( ). =A *B ( ), : . AB .
.
, R .
G(R). A, R ( x y , xRy).
( ). , , , , .
,
, .
;
, . [ =A *B ( ), : . AB . ]
; ;
;
; ;
;
/; .
: ={(a,2),(a,6),(c,1),(c,2),(c,4),(c,5),(d,6)}. ; ;
=
={(a,1),(a,3),(a,4),(a,5),(b,1),(b,2),(b,3),(b,4),(b,5),(b,6),(c,3),(c,6),(d,1),(d,2),(d,3),(d,4),(d,5)}
a | b | a & b | a Ú b | a b | a ~ b | a Å b |
x 1 | x 2 | f 0 | f 1 x 1Ù x 2 | f 2 | f 3 x 1 | f 4 | f 5 x 2 | f 6 x 1Å x 2 | f 7 x1Úx2 | f 8 x 1¯x2 | f 9 x 1~ x 2 | f 10 | f 11 x 2 x 1 | f 13 x 1 x 2 | f 14 x 1½ x 2 | f 15 | |
:
|
|
1) ;
2) , ;
3) , ;
4) , ;
5) , ;
6) , ;
7) , , , ;
8) , ;
9) ;
10) ;
11) ;
12) .
: .
. f*(x1, , xn) f(x1, , xn), f(x1, , xn) ,
. , .
() . ( ), ().
:
, :
:
( , ; ). , :
2.9.
.
2.4. , M n, ()( ).
.
.
.
x y z f
0 0 0 0 0 0 1 1 0 1 0 1 1
0 0 1 0 0 1 0 1 1 1 1 z
0 1 0 1 1 1 1 0 0 0 y
0 1 1 1 0 0 1 0 0 yz
1 0 0 0 0 1 1 0 x
1 0 1 1 1 0 1 xz
1 1 0 0 1 1 xy
1 1 1 1 0 xyz
: f(x, y, z) = y⊕xz⊕xy
( ) ().
. , (1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0).
, :
( ) = ( )
( )
.
:
´ | ´ | ||||||||
´ | ´ | ||||||||
´ | ´ | ||||||||
´ | ´ | ||||||||
´ | ´ | ||||||||
´ | ´ | ||||||||
´ | ´ | ´ | ´ |
, ; . , ( 3, 4, 5, 6). . 4 , , ; , :
|
|
.
, 4 :
, , .
.
, , , : (), (), ().
1. , , ().
2. , , (), , .
3. , , (), , .
( ) ANSI:
" " (XOR)
, -. - ( ).
.
1. f =D f =0, c = .
2. : f = f +D f. D c, c D f.
3. D c l s t, . j . j =0 ( ), 4; D f,
2.
4. . f .
c f . D c :
D c (u, v)= c (u, v)- f (u, v)+ f (v, u).
:
t | ||||
s | ||||
s t . , .
1
, , .
|
|
2
, . .
1. . : 10. /
t | ||||
s | 0/10 | |||
5/10 | ||||
A/B/C, A = c(u,v) , B = c(v,u) , C= f(u,v) . , , . , s , t , .
2. . : 7. / :
t | ||||
s | 23/7 | |||
0/7 | ||||
5/7 |
:
3. . : 5. / :
t | ||||
s | 18/5 | |||
0/5 |
:
4. . : 5. / :
t | ||||
s | 18/5 | |||
0/5 | ||||
5/5 |
:
5. . .
:
( ). , , ( 0). ( )
:
15+5+7=27=, -.