NEWsbornik

A рекурсивно.

o

рекурсивным433. Докажите,. что множество A = {(k, k+1) | k N0} является

âèþ434. Пусть общерекурсивная функция f(x) удовлетворяет услорекурсивноf(x) >. x ïðè x N0 . Докажите, что множество A = f(N0)

o

общерекурсивную435. Пусть множествофункциюA рекурсивно и бесконечно. Определим 1) f условиями: Докажите,f(0) = µx÷òî(JAфункция(x) = 1); 2) f(t + 1) = µx(JA(x) = 1 x > f(t)).

fстрого возрастает и A = f(N0).

436.Пусть π(x, y) нумерующая функция Пеано. Вычислите

π(3; 4), l(33), r(33).

437. Пусть π3(x, y, z) = π(π(x, y), z). Вычислите π3(1; 2; 3). 438.o Найдите x, y, z , åñëè π3(x, y, z) = 11.

440. Пусть непустое множество A N × N

речислимо. Докажите, что существуют примитивно0 0 рекурсивнорекурсивныепефункции f è g такие, что A = {(f(k), g(k)) | k N0}.

441à). Пустьмножествоπ(A) = {π(x, y) | (x, y) A}. Докажите, что б) множество A рекурсивно π(A) рекурсивно;

но перечислимо. A рекурсивно перечислимо π(A) рекурсив-

o

график442. Пусть функция y = f(k) имеет рекурсивно перечислимый

. Докажите, что функция f частично рекурсивна.

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

порождаемый443. Постройтерегулярнойвыводы несколькихграмматикойцепочексо следующимии найдите языкпродукL-,

циями: I → a | b | aB | bA, A → a | aA, B → b | bB .

36

В задачах 502 508 найдите II форму и многочлен для указанных функций трехзначной логики.

41

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

397. Напишите программу для м-т MR : q101x0 ` q0001x0. 398.o Напишите программу для м-т P L : q101x01y0 ` q001x+y0.

словам399. Постройтевида м-т T в алфавите {0, 1}, которая применима к 012n0, но не применима к словам вида 012n+10.

то соответствующую машину Тьюринга построитьx невозможно> 0 íà x >.0,

âèäà402.o Постройте м-т T в алфавите {0, 1}, применимую к словам 01m01n0 ïðè m = n и не применимую при m 6= n.

дующей416. Найдитесистемойфункциюкоманд:f(x), которую вычисляет м-т T ñî ñëå-

q10 → q20R, q20 → q01L, q21 → q30R, q31 → q31E , q30 → q40L, q41 → q01L, q40 → q00L.

o

дующей417. Найдитесистемойфункциюкоманд:f(x), которую вычисляет м-т T ñî ñëå-

q10 → q20R, q20 → q31R, q21 → q31R, q30 → q41R, q31 → q41R, q41 → q40R, q40 → q50L, q50 → q50L, q51 → q61L, q61 → q01L.

34

ðûõ511.являетсяНайдитеистинныммножествопредикатвсех значений переменной y, äëÿ êîòî-

1)0) (1 6 y 6 5) x(x > y), åñëè x [0; 4], y [0; ∞), 2) y 6 8 → x(y + 1 > 2x), åñëè x (−∞; 3], y [0; ∞), 3) y < 5 x(y + 3 > 3x), åñëè x (−∞; 2], y [0; 10], 4) y > 2 x(y < 2x + 3), åñëè x [0; ∞), y [0; ∞), 5) y > 1 → x(y < 5x + 2), åñëè x [0; 7], y [0; ∞),

6) y > 5 x(y < 7x + 1), åñëè x [0; 3], y [0; 7], 7) y > 6 x(2y < 3x + 1), åñëè x [0; 5], y [0; 9],

8) y > 7 x(3y < 2x + 1), åñëè x [−2; 1], y [0; ∞), 9) y > 8 x(4y < 2x + 6), åñëè x (−∞; 1], y [0; 9],

10) y < 7 x(y > x + 5), åñëè x [0; ∞), y [0; 8], 11) y > 1 x(y < 3x + 1), åñëè x [−1; 2], y [0; ∞),

12) x(y > 2x + 1 3x + y < 1), åñëè x [−1; 1], y [0; 7], 13) y < 10 x(y > 3x + 4), åñëè x [−2; 0], y [0; ∞), 14) x(y > 2x + 4 x + y < 3), åñëè x [−3; 4], y [0; 6], 15) y > 2 x(y < x + 4), åñëè x [−4; 1], y [0; ∞),

16) x(y < x + 3 3x + y < 2), åñëè x [−4; 1], y [0; ∞), 17) y > 3 → x(y < 2x + 2), åñëè x [−2; 1], y [0; 7],

18) x(y > x + 2 x + y < 3), åñëè x [−3; 4], y [0; ∞), 19) y < 10 x(y < 4x + 2), åñëè x [−2; 0], y [0; ∞), 20) x(y < 3x + 3 2x + y > 2), åñëè x [−2; 2], y [0; 5], 21) y > 2 x(y < 3x + 2), åñëè x [−2; 3], y [0; 7],

22) x(y > 2x + 4 y > 3 − 3x), åñëè x [−1; 1], y [0; ∞),x(y > 4x + 3) → (y > 2), åñëè x [−2; 1], y [0; 8],

43

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

митивной рекурсии, если g(t) = 2t, h(t, x, y) =

åñëè

åñëè

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

f(x) =

0, åñëè x четно,

1, åñëè x нечетно.

o

рекурсивной378. Докажите,. что функция f(x) = [x/2] является примитивно

Оператор наименьшего значения

379. Следующие функции, заданные с помощью ограниченного оператора наименьшего значения, представьте в виде суперпозиции основных примитивно рекурсивных функций:

à) f(x) = µt (t + 10 > 2x);

t6x

á) g(x) = µt (t + 8 > x2);

t62x

â)o h(x) = µt (t > x2 + 2).

383.o g(x) сумма делителей числа x, ãäå g(0) = 0.

384.o p(x) число x является простым.

385. ÍÎÊ(x, y), считая, что НОК (x, 0) = 0 è ÍÎÊ(0, y) = 0.

√

386. f(x) = [x 2].

387.o [√x + √y].

388. Докажите примитивную рекурсивность следующих функций и выразите их через основные п-р функции:

32

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

21) (A ∩ C) \ B = (A ∩ C) (A ∩ B) \ C = A ∩ B ;

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

23) A \ (A \ B) = C \ (C \ B) B \ A = B \ C ;

24) (A ∩ B) C = (B C) ∩ A C A;

25) A ∩ (B4C) = A ∩ B A ∩ C = ;

26) (A4B) ∩ C = (A ∩ C)4(B ∩ C);

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

28) A (B \ C) = (A B) ∩ (A C);

29) A4C B A B = B C .

513. Даны бинарные отношения R1 A × P è R2 B × P , ãäå

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

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

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

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

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

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

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

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

45

5. Рекурсивные функции

Понятие примитивно рекурсивной функции

äëÿ361âñåõ. Докажите,значенийчто п-р функция f(x1, x2, . . . , xn) определена

xi N0 .

o

äëÿ362âñåõ. Докажите,значенийчто п-р предикат P (x1, x2, . . . , xn) определен

xi N0 .

рекурсивность363. Дана п-рфункциифункция f(x1, x2, x3). Докажите примитивную

à)â) g(x1, x2, x3) = f(x1, x3, x2), á) g(x1, x2, x3, x4) = f(x1, x2, x3),

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

30

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

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

24)R1 = {(b, p), (b, q), (b, t), (c, q), (c, t)},

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

25)R1 = {(a, q), (b, p), (b, r), (c, r), (c, t)},

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

26)R1 = {(a, q), (a, r), (a, t), (b, p), (c, r)},

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

27)R1 = {(a, p), (a, q), (b, p), (b, t), (c, r)},

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

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

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

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

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

íèè515многочлена:. Найдите коэффициент при указанной степени x в разложе-

335.o Докажите, что можно реализовать граф K

пространстве так, чтобы все его ребра были отрезкамиn в трехмерном.

Связность. Деревья. Цикломатическое число

336. Какое наименьшее число компонент связности может иметь граф, у которого 100 вершин и 60 ребер?

337. Расстоянием между вершинами графа называется минимальная длина цепи, соединяющей эти вершины. Диаметром связного графа называется расстояние между самыми удаленными его вершинами. Найдите диаметры графов, которые изображены на рис. 7.

338. Укажите какой-нибудь простой связный граф, который нельзя представить в виде соединения двух графов.

n вершин. Докажите, что G является связным.

o '

связными340. Известно,. что G G. Докажите, что эти графы являются

341. Плоский связный граф имеет только треугольные грани. Докажите для этого графа равенства m = 3n − 6 è l = 2n − 4. 342.o Плоский связный граф имеет только четырехугольные грани. Докажите для этого графа, что и l = n − 2.

343.При каких n является эйлеровым граф Kn ?

344.При каких m è n является эйлеровым граф Km,n ?

незамкнутая345. Ãðàô Gцепь,называетсясодержащаяполуэйлеровым,все ребра графаеслиимеется простая что связный граф является полуэйлеровым тогда иGтолько.Докажите,тогда,

когда он имеет ровно две нечетные вершины, причем эти вершины служат концами простой цепи, содержащей все ребра графа.

28

Решите следующие рекуррентности (305 310).

305. u1 = 2, u2 = 3; un = 2un−1 − un−2 .

306. a1 = 14, b1 = −6; an+1 = 3an + bn , bn+1 = −an + bn .

307.o a0 = 1, b0 = 0; an+1 = an + bn+1 , bn+1 = an − 2bn .

308. a1 = b1 = 0; an+1 = bn + 10, bn+1 = an + 6.

2n + 3 309. a1 = 2; an+1 = 3an + n(n + 1) .

310. x0 = 1, x1 = cos α; xn = 2 cos α · xn−1 − xn−2 .

311. На какое максимальное количество частей могут разделить

плоскость n прямых?

312.o На какое максимальное количество частей могут разделить

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

Понятие графа. Изоморфизм. Планарность

315. Приведите пример графа с вершинами x1, x2, x3 такого, что äèòådeg x1åãî= матрицу3, deg x2 смежности= 4, deg x3. = 5. Для построенного графа най-

317. Пусть даны неотрицательные целые числа s1, s2, . . . , sn òà- êèå, ÷òî n

P

si = 2m. Постройте граф с вершинами x1, x2, . . . , xn

i=1

так, чтобы deg xi = si ïðè i = 1, 2, . . . , n.

280. Найдите количество натуральных чисел, не превосходящих 1000, которые не делятся ни на 3, ни на 5, ни на 7.

281.o Найдите количество натуральных чисел, не превосходящих 1000, которые не делятся ни на 6, ни на 10, ни на 15.

282. Сколько чисел от 0 до 999 не имеют ни одной цифры 1 в своей десятичной записи?

283.o Сколько имеется булевых функций от трех существенных переменных?

284. Сколькими способами можно положить 5 различных шаров в 3 различных ящика так, чтобы не было пустых ящиков?

âîé285строкой. Сколько имеется латинских квадратов размера 4 ×4, ñ ïåð- (1 2 3 4) и второй строкой (4 3 2 1)?

ùèõ287.oровноПусть Pn(k) число перестановок чисел 1, 2, . . . , n, èìåþ-

Производящие функции. Рекуррентности

288. Найдите A(t) для последовательности (uk)∞k=0 , åñëè uk = 1 ïðè 0 6 k 6 n è uk = 0 ïðè k > n.

289à). Найдите E(t) для последовательности

P0, P1, . . . , Pk, . . ., á) A0n, A1n, . . . , Ann, 0, 0, . . ..

290. Найдите A(t) è E(t)

A0(n), A1(n), . . . , Ak(n), . . ..

291. Найдите A( 12 ) для последовательности uk = C(kn) .

292à). Найдите A(t) для последовательности (uk)∞k=0 , åñëè

uk = k, á) uk = k2 .

293.o Найдите A(t) для последовательности uk = k(k − 1). 24

Рекурсивные функции

521. Представьте в виде суперпозиции основных примитивно рекурсивныхона вычисляетсяфункцийпо указаннойфункцию нижеf(x), формуле:еслиf(0) = 1, à ïðè x > 1

o

äëÿ250любого. Сколькочислаимеется перестановок чисел 1, 2, . . . , n, в которых из чисел k, стоящего не на первом месте, хотя бы одно

k + 1 èëè k − 1 находится левее, чем k?

Перестановки с повторениями. Сочетания

251. Сколько различных перестановок можно образовать из букв слова "математика"?

252.o Сколькими способами можно переставлять буквы в слове "кофеварка" так, чтобы гласные и согласные буквы чередовались?

253. Имеется 5 яблок, 2 груши, 3 апельсина. Сколькими способами можно есть по одному фрукту в течение 10 дней?

254. Сколькими способами могут 3 разбойника поделить между собой 9 различных предметов так, чтобы первому разбойнику досталось 4 предмета, второму 3, третьему 2 предмета?

o ×

êî255различных. На клетчатойпутейбумагедлинывыделен прямоугольник m n. Скольпрямоугольника в противоположнуюm + n ведетвершину,из некоторойесли идтивершиныможно

только по сторонам клеток?

256.С каким коэффициентом входит ab2c3 в разложение мно- гочлена (a + b + c + d)6 ?

257.Найдите коэффициент при x8 у многочлена (1 − x2 + x3)9 .

258.Найдите коэффициент при t5 в разложении (1 + 2t − 3t2)8 .

259.o Найдите наибольший коэффициент в разложении (1 + x)10 .

260. Напишите разложение многочлена (x1 + x2 + . . . + xk)2 . 261.o Напишите разложение многочлена (x1 + x2 + . . . + xk)3 .

263.Вычислите C1412 + C53 − P (3, 0, 2).

264.Докажите, что Cnk + 2Cnk+1 + Cnk+2 = Cnk+2+2 .

265.o Найдите k, åñëè Ck = Ck+4

10 10 .

22

524. Постройте (в командах) машину Тьюринга для вычисления указанного предиката P (x, y):

является227. Докажите,инъективнойчто, .если F не инъективна, то F ◦ G также не

является228. Докажите,сюръективнойчто, если. G не сюръективна, то F ◦ G также не

Приведите пример множеств A, B и функций F : A → B , à)G : B → A таких, что

á) G не инъективна, но F ◦ G инъективна; в) F не сюръективна, но F ◦ G сюръективна;

ã) F ◦ G инъективна, но G ◦ F не инъективна; д) F ◦ G сюръективна, но G ◦ F не сюръективна;

F ◦ G биективна, но G ◦ F не биективна.

230. Выясните существование обратной функции F −1 и найдите формулу для ее вычисления, если

à) F : [−2; 1] → [0; 4], F (x) = x2 , á) F : [1; 2] → [1; 5], F (x) = x2 ,

â) F : [−2; −1] → [1; 4], F (x) = x2 ,

ã) F : Z → Z, F (n) =

n + 1, åñëè n четно, n − 1, åñëè n нечетно.

à)231. Пусть f : X → Y , A, B Y . Докажите, что

á) f−1(A B) = f−1(A) f−1(B), â)o f−1(A ∩ B) = f−1(A) ∩ f−1(B), ã)o f−1(A \ B) = f−1(A) \ f−1(B), o f−1(A4B) = f−1(A)4f−1(B).

3. Комбинаторика

Размещения и перестановки без повторений.

Размещения с повторениями

232. В меню столовой имеется 4 наименования закуски, 2 первого блюда, 3 второго, 3 третьего блюда и 2 варианта десерта. Сколькими способами можно составить обед, выбирая по одному блюду каждого типа?

233. Сколько делителей имеет число 37 ·54 ? Найдите сумму всех этих делителей.

20

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

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

209.o Åñëè R эквивалентность, то R ◦ R эквивалентность.

è210åãî. подмножестваПриведитепример частично упорядоченного множества M а) два минимальныхAэлементатак,чтобыи триA максимальныхимело элемента;

б) верхнюю грань, максимальные элементы, но не имело наибольшего элемента; в) единственный максимальный элемент, но не имело наибольшего элемента;

г) верхнюю грань, но не имело максимальных элементов.

211. Докажите, что пересечение двух частичных порядков на данном множестве снова является частичным порядком.

o

объединение212. Приведитекоторыхпримерне являетсячастичныхчастичнымпорядковпорядкомна M =. {a, b, c},

213. Приведите пример линейного порядка на N × N.

214.o Приведите пример линейного порядка на Z × [0; 1].

отношение215. Пусть A è B упорядоченные множества. Докажите, что порядок на (a, b) 6 (a0, b0) (a < a0) (a = a0 b 6 b0) задает

A × B .

o

множества216. Пусть.Докажите,A è B непересекающиесячто бинарное отношениелинейно упорядоченные

x 6 y

задает(x A линейныйy B) (порядокx A yíà A x 6 y) (x B y B x 6 y)

A B .

Докажите следующие утверждения (217 219). линейным217. ЕслипорядкомR линейныйна порядок на M , òî R◦R также является

M .

219.o Åñëè R линейный порядок на M , òî R ◦ R−1 = M × M .

Функциональные отношения

нальным220. ПустьбинарноеA = {a,отношениеb, c, d}, B = {p, q, r}. Является ли функцио- R A × B , åñëè

18