Множества. Конечные и бесконечные множества. Способы задания множеств
Министерство образования и науки Украины
Ялтинский университет менеджмента
Контрольные задания и учебные материалы
По курсу «Основы дискретной математики»
(3 семестр)
Для заочного отделения
Специальности
«Программное обеспечение автоматизированных систем»
Г. Ялта
Г.
Содержание
Контрольные вопросы по курсу «Основы дискретной математики». 4
Глава 1.Позиционные системы счисления Перевод чисел из одной позиционной системы счисления в другую Арифметические операции с числами в позиционных системах счисления 9
Контрольные вопросы и задания.. 15
Примеры решения задач.. 16
Контрольные вопросы и задания.. 20
Глава 2. 21
2.1. Множества. Конечные и бесконечные множества. Способы задания множеств. 21
2.2. Подмножества. Универсальное множество. Множество всех подмножеств данного множества. 22
2.3. О числе к-элементных подмножеств n - элементного множества. 24
2.5. Понятия алгебраических и кардинальных операций. Алгебраические операции над множествами. Покрытие и разбиение множества. 26
2.6. Поэлементное доказательство теоретико-множественных равенств. 27
2.7. Понятие алгебры. Алгебра множеств. Законы алгебры множеств. Двойственность в алгебре множеств. 27
2.8. Уравнения и системы уравнений в алгебре множеств. 29
2.9. Основные леммы, используемые при решении уравнений в алгебре множеств. 30
2.10. Понятие счетного множества. Примеры счетных множеств. Свойства счетных множеств. Канторовская диагональная процедура. 32
2.11. Множества мощности континуум. 34
Теорема Кантора о существовании несчетных множеств. 34
Теорема Кантора о существовании множеств мощности более континуума. 35
2.12. Теорема Кантора-Бернштейна. 36
2.13. Доказательство существования иррациональных и трансцендентных чисел. 37
2.14. Кардинальные операции над множествами. Прямое произведение множеств. Понятие вектора. 38
2.15. Проекция множеств. 39
2.16. Бинарные отношения. Свойства бинарных отношений. 39
2.17. Представления бинарных отношений в виде орграфов, матриц, верхнего и нижнего сечений. 40
2.18. Операции над бинарными отношениями. 41
2.19. Выражение свойств бинарных отношений через задающие их множества. 41
2.20. Отношения порядка. Упорядоченные множества. 42
2. 21. Отношение эквивалентности. Классы эквивалентности. Системы различных представителей. 42
2.22. Лексикографическое отношение порядка. 43
2.23. Мажоранта и миноранта множеств. Максимум и минимум множеств. Точные грани множеств. 43
2.24. Понятие графика. Функциональные, инъективные графики. Инверсия графика. 44
2.25. Соответствия. Функциональные, инъективные, сюръективные и биективные соответствия. Общее понятие функции. 45
2.26. Высказывания. Операции над высказываниями. 45
2.27. Формулы и функции алгебры логики. 46
2.27. Равносильные формулы. Законы алгебры логики. 48
2.28. Дизъюнктивные и конъюктивные нормальные формы. 49
2.29. Разложение функций алгебры логики по к переменным. СДНФ и СКНФ. 50
2.30. Тавтологии и противоречия. Проблема разрешимости в алгебре логики. Логические следствия. 55
2.31. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев. 58
2.32. Суперпозиция функций алгебры логики. 60
2.33. Полные системы функций. Понятие базиса. 60
2.34. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Линейные функции. 61
2.35. Замкнутые классы функций. 62
2.36. Монотонные функции. Теорема о монотонных функциях. 63
2.37. Двойственность в алгебре логики. Самодвойственные функции. 64
2.39. Теорема Поста о функциональной полноте. 64
Глава 3. Задачник с решением типовых задач. 67
3.1. Определить, является ли данная функция алгебры логики монотонной. 67
3.2. Определить, является ли данная функция алгебры логики линейной. 68
3.3.Является ли данная функция самодвойственной. 69
3.4.Полна ли система функций. 70
3.5.Построить полином Жегалкина для функции.. 71
3.6.Построить СДНФ для функции.. 72
3.7. Построить СКНФ для функции.. 73
3.8. Построить множество всех подмножеств P(M), если М={3,a,5} 74
3.9.Дать анкету бинарного отношения, заданного.. 75
3.10. Определить, является ли соответствие Q=(F,A,B), где A=B, 76
3.11. Решить систему уравнений. 76
Глава 4. Вопросы к экзамену. 78
Контрольные задания по курсу «Основы Дискретной Математики». 80
Список используемой литературы.. 93
Контрольные вопросы по курсу «Основы дискретной математики».
1. Приведите пример записи чисел в не позиционных системах счисления.
2. Дайте определение позиционной системы счисления.
3. Запишите число в позиционной системе счисления.
4. Запишите дробное число в позиционной системе исчисления.
5. Каков принцип записи чисел в позиционных системах счисления с основанием больше десяти? Как записываются числа в шестнадцатеричной системе счисления?
6. Как записать десятичное число в k-ичной системе счисления?
7. Как записать число, заданное в k-ичной системе отсчета в десятичной системе.
8. Двоичная система счисления.
9. Запись целых, дробных чисел в двоичной системе.
10. Как осуществляется перевод чисел из десятичной системы в двоичную?
11. Четверичная система счисления.
12. Запись чисел в четверичной системе счисления.
13. Перевод чисел из десятичной системы счисления в четверичную и наоборот.
14. Восьмеричная система счисления.
15. Запись чисел в восьмеричной системе счисления.
16. Перевод чисел из десятичной системы счисления в восьмеричную и наоборот.
17. Таблица сложения, умножения в двоичной системе счисления.
18. Операции вычитания, деления в двоичной системе счисления.
19. Таблица сложения, умножения в четверичной системе счисления.
20. Операции вычитания, деления в четверичной системе счисления.
21. Таблица сложения, умножения в восьмеричной системе счисления.
22. Операции вычитания, деления в восьмеричной системе счисления.
23. Таблица сложения, умножения в шестнадцатеричной системе счисления.
24. Операции вычитания, деления в шестнадцатеричной системе счисления.
25. Какова процедура перевода чисел из k-ичной системы счисления в p-ичную.
26. Дайте определение понятия диада.
27. Дайте определение понятия - триада.
28. Дайте определение понятия - тетрада.
29. Опишите процедуру перевода чисел из двоичной системы счисления в шестнадцатеричную и наоборот.
30. Каковы принципы представления информации в компьютерах?
31. Дайте определение понятия - байт.
32. Дайте определение понятия - слово.
33. Запись чисел с фиксированной точкой.
34. Запись чисел с плавающей точкой.
35. Определите понятие множество.
36. Что такое подмножество?
37. Что такое пустое множество?
38. Как вычислить число возможных подмножеств n-элементного множества.
39. Определите понятие - объединение множеств.
40. Определите понятие - пересечение множеств.
41. Определите понятие - разность множеств.
42. Определите понятие - дополнение множеств.
43. Определите понятие - мощность множеств.
44. Что называется равномощными множествами?
45. Дайте определение счетного множества.
46. Докажите существование несчетных множеств.
47. Определите понятие - прямое произведение множеств.
48. Определите понятие - отношения множеств.
49. Какие операции над отношениями существуют?
50. Определите бинарное отношение.
51. Определите транзитивное замыкание отношений.
52. Определите понятие - отношение эквивалентности.
53. Дайте теоретико-множественное определение понятия функция.
54. Определите понятие - сюръекция.
55. Определите понятие - биекция.
56. Определите понятие - размещение.
57. Определите понятие - сочетание.
58. Определите понятие - перестановка.
59. Приведите формулу для вычисления числа перестановок.
60. Приведите формулу для вычисления размещений.
61. Приведите формулу для вычисления числа сочетаний.
62. Определите процедуру вычисления числа сочетаний с возвратом.
63. Задача о выигрыше в лотерее.
64. Решите задачу о ханойской башне.
65. Решите задачу Иосифа Флавия.
66. Определите - бином Ньютона и выпишите формулу для биномиальных коэффициентов.
67. Треугольник Паскаля.
68. Сформулируйте малую теорему Ферма.
69. Перечислите доказательство малой теоремы Ферма с использованием комбинаторики.
70. Приведите свойства биномиальных коэффициентов.
71. Напишите полиномиальную формулу.
72. Напишите формулу для числа возможных разбиений n-элементного множества на пустых подмножествах.
73. Приведите примеры рекуррентных соотношений.
74. Метод решения рекуррентных соотношений, основанный на методе математической индукции.
75. Метод суммирующего множителя для разрешения рекуррентностей.
76. Метод разрешения линейных рекуррентных соотношений с постоянными коэффициентами.
77. Числа Фибоначчи.
78. Производящие функции.
79. Производящие функции для чисел Фибоначчи.
80. Специальные производящие функции.
81. Дайте определение понятию - свертка.
82. Приведите пример экспоненциальной производящей функции.
83. Производящая функция Дирхле.
84. Определите префикс и постфикс слова.
85. Дайте определение разделимой схемы.
86. Дайте определение префиксной схемы.
87. Приведите вывод неравенства Мак Миллана.
88. Приведете критерий однозначности декодирования.
89. Приведите алгоритм распознавания однозначности декодирования.
90. Принципы минимизации длины кода сообщения.
91. Дайте определение цены кодирования.
92. В чем суть алгоритма Фано.
93. Определите понятие - оптимальное кодирование.
94. В чем суть алгоритма Хафмена.
95. Дайте определение кодов с минимальной избыточностью.
96. В чес суть кодирования с исправлением ошибок.
97. Приведите классификацию ошибок.
98. Возможно ли исправить все ошибки.
99. Что такое кодовое расстояние.
100. В чем суть кода Хэминга для исправления одного замещения.
101. В чем заключается принцип сжатия текстов.
102. Построение словаря для процедуры сжатия данных, идеи и принципы.
103. Алгоритм Лемпела-Зива.
104. Идем современной криптографии.
105. Идеи шифрования с помощью случайных чисел.
106. Идеи шифрования с открытым ключом.
107. Идеи шифрования по методу RSA.
108. Идеи цифровой подписи.
109. Булева алгебра.
110. Аксиомы алгебры логики.
111. Теоремы алгебры логики.
112. Функции алгебры логики.
113. Существенные и несущественные переменные.
114. Примеры элементарных булевых функций.
115. Булевы функции одной переменной.
116. Булевы функции двух переменных.
117. Понятие о дизъюнктивной нормальной форме (ДНФ).
118. Совершенная дизъюнктивная нормальная форма (СДНФ).
119. Совершенная конъюнктивная нормальная форма. (СКНФ)
120. Совершенная полиномиальная нормальная форма (СПНФ).
121. Понятие произвольной ДНФ.
122. Операция склеивания.
123. Операция поглощения.
124. Операция неполного склеивания.
125. Операция обобщенного склеивания.
126. Опишите геометрические формы представления булевых функций.
127. Представление булевой функции посредством диаграммы Вейча.
128. Представление булевой функции посредством карты Карно.
129. Опишите процедуру получения кода Грэя.
130. Определите понятие - интервальная форма.
131. Интервальное представление на матричной форме.
132. Определите симметрическую булеву функцию.
133. Сформулируйте алгоритм проверки булевой функции на симметричность.
134. Определите симметрию булевой функции в расширенном смысле.
135. Сформулируйте алгоритм проверки булевой функции на симметричность в расширенном смысле.
136. Определите монотонную булеву функцию.
137. Определите однородную булеву функцию.
138. Сформулируйте алгоритм проверки булевой функции на однородность.
139. Дайте определение самодвойственной функции.
140. Сформулируйте теорему о функциональной полноте.
141. Постановка задачи о минимизации булевой функции.
142. В чем состоит процедура построения сокращенной ДНФ.
143. В чем суть метода Квайна-Мак-Класки минимизации ДНФ.
144. Каковы основные идеи синтеза комбинационных дискретных устройств с использованием булевых функций.
145. Класки минимизация ДНФ.
146. Каковы основные идеи синтеза комбинационных дискретных устройств с использованием булевых функций.
147. Что называется графом?
148. Назовите основные элементы графа.
149. Определите ориентированный и неориентированный графы.
150. Дайте определение маршрута, цикла.
151. Определите связный, несвязный граф.
152. Определите матрицу смежности.
153. Определите матрицу инцидентности.
154. Определите понятие дерева.
155. Определите понятие бинарного дерева.
156. Приведите алгоритм бинарного поиска.
157. Приведите алгоритм вставки в дерево сортировки.
158. Приведите пример удаления дерева из сортировки.
159. Приведите пример построения кратчайшего остова.
160. Определите понятие эйлерова цикла.
161. Определите понятие гамильтонова цикла.
162. Приведите алгоритм построения максимальных независимых множеств вершин.
163. Определите понятие хроматического числа графа.
164. Приведите алгоритм раскрашивания графа.
165. Как построить кратчайший путь на графе.
166. Сформулируйте задачу о нахождении потока в сети.
167. Как вычислить максимальный поток в сети?
168. Как вычислить минимальный поток в сети?
169. Приведите интуитивное определение алгоритма.
170. Определите частично рекурсивную функцию.
171. Определите общерекурсивную функцию.
172. Определите понятие машины Тьюринга.
173. Приведите определение k-значной логики.
Глава 1.Позиционные системы счисления
Перевод чисел из одной позиционной системы счисления в другую
Арифметические операции с числами в позиционных системах счисления
Системой счисления называется совокупность приемов наименования и записи чисел. В любой системе счисления для представления чисел выбираются некоторые символы (их называют цифрами), а остальные числа получаются в результате каких-либо операций над цифрами данной системы счисления.
Система называется позиционной, если значение каждой цифры (ее вес) изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число.
Число единиц какого-либо разряда, объединяемых в единицу более старшего разряда, называют основанием позиционной системы счисления. Если количество таких цифр равно P, то система счисления называется P-ичной. Основание системы счисления совпадает с количеством цифр, используемых для записи чисел в этой системе счисления.
Запись произвольного числа x в P-ичной позиционной системе счисления основывается на представлении этого числа в виде многочлена
x = anPn + an-1Pn-1 + ... + a1P1 + a0P0 + a-1P-1 + ... + a-mP-m
Арифметические действия над числами в любой позиционной системе счисления производятся по тем же правилам, что и десятичной системе, так как все они основываются на правилах выполнения действий над соответствующими многочленами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые соответствуют данному основанию P системы счисления.
При переводе чисел из десятичной системы счисления в систему с основанием P > 1 обычно используют следующий алгоритм:
1) если переводится целая часть числа, то она делится на P, после чего запоминается остаток от деления. Полученное частное вновь делится на P, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P выписываются в порядке, обратном их получению;
2) если переводится дробная часть числа, то она умножается на P, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на P и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием P.
Примеры решения задач
1. Перевести данное число из десятичной системы счисления в двоичную:
а) 464(10); б) 380,1875(10); в) 115,94(10) (получить пять знаков после запятой в двоичном представлении).
Решение.
464 | 0 380 | 0 |1875 115 | 1 |94
232 | 0 190 | 0 0|375 57 | 1 1|88
116 | 0 95 | 1 0|75 28 | 0 1|76
58 | 0 47 | 1 1|5 14 | 0 1|52
а) 29 | 1 б) 23 | 1 1|0 в) 7 | 1 1|04
14 | 0 11 | 1 3 | 1 0|08
7 | 1 5 | 1 1 | 1 0|16
3 | 1 2 | 0
1 | 1 1 | 1
а) 464(10) = 111010000(2); б) 380,1875(10) = 101111100,0011(2); в) 115,94(10) 1110011,11110(2) (в настоящем случае было получено шесть знаков после запятой, после чего результат был округлен).
Если необходимо перевести число из двоичной системы счисления в систему счисления, основанием которой является степень двойки, достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8 = 23). Итак, в целой части будем производить группировку справа налево, в дробной — слева направо. Если в последней группе недостает цифр, дописываем нули: в целой части — слева, в дробной — справа. Затем каждая группа заменяется соответствующей цифрой новой системы. Соответствия приведены в таблицах.
| P | |||||
| P | |||||||||
| P | |||||||||||||||||
| A | B | C | D | E | F |
Переведем из двоичной системы в шестнадцатеричную число 1111010101,11(2).
001111010101,1100(2) = 3D5,C(16).
При переводе чисел из системы счисления с основанием P в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер -1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления.
2. Перевести данное число в десятичную систему счисления.
а) 1000001(2).
1000001(2)=1× 26+0× 25+0× 24+0× 23+0× 22+ 0× 21+1× 20 = 64+1=65(10).
Замечание. Очевидно, что если в каком-либо разряде стоит нуль, то соответствующее слагаемое можно опускать.
б) 1000011111,0101(2).
1000011111,0101(2)=1×29 + 1×24 + 1×23 + 1×22 + 1×21 + 1×20 + 1×2-2 + 1×2-4 = 512 + 16 + 8 + 4 + 2 + 1 + 0,25 + 0,0625 = 543,3125(10).
в) 1216,04(8).
1216,04(8)=1×83+2×82+1×81+6×80+4× 8-2 = 512+128+8+6+0,0625 = 654,0625(10).
г) 29A,5(16).
29A,5(16) = 2×162+9×161+10×160+5×16-1 = 512+144+10+0,3125 = 656,3125(10).
Для выполнения арифметических операций в системе счисления с основанием P необходимо иметь соответствующие таблицы сложения и умножения. Для P = 2, 8 и 16 таблицы представлены ниже.
|
|
|
|
|
|
3. Сложить числа:
а) 10000000100(2) + 111000010(2) = 10111000110(2).
б) 223,2(8) + 427,54(8) = 652,74(8).
в) 3B3,6(16) + 38B,4(16) = 73E,A(16).
10000000100 223,2 3B3,6
+ 111000010 + 427,54 +38B,4
------------ ------- -----
10111000110 652,74 73E,A
4. Выполнить вычитание:
а) 1100000011,011(2) - 101010111,1(2) = 110101011,111(2).
б) 1510,2(8) - 1230,54(8) = 257,44(8).
в) 27D,D8(16) - 191,2(16) = EC,B8(16).
1100000011,011 1510,2 27D,D8
- 101010111,1 -1230,54 -191,2
-------------- ------- ------
110101011,111 257,44 EC,B8
5. Выполнить умножение:
а) 100111(2) ´ 1000111(2) = 101011010001(2).
б) 1170,64(8) ´ 46,3(8) = 57334,134(8).
в) 61,A(16) ´ 40,D(16) = 18B7,52(16).
100111 1170,64 61,A
*1000111 * 46,3 *40,D
------------- -------------- ----------
100111 355 234 4F 52
+ 100111 + 7324 70 + 1868
100111 47432 0 ----------
100111 ------------- 18B7,52
------------- 57334,134
Контрольные вопросы и задания
1. Дать определение системы счисления. Назвать и охарактеризовать свойства системы счисления.
2. Какие символы используются для записи чисел в двоичной системе счисления, восьмеричной, шестнадцатеричной?
3. Чему равны веса разрядов слева от точки, разделяющей целую и дробную часть, в двоичной системе счисления (восьмеричной, шестнадцатеричной)?
4. Чему равны веса разрядов справа от точки, разделяющей целую и дробную часть, в двоичной системе счисления (восьмеричной, шестнадцатеричной)?
5. Зашифруйте следующие десятичные числа, преобразовав их в двоичные (восьмеричные, шестнадцатеричные): 0, 1, 18, 25, 128.
6. Дешифруйте следующие двоичные числа, преобразовав их в десятичные: 0010, 1011, 11101, 0111, 0101.
7. Дешифруйте следующие восьмеричные числа, преобразовав их в десятичные: 777, 375, 111, 1015.
8. Дешифруйте следующие шестнадцатеричные числа, преобразовав их в десятичные: 15, A6, 1F5, 63.
Примеры решения задач
1. Перевести данное число из десятичной системы счисления в двоичную:
а) 464(10); б) 380,1875(10); в) 115,94(10) (получить пять знаков после запятой в двоичном представлении).
Решение.
464 | 0 380 | 0 |1875 115 | 1 |94
232 | 0 190 | 0 0|375 57 | 1 1|88
116 | 0 95 | 1 0|75 28 | 0 1|76
58 | 0 47 | 1 1|5 14 | 0 1|52
а) 29 | 1 б) 23 | 1 1 |0 в) 7 | 1 1|04
14 | 0 11 | 1 3 | 1 0|08
7 | 1 5 | 1 1 | 1 0|16
3 | 1 2 | 0
1 | 1 1 | 1
а) 464(10) = 111010000(2); б) 380,1875(10) = 101111100,0011(2); в) 115,94(10) » 1110011,11110(2) (в настоящем случае было получено шесть знаков после запятой, после чего результат был округлен).
Если необходимо перевести число из двоичной системы счисления в систему счисления, основанием которой является степень двойки, достаточно объединить цифры двоичного числа в группы по столько цифр, каков показатель степени, и использовать приведенный ниже алгоритм. Например, если перевод осуществляется в восьмеричную систему, то группы будут содержать три цифры (8 = 23). Итак, в целой части будем производить группировку справа налево, в дробной — слева направо. Если в последней группе недостает цифр, дописываем нули: в целой части — слева, в дробной — справа. Затем каждая группа заменяется соответствующей цифрой новой системы. Соответствия приведены в таблицах.
| P | |||||
| P | |||||||||
| P | |||||||||||||||||
| A | B | C | D | E | F |
Переведем из двоичной системы в шестнадцатеричную число 1111010101,11(2).
001111010101,1100(2) = 3D5,C(16).
При переводе чисел из системы счисления с основанием P в десятичную систему счисления необходимо пронумеровать разряды целой части справа налево, начиная с нулевого, и в дробной части, начиная с разряда сразу после запятой слева направо (начальный номер -1). Затем вычислить сумму произведений соответствующих значений разрядов на основание системы счисления в степени, равной номеру разряда. Это и есть представление исходного числа в десятичной системе счисления.
2. Перевести данное число в десятичную систему счисления.
а) 1000001(2).
1000001(2)=1× 26+0× 25+0× 24+0× 23+0× 22+ 0× 21+1× 20 = 64+1=65(10).
Замечание. Очевидно, что если в каком-либо разряде стоит нуль, то соответствующее слагаемое можно опускать.
б) 1000011111,0101(2).
1000011111,0101(2)=1×29 + 1×24 + 1×23 + 1×22 + 1×21 + 1×20 + 1×2-2 + 1×2-4 = 512 + 16 + 8 + 4 + 2 + 1 + 0,25 + 0,0625 = 543,3125(10).
в) 1216,04(8).
1216,04(8)=1×83+2×82+1×81+6×80+4× 8-2 = 512+128+8+6+0,0625 = 654,0625(10).
г) 29A,5(16).
29A,5(16) = 2×162+9×161+10×160+5×16-1 = 512+144+10+0,3125 = 656,3125(10).
Для выполнения арифметических операций в системе счисления с основанием P необходимо иметь соответствующие таблицы сложения и умножения. Для P = 2, 8 и 16 таблицы представлены ниже.
|
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||