StudyDocs.ru Logo

Контрольная ОДМИТА, 4 вариант.docx


Министерство образования Республики БеларусьУчреждение образованияБелорусский Государственный университет информатикии радиоэлектроники



Контрольная работа + ТестПо курсу “Основы дискретной математики и теории алгоритмов





Контрольная работа. Вариант 4Задание 1. Используя диаграммы Эйлера-Венна, решить задачу.4. Экзамен по математике содержал три задачи: по алгебре, геометрии и тригонометрии. Из 800 абитуриентов задачу по алгебре решили 250 человек, по алгебре или геометрии - 660 человек, по две задачи решили 400 человек, из них две задачи по алгебре и геометрии решили 150 человек, по алгебре и тригонометрии 50 человек; ни один абитуриент не решил все задачи; 20 абитуриентов не решили ни одной задачи; только по тригонометрии задачи решили 120 человек. Сколько решили только одну задачу? Сколько человек решили задачи по геометрии?РешениеА – алгебра, Г – геометрия, Т – тригонометрия.<Object: word/embeddings/oleObject1.bin>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. <Object: word/embeddings/oleObject2.bin> = U B ( = U (A )\А = U = UЗадание 3. С помощью ДНФ и КНФ установить выполнимость формул.24. A<Object: word/embeddings/oleObject3.bin>B<Object: word/embeddings/oleObject4.bin>CC<Object: word/embeddings/oleObject5.bin>








Полученная ДНФ не удовлетворяет Теореме номер 2 следовательно формула является выполнимой.
Задание 4. С помощью совершенных нормальных форм установить, равносильны ли формулы.34. = A (B<Object: word/embeddings/oleObject6.bin>); = AB.

АВС
00101011
01011001
01100111
00011011
10101011
11011000
11100111
10011011

СДНФ = СКНФ =



АВ
001
011
100
111
СДНФ = СКНФ = Т. к. СКНФ формул отличаются то они (формулы) не равносильны.
Задание 5. Проверить правильность рассуждения любым из трех способов.44.Если функция непрерывна на данном интервале и имеет одинаковые знаки на концах данного интервала, то внутри его функция не обращается в ноль. Данная функция непрерывна, следовательно, на концах интервала функция имеет разные знаки.А — ф-ция непрерывна на данном интервалеВ — ф-ция не обращается в ноль на данном интервалеС — ф-ция имеет одинаковые знаки на концах данного интервала Р1А Р2 Q

АВС
00010101
00100101
01010101
01100101
10010111
10101001
11010111
11101110

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

Задание 6. По заданной функции проводимости построить наиболее простую схему.54. f(1,0,1)=f(0,1,1)=f(1,1,1)=1S =



Задание 7. Упростить схему.<Object: word/embeddings/oleObject7.bin>
S = Упрощенная схема:Задание 8. Для заданного графа построить(предварительно пронумеровав вершины графа):1. матрицу смежности,2. матрицу инциденций,3. матрицы достижимостей и контрдостижимостей4. найти число внутренней устойчивости, считая граф неориентированным5. найти число внешней устойчивости, считая граф неориентированным.<Object: word/embeddings/oleObject8.bin>
Матрица смежностиС = (Сij) =
12345
101001
200110
300010
410000
501010

Матрица достижимостей
12345
111111
211111
311111
411111
511111
R = (rij) =




Матрица контрдостижимостейQ = (qij) =
12345
111111
211111
311111
411111
511111





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

е1е2е3е4е5е6е7е8
110001010
211000101
301100000
400110011
500011100




Число внутренней устойчивости η(G) Ψ1 = {x1 ; x3} Ψ2 = {x3 ; x5} η(G) = 2Число внешней устойчивости 5
Задание 8. Для графов G1 и G2 найти <Object: word/embeddings/oleObject9.bin>;<Object: word/embeddings/oleObject10.bin>.<Object: word/embeddings/oleObject11.bin>X1 = {X1 ; X2 ; X3} , Г11) = {Х2} , Г1(Х2) = {Х3} , Г1(Х3) = X2 = {X1 ; X2 ; X3} , Г21) = {Х2 ; Х3} , Г2(Х2) = {Х3} , Г2(Х3) =
X1 X2 = {X1 ; X2 ; X3} , Г11) Г21) = {Х2 ; Х3} , Г1(Х2) Г2(Х2) = {Х3} , Г1(Х3) Г2(Х3) = X1 X2 = {X1 ; X2 ; X3} , Г11) Г21) = {Х2} , Г1(Х2) Г2(Х2) = {Х3} , Г1(Х3) Г2(Х3) =
<Object: word/embeddings/oleObject12.bin>



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

XYZ
0001111010
0011011011
0101111110
0111011101
1000101010
1010001011
1100110110
1110010101

3.Доказать равносильность формулX|Y = X
XYX|Y
001
011
101
110


XYX
0011
0101
1011
1100

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



XYZ
00010101
00111010
01001110
01101010
10001010
10101101
11010011
11111110

СДНФ: СКНФ:
9. Задать графы G1 и G2 гтруктурой смежности.






G1 струтура смежности:1: 42: 53: 4, 54: 1, 35: 2, 3




G2 струтура смежности:1: 42: 53: 54: 35:





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





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