Контрольная работа. Решение Решение Найдем множество корней уравнения Методом подбора получаем Тогда Откуда
![]()
|
![]() ![]() ![]() Контрольные работы по дисциплине «Дискретная математика» для студентов ИИФО специальностей 09.03.01 и 11.03.02 Стр5из19 КОНТРОЛЬНАЯ РАБОТА ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ Основные понятия теории множеств. Способы задания множеств. Операции над множествами ![]() ![]() Решение: Решение: Найдем множество корней уравнения ![]() Методом подбора получаем ![]() ![]() ![]() Тогда ![]() Откуда ![]() ![]() ![]() ![]() ![]() ![]() ![]() Поскольку ![]() ![]() ![]() Диаграммы Эйлера-Венна ЗАДАНИЕ 1.2Используя диаграммы Эйлера – Венна, опишите множество, соответствующее части диаграммы, закрашенной серым цветом. ![]() Решение: Имеем множество тех элементов, которые не принадлежат ни множеству А, ни множеству В, но принадлежат множеству С и универсальному множеству. Таким образом, имеем объединение множеств ![]() ![]() И ![]() ![]() Тогда данное множество имеет вид ![]() Ответ: ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 1 |
Построим таблицу истинности для второй формулы:
![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
0 | 0 | 0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 |
Поскольку при одинаковых наборах переменных формулы принимают одинаковые значения, то они эквивалентны.
Определим, является ли переменная
![](356460_html_d8927c486a96be86.gif)
Поскольку
![](356460_html_82c5368c8e15fe2b.gif)
![](356460_html_d8927c486a96be86.gif)
Поскольку
![](356460_html_87996d578dd833b5.gif)
![](356460_html_b77d76b63a325c2f.gif)
Поскольку
![](356460_html_ec3ac82dee3b3efc.gif)
![](356460_html_f3e71acd2f0b12c1.gif)
Представление булевых функций разложением по переменным
ЗАДАНИЕ 2.2
Для булевой функции, заданной вектором значений, определить:
СДНФ,
СКНФ,
![](356460_html_6e6a60ee48b06a1.png)
Решение:
![](356460_html_bf2a3b2911ba8ec7.gif)
Решение:
Построим таблицу истинности для данной функции
![]() | ![]() | ![]() | ![]() |
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
Для построения СДНФ для каждого набора переменных, при котором функция равна 1, записываем произведение, причем переменные, которые имеют значение 0, возьмем с отрицанием.
Получим СДНФ:
![](356460_html_7066438036a13091.gif)
Для построения СКНФ для каждого набора переменных, при котором функция равна 0, записываем сумму, причем переменные, которые имеют значение 1, возьмем с отрицанием.
Получим СКНФ:
![](356460_html_ebe391f3e8984d54.gif)
Построим полином Жегалкина при помощи метода неопределенных коэффициентов.
Будем искать полном в виде:
![](356460_html_8f1920c21f3d8723.gif)
![](356460_html_dabe9c5b45c77bb5.gif)
Тогда
![](356460_html_a9065e762a339948.gif)
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. ОПТИМИЗАЦИЯ НА ГРАФАХ
Основные понятия теории графов
ЗАДАНИЕ 3.1
В таблице для каждого варианта заданы декартовы координаты вершин графа и перечислены ребра графа. Граф неориентирован. Следует построить граф на плос- кости xOyи найти:
таблицу степеней вершин;
матрицу смежности;
матрицу инцидентности;
таблицу расстояний в графе;
![](356460_html_fdf41536dc0f7897.png)
Решение:
Построим данный граф:
![](356460_html_25760cdf6bd61caa.png)
Построим таблицу степеней вершин:
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | 3 | 3 | 4 | 3 | 2 | 3 | 2 | 0 |
Построим матрицу смежности для данного графа:
![](356460_html_f9e8254d92103d0b.gif)
Построим матрицу инцидентности для данного графа. Строки будут отвечать вершинам, столбцы – ребрам. Получим:
![](356460_html_e05f730dc1eebdb.gif)
| ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | 0 | 1 | 1 | 1 | 2 | 3 | 2 | 3 |
![]() | 1 | 0 | 1 | 2 | 1 | 2 | 3 | 3 |
![]() | 1 | 1 | 0 | 1 | 2 | 1 | 2 | 2 |
![]() | 1 | 2 | 1 | 0 | 3 | 2 | 1 | 3 |
![]() | 2 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
![]() | 3 | 2 | 1 | 2 | 1 | 0 | 1 | 3 |
![]() | 2 | 3 | 2 | 1 | 2 | 1 | 0 | 3 |
Тогда радиус графа равен
![](356460_html_b3ace5957fb130f7.gif)
Тогда центр графа составляют множество вершины
![](356460_html_b41359c1fa5be508.gif)
Задачи оптимизации на графах
ЗАДАНИЕ 3.2
Для графа, описанного в задании 3.1 вычислить:
Минимальное остовное дерево.
Кратчайший путь из одного источника.
Для решения задач данного раздела считать граф ориентированным (направле- ние дуги отмечается упорядоченной парой вершин, формирующих ребро). Вес дуги равен длине отрезка между вершинами графа.
Решение:
Изобразим данный нагруженный граф:
![](356460_html_c7134bdcc56e772f.png)
Построим остовное дерево минимального веса. Построение начнем с ребра с минимальным весом
![](356460_html_f804a47d4ea56333.gif)
![](356460_html_f4b8c5724a81aad8.gif)
![](356460_html_154e9564df9d1348.gif)
![](356460_html_53dea83761888de4.gif)
![](356460_html_3353aeaa4ba1c34c.gif)
![](356460_html_d67ed4aa49b8b1e6.gif)
![](356460_html_12de6941caf2059.png)
Вес остова равен
![](356460_html_51f30d435986bc19.gif)
Найдем кратчайший путь из вершины
![](356460_html_431bf3c3b51729f6.gif)
![](356460_html_46a68db37af050b.gif)
Вершины снабжаем пометками, и в графе будут присутствовать метки
![](356460_html_5ba281c115063dfe.gif)
Вершины, которые будут становиться постоянными, выделяем знаком *.
![](356460_html_54f97f5652be950b.png)
Вершина
![](356460_html_431bf3c3b51729f6.gif)
![](356460_html_cd618cea89640e85.gif)
![](356460_html_64ccc0f0918a82e8.gif)
Минимальное из расстояний
![](356460_html_41ef6f85a9e5b037.gif)
![](356460_html_465bc29d2c8bfe5f.gif)
![](356460_html_61a5a3a1822e27e8.png)
Вычислим расстояние до смежных с
![](356460_html_465bc29d2c8bfe5f.gif)
![](356460_html_aa4192a8cbaeb4b7.gif)
![](356460_html_ef2c131978cd866c.gif)
Минимальное из расстояний
![](356460_html_17b390b107d6d52a.gif)
![](356460_html_b41359c1fa5be508.gif)
![](356460_html_d1ed2a835549ed2b.png)
Вычислим расстояния от вершины
![](356460_html_cd436c5f3f12da2c.gif)
![](356460_html_6d4c650ad4a7593.gif)
Вычислим расстояние от вершины
![](356460_html_642f83c4c5a50bbd.gif)
![](356460_html_97f5216c36b5e794.gif)
Поскольку
![](356460_html_c304478cbd8db41c.gif)
![](356460_html_3d73effe37d14022.gif)
![](356460_html_36a7666320223b9e.gif)
Минимальное из расстояний
![](356460_html_171bbe5bb0b60a18.gif)
![](356460_html_ef372d06d63c2fce.gif)
![](356460_html_faac4c17f5d5298a.png)
Вычислим расстояние от вершины
![](356460_html_aaf48c4b12bbb22f.gif)
![](356460_html_7d85b3a207215f09.gif)
![](356460_html_144b82f8b89b5f38.gif)
![](356460_html_3d73effe37d14022.gif)
![](356460_html_7d85b3a207215f09.gif)
![](356460_html_1093a7490e96b4bc.gif)
Поскольку
![](356460_html_ae24f6f9fde5f4a1.gif)
![](356460_html_7d85b3a207215f09.gif)
![](356460_html_a9fb7f4ac0cd8b7e.gif)
Минимальное из расстояний
![](356460_html_372c561a73e41065.gif)
![](356460_html_1d7fb65a00ec3499.gif)
![](356460_html_c1cf2825e0259cd4.png)
Таким образом, получены минимальные расстояния из вершины
![](356460_html_431bf3c3b51729f6.gif)
![](356460_html_465bc29d2c8bfe5f.gif)
![](356460_html_64ccc0f0918a82e8.gif)
![](356460_html_b41359c1fa5be508.gif)
![](356460_html_cd618cea89640e85.gif)
![](356460_html_ef372d06d63c2fce.gif)
![](356460_html_1d7fb65a00ec3499.gif)
![](356460_html_93e17621777b8c2.gif)
![](356460_html_78b04eb3f356ddc3.gif)
![](356460_html_6dcb02d26be1d7b0.gif)
![](356460_html_384612efc3a6c2e8.gif)
![](356460_html_ed8cfe9c5e91de6d.gif)