Вопросы к зачет у по дискретной математике.
Понятие высказывания. Отрицание высказывания. Конъюнкция, дизъюнкция, импликация двух высказываний. Эквивалентность двух высказываний. Формулы алгебры высказываний. Классификация формул алгебры высказываний. Конструирование сложных высказываний. Составление таблиц истинности для формул. Тавтологии алгебры высказываний. Основные тавтологии. Свойства логических операций. Основные правила получения тавтологий. Логическая равносильность формул. Признак равносильности формул. Примеры равносильных формул. Лемма о замене. Равносильные преобразования формул. Нормальные формы для формул алгебры высказываний. Представление формул алгебры высказываний СДН и СКН формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме. Логическое следование формул. Признаки логического следствия. Свойства логического следования. Следование и равносильность формул. Правила логических умозаключений. Проверка логического следования. Нахождение следствий из данных посылок. Нахождение посылок из данного следствия. Необходимые и достаточные условия. Противоположная и обратная противоположенной теоремы. Закон контрапозиции. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Принцип полной дизъюнкции. Бинарные отношения и функции. Понятие n – арного отношения. Булевы функции от одного и двух аргументов. Свойства булевых функций. Булевы функции от n аргументов. Суперпозиция булевых функций. Теорема о числе булевых функций от n аргументов. Полиномы Жегалкина и линейные булевы функции. Выражение одних булевых функций через другие. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций. Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций. Применение булевых функций к релейно-контактным схемам. Функция проводимости. Реализация булевых функций в виде релейно-контактных схем. Алгебраические структуры, полугруппы, моноиды, примеры. Понятие группы, группы перестановок, циклические группы. Понятия изоморфизма и гомоморфизма групп. Теорема Кэли. Понятия кольца, кольцо классов вычетов, гомоморфизм колец, целостные кольца. Теорема об обратимых элементах кольца. Понятие поля, подполя, расширение поля. Изоморфизм полей. n – местные отношения, графы и мультиграфы. Матрица смежности и инцидентности, теорема об изоморфизме графов и мультиграфов. Взвешенные графы, матрица весов, структура смежности. Подграфы и части графа. Операции над графами. Понятие полного графа и n – мерного куба. Композиция графов. Маршруты, цепи и циклы, примеры. Связные и сильно связные графы и компоненты. Теорема о маршрутах длины к и ее следствия. Матрицы связности, достижимости и контрдостижимости. Расстояние в графах, диаметр графа, вес маршрута. Алгоритмы Форда –Беллмана и Дейкстры, примеры. Элементы комбинаторного анализа.
