Martynyuk_A_N_Diskretnaya_matematika

. % 30.7

x3

x3

x3

x3

x2

x2

x2

x2

x1

x1

x1

x1

x4|

•

•

•

•

•

•

•

•

•

•

x5|

x4|

•

•

x5|

•

•

•

•

•

•

%) „ = {x1, x2, x3}, & – «~0~10», % ( «101»

. % 30.8

x3

x3

x3

x3

x2

x2

x2

x2

x1

x1

x1

x1

x4|

•

•

•

•

•

•

•

•

•

•

x5|

x4|

•

•

x5|

•

•

•

•

•

•

) „ ={x1, x2, x3},

' ", % ( «010»

. % 30.9

x3

x3

x3

x3

x2

x2

x2

x2

x1

x1

x1

x1

x4|

•

•

•

•

•

•

•

•

•

•

x5|

x4|

•

•

x5|

•

•

•

•

•

•

) „ ={x1, x2, x3},

' ", % ( «001»

. % 30.10

x3

x3

x3

x3

x2

x2

x2

x2

x1

x1

x1

x1

x4|

•

•

•

•

•

•

•

•

•

•

x5|

x4|

•

•

x5|

•

•

•

•

•

•

< 4 8 : 5 , A 4 : 5 4 4 8 (8 4 ).

151

30.2.+F$ *+, D

1.2 9 4 m M1 6 : 5 k 6

9 M1 M6.

2. 1 8 : 5 m M1 C k, A 6

5, 4 8 : 5 C.

3. .8 + 5 5 , A 5 m, 6 8 : 5 , : 8 5C , A C 9

M1 (++ 8 9 9 6).

4.’+, A : 8 5 , : 5

5 + 2-z. 1 8 M1, 8 , 5 M6 (+ 5 «×»).

5.D A A : 9 M1, : 5 . 2. = C

: 5 6.

6.- + 5 , 8 8 A 2-z, A 6 8 4 6 C 8 ,

: 5 +: 5 ’+ 2-z. .

8 , A C, 5 , 9

5 6 8 , 5 . B

4 : 8 5 8 2-z. < 9 4 2-z:

a) 4 . . . 6 4 : 5 5

’ , 8 2-z +, 8 9

M1 (8 ) 6 8 , 9 9 M0 (8

9 ) 9 .

b) 4 '. ? -* : 4 8 5 6 ’5 8 + .

M 4 -z : 5 4 2-z 5 . . 4 6,

+ 5 4 4’ 6’:

4’. 2'+, A : 8 5 , : 5

4 -z. 1 9 M1, A 8 , 5 M6 (+ 5 «×»).

6’. - + 5 , 8 8 A -z, A 6 8 4 6 C 8 ,

: 5 +: 5 '+ -z. . 8

, A C, 5 , 9

5 6 8 , 5 . B 4 : 8 5 8 -z.

30.3. * B+ E

. -* 8 5

>2-z, A ' .

D A 6 5 2-z, 9 9 2-z 9 " & 1 ", 9 " '

$ " .
ac b c = ac b c ab;	(a c) (b c) = (a c) (b c) (a b);
ac a=a;	(a c) a=a.

. 8 : 5, A + 5 . <

C : 5 4 5 4 + 9, 4

: 5 4.

152

2, ac b c = (ac abc) (b c ab c) = ac b c ab(c c) = ac b c ab. 16

9 5 8 9 5 8 5- 8 œ , ’+

6.

? 9 5 4 5 4 + + 5 , 5

' ’+, 5 4 + 5 9 5 4 ( 9 9 :). * 9 , A 5

2-z 5 2-z 6 9 6 4 5 6

+ 5 4 a ab = a. . 5 9 :

1. ’+ 5 xj, ’+ b – : 9 xj (8 ). ? ab=0 5 4 5 4 + 6 5

. ? , : 5 , 6 4 5

xj xj.

2.’+ 5 , 6 5 ’+ + b (8 ), 8 b

=. ? axi b xi = axi ac xi = axi ac xi ac = axi ac = axi b, 8 6 2-z 4 : 5 , 5 4 5 4 +.

4 &. E ( " P & , 8 & & 0E-

y= x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3.

4 ' $ % & '

y= x1 x2 x1 x3 x2x3 x1x3.

4 ( & '

y= x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x1 x3 x2x3 x1x3 =x1 x2 x1 x3 x2x3 x1x3.

+, 0E- &$
y= x1 x2 x1 x3 x2x3 x1x3.
4 &	&	%, 8 &$'
$, " &:
_a= 000	_b=	000	_ =
001		001
010		010
101		101
111		111
(E % ` )		00×	00×
		0× 0	0× 0
		× 01	× 01
		1× 1	1× 1
. _a – ( & 0E-, _b – ( & 0E- $ %, '
'			$ ,

_ – & P, 8 & ' % {00× , 0× 0, × 01, 1× 1},

' . ž" & & 0E-

y= x1 x2 x1 x3 x2x3 x1x3.

4 &. E ( " P & &$ 0E- y=x2 x3 x4 x1x2 x3 x1 x2x4 x1x2x4 x1 x2x3x4.

) ' $ & (x2 x3 x4, x1x2x4), (x1x2 x3,

x1 x2x4), (x1x2, x3 x1x2x4), (x1 x2x4, x1 x2x3x4) % , 8 & ( ( (

&% ' , &

y=(x2 x3 x4 x1x2x4 x1x2 x3) (x1x2 x3 x1 x2x4 x1 x3x4)(x1x2 x3 x1x2x4 x2 x3x4) (x1 x2x4 x2x3x4) ( x1x2x4 x1x3x4).

153

> & & ( a a=a " ( ( & &

y=(x2 x3 x4 x1x2x4 x1x2 x3 x1 x2x4) ( x1x2 x3 x1 x3x4 x2 x3x4 x2x3x4 x1x3x4).

4 & '` ' $ & ' ,

0E-. .

(x2 x3 x4, x1 x3x4), (x2 x3 x4, x2 x3x4), ( x1x2x4, x1 x3x4), ( x1x2x4, x2x3x4), (x1x2 x3, x1x2 x3), (x1 x2x4, x2 x3x4), (x1 x2x4, x1x3x4), ( x1x2 x3, x1 x3x4), ( x1x2 x3, x1x3x4), (x1 x3x4, x2x3x4),

(x2 x3x4, x1x3x4).

) & ’$" ' $ "

& & & & ( & " : y= x1x2x4 x1 x2x4 x1 x3x4 x2x3x4 x1x3x4 x2 x3.

Ÿ& " " x2 x3 ` ( & ' &

( , P $ 0E-.

4 & & & P % " &:

_a= × 100	_b=	× 100	_ = × 100
110×		110×	110×
10× 1		10× 1	10× 1
01× 1		01× 1	01× 1
0011
(E % ` )		1× 01	1× 01
		× 101	× 101
		× 011	× 011
		0× 11	0× 11
		010×	010×

(E % & )

× 10×

3 & _ $ .

2 + 4, 9 3 9

-z.

4 &. E ( " P & , 8 & & _E- (

$ 1 ")

y= (x1 x2) ( x1 x2 x3).

4 ' $ % & " , 8 &

y= (x1 x2) ( x1 x2 x3) (x2 x3).

4 % & "

y= (x1 x2) (x2 x3).

4 & & & P % " &:

_a= 00×	_b= 00×	_ = 00×
100	100
(E % ` )
	× 00	× 00

_ _ , 8 & ' & ( % {00× , × 00}, $ .

154

+H . % ,

1.S & ` " % & ' (

&& ?

2.S & & " % & ' ( & & ?

3.S & " % & ' (

&& ?

4.S $ % & ' ( & 0E-?

5.S %( & & % & ' ( &

_E-?

6.S $' & 1 "?

7.3 & 1 " _"-A_ ?

8.> ( & 1 "?

9.S %( & & & 1 " & _E-?

% +

+

1.) " 9.0. " & b( (, – A.: E, 1991. – N.123-

130.

2.N " >.4. A " . – _.: .(, 1975. -

N.555.

0 &

3.E >.d., N 9.>. 4 & & -

(. 0 & ( (. – _.: 3 %-

& " % b ` %, 1992. - N.146-183. 0 ( '

4.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.38-40.

155

? 31. : ? B " D

" %

& % & % ( P ".

, ’$ ,

%( & ' ' . E & " & 1-4 ', 8

'$ & _"-A_ " " & 8 $ P$. ) % & " ` &.

3 & & :

31.1.+

31.2.> % ( P " & _N

31.3. ." & 1-4 ' % ( P " 31.4. r " & 8 0E- $ P$

31.1. .-,

( 8 5C + 5 8 , 4 f1(x1,x2,…,xn)

f2(x1,x2,…,xn)

…

fm(x1,x2,…,xn)

( 8 6 31.1, 31.2, 31.3 8 6 .

				. % 31.1
			x2	x2
		x1	x1
x3|		•
		•	•
x4| x3|		•	•	•
x4|	•	•	•	•

D A 9 + , C 8 6 :

f1 = x1 x2 x3 x1x2

f2 = x2 x3 x1 x2 x1x2x3

f3 = x1 x2x3

> 5 2-z +: 5 ’+ 8 15

. * 9 C , 8 6 4, A

5 : , 5 +: 5 6 ’+, A 5 10 .

f1 = x1 x2 x3 x1x2

f2 = x1 x2 x1 x2 x3 x1x2x3

f3 = x1 x2 x1x2x3 x1x2

>. E " `$ 0E- % ( P " '

0E-, 8 ' " ` ( ’$", 8 ' 0E-. >. A '$ 0E- % ( P " '

0E-, 8 ' " ` , 8 ' ’$ 0E-).

9 ’+ 6 6 6 : 5 , 2-z 6

’+ 6 5. * 9 2-z, 9 ’+,

: 5 . > 2-z 9 ’+

.

156

2 C 2-z 6 5

x1 x2 x3 /f1, x1x2 /f1, x1 x2 /f2, x2 x3 /f2, x1x2x3 /f2, x1 /f3, x2x3 /f3.

2 4 2-z 6 5

x1 x2 x3 /f1f2, x1x2 /f1f3, x1x2x3 /f2f3, x1 x2 /f2f3.

>. 4$ $ % ( P " '

’$ , ’$ $ % % '` ,

' & ’$ ( % & " P .

2 4 4 8 6 :

6 C ’+ . = : A

6 - x2 x3 /f2, x1 /f3, x2x3 /f3. ? 8, : x1x2 /f1f3, x1 /f3. ( C 6 8 5C , 4 C ’+, 8 8 5C 8 .

32.2. " , $ G + ( / C E *+, .

8 + 5 6 8 : 5 6 6, 4 8 6

+ 5 8 . > 5 6 4

+ 6 : 8 . -C

8 ( 5 ) - 8 {= (AND), M3 (OR), -= (NOT)}, 8 A : , . 31.1.

0 31.1. T 8 8

( 8 8 C 4 + 5 6,

. 31.2 . 31.3.

. 6 + : 4 5 8 6

9 : 5 5 6 5 C 5 2-z

8 6 .

0 31.2. >6 C

157

0 31.3. >6 4

31.3 -E $* $ $. C $ G + ( / C E B-+, H F

* : 4 5 -* 6

’+ .

. 8 6 ++ 5 8, A + 5

+ 6 + 5 9 , 5 + : 5

.
0	1	0	f1f3	0	1	0	f2f3
1	1	0	f1f2	1	1	0	f1f4
~	1	0	f1		- ++ 5

9 8, A ++ 5, : 5 5 , 5

+ 5 4 8 . z +

- C : 5 9 *1 8 6 , + 9

6 5 8, 6 6 8 8 +: . 9 8

: 5 - 9 , A ++ 5 5 8.

- 4 9 *1 8 : 5 *1i, 0,i,n.

- 5 + 5 + 8 6 *1i *1i+1

6 8 + 8 8 6 . ( 5

: 5 9 *1i’ 5 + 5, 0,i,n-1.

- 8 9 *1 '+ 5

5 8 8 6 .

3, 4 + 5 8 9 *1i’.

- ' 8 : 5 8 , + 5

5 8, – 9 *1, , 9

+: 5 5 , 5 8 6 + 5 4 , 9 4 8 6 5 5 6 4 , 9 4 .

- C C : 5 8 : 5 2-z. .

6 2-z 6 + 5 .
8 8 (8. 31.2) 4 + 5:										K3:=
0: 61 62 63			f2f3	K1:		x1 x2 x3		K2:	x1 x2 x3
0	0	0		~ 0 0			f2	0 ~ ~ f3
1	0	0	f1f2	0	~ 0		f3
0	1	0	f1f3	0	0	~ f2f3
0	0	1	f2f3	0	1	~ f1f3

158

0 1 1		f1f3			0 ~ 1 f3
1 1 1		f2f3			~ 1 1 f3.								. % 31.2
	000		000	100	100	010		010	001	001	011	011	111	111
	f2		f3	f1	f2	f1		f3	f2	f3	f1	f3	f2	f3
100 f1f2				1	1
111 f2f3													1	1
~00 f2	1				1
00~ f2f3	1		1						1	1
01~ f1f3						1		1			1	1
~11 f3												1		1
0~~ f3			1					1		1		1

> 5 6 , 8 6 , : 4 2-z,

C.

x1 x2 x3 /f1f2, x1x2x3 /f2f3, x1 x2 /f2f3, x1x2 /f1f3.

* 9 4 5 3-. 5 4 + 6

8 6 4 4 5 + -*.

31.4. E $* % S , $ D . $ -' /$'

* 3-. 5 4 4 8 6 . Ÿ + 5 8 6 5 6

< 5 4, 9 6 5 4 ’

.

-: 86 + 5 4 ’ , 5

5 6 , A 6 5 5 6 . ( 8 4 5 6 6 86 4 5 6 6

C . 5 5 + 5

5 .

-9 ( 8. 31.3, 31.3, 31.4 31.5, 31.6, 31.7,

9 6 ) , A 8 + 5 9

5 4 ’ 8 6 .

. % 31.3

x2 x2

x1

x1

x3|

• I

• II

•

. % 31.4

x2

x2

x1

x1

x3|

• IV

• I

•

• III

. % 31.5

x2

x2

x1

x1

x3|

• IV

• II

•

• III

•

159

x1 x2 x3 /f1f2, x1x2x3 /f2f3, x1 x2 /f2f3, x1x2 /f1f3

				. % 31.6
					x2	x2
			x1		x1
	x3|		•		•
		•	•		•	•
x4|	x3|				•
x4|		•
						. % 31.7
					x2	x2
			x1		x1
	x3|		•		•
					•
x4|	x3|	•	•		•
x4|		•

x1 x3 x4 /f1f2, x1x2x3 /f1f2, x1 x2 x3x4 /f1f2, x3 x4 /f1, x2x3x4 / f1 = x1 x3 x4 x1x2x3 x1 x2 x3x4 x3 x4

f2 = x1 x3 x4 x1x2x3 x1 x2 x3x4 x2x3x4.

+H . % ,

1.Y ' " `$ " '$ 0E- % ( P "?

2.Y $' '$" % ( P "?

3.Y ' $ $ % ( P "?

4.S % ( P " & _N?

5.S $$' % & % ( P "?

6.S P & 1-4 '?

7.S " & 8 0E- $

P$?

% +

+

1.E >.d., N 9.>. 4 & & -

(. 0 & ( (. – _.: 3 %-

& " % b ` %, 1992. - N.176-180. 0 ( '

2.A & & & ' ( % & «+ & » & & P P ( 6.0804, 6.0915 / +.A. A$ . – +&: +E43, 2001. – N.45-50.

160