Раздел I элементы теории множеств.

Содержание

Лекция 1 Введение…………………………………………………………… 4

Раздел I. Элементы теории множеств …………………………........... 4

§1 Определение множеств………………………………............... 4

Лекция 2 §2 Операции над множествами…………………………............... 5

§3 Отношения между множествами……………………............... 7

§4 Основные свойства теоретико-множественных

операций……………………………………………………… 8

Лекция 3 §5 Доказательства тождеств в алгебре множеств………............. 9

§6 Разбиение………………………………………………………. 10

§7 Кортеж…………………………………………………………. 11

Лекция 4 §8 Декартово (прямое) произведение……………………............ 12

§9 Отображение…………………………………..………............. 13

§10 График………………………………………………...………. 14

Лекция 5 §11 Соответствие…………………………………………………. 15

Лекция 6 §12 Отношение……………………………………………............. 17

Лекция 7 Раздел II. Элементы математической логики …………………… 21

Часть 1. Исчисление высказываний……………………………………. 21

§1 Высказывания………………………………………...………... 21

§2 Свойства логических операций……………………….……… 23

§3 Логические формулы………………………………..………… 24

Лекция 8 §4 Функции алгебры логики (ФАЛ)……………...………............ 24

Лекция 9 §5 Способы вычисления ФАЛ…………………………................ 28

§6 Проблема разрешения…………………………………………. 29

Лекция 10 §7 Аналитические (канонические) формы

представления ФАЛ………………………………….. ….. 30

Лекция 11 §8 Интерпретация алгебры логики………………………………. 34

§8.1 Интерпретация алгебры логики в исчислении

высказываний…………………………………...…………. 34

§8.2 Интерпретация алгебры логики в теории

множеств…………………………………………………... 35

§8.3 Интерпретация алгебры логики в теории

конечных автоматов……………………………………… 36

Лекция 12 §9 Анализ простейших рассуждений…………………....……… 37

§10 Методы доказательств……………………………….……… 41

Лекция 13 §11 Предикаты……………………………………………………. 42

§12 Кванторы………………………………………………........... 44

§13 Формулы исчисления предикатов………………………….. 45

Лекция 14 §13.1 Операции логики высказываний над предикатами............ 46

§14 Равносильные формулы в исчислении предикатов............... 48

Лекция 15 §15 Подходы к построению выводов………………….....…….... 51

§16 Минимизации булевых функций…………………..……….. 51

Лекция 16 §17 Геометрическое представление булевых функций…............ 55

§18 Методы минимизации булевых функций ………………….. 57

1. Метод неопределенных коэффициентов…………………….. 57

2. Метод минимизирующих карт (Гарвардский

метод)………………………………………………. ……….. 59

Лекция 17 §19 Основные классы булевых функций………………...……… 60

Критерий Поста-Яблонского……………………….................. 62

Раздел III. Элементы теории графов ………………………………….. 63

Лекция 18 §1 Основные определения……………………………………….. 63

Простейшие примеры графов……………………..………….. 63

Описание графов с помощью матриц……………...………… 66

Лекция 19 §2 Связь бинарных отношений и графов……………….………. 68

§3 Связность в графах……………………………………............ 72

Лекция 20 §4 Эйлеровы и Гамильтоновы графы…………………………... 73

Список литературы …………………………………………………….. 75

Список №1 (по теории множеств – раздел I)………………….. 75

Список №2 (по математической логике – раздел II)…………… 76

Список №3 (по теории графов – раздел III)…………………….. 77

Калядин Н.И. Дискретная математика: Учебно-методическое пособие – Ижевск: Изд-во ИМИ, 1977г. – 78с.

Лекции были прочитаны в Ижевском механическом институте на специальности «инженер - математик» на кафедре «Прикладная математика».

Учебно-методическое пособие представляет интерес для студентов по специальностям 230101, 230401, 07550.

Компьютерный набор и верстка выполненены студентами Мерзляковым О.В., Сазоновым А.С.

Введение.

Вся современная математика условно может быть разделена на 2 части:

Часть I Классическая математика ЧастьII Дискретная математика

(с непрерывным аргументом) (с прерывным аргументом)

Дискретная математика получила широкое развитие в связи с развитием средств вычислительной техники. Курс «Дискретная математика» включает:

1. Элементы теории множеств.

2. Элементы математической логики.

3. Элементы теории графов.

4. Алгебраические системы.

5. Числовые системы.

6. Комбинаторика.

РАЗДЕЛ I ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ.