Контрольная работа. Решение Решение Найдем множество корней уравнения Методом подбора получаем Тогда Откуда

• Название: Решение Решение Найдем множество корней уравнения Методом подбора получаем Тогда Откуда
• Анкор: Контрольная работа
• Дата: 09.02.2022
• Размер: 3.05 Mb.
• Имя файла: 3718939.docx
• Тип: Решение; #356460

Контрольные работы по дисциплине «Дискретная математика»

для студентов ИИФО специальностей 09.03.01 и 11.03.02

Стр5из19

КОНТРОЛЬНАЯ РАБОТА

1. 
   ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
   
   1. 
      Основные понятия теории множеств. Способы задания множеств. Операции над множествами
      

ЗАДАНИЕ 1.1.



Решение:

Решение:

Найдем множество корней уравнения



Методом подбора получаем





Тогда



Откуда















Поскольку и и , то имеем множества общего положения.

2. 
   Диаграммы Эйлера-Венна
   

ЗАДАНИЕ 1.2

Используя диаграммы Эйлера – Венна, опишите множество, соответствующее части диаграммы, закрашенной серым цветом.




Решение:

Имеем множество тех элементов, которые не принадлежат ни множеству А, ни множеству В, но принадлежат множеству С и универсальному множеству. Таким образом, имеем объединение множеств



И :



Тогда данное множество имеет вид


Ответ:

ЗАДАНИЕ 1.3

Решение:



Тогда множество А – множество всех точек круга с центром (2,0) радиуса 2.




Множество В – множество всех точек круга с центром (-2,0) радиуса 2.




Множество С представляет собой квадрат


Изобразим множество :


Тогда множество имеет вид:



Множество имеет вид:



Откуда множество имеет вид:

3. 
   Соответствия. Декартово произведение
   

ЗАДАНИЕ 1

Решение:

Найдем



По определению композиции,

Найдем композицию



Найдем



Ответ: , ,

4. 
   Отношения
   

ЗАДАНИЕ 1.5

Решение:

1. Изобразим данное отношение графом:

2. Для того, чтобы отношение было отношением эквивалентности, необходимо чтобы оно было рефлексивно, симметрично и транзитивно.

Из того, что отношение рефлексивно, поскольку пары (4,1), (2,3), (4,2) принадлежат отношению получаем, что этому отношению должны также принадлежать пары (4,4), (1,1), (2,2), (3,3), (5,5). Из того, что отношение симметрично, поскольку пары (4,1), (2,3), (4,2) принадлежат отношению получаем, что этому отношению должны также принадлежать пары (1,4), (3,2), (2,4).

Тогда отношение будет включать отношение

Поскольку отношение должно быть транзитивным, так как пары (4,2) и (2,3) , а также (1,4) и (4,2) входят в него, необходимо его дополнить еще парами (4,3), (3,4), (1,2), (2,1). Но тогда в в нем также должны писутствовать пары (3,1), (1,3).

Тогда

Изобразим полученное отношение графически:

Запишем фактор-множество:

3. 
   Построим отношение частичного порядка на основе , путем добавления минимального количества новых пар, чтобы выполнялись условия рефлексивности, транзитивности, антисимметричности:
   

Изобразим отношение графически:

Минимальные элементы:

Максимальные элементы:

Пары несравнимых элементов:

(1,5), (2,5), (3,5), (4,5), (1,3), (1,2)

4. 
   Построим отношение на основе отношении . Для этого добавим пары, которых не хватает для свойства связности.
   

Построим граф полученного отношения:

Наименьший элемент: 4, наибольший элемент:5.

5. 
   На основе отношения доопределим его до отношения строгого порядка. Добавим минимальное количество пар, чтобы отношение было антирефлексивным, ассимметричным и транзитивным:
   

Изобразим полученное отношение графически:

Доопределим отношение до отношение строгого линейного порядка:



Изобразим полученное отношение графически:

2. БУЛЕВЫ АЛГЕБРЫ.

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

1. 
   Булевы функции
   

ЗАДАНИЕ 2.1

Используя таблицы истинности, проверить эквивалентность булевых формул.

Определить существенные и фиктивные переменные


Решение:

Построим таблицу истинности для первой формулы:

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

Поскольку при одинаковых наборах переменных формулы принимают одинаковые значения, то они эквивалентны.
Определим, является ли переменная существенной или фиктивной.

Поскольку

, то – существенная переменная.

Поскольку , то переменная является существенной.

Поскольку , то переменная является существенной. Таким образом, фиктивных переменных функция не имеет.

2. 
   Представление булевых функций разложением по переменным
   

ЗАДАНИЕ 2.2

Для булевой функции, заданной вектором значений, определить:

1. 
   СДНФ,
   
2. 
   СКНФ,
   
3. 
   полином Жегалкина.
   

Решение:



Решение:

Построим таблицу истинности для данной функции

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, возьмем с отрицанием.

Получим СДНФ:



Для построения СКНФ для каждого набора переменных, при котором функция равна 0, записываем сумму, причем переменные, которые имеют значение 1, возьмем с отрицанием.

Получим СКНФ:



Построим полином Жегалкина при помощи метода неопределенных коэффициентов.

Будем искать полном в виде:





Тогда

– полином Жегалкина данной функции.

3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. ОПТИМИЗАЦИЯ НА ГРАФАХ

   1. 
      Основные понятия теории графов
      

ЗАДАНИЕ 3.1

В таблице для каждого варианта заданы декартовы координаты вершин графа и перечислены ребра графа. Граф неориентирован. Следует построить граф на плос- кости xOyи найти:

1. 
   таблицу степеней вершин;
   
2. 
   матрицу смежности;
   
3. 
   матрицу инцидентности;
   
4. 
   таблицу расстояний в графе;
   
5. 
   определить радиус и центр графа.
   

Решение:

Построим данный граф:


Построим таблицу степеней вершин:

	3	3	4	3	2	3	2	0

Построим матрицу смежности для данного графа:


Построим матрицу инцидентности для данного графа. Строки будут отвечать вершинам, столбцы ­– ребрам. Получим:

	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

Тогда радиус графа равен



Тогда центр графа составляют множество вершины

2. 
   Задачи оптимизации на графах
   

ЗАДАНИЕ 3.2

Для графа, описанного в задании 3.1 вычислить:

1. 
   Минимальное остовное дерево.
   
2. 
   Кратчайший путь из одного источника.
   

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

Решение:

Изобразим данный нагруженный граф:



Построим остовное дерево минимального веса. Построение начнем с ребра с минимальным весом . Порядок присоединения ребер к остову: , , , , :



Вес остова равен



Найдем кратчайший путь из вершины до вершин :

Вершины снабжаем пометками, и в графе будут присутствовать метки , пока не найден путь.

Вершины, которые будут становиться постоянными, выделяем знаком *.


Вершина стала постоянной. Метки смежных вершин меняем соответственно на (4, х1), ( , х1), ( , х1):

Минимальное из расстояний , поэтому вершина становится постоянной.



Вычислим расстояние до смежных с вершин:



:

Минимальное из расстояний , поэтому вершина становится постоянной.



Вычислим расстояния от вершины до смежных вершин:



Вычислим расстояние от вершины до смежных вершин:



Поскольку , то метка вершины становится

Минимальное из расстояний , поэтому вершина становится постоянной.


Вычислим расстояние от вершины до вершины : и от вершины до вершины : .

Поскольку , то метка вершины

Минимальное из расстояний , поэтому вершина становится постоянной.



Таким образом, получены минимальные расстояния из вершины до остальных вершин:

:

:

: 4

:

:

: