ДИСКРЕТНАЯ МАТЕМАТИКА Учебное пособие Рекомендовано УМО РАЕ по классическому университетскому и техническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям подготовки: 230400 – «Информационные системы и технологии», 230100 – «Информатика и вычислительная техника», 090900 – «Информационная безопасность» Казань Издательство КНИТУ 2014 УДК 519.1, 510.6 Зайцева О. Н. <...> Пособие может быть использовано при изучении дисциплин «Дискретная математика», «Информатика», «Линейная алгебра и дискретная математика», «Логика» студентами института легкой промышленности моды и дизайна (направление подготовки «Информационные системы и технологии»), инженерного химикотехнологического института (направление подготовки «Информационная безопасность»), института управления, автоматизации и информационных технологий (направление подготовки «Информатика и вычислительная техника»). <...> В настоящей главе изучается булева алгебра, а именно множество {0, 1} с определенными на нем операциями дизъюнкции, конъюнкции и отрицания. <...> Здесь сформулированы законы булевой алгебры и проведена параллель между булевой алгеброй, логикой высказываний с одной стороны, и с алгеброй множеств с другой. <...> Показано, как булевы выражения могут быть записаны в стандартной форме, носящей название «дизъюнктивная нормальная форма». <...> В этой главе осваиваются такие новые понятия, как, например, принцип 4 включения исключения, упорядоченные пары, декартово произведение, которые потребуются для освоения последующего материала. <...> Для строгого математического описания любых связей между элементами двух множеств в четвертой главе введено понятие бинарного отношения. <...> Пятая глава посвящена функциям, которые играют центральную роль в математике, где они используются для описания любых процессов, при которых элементы одного множества каким-то образом переходят в элементы другого. <...> После определения <...>
Математические_методы_в_приложениях._Дискретная_математика.pdf
УДК 519.1, 510.6
Зайцева О. Н.
Математические методы в приложениях. Дискретная математика :
учебное пособие / О.Н. Зайцева, А.Н. Нуриев, П.В. Малов; М-во образ. и
науки России, Казан. нац. исслед. технол. ун-т. – Казань : Изд-во КНИТУ,
2014. – 173 с.
ISBN 978-5-7882-1570-9
В представленном пособии в доступной форме рассказывается о
фундаментальных понятиях дискретной математики – логике, булевых
функциях, множествах, отношениях и графах. Теория изложена кратко, но
иллюстрирована многочисленными простыми для пониманимя примерами.
Изложение курса дискретной математики представлено в форме
решения математических задач различной сложности, связанных с
программированием. Предложены алгоритмы решения этих задач,
написанные на «псевдокоде».
Пособие может быть использовано при изучении дисциплин
«Дискретная математика», «Информатика», «Линейная алгебра и
дискретная математика», «Логика» студентами института легкой
промышленности моды и дизайна (направление подготовки
«Информационные системы и технологии»), инженерного химикотехнологического
института (направление подготовки «Информационная
безопасность»), института управления, автоматизации и информационных
технологий (направление подготовки «Информатика и вычислительная
техника»).
Подготовлено на кафедре информатики и прикладной математики.
Печатается по решению редакционно-издательского совета Казанского
национального исследовательского технологического университета
Рецензенты: д-р физ.-мат. наук, проф. П. Г. Данилаев
канд. физ.-мат. наук, доц. К. А. Поташев
ISBN 978-5-7882-1570-9 © Зайцева О.Н., Нуриев А.Н., Малов П.В., 2014
© Казанский национальный исследовательский
технологический университет, 2014
2
Стр.2
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. БУЛЕВА ЛОГИКА И БУЛЕВА АЛГЕБРА
1.1. Высказывания и логика
1.2. Булева алгебра
1.3. Карта Карно
Задачи для самостоятельного решения к главе 1
ГЛАВА 2. ПРЕДИКАТЫ И МЕТОДЫ ДОКАЗАТЕЛЬСТВ
2.1. Предикаты и кванторы
2.2. Методы доказательств
2.3. Математическая индукция
Задачи для самостоятельного решения к главе 2
ГЛАВА 3. ТЕОРИЯ МНОЖЕСТВ
3.1. Множества и операции над ними
3.2. Алгебра множеств
3.3. Дальнейшие свойства множеств
Задачи для самостоятельного решения к главе 3
ГЛАВА 4. ОТНОШЕНИЯ
4.1. Бинарные отношения
4.2. Свойства отношений
4.3. Отношения эквивалентности и частичного порядка
Задачи для самостоятельного решения к главе 4
ГЛАВА 5. ФУНКЦИИ
5.1. Обратные отношения и композиция отношений
5.2. Функции
5.3. Обратные функции и композиция функций
5.4. Принцип Дирихле
Задачи для самостоятельного решения к главе 5
ГЛАВА 6. КОМБИНАТОРИКА
6.1. Правила суммы и произведения
6.2. Комбинаторные формулы
6.3. Бином Ньютона
Задачи для самостоятельного решения к главе 6
ГЛАВА 7. ГРАФЫ
172
3
7
8
15
21
25
29
30
32
35
39
42
43
49
51
56
59
60
65
68
75
78
79
83
90
94
98
102
103
105
113
117
121
Стр.172
7.1. Графы и терминология
7.2. Гамильтоновы графы
7.3. Деревья
Задачи для самостоятельного решения к главе 7
ГЛАВА 8. ОРИЕНТИРОВАННЫЕ ГРАФЫ
8.1. Ориентированные графы
8.2. Пути и орграфы
8.3. Кратчайший путь
Задачи для самостоятельного решения к главе 8
РАСЧЕТНОЕ ЗАДАНИЕ
ЛИТЕРАТУРА
122
128
132
140
145
146
150
156
163
167
171
Ответственный за выпуск доц. Е.А. Харитонов
Подписано в печать 21.04.2014
Бумага офсетная
11,0 уч.-изд. л.
Печать Riso
Тираж 100 экз.
Формат 6084 1/16
Заказ
Издательство Казанского национального исследовательского
технологического университета
Офсетная лаборатория Казанского национального
исследовательского технологического университета
420015, Казань, К.Маркса, 68
173
10,23 усл.печ.л
«С» 41
Стр.173