v10

ДИСКРЕТНАЯ МАТЕМАТИКА

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ РФ12-33Б Смирнов Леонид

1.Доказать по определению, что для произвольных множеств A, B, C справедливо тождество A ∩ (B \ C) = (A ∩ B) \ C. Проиллюстрировать при помощи диаграмм Эйлера. (4 балла)

2.Найти A × (B ∩ C), (B ∩ C) × A, |B × A|, если A = {1, 13, 15, 17}, B = {10, 11, 12, 23, 24, 25}, C = {10, 23, 26, 29}. (2 балла)

3.Даны два бинарных отношения ρ A × B, τ B × A: A = {2, 3, 4, 5, 10}, B = {1, 4, 6, 10},

ρ =	(a, b) | a A, b B, b = 3a	, τ =	(b, a) | b B, a A, b 6 a . Задать эти отношения явно (перечислением).

Найти: 1) отношения ρ−1, ρτ, ρτ, τρ; 2) область определения и область значений отношений ρ и ρ−1; 3) матрицу и графическое представление отношений ρ и ρτ. (3 балла)

4. Найти область определения, область значений отношения

n o

P = (x, y) | x, y R, x2 + y2 = 4 .

Является ли отношение рефлексивным, симметричным, антисимметричным, транзитивным? (3 балла)

5.Сформулировать высказывание соотвествующее формуле (A B) → C. (2 балла)

6.Найти СДНФ и СКНФ формулы (z (x y)) ≡ (¬x → ¬y) а) то таблице истинности, б) с помощью эквивалентных преобразований. Составить многочлен Жегалкина при помощи эквивалентных преобразований исходной формулы. (8 баллов)

7.Минимизировать в классе ДНФ логическую функцию f(x1, x2, x3, x4), которая принимает значение 1 на следующих наборах переменных (2, 3, 6, 10, 13). (2 балла)

8.Записать на языке логики предикатов определение ограниченной функции (функция f(x) называется ограниченной на множестве M, если существует такое неотрицательное число L, что для всех x M справедливо неравенство

|f(x)| < L).(2 балла)

9.1. Проверить истинность формулы a b c((a||b) → ((a c) (b c)) (a, b и c – прямые).

2. Определить область истинности предиката

P (x, y) = z((x N) (y N) (z N) ((x + y − z = 7) (x + y + z = 15))).(2 балла)

10. Для схемы переключателей составить формулу (функцию проводимости). Упростить схему. (2 балла)

BA

A C B

11. Граф G задан матрицей инцидентности

			0	0	0	1	0	0	1	0	0	1
			1	1	1	1	0	0	0	0	0	0
B	G	=	0 0 0 0 1 1 1 0 0 0 .
				0	0	0	0	0	0	1	1
			0									1
			1	0	0	0	1	0	0	1	0	0
			0	0	1	0	0	1	0	0	0	0
			0	1	0	0	0	0	0	0	1	0

1)Задать G графически и матрицей смежности AG. Рассчитать степени вершин.

2)Составить матрицу смежности AG и матрицу инцидентности BG дополнительного графа G. Задать G графически.

3)Изоморфны ли графы G и G?

4)Являются ли графы G и G связными? Определить количество компонент связности, найти мосты и точки сочленения.

5)Привести примеры цикла в графе G и цепи, не являющейся циклом, в G.

6)Привести пример остовного ациклического подграфа H графа G.(6 баллов)

12.Взвешенный граф задан матрицей весов. Построить его графическое представление, с помощью алгоритма Дейкстры определить матрицу расстояний. Найти радиус, центр и диаметр графа. (4 балла)

0	∞	1	3	∞
∞	0	∞	1	2

	1	∞	0	2	1		.
		2	1		0
	3	1	2	0	∞
∞				∞