ДМ Практикум

1		0	0	1	0	0	1	0
	0	1	0	0	1	0	0	1
	0 0 1 0 0 1 0 0
2.16 а) 1		0	0	1	0	0	1	0		; в) M = {3;6} {1;4;7} {2;5;8} .
0		1	0	0	1	0	0	1
	0	0	1	0	0	1	0	0
	1 0 0 1 0 0 1 0
	0 1 0 0 1 0 0 1

2.18 а) является; б) является; в) не является; г) является функцией.

2.19 а) не является; б) не является; в) является; г) является; д) не является.

2.20 б).

2.21 г).

2.22 в)..

2.23 а).

2.24 в).

2.25 б).

2.26 в).

2.27 а).

2.28 б).

2.29 а).

2.30 г).

Глава III. Формулы алгебры логики

3.1а) является; б) является; в) является; г) не является; д) не является;

е) является; ж) является; з) является.

3.2а) может быть истинным или ложным; в) истинное;

е) может быть истинным или ложным; ж) ложное; з) истинное.

3.3а) ложно; б) истинно; в) ложно; г) истинно; д) ложно; е) истинно; ж) ложно;

з) истинно; к) истинно.

3.8а) (10)T ; б) (1001)T ; в) (10101011)T ; г) (1110110011101100)T .

3.9Истинно.

3.10Второй.

3.11Все студенты сдали экзамен.

3.12Возможны два варианта: «мат.анализ, дискретная математика, физика» и «физика, мат.анализ, дискретная математика».

3.13а) тождественно ложное; б) выполнимое; в) тождественно ложное;

г) тождественно истинное; д) выполнимое.

3.14в).

121

3.15	в).
3.16	г).
3.17	а).
3.18	б).
3.19	в).
3.20	б).
Глава IV. Функции алгебры логики
4.2	а) не зависит существенно от переменных;		б)	существенно зависит
	только от x; в) существенно зависит только от y;			г) существенно за-
	висит и от x и от y;	д) существенно зависит и от x и от y.

4.3а) СДНФ; б) ДНФ; в) СКНФ; г) ДНФ, СКНФ; д) КНФ.

4.4

f * = 0 ,

f * = 1,

f * = x ,

f * =

, f * = x y ,

f *

= xy .

x

1

2

3

4

5

6

4.5

f1

= x Å1,

f2 = xy ,

f3 = xy Å x Å y ,

f4 = x Å y ,

f5 = x Å y Å1,

f6

= xy Å x Å1.

4.8

а) f (010) = 1,

f (110) = 0,

f (111) = 0 ;

б)

f (010) = 1,

f (110) = 1,

f (111) = 1;

в)

f (010) = 0,

f (110) = 0,

f (111) = 1.

4.9Ответ представлен в виде столбца, соответствующего исходной функции:

а) (1101)T ; б) (1111)T ; в) (11110011)T ; г) (00010001)T ; д) f (x, y, z,t) ≡ 1;

е) (1111000110011110)T .

4.10 f1 =

z Ú xy

Ú xyz Ú xyz = (x Ú y Ú z)(x Ú

Ú z)(x Ú

Ú

)(

Ú

Ú z) ,

x

y

z

y

y

z

x

y

f2

=

yz Ú xy

Ú xyz = (x Ú y Ú z)(x Ú y Ú

)(x Ú

Ú z)(

Ú

Ú z)(

Ú

Ú

) ,

x

z

z

y

x

y

x

y

z

f3

= x yz Ú

z Ú

xyz Ú xy

= (x Ú

Ú z)(

Ú y Ú

)(

Ú

Ú z)(

Ú

Ú

x

y

z

y

x

z

x

y

x

y

z

) ,

f4

=

z Ú

xyz Ú xyz = (x Ú y Ú z)(x Ú

Ú z)(

Ú y Ú z)(

Ú y Ú

)(

Ú

Ú z) .

x

y

y

x

x

z

x

y

4.11

а)

; б)

z

yz xy

x

z xyz

xyz ;

x

y

x

y

z

x

y

x

yz

x

z

y

в)

xyz

xyz

xyz;

г)

yz

yz xyz ;

д)

xyz

x

yz

x

x

yz

x

xy

z x yz

;

x

y

z

x

yz

е)

Ú

t Ú

Ú

zt Ú

Ú

t Ú

yzt

Ú

yzt Ú x

zt .

t

zt

t

x

y

z

x

y

z

x

y

x

y

x

yz

x

yz

x

x

y

4.12

а) x

; б)( x y

)(

y

) ;

y

z

x

z

в) ( x

)(

y z )(

y

)(

z ) .

y

z

x

x

z

x

y

122

4.13а) x1x2 x3 x1x2 x3 x1x2 x3 ; б) x1x2 x3 x1x2 x3 x1x2 x3 ; в) x1x2 x3 x4 .

4.14а) ( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 );

б)

( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 )( x1 Ú x2 Ú x3 ) ;

в)

(x1 Ú x2 Ú x3 Ú x4 )( x1 Ú x2 Ú x3 Ú x4 )(x1 Ú x2 Ú x3 Ú x4 )(x1 Ú x2 Ú x3 Ú x4 )(x1 Ú x2 Ú x3 Ú x4 ).

4.15а) x; б) x, y, z; в) существенных переменных нет; г) существенных пере- менных нет.

4.16а) xz ; б) x y z xyz ; в) x y z xz ; г) x y xyz .

4.17а) является; б) не является; в) не является; г) является; д) не является.

4.18а) x ×1 = x ; б) x ×( x Ú y ) = xy ; в) xy = (x Ú y) x y .

4.19а) xy Å x Å y Å1 ; б) xyz Å xy Å xz Å yz ; в) xyz Å xz Å1; г) xy Å x Å y .

4.20а) не является; б) не является; в) является; г) не является.

4.26а) не полная; б) не полная; в) полная; г) полная; д) полная; е) полная.

4.27а) f T0 , f T1 ; б) f T1 ; в) f T0 ; г) f T1 .

4.28а).

4.29б).

4.30а).

4.31г).

4.32в).

4.33в).

4.34а).

4.35а).

4.36б).

4.37а).

4.38г).

4.39г).

4.40г).

4.41г).

4.42в).

Глава V. Предикаты

5.7а) ложно; б) ложно; в) истинно; г) ложно; д) истинно; е) ложно.

5.8а) выполнимая; б) тождественно истинная; в) тождественно истинная;

г) тождественно истинная; д) тождественно истинная.

5.9а) x Î(3;+¥) ; б) x Î(-3;+¥); в) x Î(-¥; +¥) ; г) x Î(-¥;-3] È (3;+¥);

123

д) ; е) x (−∞; +∞) .

5.10а) y [−1;1] ; б) y (−∞;−1] [1; +∞) ; в) y (−∞;+∞) ; г) ;

д) y [−2;0] (1;2] ; е) y (4;5] .

5.11а) y [0;3] [5;10) ; б) y (0;21) ; в) y [0;4) ; г) y [6; +∞) .

5.12а) x y z (P(z, y) Q(x, y)); б) x y z (P(x, y) & Q(x) R( y, z));

в) x y z (P(x, z) & Q(x, y) R(z)); г) x z t y (P(x,t) Q(z, y)).

5.13а).

5.14б).

5.15б).

5.16в).

5.17б).

5.18г).

5.19а).

5.20в).

5.21в).

5.22г).

Глава VI. Машины Тьюринга

6.4а) 000q0101; б) 0011q011; в) T не применима к P.

6.5а) 00q0111; б) 00q010 ; в) T неприменима к P; г) T неприменима к P.

6.11а).

6.12а).

6.13в).

6.14г).

Глава VII. Графы

		2	1	1	1	0	0	0	a			1	0	0	0	0	0
		1	0	0	1	1	0	0	b
												1	0	1	1	1	1
		1	0	0	1	0	1	3		c
	7.10 а) A(G ) =											0	0	0	0	0	1
		1	1	1	0	0	0	1	d ,		A(G2 ) =							;
	1	0	1	0	0	0	0	2			0		0	0	1	0	0
									e
												0	0	0	0	0	0
		0	0 1		0 0 0 1					f
													0	0	0	0	0
			0	3	1	2	1	0			0
	0								g

124

		1 1 1 1 0 0 0 0 0 0 0 0 0 0 0
		0 1 0 0 1 1 0 0 0 0 0 0 0 0 0
		0 0 1 0 0 0 1 1 1 1 1 0 0 0 0
б) B(G ) =		0 0 0 1 1 0 1 0 0 0 0 1 0 0 0	,
1
		0 0 0 0 0 1 0 0 0 0 0 0 1 1 0
		0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
		0 0 0 0 0 0 0 0 1 1 1 1 1 1 1

		1 −1		0	0	0	0	0	0
	−1 1 1 1 1 1 0								0
		0	0 −1		0	0	0
								1 0
B(G2)=		0	0	0 −1		0	0		;
								0 ±1
					0 −1 0
		0	0	0				0	0
	0		0	0	0	0 −1 −1 0

в)

deg(a) = 5,deg(b) = 3,deg(c) = 6,deg(d ) = 4,deg(e) = 3,deg( f ) = 2,deg(g) = 7 ,

deg+ (1) = 1,deg+ (2) = 5,deg+ (3) = 1,deg+ (4) = 1,deg+ (5) = 0,deg+ (6) = 0,

deg− (1) = 1,deg− (2) = 1,deg− (3) = 1,deg− (4) = 2,deg− (5) = 1,deg− (6) = 1.

7.13а) {1}, {2}, {3,4,5}, {6} ; б) {1, 2,3, 4,5,6} ; в) {1, 2,3, 4}, {5}, {6};

г) {1,3,5,6}, {2}, {4}; д) {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8} ;

е) {1},{2,3,4,6},{5,7,8}.

						0	0	0	1	0	0	0	0
0 0 0 1		0			0 0 0 0 0 1							0	0
	0 0 0 0	0				0	0	0	0	0	0	0	0
7.14 A(G) =	0 0 0 0	0	.	7.15 A(G) =		1	0	0	0	0	0	0	0	.
	1 0 0 0	0				0	0	0	0	0	0	0	0
						0	1	0	0	0	0	0	0
						0	0	0	0	0	0	0	0
0 0 0 0		0
						0	0	0	0	0	0	0	0

125

										0		1 1 1 1 1 1 1 1 1 1 1 1 1 1
										1 0			1 1 1 1 1 1 1 1 1 1 1 1 1
										1 1 0				1 1 1 1 1 1 1 1 1 1 1 1
		0	0	1 0		0	0				1 1 1 0				1 1 1 1 1 1 1 1 1 1 1
		0	0	1	0	0	0				1 1 1 1 0					1 1 1 1 1 1 1 1 1 1
											1 1 1 1 1 0						1 1 1 1 1 1 1 1 1
	A(G) =	1	0	1	0	0	0
7.16								. 7.17			1	1	1	1	1	1	0 1 1	1 1 1 1 1 1 .
		0	0	0	0	0	0		A(G) =		1	1 1 1 1				1 1 0 1		1 1 1 0 0 0
		0	0	0	0	0
							1				1 1 1 1 1 1 1 1 0							1 1 1 0 0 0
		0	0	0 0							1 1 1 1 1 1 1 1 1 0 1 1 1 1 0
						1 0
											1 1 1 1 1 1 1 1 1 1 0								1 1 1 0
											1 1 1 1 1 1 1 1 1 1 1 0									1 1 0
											1 1 1 1 1 1 1 0 0							1 1 1 0			1 1
											1 1 1 1 1 1 1 0 0							1 1 1 1 0
																						1
										1 1 1 1 1 1 1 0 0 0 0 0										1 1 0

7.18Изоморфными являются пары графов {а), б)} и {д), е)}.

7.19а).

7.20а).

7.21б).

7.22в).

7.23в).

7.24б).

7.25г).

Глава VIII. Некоторые задачи на графах

8.13а) w(T (G1 )) = 8 ; б) w(T (G2 )) = 7 .

8.14а)

d (v1, v2 ) = 1, d (v1 , v3 ) = 3, d (v1, v4 ) = 2, d (v1, v5 ) = 2, d (v1, v6 ) = 1, d (v1, v7 ) = 3, d (v1, v8 ) = 1 ;

б)

d (v1 , v2 ) = 1, d (v1 , v3 ) = 2, d (v1, v4 ) = 3, d (v1, v5 ) = 4, d (v1, v6 ) = 1, d (v1 , v7 ) = 1, d (v1 , v8 ) = 1 .

8.15 а)

d (v2 , v1 ) = 2, d (v2 , v3 ) = 3, d (v2 , v4 ) = 2, d (v2 , v5 ) = 1, d (v2 , v6 ) = 2, d (v2 , v7 ) = 3 ;

б)

d (v2 , v1 ) = 4, d (v2 , v3 ) = 3, d (v2 , v4 ) = 1, d (v2 , v5 ) = 4, d (v2 , v6 ) = 3, d (v2 , v7 ) = 1;

в)

d (v2 , v1 ) = 3, d (v2 , v3 ) = 4, d (v2 , v4 ) = 4, d (v2 , v5 ) = 3, d (v2 , v6 ) = 4, d (v2 , v7 ) = 2 ;

г) d (v2 , v1 ) = 2, d (v2 , v3 ) = 2, d (v2 , v4 ) = 5, d (v2 , v5 ) = 3, d (v2 , v6 ) = 2, d (v2 , v7 ) = 1 .

8.18а).

8.19а).

8.20г).

8.21б).

8.22б).

8.23г).

126

8.24 б).

Глава IX. Конечные детерминированные автоматы Примечание: таблицы и уравнения для к.д.а. задаются неоднозначно!

9.6

а)

б)

в)

г)

д)

е)

9.7

S\X

0

1

2

а)

B1={S1,S5},

B1

B3/1

B1/0

B1/1

B2={S4},

B2

B2/1

B4/0

B1/1

B3={S2, S6},

B4={S3,S7}

B3

B3/0

B3/0

B1/1

B4

B3/1

B3/0

B4/1

б)

S\X

0

1

2

B1={S1, S3}, .

B1

B2/1

B3/0

B1/0

B2={S4},

B2

B2/1

B1/0

B1/0

B3={S2, S5, S6, S7}

B3

B3/0

B3/0

B3/1

y(t) = s(t),

9.8а) s(t +1) = x(t),

s(1) = 0;

y(t) = s1 (t),

s1 (t +1) = s2 (t), б) s2 (t +1) = x(t),

s1 (1) = s2 (1) = 0;

y(t) = s(t) x(t),

в) s(t +1) = s(t),

s(1) = 0;

127

y(t) =

(

×

Ú s2

(t)),

s1 (t)

s2 (t)

s3

(t)

s1 (t +1) = (

× s2 (t) Ú s1 (t) ×

)×

× x(t),

s1 (t)

s2 (t)

s3 (t)

г)

s2 (t +1) =

×(

×

Ú s3 (t) × x(t))Ú

×

(

× s2 (t) Ú s1 (t) ×

),

s1 (t)

s2 (t)

s3 (t)

s3 (t)

s1 (t)

s2 (t)

x(t)

s3 (1) = x(t),

s1 (t) = s2 (t) = s3 (t) = 0;

y(t) =

Ú x(t),

y(t) = s(t) x(t),

s(t)

е) s(t +1) = s(t) Ú x(t),

д) s(t +1) = s(t) Ú

x(t),

s(1) = 0;

s(1) = 0.

9.9 а)

б)

	1	(t) = (x		1	x	2	)s,				s(t)	x	1	t	x	2	t	y	1	t	y	2	t	s(t+1)
y
														( )			( )			( )			( )
											0	0			0			0			1			0
9.12 y	2(t) = (			1	x 2)					,
			x						s
											0	0			1			0			0			0
					1 2			.			0	1			0			0			1			0
s(t + 1) = x x
											0	1			1			1			0			0
											1	0			0			0			0			0
											1	0			1			1			0			0
											1	1			0			0			1			1
											1	1			1			1			0			1

S\X	00	01	10	11
S0	S0/01	S0/00	S0/01	S0/10
S1	S0/00	S0/10	S1/01	S1/10

(00,00) (11,10)

(00,01)

(01,00)

(10,01)

(11,10)

(10,01)

01,10

9.17 а).

128

9.18б).

9.19а).

9.20г).

Глава X. Элементы комбинаторики

10.315.

10.4а) 336; б) 400.

10.560; 36.

10.64960.

10.713800.

10.82187.

10.9а) 120, б) 60, в) 840, г) 420.

10.10210.

10.11Шести студентам.

10.12в).

10.13б).

10.14в).

10.15б).

10.16г).

10.17в).

10.18в).

129

СПИСОК ЛИТЕРАТУРЫ

[1]Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математи-

ке. — М.: Наука, 1977. – 312 с.

[2]Бернштейн Т.В., Макаров Р.Н., Храмова Т.В. Дискретная математика: Учебное пособие. – Новосибирск: СибГУТИ, 2004. – 91 с.

[3]Бернштейн Т.В., Храмова Т.В. Дискретная математика: Сборник задач. – Новосибирск: СибГУТИ, 2004. – 50 с.

[4]Виленкин Н.Я. Комбинаторика. - М.:Наука, 1969. – 328 с.

[5]Ерусалимский Я.М. Дискретная математика, теория, задачи.— М.: Вуз.

кн., 1998. – 279 с.

[6]Карпов Ю. Г. Теория автоматов. – СПб: Питер, 2003. – 208 с.

[7]Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для ин- женеров. — М.: Энергоатомиздат, 1988. – 478 с.

[8]Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математиче- ской логике и теории алгоритмов. — М.: Наука, 1975. – 256 c.

[9]Логинов Б.М. Лекции и упражнения по курсу «Введение в дискретную математику». — Калуга, 1998. – 423 с.

[10]Мальцев И.А. Дискретная математика. – Новосибирск: Изд-во Института математики, 2007. – 228 с.: ил.

[11]Москинова Г.И., Дискретная математика. Математика для менеджера в примерах и упражнениях. — М.: Логос, 2002. – 240 с.

[12]Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учебное по-

собие. — М.: Изд– во МАИ, 1992. – 264 с.

[13]Новиков Ф.А. Дискретная математика для программистов. – СПб: Питер, 2000. – 304 с.

[14]Носов В.И., Бернштейн Т.В., Носкова Н.В., Храмова Т.В.Элементы тео- рии графов: Учебное пособие. - Новосибирск: СибГУТИ, 2008. – 107 с.

[15]Оре О. Теория графов. – М.: Наука, 1968. – 352 с.

[16]Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд– во НГТУ, 2002. – 280 с.

130