Типовые расчеты по дискретной математике

• Название: Типовые расчеты по дискретной математике
• Дата: 29.04.2022
• Размер: 0.71 Mb.
• Имя файла: 4_11_Variant_5 (1).doc
• Тип: Документы; #504344
• страница: 1 из 2

www.dismatem.ru – типовые расчеты по дискретной математике m.dismatem.ru – заказать типовой с мобильного

Вариант	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	Итого
5	+	+	+	+	+	+	+	+	+	+	+	+	+	+	+	+	+		560 р.

З адание 1.

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

1)



2)






Задание 2.

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

[a,b] R.
Сначала докажем равенство мощностей отрезка [a,b] и отрезка [0,1]. Оно обеспечивается биекцией



Равенство мощностей отрезка [0,1] и интервала (0,1) обеспечивается биекцией, задаваемой по правилу:


Биекция определяет эквивалентность интервала (0,1) и множества R.

Поэтому [a,b] R.







Задание 3.

Докажите методом математической индукции.



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

n=1



Предположим, что соотношение верно для некоторого n.

Докажем, что .







- верно по предположению.

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

.


Задание 4.

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












1
2


3
4

[ ]= [ ]=

[ ]=



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

3 ) – неантисимметрично.
4)
/ / //= отношение – нетранзитивно.




З адание 5.

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


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



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



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

2)



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

4) Так как , тогда x–(z+m)=k x–z=k+m

(так как k+m Z) . Поэтому P транзитивно.







Задание 6.

Является ли алгеброй следующий набор B= ?
Так как число , но , то операция “извлечение корня” не замкнута на множестве Q. Поэтому набор B= не является алгеброй.







Задание 7.

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




,





,



B(X) = .



Задание 8.

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

, , ,


(67 (mod 11) + 79 (mod 11))(mod 11) = (1 + 2)(mod 11) = 3

(67 (mod 7) + 79 (mod 7))(mod 7) = (4 + 2)(mod 7) = 6

(67 (mod 3) + 79 (mod 3))(mod 3) = (1 + 1)(mod 3) = 2

(67 (mod 2) + 79 (mod 2))(mod 2) = (1 + 1)(mod 2) = 0




(67 (mod 11) – 79 (mod 11))(mod 11) = (1 – 2)(mod 11) = 10

(67 (mod 7) – 79 (mod 7))(mod 7) = (4 – 2)(mod 7) = 2

(67 (mod 3) – 79 (mod 3))(mod 3) = (1 – 1)(mod 3) = 0

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




( 67) (mod 11) = 3

( 67) (mod 7) = 5

( 67) (mod 3) = 0

( 67) (mod 2) = 1




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

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

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

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




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

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

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

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

(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, 6, 1, 0] или [6, 1, 0]

Вектор оснований сокращаем до = [7, 3, 2]
Для вычисления вычислим

[2, 2, 1]

Умножим на этот элемент, в результате получим [5, 2, 0]

Таким образом, 5

Вычитая из последнего выражения, получаем [0, 0, 1] или [0, 1]

Вектор оснований = [3, 2]
Вычисляем

[1, 1]

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

Поэтому 0

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

[1]

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

Отсюда следует, что 1
Поэтому число x – отрицательное.



Задание 9.

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







3

2

1

4

3

2

1

4

3

2

1



3

2

1

4

3

2

1









Для графа :

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





1









2



3






4







– матрица инцидентности

B=E+A+ =



– матрица сильных компонент.
– матрица маршрутов длины 2.
Маршруты длины 2, исходящие из вершины 1: (1;1;1).







Задание 10.

Найдите матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли изображенный граф эйлеровым? Является ли изображенный граф планарным?

2

Для получения остова удалим из графа 12–8+1=5 ребер.


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



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



K=

Диаметр d(G)=3

Радиус r(G)=2

Минимальное количество покрывающих цепей графа – 1.

7,2,8,1,7,3,2,6,3,5,4,6,7
Граф является эйлеровым, так как степени всех его вершин четные.

Граф планарный.






Задание 11.

Составьте таблицы истинности формул:
1)

x	y
0	0	1	1	0	0
0	1	0	0	1	1
1	0	1	1	1	1
1	1	0	1	0	0

2)

x	y	z
0	0	0	1	0	1	1	1	0
0	0	1	1	0	0	1	1	0
0	1	0	0	1	1	0	0	1
0	1	1	0	1	0	1	0	0
1	0	0	1	1	1	0	0	1
1	0	1	1	1	0	1	0	0
1	1	0	0	0	1	1	0	0
1	1	1	0	0	0	1	0	0

Задание 12.
Проверьте двумя способами, будут ли эквивалентны следующие формулы

=x (yz) и =(x y) (x z)

а) составлением таблиц истинности

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
а)

x	y	z	yz		x y	x z
0	0	0	1	0	0	0	1
0	0	1	1	0	0	0	1
0	1	0	0	0	0	0	1
0	1	1	1	0	0	0	1
1	0	0	1	1	0	0	1
1	0	1	1	1	0	1	1
1	1	0	0	0	1	0	0
1	1	1	1	1	1	1	1

Так как столбцы и различны, то формулы неэквивалентны.
б)




Так как СДНФ двух формул отличаются, то формулы неэквивалентны.







Задание 13.

С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.








Задание 14.

Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции двумя способами:

а) методом Квайна б) с помощью карт Карно

Каким классам Поста принадлежит эта функция?


а)

x	y	z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

	*		*
	*				*
		*	*
				*	*

тупиковые и минимальные ДНФ.
б)







тупиковые и минимальные ДНФ.
1) функция, сохраняющая ноль

2) функция, не сохраняющая единицу

3) – функция несамодвойственная.

4 ) – функция немонотонная






Задание 15.

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

(1100 1011 1111 1011)

x	y	z	v
0	0	0	0	1
0	0	0	1	1
0	0	1	0	0
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	1

– сокращенная ДНФ.
тупиковые и минимальные ДНФ.


- сокращенная, тупиковая и минимальная КНФ.






Задание 16.

Является ли полной система функций