Главная страница

Дискретка. Задание 1 Докажите тождества, используя только определения операций над множествами. 1 2 то невозможно будет определить кортеж, принадлежащий а значит, доказать соотношение становится невозможно. Задание 2


Скачать 241.68 Kb.
НазваниеЗадание 1 Докажите тождества, используя только определения операций над множествами. 1 2 то невозможно будет определить кортеж, принадлежащий а значит, доказать соотношение становится невозможно. Задание 2
Дата12.03.2019
Размер241.68 Kb.
Формат файлаdocx
Имя файлаДискретка.docx
ТипДокументы
#70227




Задание 1:

Докажите тождества, используя только определения операций над множествами.

1)

2)то невозможно будет определить кортеж, принадлежащий а значит, доказать соотношение становится невозможно.

Задание 2:

Докажите утверждение.

(0,1]

[0,

Для доказательства эквивалентности необходимо построить биекцию между этими интервалами. Этой биекцией будет функция:



Так как между точками интервалов существует взаимно-однозначное соответствие, то (0,1] [0,).

Задание 3:

Докажите методом математической индукции, что кратно 9 для всех .

Найдем базис индукции:

n=0

– кратно 9

Предположим, что кратно 9 для некоторого n.

Докажем, что также кратно 9.

– кратно 9 по предположению индукции

– кратно 9.

– кратно 9.

Значит, так как справедливость утверждения доказана для n+1, то верно утверждение, что кратно 9 для всех .

Задание 4:

A={a,b,c}, B={1,2,3,4}, Изобразите , графически. Найдите []. Проверьте с помощью матрицы [], является ли отношение рефлексивным, симметричным, антисимметричным, транзитивным?




1

2

3

4
a

b

c

4

4

3

1

2

1

2

3
[]= []=

[]=



1) []= – по диагонали нет нулей – рефлексивно.

2) – поэтому – симметрично.
3) – неантисимметрично.

4)



Задание 5:

Найдите область определения, область значений отношения P. Является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным?



Область определения:



Область значений:



1) P – рефлексивно.



3) Так как но поэтому P – неантисимметрично.
4)
P – транзитивно.

Задание 6:

Является ли алгеброй следующий набор B=?

Так как 0R, но при делении на ноль выходим за границы множества R, поэтому операция деления не замкнута на множестве R. Значит, набор B= не является алгеброй.

Задание 7:

Постройте подсистему B(X), если B=<;+, >, X={2}

Подставим элементы из X в термы из B.

2+2+2+…=2n, n

, n

Получим, что B(X)=.

Задание 8:

Используя многомодульную арифметику с вектором оснований , вычислить , , , . Каков знак числа ?

, , ,


(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




(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




(73) (mod 7) = 2

(73) (mod 11) = 10

(73) (mod 3) = 0

(73) (mod 2) = 1




(mod 7) = 5 (mod 7) = 5

(mod 11) = 2 (mod 11) = 2

(mod 3) = 2 (mod 3) = 2

(mod 2) = 1 (mod 2) = 1




(mod 7) (mod 7))(mod 7) = ((6)(mod 7) –

3)(mod 7))(mod 7) = (5 – 1)(mod 7) = 4

(mod 11) (mod 11))(mod 11) = ((6)(mod 11) –

7)(mod 11))(mod 11) = (1 – 2)(mod 11) = 10

(mod 3) (mod 3))(mod 3) = ((1)(mod 3) –

1)(mod 3))(mod 3) = (2 – 2)(mod 3) = 0

(mod 2) (mod 2))(mod 2) = ((1)(mod 2) –

1)(mod 2))(mod 2) = (0 – 1)(mod 2) = 1



Определим знак числа

Очевидно, что 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]

Вычисляем

[2, 1]

Умножаем на полученный элемент, в результате получаем [4, 0]

Поэтому 4

[0, 0] или [0] для вектора оснований = [2]

Находим

[1]

При умножении на получаем [0]

Отсюда следует, что 0

Поэтому число x – положительное.

Задание 9:

Даны графы и . Найдите , , , . Для графа найдите матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.

3

2

1

4

3

2

1




(4,3)

(3,3)

(2,3)

(1,3)

(4,2)

(3,2)

(2,2)

(1,2)

(1,1)

(2,1)

(3,1)

(4,1)



3

2

1





4

3

2

1

4

3

2

1
Рассмотрим граф :

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

1

3

2
















– матрица инцидентности
B=E+A+=

– матрица сильных компонент.

– матрица маршрутов длины 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

Матрица фундаментальных циклов:



C=
Матрица фундаментальных разрезов:



K=

Диаметр 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


написать администратору сайта