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