Geum.ru

Календарный план учебных занятий по обязательной дисциплине «Дискретная математика и математическая логика» (3-й семестр, 2-й курс). Направление подготовки «Математика. Прикладная математика»

Вид материалаЛекции

Содержание


Виды и содержание учебных занятий
Подобный материал:
Российский Университет Дружбы народов

Факультет физико-математических и естественных наук


Кафедра нелинейного анализа и оптимизации

117198, Москва, ул. Орджоникидзе, д. 3, кк. 511-514, тел.: (495) 955-09-36


КАЛЕНДАРНЫЙ ПЛАН

учебных занятий по обязательной дисциплине «Дискретная математика и математическая логика» (3-й семестр, 2-й курс).


Направление подготовки «Математика. Прикладная математика».


Виды и содержание учебных занятий:

Неделя
Лекции
Число часов
Практические занятия
Число часов

1
  1. Множества, подмножества, равенство множеств. Основные операции над множествами (объединение, пересечение, разность, симметрическая разность, возведение в степень) и их важнейшие свойства. Универсальное множество. Операция дополнения и ее свойства. Декартово произведение двух и более множеств. Равномощность множеств. Примеры. Теоремы о счетных множествах. Примеры несчетных множеств.
2
Операции над множествами, равномощность множеств
2

2
  1. Теорема Кантора-Бернштейна. Сравнение мощностей.
  2. Теорема Кантора о мощности множества всех подмножеств данного множества. Противоречивость понятия множества всех множеств. Парадокс Рассела.
  3. Мощность континуума, ее несчетность. Равномощность отрезка и квадрата.
2
Мощности множеств
2

3
  1. Канторово множество. Его равномощность отрезку. Алгебраические и трансцендентные числа. Существование трансцендентных чисел.
  2. Арифметика кардинальных чисел (мощностей). Свойства степени. Свойства монотонности.
  3. Упорядоченные пары по Куратовскому и Винеру. Декартово произведение множеств.
2
Мощности множеств
2

4
  1. Отношения на декартовом произведении двух множеств (бинарные отношения). Функциональные отношения (отображения). Композиция отображений. Инъективные, сюръективные и биективные отображения. Обратное отображение. Условие его существования и един­ственности.
  2. Отношения эквивалентности на множестве. Разбиение на классы. Фактормножество. Примеры.
2
Отношения и функции
2

5
  1. Отношения строгого и нестрогого порядка на множестве. Эквивалентность получающихся конструкций. Изоморфизм упорядоченных множеств. Автоморфизмы. Важнейшие примеры. Наибольшие и максимальные элементы. Операции над упорядоченными множествами.
  2. Изоморфизм счетных плотных линейно упорядоченных множеств без наибольшего и наименьшего элементов.
2
Отношения эквивалентности
2

6
Фундированные множества. Эквивалентность различных определений.
2
Упорядоченные множества
2

7
Вполне упорядоченные множества, их основные свойства и структура. Предельные элементы. Теорема о возрастающем эндоморфизме вполне упорядоченного множества (различные доказательства). Арифметика ординалов.
2
Упорядоченные множества
2

8
  1. Аксиома выбора, теорема Цермело, лемма Цорна. Существование базиса Хамеля в любом линейном пространстве. Наличие продолжения любого порядка на множестве до линейного.
2
Комбинаторика
2

9
  1. Функции алгебры логики (булевы функции). Способы их задания. Существенные и фиктивные (несущественные) переменные. Равенство функций. Формулы. Реализация функций формулами. Основные функции и их важнейшие свойства.
  2. Разложение функции по переменным. Совершенная дизъюнктивная нормальная форма (СДНФ) булевой функции.
2
Комбинаторика
2

10
  1. Двойственная функция. Принцип двойственности. Совершенная конъюнктивная нормальная форма (СКНФ) булевой функции.
  2. Операция замыкания. Ее простейшие свойства. Замкнутые классы функций. Полные системы функций. Примеры полных систем. Примеры полных систем, состоящих из ровно одной функции.
  3. Полиномы Жегалкина. Теорема существования и единственности полинома для заданной функции. Линейные функции.
  4. Самодвойственные функции. Примеры. Отсутствие самодвойственных функции, существенно зависящих ровно от двух переменных. Лемма о несамодвойственной функции.
2
Функции алгебры логики
2

11
  1. N-мерный куб. Монотонные функции. Число монотонных функций от 1, 2, 3 и *4-х переменных. Лемма о немонотонной функции.
  2. Важнейшие классы булевых функций (T0, T1, S, M и L). Их замкнутость. Подсчет числа функций от n переменных в них (кроме класса M).
2
Подсчет числа функций в различных классах
2

12
  1. Следствия из теоремы Поста (о замкнутом классе и о пяти предполных классах). Формулировки («сильных») результатов Поста.
  2. Базисы в замкнутых классах. Возможность выделения в каждой полной системе базиса, состоящего не более чем из четырех функций. Точность последней оценки.
2
Полнота и замкнутость
2

13
Коллоквиум
2
Разные задачи на функции алгебры логики
2

14
  1. Элементарные конъюнкции. Дизъюнктивные нормальные формы. Допустимые конъюнкции (импликанты). Геометрическая интерпретация. Минимальные и кратчайшие ДНФ. Сокращенная ДНФ, геометрический алгоритм ее построения.
  2. Теоремы о связи минимальных и кратчайших с сокращенной ДНФ.Теорема о сокращенной ДНФ монотонной функции. Базис класса М.
2
Минимизация в классе ДНФ. Геометрический алгоритм
2

15
  1. Неприводимые покрытия куба интервалами. Тупиковые ДНФ. Геометрический алгоритм отыскания всех минимальных ДНФ и хотя бы одной кратчайшей.
2
Метод Блейка. Критерий поглощения.
2

16
  1. Метод Блейка построения сокращенной ДНФ.
2
Подготовка к контрольной работе
2

17
  1. Критерий поглощения. Алгоритм построения всех тупиковых ДНФ.
2
Контрольная работа
2

18
Заключительная обзорная лекция
2
Разбор контрольной работы, подготовка к зачету
2

19 – 20
ИТОГОВЫЙ КОНТРОЛЬ ЗНАНИЙ – ЗАЧЕТ



Заведующий кафедрой нелинейного анализа и оптимизации, проф. ______ Арутюнов А.В.