 |
|
Тема 1. Логические высказывания и предикаты.
Бучацкая В.В.
Введение в дискретную математику
Методические указания для студентов по курсам
«Дискретная математика», «Дискретная математика, математическая логика и алгоритмизация»
Для студентов направлений подготовки
080500 «Бизнес-информатика»
090900 «Информационная безопасность»
220400«Управление в технических системах»
230100 «Информатика и вычислительная техника»
Майкоп 2012
Содержание.
Введение. 4
Тема 1. Логические высказывания и предикаты. 5
1. Понятие высказывания. Логические операции над высказываниями. 5
2. Формулы и их логические возможности. 6
3. Свойства логических операций (законы логики). 6
4. Понятие предиката. Операции над предикатами. 8
5. Кванторы. 8
Практическая работа по теме 1. 10
Задания для самостоятельной работы по теме 1. 12
Контрольные вопросы по теме 1. 16
Тема 2. Множества. Отношения. Отображения. 17
1.Основные понятия. 17
2. Операции над множествами. 18
3. Геометрическое моделирование множеств. Диаграммы Венна. 19
4. Соотношение между множествами и составными высказываниями. 19
5. Алгебра множеств. Основные тождества алгебры множеств. 20
6. Эквивалентность множеств. 22
Практическая работа по теме 2. 25
Задания для самостоятельной работы по теме 2. 26
Контрольные вопросы по теме 2. 28
Тема 3. Отношения. Функции. 29
1. Основные понятия и определения. 29
2. Бинарные отношения и их свойства. 30
3. Отношение эквивалентности. 32
4. Функции. Основные понятия и определения. 33
Практическая работа по теме 3. 34
Задания для самостоятельной работы по теме 3. 35
Контрольные вопросы по теме 3. 36
Тема 4. Булевы функции. 36
1. Определение булевой функции. 36
2. Существенные и фиктивные переменные. 37
3. Формулы логики булевых функций. 38
4. Эквивалентность булевых формул. 38
5. Равносильные преобразования формул. 39
6. Двойственность. Принцип двойственности. 40
7. Нормальные формы. 41
8. Полные системы булевых функций. 44
9. Полином Жегалкина. 44
10. Замкнутые классы функций. 45
11. Функциональная полнота. 46
Задания для самостоятельной работы по теме 4. 50
Контрольные вопросы по теме 4. 51
Тема 5. Основные понятия теории графов. 52
1. Основные понятия теории графов. 52
2. Планарность и изоморфизм графов. 58
3. Способы задания графов. 60
4. Связность графа. 63
5. Алгоритм обхода вершин графа. 64
6. Нагруженные графы.. 67
7. Деревья. 67
Практическая работа по теме 5. 70
Задания для самостоятельной работы по теме 5. 74
Контрольные вопросы к теме 5. 76
Задания контрольной работы.. 78
Список источников литературы.. 81
Введение.
Дискретная математика - часть математики, которая уходит своими истоками в глубокую древность. Само название этого раздела математики говорит о том, что его спецификой является дискретность, т.е. антипод непрерывности. В широком смысле дискретная математика включает в себя такие сложившиеся разделы как теория множеств, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в связи с научно-техническим прогрессом. Создание сложных управляющих систем и внедрением ЭВМ в различные сферы деятельности дали новый импульс для развития теории функциональных систем, теории графов и сетей, комбинационного анализа, целочисленного программирования и т.п. Таким образом, дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования.
Дисциплины «Дискретная математика», «Дискретная математика, математическая логика и алгоритмизация» являются общим теоретическим и методологическим основанием для всех математических дисциплин и дисциплин информационного блока, входящих в ООП бакалавра по направлениям подготовки 080500 «Бизнес-информатика», 090900 «Информационная безопасность», 220400«Управление в технических системах», 230100 «Информатика и вычислительная техника».
Методические указания по учебным дисциплинам «Дискретная математика» и «Дискретная математика, математическая логика и алгоритмизация» разработаны в соответствии с требованиями федеральных государственных образовательных стандартов высшего профессионального образования указанных направлений подготовки бакалавров. Изучение курса базируется на знаниях, полученных в результате освоения дисциплин «Основы современной математики», «Информатика», «Языки программирования».
Цели и задачи курса:
– ознакомить с основами разделов дискретной математики: математическая логика, теория множеств, теория булевых функций, теория графов;
– дать представление о теоретических основах и методах дискретной математики как математических моделях для описания и исследования объектов реального мира, полезных для решения практических задач.
В результате изучения дисциплины студенты должны:
– получить представление о понятиях и теоретических моделях изучаемых направлений дискретной математики;
– освоить приемы применения теоретических моделей для описания предлагаемых заданий и получения результатов;
– приобрести практические навыки по отработке формализованных описаний объектов методами дискретной математики.
Лекционные занятия по данной дисциплине являются установочными, базовыми для самостоятельной работы студентов. Каждый студент слушает курс лекций, проходит практикум и может выполнить задания контрольной работы, включенные в пособие.
Курс состоит из трех модулей: «Основы математической логики», «Множества. Отношения. Отображения», «Булевы функции. Основы теории графов», каждый из которых включает следующие разделы:
· минимальные теоретические сведения по рассматриваемой теме;
· типовые задания и их решения;
· варианты заданий для практической и самостоятельной работы;
· контрольные вопросы.
Методические указания нацелены на активизацию самостоятельной работы студентов.
Тема 1. Логические высказывания и предикаты.