001 P1=a
011 P3=a+b
100 P4=c
110 P6=c+d
111 P7=b+d
, :
= ( + b) ( + d)(b + d)
, , :
= ( + b) c (c + d)(b + d) = ac (b + d) = acb + acd
acb { 0x1, 1x0, x11 }
acd { 0x1, 1x0, 11x }
f 1 = 1M2 + M1 3 + M2M3
f 2 = 1M2 + M1 3 + M1M2
.
:
Kj | F |
, .
0100 010x
0011 x100
0101 0x11
1001 x011
1100 01x1
0111 x101
1011 10x1
1101 1x01
110x
, : 10 10
x10x | A | ||||||||
0x11 | B | ||||||||
x011 | C | ||||||||
01x1 | D | ||||||||
10x1 | E | ||||||||
1x01 | F |
f 1 = M2 3 + 1M3M4 + M1 2M4
f 2 = M2 3 + 1M3M4 + 2M3 4 + M1 3M4
f 3 = M2 3 + 2M3M4 + 12 4 + M1 2M4
f 4 = M2 3 + 2M3M4 + 12 4 + M1 3M4
. :
S1 = 8, S2 = 11, S3 = 11, S4 = 11
f1
P = a(b+c)(a+d)(e+f)a(b+d)(c+e)(a+f) = a(b+c)(e+f)(b+d)(c+e) = a(b+cd)(e+cf) =
(ab+acd)(e+cf) = abe + abcf + acde + acdf
, , .
f (mi) Î Mi; mi Î M.
, . , , S . . . :
< , S >
.
1. = < , f0 >, f0 - , . f: a, b , c = ab -
:
- (,b Î ,
[(ab) Î M]
;
- (ab)c = a(bc) -
- (ax) = b, ya = c -
, :
ab = ba
|
|
.
N -
R -
Z -
:
= < N, +, *, - >
= < N < +, *, > -
.
. .
3- 1, 2,3.
.
x1 | x2 | x3 | |
x1 | x3 | x2 | |
x3 | x2 | x1 | |
x2 | x1 | x3 | |
x2 | x3 | x1 | |
x3 | x1 | x2 |
a = x1 x2 x3 b = x1 x2 x3 c = x1 x2 x3
x1 x2 x3 x1 x3 x2 x2 x1 x3
d = x1 x2 x3 e = x1 x2 x3 c = x1 x2 x3
x2 x3 x1 x3 x1 x2 x3 x2 x1
b ,
1 1
2 3
3 2
, :
bc = x1 x2 x3 x1 x2 x3 = x1 x2 x3 = d
x1 x3 x2 x2 x1 x3 x2 x3 x1
:
a | b | c | d | e | f | |
a | a | b | c | d | e | f |
b | c | a | d | c | f | e |
c | c | e | a | f | b | d |
d | d | f | b | e | a | c |
e | e | c | f | a | d | b |
f | f | d | e | b | c | a |
:
(bd)f = cf =d
b(df) = bc =d
, .
, ., , .
.
= < , *, + >
, < , + > , .
. . < , * > 1, .
. . . , . , .
:
1. . . .
2. :
= < , 0 , + >, {0,1,2,3,4,5} 0 , + 6.
.
= + mod 6
+ | ||||||
= mod 6
* | ||||||
|
|
, . 1.
3. = < , 0, + > {0,1,2,3,4,5,6} c = a + b mod 7
+ | |||||||
* | |||||||
.
= (-)
:
- | |
.
1-1=1; 2-1=4; 3-1=5; 4-1=2; 5-1=3; 6-1=6;
.
.
. :
X1+3x2+6x3=2
4x1+5x2+2x3=1
2x2+x3=5
:
1 3 6
= 4 5 2 mod 7 = (5+48412) mod 7=37 mod 7 = 2
0 2 1
2 3 6
1 = 1 5 2 mod 7 = (109) mod 7=(140-109) mod 7 = 31 mod 7 = 3
0 2 1
2 = 103 mod 7 = 5 3 = (27-21) mod 7 = 0
x1=3*2-1=3*4=5
x2=5*2-1=5*4=6
x1=0*2-1=0*4=Æ
5+3*6+6*Æ=5+4+Æ=2+Æ=2
4*5+5*6=6+2=1
2*6=5
.
j .
fi(x1,xn) =xk Þ j (fi)[j (x1),j (xn)] = j (xk)
j -.
, , .
:
A = < M, +, *, - > :
" i Î M
1. xi + xj = xj + xi
2. xi * xj = xj * xi
3. (xi + xj) + xk = xi + (xj +xk)
4. (xi * xj) * xk = xi * (xj *xk)
5. (xi + xj) * xk = xi *xk+ xj*xk
6. xi + xj * xk = (xi + xj)(xi+xk)
7. xi+xj Î M, xi xj Î M
8. x E = x; xÆ = Æ; x + E = E; x + Æ = x;
9. x * = E; x * = Æ;
= {Ij, E, Æ}
Ij ;
E ;
Æ - ;
+, *, - . .
.
, 0 1. . , -, .
- , - .
. :
1 2 ~ x1 + x2
:
x1&x2
0 0 = 0 0 & 0 = 0
0 1 = 1 0 & 1 = 0
|
|
1 0 = 1 1 & 0 = 0
1 1 = 1 1 & 1 = 1
:
1.
1(2 3)=12 13
:
x1 | x2 | x3 | 1(2 3) | 12 13 |
1- . 2- .
(1 2) (1 3) = x1 (x2 & x3)
x1 | x2 | x3 | (1 2) (1 3) | x1 (x2 & x3) |
2. .
.
1& 2 = 1 2
x1 | x2 | 1& 2 | 1 2 |
.
1 2 = 1& 2
x1 | x2 | 1 2 | 1& 2 |
.
.
1.
2. &
3. Å
4.
.
( ).
.
1. Ż -
0 1
1 0
2. 1 2 Ȼ
1 2 | 1 2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
3. 1& 2 Ȼ
1 2 | 1& 2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
4. 1 2 λ
1 2 | 1 2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
5. 1 ~ 2
1 2 | 1 ~ 2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
.
:
x1 | x2 | x3 | f |
. . . . () - , , = 1.
, , n . :
1) , .
2) , . xi 1, , . i 0, .
|
|
3) .
f(1,2, 3) = 1 2 3 1 x2 3 1 2 x3 x1 2 3 x1 2 x3
x1 x2 3
-
, , . , n- .
:
1) , .
2) , . i , , i 1, .
f(1,2, 3) = (x1 x2 3) & ( 1 2 3)
:
, . - - - , 1 0 ,
() f(1,2,3) = m0 m2 m3 m4 m5 m6
() f(1,2,3) = m1 & m7
:
f(1,,k) = f(d1,,dk) & x1d1* x2d2 xkdk
:
x1 | x2 | x3 | f |
f(1,2, 3) = 1 2 3 1 x2 3 1x2 x3 x1 x2 x3 ()
-.
, m=2 , , V=2m=22^k
:
- - .
:
:
j (i)=xi -
j (fi)=yi -
:
fj(Mi) = Mvdv ;
yj(xi) = xvdv ;
.
:
0 0 0
0 1 0 00
0 1 1 11
1 1 1
:
00 | ||||
11 |
Y(x1, x2, x3) = 1 3 x2x3
:
1 23 | ||||
f(x1, x2, x3) = 1 3 x2x3
.
1- .:
x | y1 | y2 | y3 | y4 |
y1 ;
y2 ;
y3 . ;
y4 - 1.
.
1 | 2 | F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 | F9 | F10 | F11 | F12 | F13 | F14 | F15 |
:
F1(x1, x2) = x1 * x2 -
F6(x1, x2) = x1 Å x2 - . 2
F7(x1, x2) = x1 x2 -
:
F0 | - 0 | Æ |
F1 | . . 12 | |
F2 | 2 | 1 2 |
F3 | - 1 | 1 |
F4 | 1 | 12 |
F5 | - 2 | 2 |
F6 | mod 2 | 1Å2 |
F7 | . . 1 2 | |
F8 | 1 ¯ 2 | |
F9 | - | 1 ~2 |
F10 | 2 | 2 |
F11 | 2 | 2x1 |
F12 | 1 | 1 |
F13 | 1 | x1 2 |
F14 | . | 1 2 |
F15 | - 1 |
|
|
- , .
- .
- , .
- , :
= < M, , &, - >
.
1 = < M, , - >, 2 = < M, &, - >
- .
, , , , . 2, . . , , .
F1 = 1*2 |
F2 = 1* 2 |
F4 = 1*2 |
F6 = 1Å2 = 1*2 1* 2 |
F7 = 1 2 |
F8 = 1* 2 = 1 2 |
F9 = 1 2 12 = 1Å2 |
F10 = 2 |
F11 = 1 2 1 2 12 = x1 2 |
F12 = 1 |
F13 = 1 2 12 12 = 1 2
F14 = 1 2 12 1 2 = 1 2 = 1 2
.
.
F1 = x1x2 F2 = x1 2 F4 = 1x2
x1 x1 x1
x2 & y1 x2 & y2 x2 & y4
F6 = 1Å2 F7 = 1 2 F8 = 1 2
x1 x1 x1
x2 y6 x2 1 y7 x2 1 y8
F9 = 1Å2 F10 = 2 F11 = x1 2
x1 x1 x1
x2 y9 x2 1 y10 x2 1 y11
F12 = 1 F13 = 1 2 F14 = 1 2
x1 x1 x1
x2 1 y12 x2 1 y13 x2 & y14
.
f(1,2,3) = 123 12 1 2 1 2 3
02 07
x1 00 1
x2 01 & 03 04 12
04 05 09 1
x3 02 & 06 & 08 09 1 14 f
00 1 07 &
05 10 10
01 01 & 11 1
1 00
& 11
06
f(1,2,3):
f(1,2,3) = 1 23 & 13
x1 00 04
x2 01 & 03 04 1 06
x3 02 & 04
& 08 1 f 09
05 07
& 05 05 1
f(1,2,3) = 1