NEWsbornik

Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Обнинский институт атомной энергетики НИЯУ МИФИ

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

нечеткие множества:,

Найдите488. ПустьследующиеA = {0.1/x1, 1/x2, 0.8/x5} B = {0.5/x2, 0.3/x3

à) A2 B , á)

· (A + B), â) (A B)2 , ã)o

489à). Докажите, что, если A è B четкие множества, то

A · B = A ∩ B , á) A + B = A B , â) An = A.

.pdf

Скачиваний:

142

Добавлен:

11.06.2015

Размер:

5.12 Mб

Скачать

☆

<<< < Предыдущая 12 / 42 3 4 > Следующая >>>

24)	P (x, y) = (x < 2 y = 0),	25)	P (x, y) = (x 6 1 y = 0),
26)	P (x, y) = (x > 1 y > 0),	27)	P (x, y) = (x > 0 y > 1),
28)	P (x, y) = (x = 0 y 6 1),	29)	P (x, y) = (x 6 1 y = 0).

функции525. Пусть даны машины Тьюринга F , P , Q è R, вычисляющие ния аргументаf(x, y,. Постройтеz), p(x), qмашину(x) è r(xТьюринга) соответственно без сохране-

функции					H для вычисления
y = h(x), заданной формулой					,
	q(r(p(x))), q(x), x	,	1)		,
0) y = f	q(r(p(x))), q(x), x	,		y = f	p(p(x)), q(x), r(x)
		,	3)		,
2) y = f p(x), q(q(x)), r(x)		,		y = f p(x), q(x), r(r(x))
		,	5)		,
4) y = f p(p(x)), q(r(x)), x		,		y = f p(q(x)), q(r(x)), x
		,	7)		,
6) y = f r(p(x)), q(q(x)), x		,		y = f p(p(x)), x, r(q(x))
		,	9)		,
8) y = f q(p(x)), x, r(p(x))		,		y = f q(p(x)), x, r(r(x))
	x, r(p(x)), q(q(x))	,	11)		,
10) y = f	x, r(p(x)), q(q(x))	,		y = f	x, r(q(x)), p(q(x))
	x, p(r(x)), r(q(x))	,	13)		,
12) y = f	x, p(r(x)), r(q(x))			y = f	p(q(x)), x, r(x)
	,		15)		,
14) y = f	q(r(x)), x, p(x)			y = f	x, p(r(x)), q(x)
	,		17)		,
16) y = f	x, r(x), q(p(x))			y = f	r(q(x)), p(x), x
	,	,	19)		,
18) y = f	q(x), r(p(x)), x			y = f	p(q(r(x))), x, r(x)
	q(r(p(x))), q(x), x		21)		,
20) y = f	q(r(p(x))), q(x), x	,		y = f	x, p(r(q(x))), p(x)
	r(x), q(p(r(x))), x	,	23)		,
22) y = f	r(x), q(p(r(x))), x	,		y = f	x, q(x), r(p(q(x)))
	p(x), x, r(q(p(x)))	,	25)		,
24) y = f	p(x), x, r(q(p(x)))	,		y = f	p(q(x)), r(x), p(x)
	q(r(x)), q(x), p(x)	,	27)		,
26) y = f	q(r(x)), q(x), p(x)	,		y = f	r(x), p(x), r(q(x))
	p(x), q(x), r(p(x))	,	29)		.
28) y = f	p(x), q(x), r(p(x))			y = f	p(x), r(q(x)), p(x)

Формальные языки и грамматики

íóþ526.грамматикуДляданного языка L найдите порождающую его регулярмающий язык G и постройте конечный автомат K , восприни-

0)	L, åñëè	1) L = {a2}+ · {bc2} ,
	L = {a2, b2c}+,	1) L = {a2}+ · {bc2} ,
2)	L = {a2} {bc2}+,	3)	L = {ab, bc2} ,
4) L = {a} · {b2c2}+,		5) L = {a}+ {b2c2} ,
6)	L = {abc, b2}+,	7)	L = {(ab)2}+ · {c} ,
8) L = {(ab)2} {c}+,		9) L = {(ab)2, c}+,
		56

234.Вычислите значение P6 − A4 − A5

Сколькими способами 7 человек7 могут(3) . встать в очередь?

235.

236. Сколькими способами можно рассадить 6 гостей за круглым столом? Одинаковыми считаются те способы, которые получаются друг из друга посредством вращения.

237.o Сколькими способами можно раскрасить грани куба в шесть разных цветов, если каждую грань красят только одним цветом, а различные грани в разные цвета?

числа238. Сколько1и 2 расположеныимеется перестановокрядом? чисел 1, 2, . . . , n, в которых

239.Сколько имеется трехзначных чисел, у которых все цифры различны?

240.Сколько размещений из n ïî k содержат данный элемент

a èç n-множества?

241.o Сколько имеется пятизначных чисел, у которых все цифры различны?

242.o Сколько имеется четных пятизначных чисел, у которых все цифры различны?

243. Сколько трехзначных чисел можно написать с помощью цифр 1, 2, 3, 4? Найдите сумму всех этих чисел.

шаров244. Сколькимипо способами можно распределить n различных

kразличным урнам?

245.Сколько имеется подмножеств у n-множества?

o	→и биективныхB , ãäå \|A\| функций?= m, \|B\| = n?
Сколько246. Сколькосреди нихфункцийинъективныхf : A

247. Сколько различных элементарных конъюнкций можно образовать из переменных x1, x2, . . . , xn ?

переменных?248. Сколько имеется линейных булевых функций от n данных

переменных?249. Сколько имеется самодвойственных булевых функций от n


27)	f(x) = f(x −.	1)	+ 5	sg(4 −. x) + 13 sg(4 −. x);
28)	f(x) = f(x −.	1)	+ 9 + 17 sg(8 −. x);
29)	f(x) = f(x −.	1)	+ 3 + 16		sg(8 −. x).

522. Следующие функции, заданные с помощью ограниченного
оператора наименьшего значения, представьте в виде суперпози-
ции основных примитивно рекурсивных функций:
0) f(x) = µt (t > 7x + 1);				1) f(x) = µt (t > 4x + 1);
		t65x+17				t62x+21
2)	f(x) =	µt	(t > 7x + 19);	3)	f(x) =	µt	(t > x + 22);
		t69x+1				t63x+2
4)	f(x) =	µt	(t > 3x + 4);	5)	f(x) =	µt	(t > 5x + 18);
		t6x+20				t67x+2
6)	f(x) =	µt	(t > 2x + 25);	7)	f(x) =	µt	(t > 9x + 3);
		t64x+3				t67x+21
8)	f(x) =	µt	(t > 3x + 18);	9)	f(x) =	µt	(t > 5x + 1);
		t65x+2				t63x+19
10)	f(x) =	µt	(t > 4x + 23);	11)	f(x) =	µt	(t > 6x + 2);
		t66x+1				t64x+22
12)	f(x) =	µt	(t > x + 23);	13)	f(x) =	µt	(t > 4x + 3);
		t64x+1				t6x+20
14)	f(x) =	µt	(t > 2x + 26);	15)	f(x) =	µt	(t > 5x + 1);
		t65x+2				t62x+19
16)	f(x) =	µt	(t > 3x + 29);	17)	f(x) =	µt	(t > 6x + 2);
		t66x+1				t63x+20
18)	f(x) =	µt	(t > 4x + 31);	19)	f(x) =	µt	(t > 7x + 1);
		t67x+3				t64x+21
20)	f(x) =	µt (t > x2 + 1);		21)	f(x) =	µt (t > 5x + 5);
		t65x+8				t6x2
22)	f(x) =	µt (t > x2 + 2);		23)	f(x) =	µt (t > 3x + 9);
		t63x+13				t6x2
24)	f(x) =	µt (t > x2 + 3);		25)	f(x) =	µt (t > 6x + 6);
		t66x+11				t6x2
26)	f(x) =	µt (t > x2 + 1);		27)	f(x) =	µt	(t > 6x + 13);
		t65x+16				t6x2+x
28)	f(x) =	µt (t > x2 + x);		29)	f(x) =	µt	(t > 6x + 16).
		t67x+17				t6x2+1

266.Сколько имеется четырехзначных чисел, у которых цифры слева направо возрастают?

267.Сколько всего получится параллелограммов, если серию из четырех параллельных прямых пересечь серией из пяти параллельных прямых?

268.Сколько четырехзначных чисел можно образовать из цифр числа 1111222345600?

натуральных269. Докажите,чиселчтоделитсяпроизведениебез остаткалюбыхна k последовательных

k!.

270.o Докажите, что Cn0−k + Cn1−k+1 + . . . + Cnk−−11 + Cnk = Cnk+1 . 271.o Докажите, что C2nn четное число.

272.o Докажите, что C2kn четное число при 0 < k < 2n .

Сочетания с повторениями. Формула включений и исключений

273. Докажите, что C(kn) =

n + 1

· . . . ·

n + k − 1

. Найдите

открытки 10 видов. Сколькими способа-

(100) ,В киоске(100) , имеются(10) .

274.

ми можно выбрать 12 открыток?

шаров275. Сколькимипо способами можно распределить k одинаковых n различным урнам?

276.o Сколькими способами можно разместить в ряд p белых и лагалисьq черныхрядом?шаров так, чтобы никакие два черных шара не распо-

натуральных277. Сколькочислах?решений имеет уравнение x1 + x2 + x3 = 10 â

шаров278. Сколькимипо способами можно распределить k одинаковых ков? n различным ящикам так, чтобы не было пустых ящи-

279. Найдите количество слагаемых после приведения подобных членов в разложении многочлена (x1 + x2 + x3 + x4)5 .

G5 LLb

AAb

b	b	b	b		b	b
b	bb	b	b			b
G2 bb	bb		G3b b			b b
b		b		Z	b
b		b			b	Zb
				Z
	bb			b	Z
b		"			Z
b		"			Z
"b						Zb
G6 b	"				Z
G6 b	"		G7 Z
b"

b	XbX b			b
X		X
@		X
@			X
	S
	SSb
	G4b b		b

G8bb

Ðèñ. 12

520. Для указанного графа ( G

цикломатическое и хроматическоеi изображенычисло, а такжена рисвыясните.13) найдитеего

планарность. Если граф планарный, то надо привести его реализацию на плоскости. Если граф не планарный, то укажите в нем

подграф, стягиваемый к K

èëè ê K

3,3 .

K3 + K1,2 , 1) O2 + G1 ,

2) K2 + G1 ,

3) O2 + G8 ,

K2 + G8 ,

5) O2 + G2 ,

K2 + G2 ,

7) O2 + G9 ,

12)

K2 + G9 ,

9) O2 + G3 ,

10) K2 + G3 ,

11) O2 + G10 ,

16)

K2 + G10 ,

13) O2

+ G4 ,

14)

K2 + G4 ,

15) O2 + G11 ,

20)

K2 + G11 ,

17) O2

+ G5 ,

18)

K2 + G5 ,

19) O2 + G12 ,

24)

K2 + G12 ,

21) O2

+ G6 ,

22)

K2 + G6 ,

23) O2 + G13 ,

28)

K2 + G13 ,

25) O2

+ G7 ,

26)

K2 + G7 ,

27) O2 + G14 ,

+ G14 ,

29)

+ K1,2 .

b G1

b G2

b G3

Gb4

Gb6

Gb7

b#c b

#c b

# c

b b

Ðèñ11. 13

294.o

Найдите

E(t)

для последовательности

∞

à)

(uk)k=0 , åñëè

uk = k,

á) uk = k2 .

Найдите следующие суммы (295 300).

295. Cn

Cn + . . . +

Cn .

n + 1

296.o

Cn0 − Cn1 + Cn2 + . . . + (−1)nCnn .

297.o

Cn1 + 2Cn2 + 3Cn3 + . . . + nCnn .

∞

298.

P(2k + 3)C(kn)tk .

k=0

∞

299.

k=1

(k + 2)k! .

∞

300.

X tk

k=4

k − 3 .

Докажите, что

301.o

X(−1)kkmCnk = 0 ïðè m = 0, 1, . . . , n − 1.

k=0

302. Используя тождество (1+t)m(1+t)n = (1+t)m+n докажите, ÷òî k

P Cmi Cnk−i = Cmk +n ïðè 0 6 k 6 min(m, n).
i=0
303.o Докажите следующие тождества:
à) n		p
P(Cni )2 = C2nn ,	á)	P Cnk+iCpi = Cnk++pp	ïðè n > p + k.
i=0		i=0

ления304. Докажите,числа что количеством K(N, n, m) способов представесть одно из чиселN в виде суммы n слагаемых, каждое из которых 0, 1, 2, . . . , m − 1, является коэффициент при

xN в формуле		(m−1)n
(1 + x + x2 + . . . + xm−1)n =		(m−1)n
(1 + x + x2 + . . . + xm−1)n =		P K(N, n, m)xN .
		N=0
	[N/m]
Убедитесь, что K(N, n, m) =	P (−1)kCnkC(Nn−) km		и найдите по

этой формуле количество "счастливых"k=0 билетов с шестизначными номерами.


21)	a0 = 5		, an+1 = 4an − 6(−2)n ;
22)	a1 = 1		, a2 = 7		, an+1		= −2 + 3an−1 ;
23)	a0 = 0		, an+1 = 4an + 5(−1)n ;
24)	a0 = 0		, a1 = −1			, an+2		= 2(−1)n − 2an+1 − an ;
25)	a0 = 5		, a1 = −1			, an+2		= 2an+1 + 8an − 9;
26)	a0	= 5	, a1	= 0	, an+2		= an+1 + 12an − 24;
27)	a0	= 2	, a1	= −2		, an+2		= 4an+1 + 5an + 24;
28)	a0	= 6	, a1	= 16, an+2 = 6an+1 − 8an − 6;
29)	a0	= 2	, a1	= 6	,	an+2	= 6an+1 − 9an + 12.

Теория графов

жество518. Найдитевершинматрицу смежности для графа G(X, ), åñëè ìíî-

X= {x1, x2, x3, x4}, а набор ребер указан ниже:

0)= ((x1, x2)?3, (x1, x3), (x1, x4)?2, (x2, x3)?2, (x3, x4), (x3, x3));

1)= ((x1, x2)?2, (x1, x3), (x1, x4)?3, (x2, x3), (x3, x4)?2, (x1, x1));

2)= ((x1, x2), (x1, x3), (x1, x4)?2, (x2, x3)?2, (x3, x4)?3, (x4, x4));

3)= ((x1, x2)?2, (x1, x3), (x1, x4), (x2, x3)?3, (x3, x4)?2, (x4, x4));

4)= ((x1, x2)?3, (x1, x3), (x1, x4)?2, (x2, x3), (x3, x4)?2, (x3, x3));

5)= ((x1, x2), (x1, x4)?3, (x2, x4), (x2, x3)?2, (x3, x4)?2, (x1, x1));

6)= ((x1, x2)?2, (x1, x4)?2, (x2, x3), (x2, x4), (x3, x4)?3, (x4, x4));

7)= ((x1, x2), (x1, x3), (x1, x4)?2, (x2, x3)?3, (x3, x4)?2, (x4, x4));

8)= ((x1, x2)?3, (x1, x4)?2, (x2, x3), (x2, x4)?2, (x3, x4), (x3, x3));

9)= ((x1, x2), (x1, x3)?2, (x1, x4)?3, (x2, x3), (x3, x4)?2, (x3, x3));

10)= ((x1, x2), (x1, x4), (x2, x3)?2, (x2, x4)?2, (x3, x4)?3, (x3, x3));

11)= ((x1, x2), (x1, x4), (x2, x3)?3, (x2, x4)?2, (x3, x4)?2, (x4, x4));

12)= ((x1, x2)?3, (x1, x4)?2, (x2, x3), (x2, x4), (x3, x4)?2, (x3, x3));

13)= ((x1, x2)?2, (x1, x4)?3, (x2, x3)?2, (x2, x4), (x3, x4), (x4, x4));

14)= ((x1, x2)?2, (x1, x4), (x2, x3)?2, (x2, x4), (x3, x4)?3, (x3, x3));

15)= ((x1, x2), (x1, x4)?2, (x2, x3)?3, (x2, x4), (x3, x4)?2, (x4, x4));

318. Постройте простой граф с вершинами x , x		2	, x	3	, x
÷òî	1				4 такой,

deg x1 = deg x2 = 2, deg x3 = deg x4 = 3.

319.o Докажите, что, если у простого графа не менее двух вершин, то у него найдутся две вершины одинаковой степени.

320.Сколько ребер имеет полный граф Kn ?

321.Найдите количество ребер графа On + Km,n .

322.o

+ Kn

Докажите, что Km

= Km+n

@ a

a a

a 1

a a

a 2

Ðèñ. 6

Ðèñ. 7

323. Для графа G

1 , (см. рис. 6), найдите его дополнительный

ãðàô.

324. Сколькими способами можно граф G

1 , (ñì. ðèñ. 6), èçî-

морфно отобразить на граф

G2 ?

325. Приведите пример графа G изоморфного графу

326. Докажите, что графы G

è G

2 , изображенные на рис. 7, не

изоморфны между собой.

o '

ó327ýòèõ. Известно,графовравночто G G. Докажите, что количество вершин

4k èëè 4k + 1.

328.Выясните планарность графа O3 + K2,2 .

329.При каких m, n ãðàô Km,n является планарным?

330.o При каких n ãðàô Kn является планарным?

331. Реализуйте граф K3,3 на поверхности тора.

332.o Реализуйте на поверхности тора графы K5 è K6 .

333.o Докажите, что среди любых шести людей найдется тройка попарно знакомых или тройка попарно незнакомых.


2)	(2 − 2x2 + x3)7 ïðè x12;				3)	(3 − x2 − x3)7 ïðè x12;
4)	(1 − 3x2 + x3)8			ïðè x12;	5)	(1 − x2 + 3x3)8		ïðè x12;
6)	(1 − 2x2 − 2x3)8 ïðè x12;				7)	(2 − x2 + 2x3)8		ïðè x12;
8)	(2 − 2x2 − x3)7			ïðè x14;	9)	(3 − x2 + x3)7 ïðè x14;
10)	(1 − 3x2	− x3)7		ïðè x14;	11)	(1 − x2 − 3x3)7		ïðè x14;
12)	(1 − 2x2	+ 2x3)8 ïðè x14;			13)	(2 − x2 − 2x3)8		ïðè x14;
14)	(2 − 2x2	+ x3)8		ïðè x14;	15)	(1 − 2x + 3x3)7 ïðè x6;
16)	(1 − 3x + 2x3)7 ïðè x6;				17)	(2 − x + 3x3)7	ïðè x6;
18)	(2 − 3x + x3)7		ïðè x6;		19)	(1 + 2x − 3x3)8 ïðè x6;
20)	(1 + 3x − 2x3)8 ïðè x6;				21)	(2 + x − 3x3)8	ïðè x6;
22)	(2 + 3x − x3)8		ïðè x6;		23)	(3 + x − 2x3)7	ïðè x7;
24)	(3 + 2x − x3)7		ïðè x7;		25)	(3 − x + x3)7 ïðè x7;
26)	(1 − 3x + x3)7		ïðè x7;		27)	(1 − x + 3x3)8	ïðè x7;
28)	(−1 + 2x − 3x3)8 ïðè x7;				29)	(−1 + 3x − 2x3)8 ïðè x7.

516. Найдите указанные суммы

∞

4k + 3

1) X

k(k + 1)

k=0 (k + 1)2k

(5)

k=0

∞

X k2 + 3k + 2 k

X tk

4) k=2

k − 1

k=2

∞

Xk(k + 1)C(kn)tk,

7) Xk22k,

k=0

∞

C(kn)3−k,

10)

C(n)

k=0 k + 2

k=0

12)

∞

2−k

k+1

(k + 1)Cn

13)

k=2

k=0 k + 2

15)

∞

Ck,

16)

k=0 k + 3

k=1 2k

(n)

18)

∞

C(3)t

19)

X(2k + 3)tk,

k=0

k2 + 3k + 2

k=0

	n
2)	Xk(k+1)Cnk2k,
	k=0	(−1)kCnk
	n
5)	X				,
5)	X	k + 1			,
	k=0	k + 1
	k=0
	∞
8)	X	2k + 5			2k,
8)	X	(k + 2)k!			2k,
	k=0	(k + 2)k!
	k=0
	∞	(k + 1)2
	X	(k + 1)2				k
11)				2			,
11)				2			,
	k=0	k!
	n
14)	Xk2Cnk(−3)k,
	k=0
	∞
17)	X	2k + 3	tk,
17)	X		tk,
	k=0	k + 3
	∞
20)	X(2k + 1)t−k,

k=2

346. На рис. 8 показана планировка дома из пяти комнат.

Имеются двери из любой комнаты в лю-

бую соседнюю комнату и на улицу. Вна-

чале все двери открыты, но при прохож-

дении через любую дверь, она автома-

тически закрывается. Можно ли одному

Ðèñ. 8

человеку закрыть все двери?

347. Сколько имеется деревьев с пятью и с шестью вершинами?

Постройте их.

348.o Докажите, что, если для связного графа выполнено равен-

ñòâî m = n − 1, то он является деревом.

349.o Сколько имеется корневых деревьев с пятью вершинами?
Постройте их.
350. Найдите цикломатическое число графа
à) K3,3 ,	á) Kn ,	â) O4 + K2,5 .

ëîâ351может. Известно,иметьчтоэтотγ(Gãðàô?) = 2. Какое наибольшее количество цик-

òå,352÷òî. Простойв нем можнограф Gвыбратьимеет 1989цикл,вершиндлинойине4000болееребер20.. Докажи-

Хроматическое число и хроматический многочлен. Алгоритмы обхода графа

353.Найдите хроматическое число графа K4 + K3 + K2,1 .

354.Докажите, что, если граф G имеет k компонент связности

G1, G2, . . . , Gk , òî χ(G) = max(χ(G1), χ(G2), . . . , χ(Gk).

äëÿ355графа. Докажите, что, если χ(G) = 2, то он является частичным

Km,n .

æèòå,356. Пустьчто p = max deg xi , ãäå xi вершины графа G. Äîêà-

χ(G) 6 p + 1.

357. Найдите хроматический многочлен графа а) K1,2 , á) K2,2 .

8)R1 = {(a, p), (a, q), (b, q), (b, r), (c, q), (c, t)}, R2 = {(x, r), (y, p), (y, q), (y, r), (y, t), (z, r)};

9)R1 = {(a, p), (b, p), (b, q), (b, r), (c, q), (c, r)}, R2 = {(x, p), (x, q), (x, r), (y, q), (y, r), (z, t)};

10)R1 = {(a, p), (a, q), (b, q), (b, t), (c, p), (c, t)}, R2 = {(x, p), (x, q), (y, q), (y, r), (y, t), (z, p)};

11)R1 = {(a, p), (a, q), (a, r), (b, q), (c, q), (c, r)}, R2 = {(x, p), (x, r), (y, q), (y, r), (z, q), (z, t)};

12)R1 = {(a, p), (a, q), (b, q), (b, r), (c, r), (c, t)}, R2 = {(x, p), (x, r), (y, q), (y, r), (y, t), (z, r)};

13)R1 = {(a, p), (a, q), (a, r), (b, q), (c, q), (c, r)}, R2 = {(x, q), (x, r), (y, q), (y, r), (z, p), (z, t)};

14)R1 = {(a, p), (a, r), (b, q), (b, r), (c, r), (c, t)}, R2 = {(x, r), (y, q), (y, r), (y, t), (z, r), (z, t)};

15)R1 = {(a, p), (a, q), (a, r), (b, r), (b, t), (c, t)}, R2 = {(x, p), (x, t), (y, q), (y, r), (z, q), (z, r)};

16)R1 = {(a, p), (a, q), (b, p), (b, q), (c, q), (c, t)}, R2 = {(x, r), (y, p), (y, q), (y, r), (y, t), (z, r)};

17)R1 = {(a, p), (a, q), (a, r), (b, t), (c, q), (c, r)}, R2 = {(x, p), (x, q), (y, q), (y, r), (z, q), (z, t)};

18)R1 = {(a, p), (b, p), (b, q), (b, r), (b, t), (c, t)}, R2 = {(x, p), (x, q), (y, r), (z, q), (z, r), (z, t)};

19)R1 = {(a, q), (b, p), (b, q), (b, t), (c, r), (c, t)}, R2 = {(x, p), (y, q), (z, p), (z, q), (z, r), (z, t)};

20)R1 = {(a, p), (a, q), (a, t), (b, p), (b, t)},

R2 = {(x, p), (y, p), (y, r), (y, t), (z, p), (z, q), (z, r)};

21)R1 = {(a, q), (a, r), (b, q), (b, r), (b, t)},

R2 = {(x, q), (x, r), (y, q), (y, t), (z, p), (z, r), (z, t)};

22)R1 = {(a, p), (a, r), (a, t), (c, p), (c, t)},

R2 = {(x, p), (x, q), (x, r), (y, t), (z, p), (z, r), (z, t)};

á)à) f(0) = 1, f(x + 1) = 2 + f(x),

â) f(0) = 0, f(x + 1) = f(x) + 2x + 1, ã) f(0) = 1, f(x + 1) = 2f(x),

f(t, 0) = t, f(t, x + 1) = f(t, x) + x.

íîé,367.иДокажите,найдитеформулу,что функцияпо которойf являетсяона вычисляется,примитивноеслирекурсив-

à) f(t, 0) = t, f(t, x + 1) = (f(t, x))t ,

á) f(t1, t2, 0) = 1, f(t1, t2, x + 1) = (t1 + t2)f(t1, t2, x).

368. Докажите примитивную рекурсивность функций

à) f(x) = xn , á) f(x) = x!, â)o f(x) = (2x + 1)!!.

Примитивно рекурсивные предикаты

369.Приведите пример, когда (x + y) −. z 6= x + (y −. z).

370.Докажите следующие свойства усеченной разности:

à)â) x + (y −. x) = y + (x −. y),	á) x(y −. z) = xy −. xz,
ox −. (y + z) = (x −. y) −. z,	ã)o(x −. y) −. z = (x −. z) −. y.

функцию371. Пустьпредикатаf è g п-р функции. Найдите характеристическую рекурсивным: P и докажите, что он является примитивно

â)à) P (x, y) = (f(x, y) = g(x, y)),	á) P (x, y, z) = (f(x, y) =6 g(x, z)),
ä) P (x, y) = (f(x, y) 6 g(x, x)),	ã) P (x, y, z, t) = (f(x, y) < g(z, t)),

o P (x, y) = (f(x, y) = 0),			å)o P (x, y, z) = (0 < f(x, y) 6 z).
372. Найдите п-р формулы для следующих функций:
à) min(x, y),	á) max(x, y),		â)o max(x, y, z).
373. Найдите п-р формулы для условных функций
	1, åñëè x < y,		á) f(x) =	0, åñëè x = 2,
à) f(x, y) =	2, åñëè x > y;			x, åñëè x =6 2.
374.o Найдите п-р формулу для условной функции
		2x, åñëè y > 9,
	f(x, y) =	x + 1, åñëè y < 5,
	x,		åñëè 5 6 y 6 9.

митивной375. Найдитерекурсии,формулуеслидля f = R(g, h), заданной по схеме при-

g(t) = 1, h(t, x, y) = t −. x.

23)24) x(y < 4x + 4 2x + y < 4), åñëè x [−2; 3], y [0; ∞), 25) y < 10 x(y > 4x + 4), åñëè x [−3; 1], y [0; 11],

26) x(y < 2x + 3 2x + y < 2), åñëè x [−2; 2], y [0; ∞), 27) y > 1 x(y > x + 1), åñëè x [−2; 0], y [0; 8],

28) x(y > 3x + 2 → 2x + y < 3), åñëè x [−1; 2], y [0; ∞), 29) x(y > 2x + 1 3x + y < 1), åñëè x [−2; 1], y [0; 5], (2 6 y 6 7) → x(y = x + 1), åñëè x [0; 5], y [0; 11].

Множества и отношения

512. Докажите следующие утверждения:

0) (A4B) \ (A C) = (B ∩ C) \ A;

1) (A C) \ ( A4B) = (A \ B) ((B ∩ C) \ A);

2) (A4 B) (C \ A) = (A ∩ B) A (B \ C); 3) ( B \ A)4(A C) = (B4C) \ A;

4) ( A \ C) (A4B) = (A \ B) ((B C) \ A);

5) (A4 B) \ (A ∩ C) = ((A ∩ B) \ C) ( B \ A); 6) ( A C) \ (A4B) = ((A ∩ B) \ C) A B ;

7) ( A4B) ∩ (B \ C) = A B C ;

8) (A \ B)4(A ∩ C) = A ∩ (B4C);

9) ( C \ B) (A4 C) = (A ∩ C) C (A \ B); 10) (A4B) \ ( A ∩ C) = (A \ B) ((B ∩ C) \ A); 11) (A ∩ C) \ (A4B) = (A ∩ B) \ C ;

12) (A4B) ∩ ( B \ C) = A \ (B C); 13) ( B \ A)4( A ∩ C) = A (B4C);

14) A4(B \ (A4C)) = (A \ B) (B \ C); 15) ( A4B) \ ( B C) = A ∩ B ∩ C ;

16) (A \ C) ∩ (A4B) = (A ∩ C) \ B ;

17) (A4 B) (B \ C) = A B (B \ (C \ A)); 18) (A \ B)4( A C) = A \ (B4C);

19) C4(B \ (A4C)) = (C \ B) (B \ A);

t −. 1			;
à) f(x) = µt			= x

2

á)â)o g(x) = µt(t < x2 + t2);

h(x) = µt(t −. (9x + 3) > (15x + 149) −. 5t).

ê389функции. Найдите функцию g, применив неограниченный µ-оператор

à)	f по переменной t, åñëè		â)o f(t) = t − 2,
ã) f(t) = 3,	á)	f(t) = t + 2,
f(t) = [t/2], ä)		f(x, t) = sg(t −. 2x),	å)o f(x, t) = x.

6. Машины Тьюринга

Понятие машины Тьюринга

390. Äàíà ì-ò T , имеющая программу q10 → q10R, q11 → q20R,

цию для начальной,		конфигурации. Найдите заключительную конфигура-
q21	→ q10R q20 → q0		1E
	à) K = q111101,		á) K = q1111111.

391.o Äàíà ì-ò T , имеющая программу q10 → q10R, q11 → q20R,

цию для начальной,	конфигурации. Найдите заключительную конфигура-
q21 → q10R q20 → q0		1E
		q111001.

392. Äàíà ì-ò T , имеющая программу q10 → q21R, q11 → q21L,

òåq 0заключительную→ q 1R, q 1 →конфигурациюq 0R, q 1 →äëÿq 1начальнойR, q 0 → конфигурацииq 0E . Найди-

2 3 2 3 3 1 3 0

q1111011.

393.o Äàíà ì-ò T , имеющая программу q10 → q21R, q11 → q21L,

òåq 0заключительную→ q 1R, q 1 →конфигурациюq 0R, q 1 →äëÿq 1начальнойR, q 0 → конфигурацииq 0E . Найди-

2 3 2 3 3 1 3 0

q111111.

свойствамиПостройте(394м-т T396)в алфавите. {0, 1}, обладающую указанными

áîìó394.словуT имеет. одно состояние, одну команду и применима к лю-

åå395работы. T имеетна любом2 команды,словенебесконечнаприменима. ни к какому слову и зона 33

КОНТРОЛЬНЫЕ ЗАДАНИЯ

Алгебра логики

509. Найдите многочлен Жегалкина, минимальную ДНФ, постройте релейно контактную схему по этой ДНФ и выясните при-

надлежность0) классам K0 , K1 , S , L, M булевой функции f(a, b, c, d)

2)	f = (0 − 2, 4, 6 − 9, 14, 15),	1)	f = (0, 1, 4, 5, 8 − 11, 13),
4)	f = (0, 2, 4 − 8, 10, 14),	3)	f = (1, 3 − 9, 11, 12),
6)	f = (2 − 4, 6, 8 − 13),	5)	f = (1 − 6, 9, 12 − 14),
8)	f = (0, 2, 4, 5, 8, 10, 12 − 14),	7)	f = (0 − 2, 4 − 7, 10, 14),
10)	f = (0, 2, 5, 8 − 11, 13),	9)	f = (0, 1, 4, 5, 10, 12 − 14),
12)	f = (0, 2, 6 − 8, 10, 14),	11)	f = (1, 3, 5 − 9, 12 − 14),
14)	f = (2 − 7, 9 − 11, 13),	13)	f = (2, 4 − 6, 9 − 14),
16)	f = (2, 5 − 10, 12 − 14),	15)	f = (2, 4 − 6, 8 − 14),
18)	f = (1 − 7, 10 − 12, 14),	17)	f = (1 − 7, 9 − 11, 13),
20)	f = (2, 3, 5 − 8, 12, 13, 15),	19)	f = (1, 3, 4, 6, 9 − 11, 14, 15),
22)	f = (0 − 3, 8, 9, 11, 12),	21) f = (0, 1, 3−5, 8, 10−12, 14),
24)	f = (0 − 2, 5 − 10, 14),	23)	f = (0 − 3, 5, 6, 10, 13, 14),
26)	f = (0, 2 − 4, 6, 8 − 13),	25)	f = (0, 2, 3, 6 − 8, 10, 12, 13),
28)	f = (0, 4, 6 − 8, 12, 14),	27)	f = (3 − 8, 11, 12),
	f = (0 − 4, 7, 11, 12, 15),	29)	f = (0, 2, 4, 6 − 8).

êèíà510.иДляминимальнуюбулевой функцииДНФ, постройтеg(a, b, c) найдитефункциональнуюмногочленсхемуЖегална-

основе элементов И-НЕ по этой ДНФ и выясните принадлежность функции0) g классам K0 , K1 , S , L, M

2) g = ab → (b ac),

1) g = ((a → b) c) b,

4) g = ((a b) →

)

3) g = ((b

)

) c,

6) g =

(a b)c

5) g =

a → (b c)

8) g =

a (b → c)

7) g = (a b)

b → c

g = q((a c) → (b

)),

9) g = (a c) (b →

Композиция машин Тьюринга

è418. Пусть даны м-т P A è QA для вычисления предикатов P (x) ленияQ(x)предикатассохранением аргумента. Постройте м-т P Q для вычис-

P (x) Q(x).

419.o Пусть даны м-т P è Q для вычисления предикатов P (x) è Q(x). Постройте м-т для вычисления предиката P (x) → Q(x).

420. Постройте м-т для перестановки чисел x

, x

, . . . , x

â îá-

ратном порядке.

ì-ò T : q101

0 . . . 01

` q001

0 ïðè

условии,421. Постройтечто

i < j .

функций422. Пусть даны м-т F , G è H для правильного вычисления суперпозицииf , g è h. Постройте м-т для правильного вычисления

f(g(x), h(x, y)).

423. Постройте м-т T для вычисления функции f(x) = x2 .

424.o Постройте м-т T для вычисления функции f(x, y) = xy.

òå425ì-.тПустьдля вычислениядана м-т F функциидлявычисления функции f(x). Построй-

µx(f(x) = 0).

òå426ì-.oтПустьдлявычислениядана м-т Fфункциидлявычисления функции f(t). Построй-

µt(f(t) = x).

Сч¼тные и перечислимые множества

à)427. Приведите пример счетных множеств A è B таких, что

A ∩ B счетно,	á) \|A ∩ B\| = 4.
à)428. Äàíî, ÷òî A è B счетны, докажите:
A B счетно,	á) A × B счетно.

à)429.o Приведите пример счетных множеств A è B таких, что

A \ B счетно, б) |A \ B| = 5.

430. Докажите, что бесконечное множество непересекающихся интервалов на числовой прямой образует счетное множество. 431.o Докажите, что монотонная функция может иметь не более счетного множества разрывов типа "скачок".

à) (x y) ( x y) 6= y, á) (x y) ( x y) 6= y,

â) (x y) ( x z) 6= (x y) ( x z) (y z),

ã)o (x y) ( x z) 6= (x y) ( x z) (y z).

485. Докажите, что в нечеткой логике

à) (x y) ( x y) 6 y, á) (x y) ( x y) > y,

â) (x y) ( x z) 6 (x y) ( x z) (y z), ã)o (x y) ( x z) > (x y) ( x z) (y z).

âèþ486. Изобразите множество точек M(x, y), удовлетворяющих усло-

предикатовp(x, y) = C , ãäå x, y, C	[0, 1], для следующих нечетких
p(x, y):	á) p(x, y) = x y,
à) p(x, y) = x y,
â) p(x, y) = x → y,	ã) p(x, y) = x y,
ä)op(x, y) = x \| y.
Найдите487. Пустьнечеткоеµ(x значениеA) = 0, 3, µ(x B) = 0, 4 è µ(x C) = 0, 8.
s предиката x M , åñëè
à) M = (B2 \ A) (A · C),	á) M = (		+ B) ∩ (A4C),
		A
â)oM = (A + B) ∩ C2,	ã)oM = (A B) · (B +				).
				C

490. Приведите пример значений p = µ(x A), q = µ(x B) è rà)= µ(x C), показывающий, что

A·(B + C) 6= A·B + A·C , á) A∩(B + C) 6= (A∩B) + (A∩C).

Многозначная логика

В задачах 491 501 найдите I форму и упростите ее для указанных функций трехзначной логики.

ñî444следующими. Найдите языкпродукциями:L, порождаемый регулярной грамматикой

I → aA, A → aB , B → b | bC | bI ,

C → c | cC .

ющуюВзадачахего регулярную445 450грамматикудля данного языка L найдите порожда-

ванный конечный автомат		G и постройте детерминиро-
	L = {a2bc2} .	K , воспринимающий язык L.
445.	L = {a2bc2} .	446. L = {a2b}+ {c}+.
447.	L = {a}+{b2c} .	448.o L = {ab, c2}+.
449.o L = {ab} {c2}+.		450.o L = {ab} {b}+.

ñòâî451.идентификаторовНайдитерегулярнуюпроизвольнойграмматикудлиныG, порождающуюв алфавите, состоямноже--

щем из символов a, b, 0, 1 è 2.

452.o Найдите регулярную грамматику, порождающую множеалфавитество всех идентификаторов α длиной не более трех символов в

{a, b, 0, 1, 2}.

453. Найдите регулярную грамматику, порождающую множебуквыство всех строк в алфавите {a, b}, в которых справа от любой

aнайдется хотя бы одна буква b.

454.Найдите регулярную грамматику, порождающую множе-

ствои всех строк в алфавите {a, b} с четным количеством букв a

которых455. ПустьлюбойязыкпрефиксL состоитсодержитиз всехбуквслов α в алфавите {a, b}, у а всего в слове a не меньше, чем букв b, порождающуюαязыкбукв a è b поровну. Найдите КС-грамматику G, знающий этот язык. L, и постройте стековый автомат M , распо-

которых456. Пустьбуквязык L состоит из всех слов в алфавите {a, b}, в грамматику a в два раза больше, чем букв b. Найдите КСтомат G, порождающую язык L, и постройте стековый ав-

Mдля распознавания этого языка.

457.Найдите КС-грамматику, порождающую все арифметиче-

ские выражения, составленные из переменных a, b, c с помощью

скобок и арифметических знаков +, −, , /.

458.o Найдите КС-грамматику, порождающую все пропозициональныеи константформулы, составленные из логических переменных a, b, c

операций дизъюнкции,true, falseконъюнкцииспомощью искобокотрицанияи знаков. логических

8. Аксиоматические теории

Âзадачах 459 462 найдите минимальную КНФ для указанных формул.


459.	(a b)c	a.			460. (ab c) → (b			c	).
461.o (a bc) (b →			ac	).	462.o a (	bc a	→ b).

Используя метод резолюций докажите справедливость следующих выводов в исчислении высказываний (463 472).

463. ` a → (b → a).

464. b → a ` a → b.

465.o a → b, a → b ` b.

466. a → c, b → c ` (a b) → c.

467.o a → b, a → c ` a → bc.

468.o ` (a → (b → c)) → ((a → b) → (a → c)).

469. a c ` (ab c) → (b c).

470.o a ` (a bc) (b → ac).

471. (a b)( b c d) ` a b c d b c.

472.o (a b d)(a b d)( b c d)(b c d) ` a c b d b d.

В задачах 473 476 найдите наиболее общий унификатор для указанных предикатов.

473. P (x, g(y), x), P (u, v, f(v, a)).

474. P (a, x, f(g(x))), P (z, f(z), f(u)).

475. P (x, f(y), x, y), P (u, v, a, u).

476.o P (x, f(g(a)), y), P (u, f(u), v), P (g(p), q, p).

в исчисленииИспользуяпредикатовметодрезолюцийи найдитедокажите,соответствующуючто F , F , .эрбранову. . , F ` F
1 2	n

область в задачах 477 482.

477. F1 = x(A(x) → (B(x) C(x))), F2 = x(A(x) D(x)),

F= x(C(x) D(x)).

478.F1 = x y(A(x, y) → C(x)), F2 = x y(B(x, y) → C(x)),

F= x y((A(x, y) C(x)) → ( B(x, y) C(x))).

479.o F1 = x(A(x) y(B(y) → C(x, y))), F2 = x(A(x) → y(D(y) → C(x, y))),

F= x(B(x) → D(x)).

480.F1 = x(A(x) B(x) → y(C(x, y) D(y))),

F2 = x(E(x) → B(x)),

F3 = x(E(x) A(x) y(C(x, y) → E(y))),

F= x((E(x) D(x)).

481.F1 = x( y(A(x, y) B(y)) → y(C(y) D(x, y))),

F= x C(x) → x y(A(x, y) → B(y)).

482.o F1 = x(A(x) → B(x)),

F = x y(A(y) C(x, y)) → z(B(z) C(x, z))

9. Нечеткая и многозначная логика

Нечеткая логика

483. Докажите, что в нечеткой логике

à) x (x y) = x, á) x (y z) = (x y) (x z), â)ox (x y) = x, ã)ox (y z) = (x y) (x z).

484. Приведите такие нечеткие значения x, y, z , ÷òî 39

<<< < Предыдущая 12 / 42 3 4 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
03.12.2018158.21 Кб59Ministerstvo_nauki_i_obrazovania_RF.doc
#
11.06.2015176.64 Кб9modul1.doc
#
18.09.201933.82 Кб6Motivatsia.docx
#
11.06.20151.6 Mб68M_Posobie_12_v2_O.doc
#
11.06.2015578.87 Кб25nasyrov_a_z_nasyrov_z_h_diskretnaya_matematika.pdf
#
11.06.20155.12 Mб142NEWsbornik.pdf
#
11.06.2015209.8 Кб35Organiezatsia_LEO.rtf
#
29.03.20163.99 Mб64ORGANIZATsIYa_EVM.doc
#
29.03.20163.03 Mб9ORGANIZATsIYa_EVM.pdf
#
13.11.2019123.9 Кб5otchet_po_praktike.doc
#
18.04.20195.43 Mб147otvety_AES_2012.doc