Файл: Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики.doc

Изучая понятие мощности множества, основные теоремы о счетных множествах, нужно подчеркнуть, что «количество элементов» в бесконечном множестве может быть различным, что дискретные множества – это конечные и счетные множества, дискретная математика – математика дискретных величин, в отличие от математики непрерывных величин.
Изучив данную тему студент должен:

• 
  Знать:
  

• 
  основные понятия теории множеств, понятие мощности множества, операции над множествами, как частный случай алгебры Буля, декартово произведение множеств, отображение множеств, типы отображений, отношения на множествах, специальные бинарные отношения.
  

• 
  Уметь:
  

• 
  иллюстрировать основные понятия примерами из различных математических прикладных дисциплин.
  

План практических занятий по теме 1.

1. 
   Алгебра Буля. Операции над множествами (иллюстрация операций диаграммами). Основные равносильные формулы. Преобразования формул.
   
2. 
   Эквивалентные множества. Мощность множества. Сравнение мощностей множеств.
   
3. 
   Прямое произведение множеств. Отображение множеств. Типы отображений.
   
4. 
   Отношения на множествах. Бинарные отношения, свойства отношений. Специальные бинарные отношения.
   

Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии «Дискретная математика». – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). /Литература 1/

Тема 2. Математическая логика
При изучении данной темы следует обратить внимание на то, что алгебра высказываний является частным примером булевой алгебры и провести аналогию между логическими и теоретико-множественными операциями.

Следует изучить основные логические операции (связки), понятие полной системы связок

---

, понятие формулы алгебры, высказываний, основные равносильные формулы. Показать, как высказываниям в естественном и математическом языке могут быть поставлены в соответствие логические формулы. Рассмотреть основное понятие – понятие логической функции и уяснить связь между формулами и функциями алгебры высказываний. Изучить логические отношения между высказываниями (отношение следования, отношение эквивалентности и отношение несовместимости), а также способы проверки правильности рассуждений.

Рассмотреть, как проблема определения типа формулы (проблема разрешимости) может быть решена с помощью приведения формулы к нормальным формам (НФ) и определить конструктивно понятие совершенной нормальной формы формулы алгебры высказываний (СНФ).

Изучить построение формулы алгебры высказываний по заданной функции.

Выяснить возможность моделирования формул алгебры высказываний релейно-контактными схемами, а также какие задачи при этом могут быть решены.

Рассмотреть формальную аксиоматическую систему, адекватную алгебре высказываний – исчисление высказываний; основные проблемы формальной логической системы, как они решаются и как она может быть применена к конкретной научной области.

Далее изучается логика предикатов, которая включает в себя алгебру высказываний как составную часть. Рассматриваются операции над предикатами, кванторы общности и существования, применение кванторов в математических науках.

Изучив данную тему студент должен:

• 
  Знать:
  

• 
  все понятия, перечисленные выше, связанные с ними свойства, соотношения, теоремы;
  
• 
  рассматриваемые в теории проблемы и способы их решения.
  

• 
  Уметь:
  

• 
  применять язык, методы и средства математической логики в математических дисциплинах и в прикладных дисциплинах.
  

Планы практических занятий по теме 2

1. 
   Логические операции. Формулы алгебры высказываний. Равносильность формул. Полные системы связок.
   
2. 
   Логические функции. Связь с формулами алгебры высказываний. Существенные и фиктивные переменные.
   
3. 
   Логические отношения. Проверка правильности рассуждений.
   
4. 
   Нормальные формы алгебры высказываний. Установление типа формулы.
   
5. 
   Совершенные нормальные формы. Построение формулы алгебры высказываний по заданной функции.
   
6. 
   Алгебра высказываний и релейно-контактные схемы. Упрощение схем.
   
7. 
   Исчисление высказываний: алфавит, формулы, аксиомы, правила вывода. Проблемы непротиворечивости, полноты и независимости системы аксиом.
   
8. 
   Логика предикатов. Операции над предикатами. Кванторы.
   

---

Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практи-ческих пособиях:

Дискретная математика. – М. : МГУЭСИ, 2009. (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников.) / Литература 1 /

Математическая логика и теория алгоритмов. – М. : МГУЭСИ, 2009. (Гриф УМО Минобрнауки РФ.) (Авторы Э.Л. Балюкевич, Л.Ф. Ковалёва.) / Литература 2 /

Тема 3. Теория графов
В этой теме рассматриваются основные понятия, связанные с конечными графами.

Даются определения ориентированных и неориентированных графов, способы их задания и представления. Рассматриваются теоремы, связанные с путями на графе, понятия связности, изоморфизма и планирности графов. Изучаются числа, характеризующие граф: цикломатическое, хроматическое число, числа внутренней и внешней устойчивости.

Далее излагаются операции над графами: объединение, пересечение, прямое произведение графов. Рассматриваются матрицы для графов и выполнение с помощью матриц смежности основных операций над графами.

Значительная часть темы рассматривает графы типа – дерево. Необходимо изучить свойства деревьев, теоремы о них. Рассматривается задача нахождения кратчайшего дерева и её экономическая интерпретация. Для отыскания кратчайшего дерева используется алгоритм Краскала.

Отдельный раздел посвящен некоторым экстремальным задачам на графах: нахождению путей минимальной и максимальной длины на графе. Дается экономическая интерпретация каждой из этих задач. Рассматривается алгоритм Форда для их решения. Для задачи нахождения пути максимальной длины на графе рассматривается её применение в сетевом планировании.
Изучив данную тему студент должен:

• 
  Знать:
  

• 
  определения основных понятий, теоремы и их доказательства;
  
• 
  рассматриваемые в теории задачи и методы их решения.
  

• 
  Уметь:
  

• 
  применять язык, методы и средства теории графов в дисциплинах прикладного характера.
  

Планы практических занятий по теме 3:

1. 
   Способы представления графов.
   
2. 
   Числа, характеризующие граф.
   
3. 
   Операции над графами.
   
4. 
   Деревья, их свойства.
   
5. 
   Задачи нахождения кратчайшего дерева, её технико-экономическая интерпретация.
   
6. 
   Задача нахождения пути максимальной длины на графе, её применении в сетевом планировании.
   

---

Рекомендации по выполнению конкретных заданий, вопросы и тесты для самопроверки содержатся в учебно-практическом пособии:

Дискретная математика. – М. : МГУЭСИ, 2009 (авторы Э.Л. Балюкевич, Л.Ф. Ковалёва, А.Н. Романников). / Литература 1 /
Список литературы

1. 
   Балюкевич Э.Л., Ковалёва Л.Ф., Романников А.Н. Дискретная математика : учебно-практическое пособие. – М. : МГУЭСИ, 2009.
   
2. 
   Балюкевич Э.Л., Ковалёва Л.Ф. Математическая логика и теория алгоритмов : учебно-практическое пособие. – М. : МГУЭСИ, 2009 (гриф УМО Минобрнауки РФ).
   

(Расширенные списки литературы с указанием интернет-ресурсов имеются в указанных выше учебно-практических пособиях.)

---