Лекция № 12. Полнота и замкнутость.

Ранее нами рассматривались два способа задания логических функций – табличный и с помощью формул. Таблица задаёт функцию непосредственно как соответствие между двоичными наборами и значениями функции на этих наборах. Этот способ универсален, то есть, пригоден для любых функций, однако слишком громоздок. Формула – гораздо более компактный способ задания функции, но она задаёт функцию через другие функции. Поэтому для любой системы функций возникает естественный вопрос: всякая ли логическая функция представима формулой в этой системе. В позапрошлой лекции был получен положительный ответ для системы (теорема 8.2). В данной лекции будет показано, как решать этот вопрос для произвольной системы .

1. Содержание

   • Конспект лекций по дисциплине “Дискретная математика”
   • Санкт Петербург Содержание.
   • Раздел I. Множества, функции, отношения. Лекция № 1. Множества и операции над ними.
   • 1. Основные понятия теории множеств.
   • 2. Операции над множествами и их свойства.
   • 3. Векторы и прямые произведения.
   • Лекция № 2. Соответствия и функции.
   • Соответствия.
   • Отображения и функции.
   • Лекция № 3. Отношения и их свойства.
   • Основные понятия и определения.
   • Свойства отношений.
   • Лекция № 4. Основные виды отношений.
   • Отношения эквивалентности.
   • Отношения порядка.
   • Лекция № 4. Пересчёт.
   • Раздел II. Введение в общую алгебру. Лекция № 6. Элементы общей алгебры.
   • 1. Свойства бинарных алгебраических операций.
   • 2. Алгебраические структуры.
   • Гомоморфизм и изоморфизм.
   • Лекция № 7. Различные виды алгебраических структур.
   • Полугруппы.
   • Группы.
   • Поля и кольца.
   • Раздел III. Введение в логику. Лекция № 8. Элементы математической логики.
   • Булевы функции.
   • Лекция № 9. Логические функции.
   • Функции алгебры логики.
   • Примеры логических функций.
   • Суперпозиции и формулы.
   • Лекция № 10. Булевы алгебры.
   • Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.
   • Булева алгебра функций.
   • Эквивалентные преобразования.
   • Лекция № 11. Булевы алгебры и теория множеств.
   • Двойственность.
   • Булева алгебра и теория множеств.
   • Днф, интервалы и покрытия.
   • Лекция № 12. Полнота и замкнутость.
   • Функционально полные системы.
   • Алгебра Жегалкина и линейные функции.
   • Замкнутые классы. Монотонные функции.
   • Теоремы о функциональной полноте.
   • Лекция № 13. Язык логики предикатов.
   • Предикаты.
   • Кванторы.
   • Истинные формулы и эквивалентные соотношения.
   • Доказательства в логике предикатов.
   • Лекция № 14. Комбинаторика.
   • Правила суммы и произведения.
   • Размещения.
   • Перестановки.
   • Сочетания. Бином Ньютона.
   • Раздел IV. Теория графов. Лекция № 15. Графы: основные понятия и операции.
   • Графы, их вершины, рёбра и дуги. Изображение графов.
   • Матрица инцидентности и список рёбер. Матрица смежности графа.
   • Идентификация графов, заданных своими представлениями.
   • Лекция № 16. Маршруты, цепи и циклы.
   • Основные определения.
   • Связные компоненты графов.
   • Расстояния. Диаметр, радиус и центр графа. Протяжённости.
   • Эйлеровы графы.
   • Лекция № 17. Некоторые классы графов и их частей.
   • Деревья.
   • Ориентированные графы.
   • Графы с помеченными вершинами и рёбрами.
   • Лекция № 18. Теория алгоритмов Понятие алгоритма
   • 1.2.1. Основные требования к алгоритмам
   • 1.2.2. Машина Тьюринга
   • Универсальная машина Тьюринга
   • 1.2.3. Тезис Тьюринга
   • 1.3. Граф машина
   • 1.3.1. Модель данных
   • 1.3.2. Построение моделей алгоритмов в системе graph
   • 2. Сложность алгоритмов
   • 2.1.Временная и пространственная сложность алгоритма. Классы dtime и dspace
   • 2.2. Классы сложности
   • 2.2.1. Полиномиальность и эффективность
   • 2.2.2. Алгоритмическая сводимость задач
   • 3. Алгоритмы и их сложность
   • 3.1. Представление абстрактных объектов (последовательностей)
   • 3.1.1. Смежное представление последовательностей
   • 3.1.2. Связанное представление последовательностей
   • Список вопросов для подготовки к экзамену по дисциплине "дискретная математика"