1(2 3) = (12)3;
1Ú (2 Ú 3) = (1Ú 2) Ú 3.
1 2 = 2 1
1Ú 2 = 2Ú 1
1 (2 Ú 3) = 12Ú 13.
1 Ú(2 × 3) = (1Ú2) × (1Ú3).*
()
x & x = x
x Ú x = x
x & 1 = x; ( )
x Ú 1 = 1;
x & 0 = 0; ( )
x Ú 0 = x;
`0 = 1;
`1 = 0;
()
()
`x x = 0;
()
`x Ú x = 1;
. .
, : , .
, : , .
: , , , .
: , , , .
.
( r = n, .. , ) , :
- r n-r , n- ;
- , : xi v ` xi = 1;
- , r 2n-r .
|
|
().
r n ( ) (6) (14) :
- r n-r ;
- , : xi ` xi = 0;
- (14) , r 2n-r .
16. . ( )
. A ( P2), A.
A={ f1, f1,, fm }, , .
, f1, , (f1, f1,, fm) .
. A = {∨, &, } .
. f , f , , . f ≡ 0, f = x & x. .
. A , A B, B .
. f (x1, , xn) : A = {g1, g2, } B = {h1, h2, }. , A , f :
f (x1, , xn) = ℑ[g1, g2,]
gi= ℜi[h1,h2,]
f
f (x1, , xn)=ℑ[ℜ1,ℜ2,...]
, B. , , B . .
. P2:
1) {V, };
2) {&, };
3) { | };
4) {&, ⊕, 1} .
.
1) ( 3), A = {&, V, } . , B = { V,. , (x& y) = (x ∨ y) , x & y = (x ∨ y), , A B. B .
2) 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) 2 2.
3) x | y=(x&y), x | x = x; x & y = (x | y) = (x | y) | (x | y) 2 .
4) x = x ⊕1 2 .
.
17. .
, S4={⊕,&,1} .
.
1.
|
|
h1⊕h2=h2⊕h1 h1&h2=h2&h1
2.
h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3
3.
h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)
4.
h&1=h h&0=0
h⊕0=h
5. h⊕h=0 h&h=h
. :
x=1⊕x
xvy=x⊕y⊕xy
x∼y=1⊕x⊕y
x→y=1⊕x⊕xy
x↓y=1⊕x⊕y⊕xy
x|y=1⊕xy
18. . . .
. ( 2) n x1,x2... xn :
c0⊕c1x1⊕c2x2⊕... ⊕cnxn⊕c12x1x2⊕... ⊕c12... nx1x2... xn,
Ck 0 1.
, ( ).
, f=x⊕yz⊕xyz f1=1⊕x⊕y⊕z - , .
. .
.
1. . P(x1,x2... xn) - , f(x1,x2... xn).
P=c0⊕c1x1⊕c2x2⊕... ⊕cnxn⊕c12x1x2⊕... ⊕c12... nx1x2... xn
Ck. x1,x2... xn . 2n 2n , . , P(X1,X2... Xn).
2. , {,&}. F {,&}, f(X1,X2... Xn). A A⊕1, , (. 3), 4 5.
. f(X,Y)=X→Y
.
1. ( ). :
P=c0⊕c1x⊕c2y⊕c12xy
,
f(0,0)=P(0,0)=C0=1
f(0,1)=P(0,1)=C0⊕C2=1
f(1,0)=P(1,0)=C0⊕C1=0
f(1,1)=P(1,1)=C0⊕C1⊕C2⊕C12=1
, C0=1, C1=1, C2=0, C12=1
: x→y=1⊕X⊕XY.
2. ( .). : x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
, ( ) , . .