Дискретная математика. Программа курса (МЭИ(ТУ), 2004-2005г)
Кафедра теоретической механики и мехатроники
  1. Множество, подмножество, собственное подмножество. Объединение множеств, пересечение, разность, симметрическая разность, абсолютное дополнением. Универсальное множество. Свойства операций (коммутативность, ассоциативность, дистрибутивность, идемпотентность). Свойства универсального и пустого множеств. Закон двойного дополнения. Законы де Моргана. Парадокс Рассела. Булеан. Мощность множества. Мощность булеана. Характеристическая функция.
  2. Прямое произведение. Упорядоченная пара. Три свойства прямого произведения. Соответствие между множествами. Область определения соответствия. Первая проекция соответствия. Область значений соответствия. Вторая проекция. Сечение соответствия. Обратное соответствие. Пустое соответствие. Полное соответствие. Булевы матрицы. Дизъюнкция и конъюнкция. Композиция соответствий. Условие существования композиции.
  3. Отображение. Отображение функциональное. Шесть свойств отображений. Сюръективное, инъективное, биективное отображение. Композиция отображений. Ассоциативность композиции отображений. Обратное отображение. Единичное отображение. Левое и правое обратное отображение. Лемма о единичной композиции двух отображений. Теорема о существовании обратного отображения.
  4. Отношения унарные и бинарные. Граф отношения. Матрица отношения. Единичное отношение. Полное отношение. Обратное отношение. Свойства отношений (рефлексивность, антирефлексивность, симметричность, антисимметричность, асимметричность, транзитивность). Композиция бинарных отношений. Условие транзитивности. Замыкание отношения. Рефлексивное замыкание. Транзитивное замыкание. Теорема о виде транзитивного замыкания. Вид транзитивного рефлексивного замыкания. Два алгоритма нахождения транзитивного замыкания. Отношение эквивалентности. Класс эквивалентности. Фактор-множество. Разбиение. Отношение порядка. Предпорядок. Полный порядок. Частичный порядок. Строгий порядок. Диаграмма Хассе. Отношение Паретто. Алфавит. Лексикографический порядок.
  5. Бинарная операция на множестве. Ассоциативность, коммутативность бинарной операции. Единичный элемент. Единственность единичного элемента. Полугруппа. Моноид. Обратный элемент моноида. Группа. Четыре аксиомы, которым удовлетворяет группа. Мультипликативная и аддитивная группа. Абелева группа. Подгруппа. Собственная подгруппа. Таблица Кэли. Свойство столбцов (строк) таблицы Кэли. Симметрическая группа. Циклическая группа. Конечная и бесконечная группа. Сравнение по модулю m. Изоморфные группы. Три свойства изоморфизма. Теорема Кэли о изоморфности. Теорема о изоморфности группе классов вычетов. Кольцо. Поле. Теорема о кольце классов вычетов на простых числах. Морфизмы.
  6. Принцип Дирихле