План подготовки к экзамену по дискретной математике

План подготовки к экзамену.

1.  Множество. Элементы множества. Универсальное множество (универсум). Множество подмножеств (булеан). Мощность. Операции над множествами. Основные свойства операций над множествами. Равенство и включение множеств. Прямое произведение множеств.

2.  Отношения. Бинарные и n-арные отношения. Способы задания отношений. Операции над отношениями. Свойства отношений.

3.  Соответствия. Свойства соответствий. Взаимно однозначное соответствие.

4.  Отображения и функции. Функциональные элементы. Суперпозиция функций.

5.  Функции алгебры логики (логические функции). Основные свойства операций над переменными функций алгебры логики.

6.  Таблицы истинности (переключений). Определение значения логической функции по таблице истинности. СДНФ. СКНФ. Релейные контактные схемы.

7.  Минимизация формул алгебры логики. Карты Карно. Логические элементы.

8.  Графы. Построение графа по программе на машине Поста. Построение графа по программе на машине Тьюринга. Ориентированные и неориентированные графы. Способы задания. Графы и бинарные отношения. Операции над графами. Маршруты, цепи и циклы. Цикломатическое число. Связные компоненты графа. Деревья. Алгоритм Дейкстры. Раскраска графов. Составления расписания с помощью графов.