Сервер Методического Обеспечения вгуэс http://abc.Vvsu.Ru

Разработка, менеджмент и поддержка abc.vvsu.ru, Гмарь Александр, все вопросы по адресу: abc@vvsu.ru

Дата конвертации: 05 Октябрь 2000, 16:36 Все права защищены © ВГУЭС 2000. ВГУЭС, 690600, г.Владивосток, ул.Гоголя, 41, http://www.vvsu.ru (4232) 25-72-21, (4232) 42-91-58

Электронное издание.

Название: ДИСКРЕТНАЯ МАТЕМАТИКА (Конспект лекций)

Автор: Ю.Е. Шишмарев

Редактор: Л.И. Александрова

Аннотация: Пособие является первой частью дискретной математики, ко-торое включает в себя как классические разделы, так и те, кото-рые получили развитие в последние годы. Курс дискретной мате-матики читается во всех ВУЗах, где имеются специальности тех-нического, технологического и естественнонаучного профиля. В первую часть входят следующие разделы: метод математической индукции и неравенство Коши-Буняковского, алгебра высказыва-ний и ее приложение к анализу электрических цепей, теория множеств и теории бинарных предикатов. Для студентов всех специальностей, на которых изучается курс дискретной математики.

Содержание:

Введение 10

ВВОДНАЯ ГЛАВА Метод математической индукции (ММИ) 10

§1. Формулировки ММИ. Доказательство равенств 10

Теорема 1 (стандартный ММИ) 11

Пример 1 11

Доказательство 11

Пример 2 12

Доказательство 12

Пример 3 13

Доказательство 13

Теорема 2 14

Теорема 3 (возвратный ММИ) 14

Теорема 4 14

§2. Доказательство неравенств ММИ. Неравенство Коши 14

Пример 1 14

Доказательство 14

Пример 2 15

Доказательство 15

Теорема 1 (неравенство Коши-Буняковского) 15

Доказательство 15

Определение 2 16

Теорема 3 (неравенство Коши) 16

Доказательство 16

ГЛАВА I Алгебра высказываний 18

§1. Основные понятия. Логические операции 18

Примеры 19

Определение 1 20

Определение 2 20

Определение 3 21

Определение 4 21

Определение 5 22

Вопросы 23

§2. Определение высказывания. Таблица истинности для высказываний 24

Определение 1 24

Определение 2 (индуктивное определение высказывания) 24

Задача 24

Соглашение 1 25

Соглашение 2 25

Соглашение 3 25

Соглашение 4 25

Соглашение 5 25

Пример 26

Теорема 3 26

Доказательство 27

Задача 28

Определение 4 28

§3. Равносильные высказывания. Основные логические тождества 29

Определение 1 29

Примеры 29

Доказательство 29

Доказательство 29

Доказательство 30

Доказательство 30

Доказательство 31

Доказательство 31

Доказательство 32

§4. Дизъюнктивные нормальные формы (ДНФ) 33

Определение 1 33

Утверждение 2 33

Доказательство 33

Определение 3 33

Примеры 34

Определение 4 34

Примеры 34

Теорема 5 34

Доказательство 34

Пример 36

Решение 36

Пример 38

Решение 38

Замечание 38

§5. Построение высказываний по таблице истинности. Совершенные дизъюнктивные нормальные формы (СДНФ) 39

Определение 1 39

Пример 39

Утверждение 2 39

Доказательство 39

Определение 3 40

Пример 40

Теорема 4 41

Доказательство 41

Определение 5 41

Примеры 41

Теорема 6 42

Доказательство 42

Пример 42

§6. Приложение алгебры высказываний к исследованию электрических двухполюсников 43

Пример 45

ГЛАВА II Введение в теорию множеств 48

§1. Основные определения, терминология 48

Понятие множества 48

Пример 1 48

Пример 2 49

Определение 1 49

Теорема 2 49

Доказательство 49

Определение 3 50

Вопрос 51

Пример 1 51

Пример 2 51

Пример 3 51

Теорема 4 51

Доказательство 51

Определение 5 51

Теорема 6 51

Доказательство 52

Определение 7 52

Задача 1 52

§2. Операции объединения и пересечения. Круги Эйлера 52

Определение 1 52

Пример 52

Теорема 2 53

Доказательство 53

Теорема 3 54

Доказательство 54

Определение 4 54

Пример 54

Теорема 5 54

Доказательство 55

Теорема 6 55

Доказательство 55

Теорема 7 (дистрибутивные законы) 56

Доказательство 56

§3. Разность множеств, дополнение 56

Определение 1 56

Пример 57

Теорема 2 57

Доказательство 57

Теорема 3 (законы Моргана) 58

Доказательство 58

Определение 4 59

Пример 59

Теорема 5 59

Доказательство 59

Теорема 6 (законы Моргана для дополнений) 59

Доказательство 59

§4. Декартовы произведения 60

Определение 1 60

Теорема 2 60

Доказательство 60

Определение 3 61

Теорема 4 61

Доказательство 61

Определение 5 61

Пример 61

Упражнения 62

Определение 6 62

Теорема 7 62

Доказательство 62

Теорема 8 64

Доказательство 64

§5. Предикаты 64

Определение 1 64

Определение 2 65

Примеры 65

Задача 66

Примеры отношений 66

Определение 3 66

Определение 4 67

Пример 1 67

Пример 2 67

Теорема 5 68

Доказательство 68

Теорема 6 68

Доказательство 68

Теорема 7 68

Доказательство 69

§6. Отношение эквивалентности 69

Определение 1 69

Пример 1 69

Пример 2 70

Пример 3 70

Пример 4 70

Задача 71

Определение 2 71

Определение 3 71

Определение 4 71

Теорема 5 71

Доказательство 72

Теорема 6 72

Доказательство 72

§7. Отношение порядка 73

Определение 1 73

Примеры 73

Определение 2 75

Теорема 3 76

Доказательство 76

Теорема 4 76

Доказательство 76

§8. Линейно упорядоченные множества. Лексикографический порядок 77

Определение 1 77

Определение 2 78

Теорема 3 78

Доказательство 78

§9. Экстремальные элементы в частично упорядоченных множествах и подмножествах 80

Определение 1 80

Пример 1 80

Пример 2 80

Пример 3 80

Задача 1 81

Задача 2 81

Определение 2 81

Теорема 3 81

Доказательство 81

Теорема 4 82

Доказательство 82

Определение 5 82

Пример 82

§10. Отображения 83

Определение 1 83

Задачи 83

Определение 2 83

Определение 3 83

Определение 4 84

Определение 5 84

Теорема 6 84

Доказательство 84

Теорема 7 85

Доказательство 85

Теорема 8 85

Доказательство 85

Теорема 9 86

Доказательство 86

Определение 10 87

Теорема 11 87

Доказательство 87

Определение 12 87

Пример 1 88

Пример 2 88

Пример 3 88

Определение 13 89

Определение 14 89

Теорема 15 89

Доказательство 90

Примеры обратных отображений 91

Теорема 16 91

Доказательство 91

Определение 17 92

Определение 18 93

Пример 94

ЛИТЕРАТУРА 94