Веретенников, В. И. Белоусова ДИСКРЕТНАЯ МАТЕМАТИКА Часть I Рекомендовано методическим советом УрФУ в качестве учебного пособия для студентов, обучающихся по всем направлениям подготовки Института радиоэлектроники и информационных технологий Екатеринбург Издательство Уральского университета 2014 УДК 519(075.8) ББК 22.176А73 В31 Рецензенты: кафедра Прикладной математики Уральского государственного экономического университета (завкафедрой, канд. физ.-мат. наук, доц. <...> 1) 978-5-7996-1195-8 Учебное пособие включает в себя базисные разделы дискретной математики: бинарные отношения, элементы общей алгебры и теорию чисел. <...> Множества обозначают большими латинскими буквами: . – пустое множество, т. е. множество, не имеющее элементов; – множество всех натуральных чисел; – множество всех целых чисел; – множество всех рациональных чисел; – множество всех действительных чисел; – множество всех комплексных чисел; – для всех, для любого; – существует, найдется; – существует (найдется) единственный; Знак заменяет выражение «если и только если»; Знак заменяет выражение «влечет»; – элемент принадлежит множеству ; – элемент не принадлежит множеству ; – подмножество в { }; – не содержится в ; – равно , т. е. и – строго содержится в , т. е. 6 ; и – пересечение множеств и , т. е. {x| x и ; }; – объединение множеств и , т. е. {x| x }; – разность множеств и , т. е. множество {x| x и }; ■ – конец доказательства. или 7 Введение Дискретная математика в наше время – это обширная наука, которая базируется на классических разделах математики – алгебре, теории чисел, математическом анализе и теории вероятностей. <...> Особенно важны для глубокого понимания методов дискретной математики алгебра и теория чисел. <...> Бинарным отношением на множестве называется любое подмножество декартова квадрата . <...> Тогда матрицей отношения называется квадратная матрица размера , состоящая из нулей и единиц, такая, что в пересечении i-й строки и j-го столбца стоит тогда и только тогда <...>
Дискретная_математика._Часть_1..pdf
УДК 519(075.8)
ББК 22.176А73
В31
Рецензенты:
кафедра Прикладной математики Уральского государственного
экономического университета (завкафедрой, канд. физ.-мат.
наук, доц. О. Б. Мельников);
канд. физ.-мат. наук, доц. И. Н. Белоусов (Институт математики
и механики УрО РАН)
Научный редактор – канд. физ.-мат. наук, доц. Н. В. Чуксина
Веретенников, Б. М.
В31 Дискретная математика : учебное пособие / Б. М. Веретенников,
В. И. Белоусова. – Екатеринбург : Изд-во Урал. ун-та,
2014. – Ч. I. – 132 с.
ISBN 978-5-7996-1199-6 (ч. 1)
978-5-7996-1195-8
Учебное пособие включает в себя базисные разделы дискретной
математики: бинарные отношения, элементы общей алгебры и теорию
чисел. В работе предлагаются упражнения для самостоятельного решения.
Предназначено для студентов всех направлений подготовки
Института радиоэлектроники и информационных технологий – РтФ.
Библиогр.: 10 назв. Рис. 21. Табл. 18.
УДК 519(075.8)
ББК 22.176А73
ISBN 978-5-7996-1199-6 (ч. 1)
978-5-7996-1195-8
© Уральский федеральный
университет, 2014
Стр.3
Оглавление
Список обозначений ......................................................................... 6
Введение ............................................................................................ 8
Глава I. Бинарные отношения ....................................................... 10
§ 1. Определение и способы задания бинарного отношения . 10
Упражнения для самостоятельной подготовки ....................... 14
§ 2. Операции над бинарными отношениями .......................... 15
Упражнения для самостоятельной подготовки ....................... 16
§ 3. Основные свойства бинарных отношений ........................ 17
Упражнения для самостоятельной подготовки ....................... 19
§ 4. Классы эквивалентности ..................................................... 20
Упражнения для самостоятельной подготовки ....................... 23
§ 5. Частичный порядок ............................................................. 25
Упражнения для самостоятельной подготовки ....................... 33
§ 6. Рефлексивное, симметричное и транзитивное.................. 33
замыкание бинарного отношения ............................................. 33
Упражнения для самостоятельной подготовки ....................... 36
§ 7. Бинарные отношения из множества в множество ............ 37
Упражнения для самостоятельной подготовки ....................... 39
Глава II. Элементы общей алгебры ............................................... 40
§ 1. Группоиды и полугруппы ................................................... 40
§ 2. Алгоритм Лайта ................................................................... 44
Упражнения для самостоятельной подготовки ....................... 47
§ 3. Конгруэнции и гомоморфизмы группоидов ..................... 48
3
Стр.4
§ 4. Группы .................................................................................. 54
Упражнения для самостоятельной подготовки ....................... 60
§ 5. Циклические группы ........................................................... 61
Упражнения для самостоятельной подготовки ....................... 64
§ 6. Группы подстановок ........................................................... 65
Упражнения для самостоятельной подготовки ....................... 73
§ 7. Матричные группы .............................................................. 75
Упражнения для самостоятельной подготовки ....................... 77
§ 8. Смежные классы .................................................................. 79
Упражнения для самостоятельной подготовки ....................... 83
§ 9. Нормальные подгруппы. Фактор-группы ......................... 85
Упражнения для самостоятельной подготовки ....................... 87
§ 10. Изоморфизмы и гомоморфизмы ...................................... 88
Упражнения для самостоятельной подготовки ....................... 91
§ 11. Кольца и поля ..................................................................... 92
§ 12. Линейное пространство над произвольным полем
§13. Идеалы и гомоморфизмы ассоциативных колец ............. 96
.... 95
Глава III. Теория чисел и теория многочленов .......................... 102
§ 1. Элементарная теория чисел .............................................. 102
Упражнения для самостоятельной подготовки ..................... 106
§ 2. Взаимно простые числа..................................................... 107
§ 3. Теория сравнений .............................................................. 108
§ 4 Китайская теорема об остатках ......................................... 113
Упражнения для самостоятельной подготовки ..................... 120
4
Стр.5
§ 5. Элементарная теория многочленов ................................. 122
Упражнения для самостоятельной подготовки ..................... 127
§ 6. Теория сравнений для многочленов ................................ 128
Упражнения для самостоятельной подготовки ..................... 129
Список литературы ................................................................... 130
5
Стр.6