Материал: Дискретная математика теория и практика
Министерство образования и науки Российской Федерации Костромской государственный технологический университет Кафедра высшей математики
А.В. Чередникова, О.Б. Садовская, Л.А. Каминская
Дискретная математика.
Теория и практика
Рекомендовано редакционно-издательским советом университета в качестве учебного пособия
Кострома
КГТУ
2011
УДК 519.1 (075)
Чередникова А.В. Дискретная математика. Теория и практика / А.В. Чередникова, О.Б. Садовская, Л.А. Каминская. – Кострома: Изд-во Костром. гос.
технол. ун-та, 2011. – 74 с.
В пособии рассматриваются следующие разделы дискретной математики: теория множеств, комбинаторика и общая алгебра. Теоретический материал изложен в доступной форме, но с сохранением необходимого уровня строгости изложения, сопровождается большим количеством примеров и решением типовых задач. Приведены разнообразные задачи и упражнения для самостоятельной работы.
Пособие предназначено для студентов бакалавриата по направлениям подготовки 090900 «Информационная безопасность», 230100 «Информатика и вычислительная техника», 230400 «Информационные системы и технологии».
Рецензенты: кафедра алгебры и геометрии КГУ им. Н.А.Некрасова; кандидат физ.-мат. наук, доцент Н.Л. Марголина
© Костромской государственный технологический университет, 2011
3
|
Оглавление |
|
Предисловие...................................................................................................................................... |
5 |
|
Введение............................................................................................................................................. |
5 |
|
Глава 1. Множества......................................................................................................................... |
6 |
|
1.1. Множества и их элементы. Способы задания множеств..................................................... |
6 |
|
1.2. Подмножества.......................................................................................................................... |
7 |
|
1.3. Операции над множествами................................................................................................... |
8 |
|
1.4. Диаграммы Эйлера – Венна ................................................................................................. |
11 |
|
1.5. Прямое произведение множеств.......................................................................................... |
12 |
|
1.6. Метод математической индукции ....................................................................................... |
14 |
|
1.7. Соответствия.......................................................................................................................... |
16 |
|
1.8 |
Задачи, связанные с определением мощности конечного множества .............................. |
18 |
Задачи и упражнения к главе 1 ................................................................................................... |
21 |
|
Глава 2. Комбинаторика............................................................................................................... |
24 |
|
2.1. Правила суммы и произведения .......................................................................................... |
25 |
|
2.2. Размещения и сочетания....................................................................................................... |
26 |
|
2.3. Примеры решения задач....................................................................................................... |
29 |
|
2.4. Бином Ньютона ..................................................................................................................... |
31 |
|
2.5. Свойства биномиальных коэффициентов. Треугольник Паскаля.................................... |
32 |
|
Задачи и упражнения к главе 2 ................................................................................................... |
33 |
|
Глава 3. Отношения. Отображения............................................................................................ |
35 |
|
3.1 |
Понятие отношения................................................................................................................ |
35 |
3.2 |
Способы задания бинарных отношений .............................................................................. |
36 |
3.3 |
Операции над бинарными отношениями............................................................................ |
37 |
3.4 |
Свойства матриц бинарных отношений.............................................................................. |
38 |
3.5 |
Свойства бинарных отношений............................................................................................ |
39 |
3.6 |
Определение свойств бинарного отношения по его матрице............................................ |
40 |
3.7 |
Отношение эквивалентности ................................................................................................ |
42 |
3.8 |
Счетные и несчетные множества.......................................................................................... |
44 |
3.9 |
Отношение порядка. Диаграммы Хассе............................................................................... |
48 |
3.10. Функции ............................................................................................................................... |
51 |
|
Задачи и упражнения к главе 3 ................................................................................................... |
52 |
|
Глава 4. Алгебраические структуры.......................................................................................... |
56 |
|
4.1. Алгебраические операции и их свойства............................................................................ |
56 |
|
4.2. Понятие алгебраической структуры.................................................................................... |
58 |
|
4.3. Алгебры с одной бинарной алгебраической операцией.................................................... |
59 |
|
4.4. Алгебры с двумя бинарными алгебраическими операциями .......................................... |
62 |
|
4.5. Конечные поля....................................................................................................................... |
64 |
|
4.6. Булевы алгебры ..................................................................................................................... |
66 |
|
4.7. Гомоморфизмы алгебр.......................................................................................................... |
68 |
|
4.8. Алгебраические системы. Решетки ..................................................................................... |
70 |
|
Задачи к главе 4 ............................................................................................................................ |
72 |
|
Список литературы ...................................................................................................................... |
74 |
|
4
Предисловие
В настоящем учебном пособии рассматриваются элементы следующих разделов дискретной математики: теории множеств (множества, отношения, функции), комбинаторики и общей алгебры (алгебраические системы).
Для краткой записи утверждений будем использовать следующие обозначения символов:
(квантор общности) читается «для любого», «для каждого», «для всех»;(квантор существования) – «найдется», «существует», «хотя бы для одного»;
(импликация, знак логического следования) – «если …, то …», «следует»;(эквиваленция, знак логической равносильности) – «тогда и только тогда».
def
Для любых предложений A и B запись A B означает, что предложения A и B равносильны по определению (от англ. definition – определение).
Знак будет обозначать конец примера, замечания или доказательства утверждения (при его отсутствии знак будет ставиться непосредственно после формулировки).
Введение
Понятие «дискретный» (от лат. discretus – разделенный, прерывный) является противоположным понятию «непрерывный». С содержательной точки зрения дискретный объект представляет собой нечто, состоящее из строго ограниченных, отделенных друг от друга неделимых частей.
Дискретная математика (или дискретный анализ) – совокупность математических дисциплин, изучающих свойства абстрактных дискретных объектов, которые возникают в математике и в ее приложениях. Эти объекты могут носить как конечный характер, так и бесконечный – в случае отделимости составляющих их элементов или скачкообразности происходящих в них процессов.
Деление математики на дискретную и классическую (непрерывную) математику достаточно условно. Так, например, методы теории множеств используются при изучении и дискретных, и непрерывных объектов. Дискретная математика также использует методы, разработанные в классической математике. Однако характер исследуемых дискретной математикой объектов настолько своеобразен, что методов классической математики не всегда достаточно для их изучения. Важными отличиями дисциплин дискретной математики от классических разделов непрерывной математики являются отсутствие понятия непрерывности и предела последовательности.
В настоящее время методы дискретной математики находят широкое применение в различных областях знаний, наиболее значимой из которых является область компьютерных технологий.
К разделам дискретной математики обычно относятся: теория множеств, комбинаторика, общая алгебра, теория графов, математическая логика, теория алгоритмов, теория кодирования, теория автоматов и многие другие.
5
Глава 1. Множества
1.1. Множества и их элементы. Способы задания множеств
Понятие множества является одним из фундаментальных понятий математики. Оно было введено в математику создателем теории множеств немецким ученым Георгом Кантором (1845 – 1918). Следуя ему, под множеством понимается совокупность объектов произвольной природы, которая рассматривается как единое целое. Объекты, входящие в состав множества, называются
его элементами.
Это описание понятия множества нельзя считать логическим определением, а всего лишь пояснением. Понятие множества принимается как исходное, первичное, то есть не сводимое к другим понятиям.
Примерами множеств могут служить множество всех книг, составляющих данную библиотеку, множество всех точек данной линии, множество всех решений данного уравнения, множество всех одноклеточных организмов и т.п.
Множества принято обозначать прописными буквами латинского алфавита: A, B, C, … Для числовых множеств будем использовать следующие обозначения:
N – множество натуральных чисел;
N0 – множество неотрицательных целых чисел; Z – множество целых чисел;
Q – множество рациональных чисел;
I – множество иррациональных чисел;
R – множество действительных чисел;
C – множество комплексных чисел.
Элементы множества будем обозначать строчными латинскими буквами:
a, b, c, …
Предложения вида «объект a есть элемент множества A», «объект a принадлежит множеству A», имеющие один и тот же смысл, кратко записывают в виде a A. Если элемент a не принадлежит множеству A, то пишут a A.
Символ называется знаком принадлежности.
Множества могут содержать как конечное число элементов, так и бесконечное. Например, множество всех корней уравнения x2 − 4x − 5 = 0 конечно (два элемента), а множество всех точек прямой бесконечно. Рассматривают в математике и множество, не содержащее ни одного элемента.
Определение 1.1. Множество, не содержащее ни одного элемента, называется пустым и обозначается символом .
Число элементов конечного множества называется его мощностью. Если множество A содержит n элементов, то будем писать А = n. Если A = , то
А = 0. Мощность бесконечного множества является более сложным понятием.
Оно будет рассмотрено в главе 3.
Замечание 1.1. Элементами множества могут быть множества. Например, можно говорить о множестве групп некоторого факультета университета.
6