Министерство образования Республики Беларусь

Учреждение образования

Белорусский Государственный университет информатики

и радиоэлектроники

Контрольная работа + Тест

По курсу “Основы дискретной математики и теории алгоритмов”

Контрольная работа. Вариант 4

Задание 1. Используя диаграммы Эйлера-Венна, решить задачу.

4. Экзамен по математике содержал три задачи: по ал­гебре, геометрии и тригонометрии. Из 800 абитуриентов за­дачу по алгебре решили 250 человек, по алгебре или геомет­рии - 660 человек, по две задачи решили 400 человек, из них две задачи по алгебре и геометрии решили 150 человек, по алгебре и тригонометрии 50 человек; ни один абитуриент не решил все задачи; 20 абитуриентов не решили ни одной зада­чи; только по тригонометрии задачи решили 120 человек. Сколько решили только одну задачу? Сколько человек реши­ли задачи по геометрии?

Решение

А – алгебра, Г – геометрия, Т – тригонометрия.

m() = 120, m(А) = 250, m(A) = 150, m(A) = 50, m(A) = 0, m() = 20, m(А ) = 660, m((A)) = 400.

m() = m(А) – m(A) – m(A) = 250 – 50 – 150 = 50 (решили только алгебру)

m(Т ) = m((A)) – m(A) – m(A) = 400 – 150 – 50 = 200 (решили тригонометрию и геометрию)

m() = m() + m(A) + m(Т ) = 120 + 50 + 200 = 370 (решили тригонометрию)

m(Г) = m(А ) – m() – m(A) = m(U) – m() – m() – m() – m(A) = 660 – 50 – 50 = 800 – 20 – 120 – 50 – 50 = 560 (решили геометрию)

m() = m(Г) – m(A) – m(Т ) = 560 – 150 – 200 = 210 (решили только геометрию)

m() + m() + m() = 50 + 370 + 210 = 630 (решили только одну задачу)

Задание 2. Упростить выражение.

14. = U B ( = U (A )\А = U = U

Задание 3. С помощью ДНФ и КНФ установить выполнимость формул.

24. ABCC

Полученная ДНФ не удовлетворяет Теореме номер 2 следовательно формула является выполнимой.

Задание 4. С помощью совершенных нормальных форм установить, равносильны ли формулы.

34.  = A (B);  = AB.

А	В	С
0	0	1	0	1	0	1	1
0	1	0	1	1	0	0	1
0	1	1	0	0	1	1	1
0	0	0	1	1	0	1	1
1	0	1	0	1	0	1	1
1	1	0	1	1	0	0	0
1	1	1	0	0	1	1	1
1	0	0	1	1	0	1	1

СДНФ =

СКНФ =

А	В
0	0	1
0	1	1
1	0	0
1	1	1

СДНФ =

СКНФ =

Т. к. СКНФ формул отличаются то они (формулы) не равносильны.

Задание 5. Проверить правильность рассуждения любым из трех способов.

44.Если функция непрерывна на данном интервале и имеет одинаковые знаки на концах данного интервала, то внутри его функция не обращается в ноль. Данная функция непре­рывна, следовательно, на концах интервала функция имеет разные знаки.

А — ф-ция непрерывна на данном интервале

В — ф-ция не обращается в ноль на данном интервале

С — ф-ция имеет одинаковые знаки на концах данного интервала

Р1

А Р2

Q

А	В	С
0	0	0	1	0	1	0	1
0	0	1	0	0	1	0	1
0	1	0	1	0	1	0	1
0	1	1	0	0	1	0	1
1	0	0	1	0	1	1	1
1	0	1	0	1	0	0	1
1	1	0	1	0	1	1	1
1	1	1	0	1	1	1	0

Выражение выполнимо, рассуждение не верно.

Задание 6. По заданной функции проводимости построить наиболее простую схему.

54. f(1,0,1)=f(0,1,1)=f(1,1,1)=1

S =

X

Y

Z

Задание 7. Упростить схему.

S =

Упрощенная схема:

Задание 8. Для заданного графа построить(предварительно пронумеровав вершины графа):

1. матрицу смежности,

2. матрицу инциденций,

3. матрицы достижимостей и контрдостижимостей

4. найти число внутренней устойчивости, считая граф неориентированным

5. найти число внешней устойчивости, считая граф неориентированным.

Матрица смежности

С = (С_ij) =

	1	2	3	4	5
1	0	1	0	0	1
2	0	0	1	1	0
3	0	0	0	1	0
4	1	0	0	0	0
5	0	1	0	1	0

Матрица достижимостей

	1	2	3	4	5
1	1	1	1	1	1
2	1	1	1	1	1
3	1	1	1	1	1
4	1	1	1	1	1
5	1	1	1	1	1

R = (r_ij) =

Матрица контрдостижимостей

Q = (q_ij) =

	1	2	3	4	5
1	1	1	1	1	1
2	1	1	1	1	1
3	1	1	1	1	1
4	1	1	1	1	1
5	1	1	1	1	1

Матрица инцидентности

	е1	е2	е3	е4	е5	е6	е7	е8
1	1	0	0	0	1	0	1	0
2	1	1	0	0	0	1	0	1
3	0	1	1	0	0	0	0	0
4	0	0	1	1	0	0	1	1
5	0	0	0	1	1	1	0	0

Число внутренней устойчивости η(G)

Ψ₁ = {x₁ ; x₃} Ψ₂ = {x₃ ; x₅} η(G) = 2

Число внешней устойчивости 5

Задание 8. Для графов G₁ и G₂ найти ;.

X₁ = {X₁ ; X₂ ; X₃} , Г₁(Х₁) = {Х₂} , Г₁(Х₂) = {Х₃} , Г₁(Х₃) = 

X₂ = {X₁ ; X₂ ; X₃} , Г₂(Х₁) = {Х₂ ; Х₃} , Г₂(Х₂) = {Х₃} , Г₂(Х₃) = 

X₁ X₂ = {X₁ ; X₂ ; X₃} , Г₁(Х₁) Г₂(Х₁) = {Х₂ ; Х₃} , Г₁(Х₂) Г₂(Х₂) = {Х₃} , Г₁(Х₃) Г₂(Х₃) = 

X₁ X₂ = {X₁ ; X₂ ; X₃} , Г₁(Х₁) Г₂(Х₁) = {Х₂} , Г₁(Х₂) Г₂(Х₂) = {Х₃} , Г₁(Х₃) Г₂(Х₃) = 

Тест. Вариант 4

1.Построить таблицы истинностей для формул

X	Y	Z
0	0	0	1	1	1	1	0	1	0
0	0	1	1	0	1	1	0	1	1
0	1	0	1	1	1	1	1	1	0
0	1	1	1	0	1	1	1	0	1
1	0	0	0	1	0	1	0	1	0
1	0	1	0	0	0	1	0	1	1
1	1	0	0	1	1	0	1	1	0
1	1	1	0	0	1	0	1	0	1

3.Доказать равносильность формул

X|Y = X

X	Y	X|Y
0	0	1
0	1	1
1	0	1
1	1	0

X	Y		X
0	0	1	1
0	1	0	1
1	0	1	1
1	1	0	0

СДНФ: Y ∪ X

СКНФ:

6. Найти совершенные нормальные формы для функций, заданных таблицей истинностей и формулами

X	Y	Z
0	0	0	1	0	1	0	1
0	0	1	1	1	0	1	0
0	1	0	0	1	1	1	0
0	1	1	0	1	0	1	0
1	0	0	0	1	0	1	0
1	0	1	0	1	1	0	1
1	1	0	1	0	0	1	1
1	1	1	1	1	1	1	0

СДНФ:

СКНФ:

9. Задать графы g1 и g2 г)структурой смежности.

G1 струтура смежности:

1: 4

2: 5

3: 4, 5

4: 1, 3

5: 2, 3

G2 струтура смежности:

1: 4

2: 5

3: 5

4: 3

5:

10. Определить в графе g3 циклический маршрут, цикл, простой цикл, приняв вершину х3 за начало.

Циклический маршрут: X3 – X4 – X5 – X2 – X6 – X7 – X1 – X2 – X3

Цикл: X3 – X4 – X5 – X2 – X1 – X7 – X6 – X2 – X3

Простой цикл: X3 – X4 – X5 – X2 – X3