Читать онлайн «Элементы дискретной математики и начала математической информатики»
Автор Т. С. Соболева
РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
НЕФТИ И ГАЗА им. И. М. ГУБКИНА
Кафедра высшей математики
СОБОЛЕВА Т. С. Элементы дискретной математики и
начала математической информатики
Курс лекций
Москва 2002
УДК 519. 1:519. 7
ББК 22. 18
Соболева Т. С. Элементы дискретной математики и начала
математической информатики: Курс лекций. - М. : РГУ нефти и газа
им. И. М. Губкина, 2002. JSBN 5-7246-0205-9
Излагаются основы дискретной математики. Рассматриваются
разделы математических теорий, ориентированные на моделирование
интеллектуальных систем (элементы теории множеств, теории
алгебраических структур и математической лоп1ки, а также
математической информатики). Учебное пособие предназначается для студентов, аспирантов и
научных работников, занимающихся вопросами современных наукоемких
технологий. Рецензенты: Б. М. Писаревский, профессор кафедры
высшей математики РГУ нефти и газа
им. И. М. Губкина
В. В. Блаженков, профессор, д. т. н. , зав. к,афедрой математики Военной академии
им. Петра Великого
ISBN 5-7246-0205-9
© РГУ нефти и газа
им. И. М. Губкина, 2002
©Соболева Т. С. , 2002
Содержание
ВВЕДЕНИЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... б
1 ОСНОВНЬIЕ ПОНЯТИЯ
ТЕОРИИ MIIOЖECTB ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 8
1. 1 Способы задания множеств ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 8
1. 2 Операции над множествами ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 12
1. 3 Характеристическая функция множества ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 14
1. 4 Декартово nроизведение множеств ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 17
2 ОТОБРАЖЕНИЯ МНОЖЕСТВ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 22
2. 1 Понятие отображения ...
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 22
2. 2 Сюръективные. ииъективные н бнективные отображення ... ... ... ... ... ... ... . . 23
2. 3 Суnерпозиция отображений ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 25
2. 4 Обратные отображения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 25
3 МОЩНОСТЬ МНОЖЕСТВА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 27
3. 1 Конечные и счетные множества ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 27
3. 2 Несчетные множества ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 30
4 ОТНОШЕНИЯ И ФУНКЦИИ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 32
4. 1 Бинарные и n-арные отношения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 32
4. 2 Обратные отношения.
