ДМ_Контр вопросы

б) «6 ділиться на 3, і 7 більше ніж 10».

48.Показати, що висловлювання A B C є логічним слідством висловлювання A C .

49.Дано істинне висловлювання «Якщо n ділиться на 9, то n ділиться на 3». Нехай також звісно, що «nділиться на 9». Який висновок можна зробити з цих двох висловлювань?

50.Чи є наступні формули загальнозначущими, суперечливими та несуперечливими:

а) ( A) A;

б) A B B A ; в) A B A A;

г) A B A B .

51.Побудуйте складні висловлювання з використанням тільки таких операцій: а) еквівалентність; б) імплікація і кон’юнкція; в) від’ємина, кон’юнкція та диз’юнкція.

52.Предметна область є множина дійсних чисел. Записати у вигляді

виразу логіки предикатів математичне затвердження: «Для всіх x вірно, що

(x 1)2 x2 2 x 1 »; «Існує число, квадрат якого дорівнює 4».

53.Визначити, які змінні є зв’язними, а які – вільними в наведених формулах: а) A(x,y); б) y(B(x) xA(x,y)); в) x(B(x) xA(x,y)).

54.Привести формулу ( x)F(x) ( x)Q(x) к ВНФ.

55. Знайти степені кожної вершини графів (для орграфів вказати (x) и

(x)). Перевірити формулу розрахунку кількості ребер, використовуючи степені вершин графа. Запишіть матриці суміжності та інциденції.

1)	2)	x2
x1	x1
x3	x2
x4	x3	x4
	x5

11

3) 4)

	x		x2
	1
x1	x2
			x3
x3	x4		x4
	x5
	x
5)	6)
x1	x1	x2	x3
	x
x3	x5

x2	x4	x4	x5

7)		x	2	x	8)	x	x2
				3
					x4
x1
			x5		x6		x3

x5 x4

Знайти графи, які задаються такими матрицями суміжності A та інциденції B.

1. x1	x2 x3		x4		2. x1	x2 x3		x4 x5			3. x1	x2 x3		x4 x5
1	0	1	0	x1	0	0	1	1	0	x1	0	0	1	1	0	x1
0	0	1	0	x2	0	2	0	0	0	x2	0	0	0	0	0	x2
A									1 x3						0 x3
1	1	1	2	x3	A 1 0 0 1						A 1 0 0 1
0	0	2	0	x4	1	0	1	1	0	x4	1	0	1	0	0	x4
					1	0	1	0	0	x5	0	0	0	0	0	x5

12

5. y1 y2 y3 y4 y5 y6 y7

6.

y1 y2 y3

y4

y5

y6

y7 y8

0	0	0	0	0	0	0	x	1 0		0	1	0	0	0	1	x1
							1									x2
1	0	1	0	0	1	0	x2	1	1	0	0	1	0	0	0
B																x3
1	1	0	1	0	1	1	x3	B 0	0	1	1	0	0	1	0
0	1	1	1	0	0	1		0	1	0	0	0	1	1 0		x
							x4									x4
								0	0	1	0	1	0	0	1		5

56.Довести, що множина усіх ребер кінцевого зв’язного графа формує простий цикл тоді та тільки тоді, коли степені усіх вершин кратні 2.

57.Довести, що граф ейлерів тоді та тільки тоді, коли множину його ребер можна розбити на прості цикли (які попарно не перетинаються за ребрами).

58.Перелічить неізоморфні дерева з шістьома вершинами.

59.Перелічить кореневі дерева з п’ятьома деревами.

60.Яка кількість ребер остового дерева зв’язного графа G з n вершинами та m ребрами.

61.Яка властивість є достатньою умовою для того, щоб довільний граф мав гамільтоновий цикл?

13

Електронне навчальне видання

ТИПОВІ КОНТРОЛЬНІ ТА ТЕСТОВІ ЗАВДАННЯ з дисципліни

«ДИСКРЕТНА МАТЕМАТИКА»

для студентів усіх форм навчання напряму 6.050101 Комп’ютерні науки

Упорядники

ВАСИЛЬЦОВА Наталія Володимирівна ЧАЛА Лариса Ернестівна

Відповідальний випусковий В.М. Левикін

Авторська редакція

14