|
Дискретка. Задание 1 Докажите тождества, используя только определения операций над множествами. 1 2 то невозможно будет определить кортеж, принадлежащий а значит, доказать соотношение становится невозможно. Задание 2
![](70227_html_m2a7690f7.gif)
![](70227_html_m2a7690f7.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_m71889984.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_m2a7690f7.gif) ![](70227_html_4467870e.gif) ![](70227_html_4467870e.gif) ![](70227_html_4467870e.gif) ![](70227_html_4467870e.gif) ![](70227_html_4467870e.gif) ![](70227_html_4467870e.gif) ![](70227_html_4467870e.gif) ![](70227_html_50f95d74.gif) Задание 1:
Докажите тождества, используя только определения операций над множествами.
1) ![](70227_html_m1ed487f7.gif)
2)![](70227_html_1924fba0.gif) ![](70227_html_64cf5a79.gif) то невозможно будет определить кортеж, принадлежащий а значит, доказать соотношение становится невозможно.
Задание 2:
Докажите утверждение.
(0,1] [0, ![](70227_html_1a935a3b.gif)
Для доказательства эквивалентности необходимо построить биекцию между этими интервалами. Этой биекцией будет функция:
![](70227_html_6d7ada19.gif)
Так как между точками интервалов существует взаимно-однозначное соответствие, то (0,1] [0, ).
Задание 3:
Докажите методом математической индукции, что кратно 9 для всех .
Найдем базис индукции:
n=0
– кратно 9
Предположим, что кратно 9 для некоторого n.
Докажем, что также кратно 9.![](70227_html_m190edb86.gif)
– кратно 9 по предположению индукции
– кратно 9.
– кратно 9.
Значит, так как справедливость утверждения доказана для n+1, то верно утверждение, что кратно 9 для всех .
Задание 4:
A={a,b,c}, B={1,2,3,4}, Изобразите , графически. Найдите [ ]. Проверьте с помощью матрицы [ ], является ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?
![](70227_html_mc360c57.gif)
1
2
3
4 a
b
c
4
4
3
1
2
1
2
3 [ ]= [ ]=![](70227_html_m98f9c12.gif)
[ ]= ![](70227_html_m589b475e.gif) ![](70227_html_7b27bc0d.gif)
![](70227_html_m5145080f.gif)
1) [ ]= – по диагонали нет нулей ![](70227_html_6a2e2eb1.gif) – рефлексивно.
2) – поэтому – симметрично. 3) – неантисимметрично.
4)
![](70227_html_m468edcc4.gif) ![](70227_html_7b27bc0d.gif)
Задание 5:
Найдите область определения, область значений отношения P. Является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным?
![](70227_html_m58dd7d46.gif)
Область определения:
![](70227_html_41ef3b39.gif)
Область значений:
![](70227_html_m1e014905.gif)
1) P – рефлексивно.
![](70227_html_71c49a80.gif)
3) Так как но поэтому P – неантисимметрично. 4) ![](70227_html_48c3211a.gif) ![](70227_html_6707b6c8.gif) ![](70227_html_7b591ec3.gif) ![](70227_html_151efd7c.gif)
P – транзитивно.
Задание 6:
Является ли алгеброй следующий набор B= ?
Так как 0 R, но при делении на ноль выходим за границы множества R, поэтому операция деления не замкнута на множестве R. Значит, набор B= не является алгеброй.
Задание 7:
Постройте подсистему B(X), если B=< ;+, >, X={2}
Подставим элементы из X в термы из B.
2+2+2+…=2n, n![](70227_html_756e482b.gif)
, n![](70227_html_756e482b.gif)
Получим, что B(X)= .
Задание 8:
Используя многомодульную арифметику с вектором оснований , вычислить , , , . Каков знак числа ?
, , , ![](70227_html_47f8845a.gif)
![](70227_html_m71873c1c.gif)
(73 (mod 7) + 36 (mod 7))(mod 7) = (3 + 1)(mod 7) = 4
(73 (mod 11) + 36 (mod 11))(mod 11) = (7 + 3)(mod 11) = 10
(73 (mod 3) + 36 (mod 3))(mod 3) = (1 + 0)(mod 3) = 1
(73 (mod 2) + 36 (mod 2))(mod 2) = (1 + 0)(mod 2) = 1
![](70227_html_m767a5d38.gif)
![](70227_html_7dc07ee1.gif)
(73 (mod 7) – 36 (mod 7))(mod 7) = (3 – 1)(mod 7) = 2
(73 (mod 11) – 36 (mod 11))(mod 11) = (7 – 3)(mod 11) = 4
(73 (mod 3) – 36 (mod 3))(mod 3) = (1 – 0)(mod 3) = 1
(73 (mod 2) – 36 (mod 2))(mod 2) = (1 – 0)(mod 2) = 1
![](70227_html_m6296a9d3.gif)
![](70227_html_m559228a5.gif)
( 73) (mod 7) = 2
( 73) (mod 11) = 10
( 73) (mod 3) = 0
( 73) (mod 2) = 1
![](70227_html_m6d944875.gif)
![](70227_html_m133a11e4.gif)
![](70227_html_45fea34a.gif) (mod 7) = 5 (mod 7) = 5
![](70227_html_21eb7b3d.gif) (mod 11) = 2 (mod 11) = 2
![](70227_html_m4c5f5757.gif) (mod 3) = 2 (mod 3) = 2
![](70227_html_3892a25f.gif) (mod 2) = 1 (mod 2) = 1
![](70227_html_m52c4211f.gif)
![](70227_html_m493b9a5f.gif)
![](70227_html_45fea34a.gif) (mod 7) (mod 7))(mod 7) = (( 6)(mod 7) –
– 3)(mod 7))(mod 7) = (5 – 1)(mod 7) = 4
![](70227_html_21eb7b3d.gif) (mod 11) (mod 11))(mod 11) = (( 6)(mod 11) –
– 7)(mod 11))(mod 11) = (1 – 2)(mod 11) = 10
![](70227_html_m4c5f5757.gif) (mod 3) (mod 3))(mod 3) = (( 1)(mod 3) –
– 1)(mod 3))(mod 3) = (2 – 2)(mod 3) = 0
![](70227_html_3892a25f.gif) (mod 2) (mod 2))(mod 2) = (( 1)(mod 2) –
– 1)(mod 2))(mod 2) = (0 – 1)(mod 2) = 1
![](70227_html_m430d19a6.gif)
Определим знак числа ![](70227_html_47f8845a.gif)
Очевидно, что 6
[0, 1, 1, 0] или [1, 1, 0]
Вектор оснований сокращаем до = [11, 3, 2]
Для вычисления вычислим
[8, 1, 1]
Умножим на этот элемент, в результате получим [8, 1, 0]
Таким образом, 8
Вычитая из последнего выражения, получаем [0, 2, 0] или [2, 0]
Вектор оснований = [3, 2]
Вычисляем ![](70227_html_73aa953e.gif)
[2, 1]
Умножаем на полученный элемент, в результате получаем [4, 0]
Поэтому 4
[0, 0] или [0] для вектора оснований = [2]
Находим ![](70227_html_6c62fbbe.gif)
[1]
При умножении на получаем [0]
Отсюда следует, что 0
Поэтому число x – положительное.
Задание 9:
Даны графы и . Найдите , , , . Для графа найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1. 3 2 1 4 3 2 1
![](70227_html_2c955827.gif)
(4,3)
(3,3)
(2,3)
(1,3)
(4,2)
(3,2)
(2,2)
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
![](70227_html_m10880c2e.gif)
3
2
1
![](70227_html_m27a6a30c.gif)
![](70227_html_4f805405.gif)
4
3
2
1
4
3
2
1 Рассмотрим граф :
Матрица смежности A=![](70227_html_ba24e69.gif) 4
1
3
2
![](70227_html_7d6d879b.gif)
![](70227_html_56f94478.gif)
![](70227_html_m1ca58e18.gif)
![](70227_html_m7aefa15c.gif)
![](70227_html_m7e840535.gif)
![](70227_html_4f809d1a.gif)
![](70227_html_m555d3988.gif)
![](70227_html_m53a5c3ae.gif)
![](70227_html_m76876748.gif) – матрица инцидентности B=E+A+ =![](70227_html_3e91d295.gif) ![](70227_html_6543c570.gif)
– матрица сильных компонент.
– матрица маршрутов длины 2.
Маршруты длины 2, исходящие из вершины 1:
(1;3;2), (1;3;3), (1;3;4).
Задание 10:
Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?
3
4 2 1
5
6
7
8 Получим остов графа. Для этого удалим из графа 12–8+1=5 ребер. 1
1
2
4
5
6
7
8
2
3
4
5
6
7
8
9
10
11
12
3
Матрица фундаментальных циклов:
![](70227_html_m32ed6fcc.gif)
C= ![](70227_html_m3c9464ea.gif) ![](70227_html_60f8de8.gif) Матрица фундаментальных разрезов:
![](70227_html_m17cf667e.gif)
K= ![](70227_html_m5d32e1f8.gif) ![](70227_html_m5c2a1bf8.gif)
Диаметр d(G)=3
Радиус r(G)=2
Минимальное множество покрывающих цепей графа – 2.
3,2,1,5,3,4,6,5,4,8,1
6,7,8
Граф не является эйлеровым, так как степени не всех его вершин четные.
Граф планарный.
1
3
2
4
5
6
7
8 |
|
|