ВОПРОСЫ НАЭКЗАМЕН/ЗАЧЕТ  ПО КУРСУ

«ДИСКРЕТНАЯ МАТЕМАТИКА»

Тема 1. Комбинаторика

Понятие выборки. Принципы подсчёта. Правило суммы и произведения в комбинаторике. Линейно упорядоченные наборы. Циклические перестановки. Размещения с повторениями и без них. Перестановки с повторениями и без них. Сочетания с повторениями и без них. Комбинаторные тождества (тождество Ньютона, тождество Паскаля). Бином Ньютона. Биномиальные коэффициенты и их свойства. Полиномиальные коэффициенты. Треугольник Паскаля. Применение производящих функций для решения рекуррентных соотношений. Метод математической индукции.

Тема2. Множества

Множества, основные определения,  задание множеств. Подмножества и их свойства. Множество всех подмножеств. Операции над множествами, диаграммы Венна-Эйлера. Свойства операций над множествами. Покрытия и разбиения множеств. Принцип Дирихле. Формулы включений и исключений. Декартово произведение множеств. Бинарные отношения и их свойства, отношение эквивалентности. Отношения строгого, нестрогого порядка, отношения соответствия, функциональные отношения. Множества бесконечные, счетные, несчетные. Сравнение бесконечных множеств. Нечеткие  множества. Основные понятия, операции.

Тема 3. Логика высказываний. Булева алгебра.

Высказывания, операции над ними и их основные союзы. Высказывательные формулы, тавтологии, логическое следование. Законы алгебры логики. Понятие предиката, местность предиката. Кванторные операции. Булевы функции. Замкнутые классы. Полные системы булевых функций. Критерий полноты Поста. Представление булевой функции в виде формулы. Свойства совершенства. Геометрическая форма. Аксиомы и теоремы булевой алгебры. Дизъюнктивная нормальная форма (ДНФ).Совершенная дизъюнктивная нормальная форма (СДНФ): способы ее получения. Конъюнктивная нормальная форма (КНФ). Совершенная конъюнктивная нормальная форма (СКНФ): способы ее получения. Минимизация БФ. Минтермы, их свойства. Метод Квайна. Методы минимизация БФ: Квайна - Мак-Класки, Блейка-Порецкого, испытания остатков. Основные характеристики методов. Минимизация БФ. Понятие импликанты, метод получения простых импликант по карте Вейча. Алгоритм построения всех тупиковых ДНФ. Понятие  порядка  БФ. Граф-схема БФ. Повышение порядка БФ. Проблема интерпретации в многозначной логике. Трехзначное  исчисление высказываний Лукасевича. Понятие о функциях k-значной логики, их особенности.