Дискретные структуры

В письменный экзамен могут войти задачи из следующих разделов курса

Введение в теорию множеств

       Способы определения множеств.

       Подмножества, собственные подмножества. Операции над множествами. Равенство множеств. Прямое произведение.

       Свойства множеств. Пустое множество, разбиение множеств. Законы Де Моргана.

Отношения

       Бинарные отношения. Свойства бинарных отношений: рефлексивность, симметричность, транзитивность.

       Представление отношений с помощью ориентированных графов.

       Отношение эквивалентности. Определение отношений с помощью классов эквивалентности (классов смежности).

Комбинаторика

       Размещения. Размещения без повторений.

       Перестановки.

       Сочетания. Сочетания с повторениями.

       Треугольник Паскаля.

       Бином Ньютона. Биномиальные коэффициенты.

       Число подмножеств конечного множества. Прочие тождества для C(n,k).

Графы и деревья

       Графы: основные понятия; способы представления графов. Ориентированные графы.

       Подграфы. Степень вершины.

       Цепи, пути и контуры. Эйлеровы и гамильтоновы контуры.

       Деревья, их свойства.

Логика высказываний

       Высказывания.

       Логические связки и составные высказывания. Таблицы истинности.

       Высказывательная форма.

       Законы Де Моргана.

       Эквивалентность высказываний.

       Тавтология и противоречие.

       Дизъюнктивная нормальная форма. Функция, порождаемая пропозициональной формой. Построение формы, порождающей заданную функцию.

       Полные системы связок.

       Формальные аксиоматические теории.  Вывод. Теорема дедукции.

Введение в синтез логических схем

       Цифровые логические схемы. Вентили и типы вентилей. Описание схем с помощью булевских выражений. Синтез схем по таблицам истинности. Эквивалентность схем.

       N-ичные системы счисления.

Логика предикатов

       Понятие предиката и множества истинности.

       Кванторы общности и существования. Отрицание квантифицированных высказываний. Связь между кванторами и связками.

       Логика предикатов, определение языка. Связанные и свободные переменные. Понятие интерпретации.

Литература

1.     Н.К. Верещагин, А. Шень. Начала теории множеств. 2-е издание, испр.- М.: МЦНМО, 2002.

2.     С.В. Судоплатов, Е.В. Овчинникова. Элементы дискретной математики: Учебник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2003. - 280 с. (Серия "Высшее образование").

3.     Б.Н. Иванов. Дискретная математика. Алгоритмы и программы: Учеб. пособие.- М.: Лаборатория Базовых Знаний, 2002 - 288 с.

4.     С.В. Яблонский. Введение в дискретную математику: Учеб. пособие для вузов. 2-е изд, перераб. и доп.- М.: Наука, Гл. ред. физ.-мат. лит., 1986.-384 с.

5.     А. Шень. Программирование: теоремы и задачи.- М.: МЦНМО, 1995.

6.     Э. Мендельсон. Введение в математическую логику.- М.: Наука, 1976.

7.     А.Н.Колмогоров, А.Г.Драгалин. Математическая логика.- М.:УРСС, 2004.