5.2. Вопросы к экзамену.
Понятие множества. Бесконечное, конечное, пустое множество. Подмножество. Понятие равенства множеств. Универсальное множество. Основные способы задания множеств.
Что называют пересечением, объединением, разностью, дополнением множеств? Изображение операций над множествами с помощью диаграмм Эйлера-Венна.
Мощность конечного множества. Понятие эквивалентности множеств. Счётное множество.
Понятие нечёткого множества. Функция принадлежности и способы её задания. Операции над нечёткими множествами.
В чём состоит правило суммы и правило произведения комбинаторики?
Что называют размещениями, сочетаниями, перестановками? Как подсчитать их число?
Что называют простым высказыванием, составным высказыванием, логической связкой? Истинностные значения, множество истинностных значений, таблица истинности высказываний.
Что называют отрицанием, дизъюнкцией, конъюнкцией, импликацией, эквиваленцией? Запишите их таблицы истинности.
Алфавит логики высказываний. Понятие формулы логики высказываний. Список переменных формулы, оценка списка переменных, таблица истинности формулы логики высказываний.
Какую формулу называют тавтологией, а какую формулу называют тождественно-ложной? Правильные рассуждения. Определение правильности рассуждений. Проблема разрешимости для логики высказываний.
Понятие равносильности формул. Основные равносильности логики высказываний.
Какие логические операции являются двойственными по отношению друг к другу? Какие формулы называют двойственными? Принцип двойственности логики высказываний?
Что называют элементарной конъюнкцией, дизъюнктивной нормальной формой (ДНФ), совершенной дизъюнктивной нормальной формой (СДНФ) формулы?
Что называют элементарной дизъюнкцией, конъюнктивной нормальной формой (КНФ), совершенной конъюнктивной нормальной формой (СКНФ) формулы?
Что называют
-местной
булевой функцией? Основные способы
задания булевых функций. Существенные
и фиктивные переменные. Понятие
двойственной булевой функции.Элементарные булевы функции
,
таблицы их значений.
Что называют полной системой булевых функций? Приведите их примеры. Базис системы булевых функций.
Замкнутые классы булевых функций. Классы Поста.
Критерии полноты систем булевых функций. Теорема Поста.
Представление булевой функции формулой логики высказываний в СДНФ, в СКНФ, полиномом Жегалкина.
Какую ДНФ называют минимальной? В чём состоит метод минимизирующих карт?
Контакты: замыкающие и размыкающие. Функция проводимости контактной схемы. Представление функции проводимости формулами логики высказываний (для 2-х последовательно соединённых контактов, для 2-х параллельно соединённых контактов). Упрощение контактных схем.
Понятие графа. Вершины и рёбра графа. Кратные рёбра, петли, дуги. Псевдограф, мультиграф, орграф, простой граф. Операции над графами.
Понятие инцидентности и смежности для графа. Матрица смежности и матрица инцидентности графа.
Понятие маршрута и пути в графе. Что называют длиной маршрута, цепью, циклом? Что называют эйлеровой цепью и циклом? Что называют гамильтоновой цепь и циклом? Понятие связности графа. Что называют деревом?