Двойственность.

Определение. Функция называется двойственной к функции , если .

Если взять отрицание обеих частей равенства и подставить вместо переменных , то получится . Это означает, что функция двойственна к функции , и, таким образом, отношение двойственности является симметричным. Из определения двойственности ясно, что для любой функции двойственная ей функция определяется однозначно. В частности, может оказаться, что функция двойственна самой себе. В этом случае она называется самодвойственной.

Пример 1. Если рассматривать логические функции, то, очевидно, дизъюнкция двойственна конъюнкции и наоборот (непосредственно следует из правил Де Моргана). Отрицание является самодвойственной функцией. Функция-константа двойственна функции . Ещё один традиционный пример самодвойственной функции – функция .

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

Теорема 10.1. Если в формуле , представляющей функцию , все знаки функций заменить соответственно на знаки двойственных им функций, то полученная формула будет представлять функцию , двойственную функции .

В булевой алгебре принцип двойственности имеет более конкретный вид, вытекающий из ранее приведённых примеров: если в формуле , представляющей функцию , все конъюнкции заменить дизъюнкциями и наоборот, все единицы заменить нулями и наоборот, то получим формулу , представляющую функцию , двойственную функции .

Если функции равны, то двойственные им функции также равны. Это позволяет с помощью принципа двойственности получать новые эквивалентные соотношения, переходя от равенства с помощью указанных замен к равенству . Примером могут служить соотношения и , которые могут быть получены друг из друга по указанному принципу.

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

   • Конспект лекций по дисциплине “Дискретная математика”
   • Санкт Петербург Содержание.
   • Раздел 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. Связанное представление последовательностей
   • Список вопросов для подготовки к экзамену по дисциплине "дискретная математика"