- •Введение в дискретный анализ
- •Глава 1. Введение в теорию множеств
- •Тема 1.1. Множества и операции над ними
- •1.1.1. Основные понятия
- •1.1.2. Операции над множествами
- •1.1.3. Векторы и прямые произведения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.2. Отношения
- •1.2.1. Основные понятия и определения
- •1.2.2. Бинарные отношения. Основные определения
- •1.2.4. Эквивалентность и порядок
- •Вопросы для повторения
- •Резюме по теме
- •Тема 1.3. Соответствия и функции
- •1.3.1. Соответствия и их свойства
- •1.3.2. Взаимно однозначные соответствия и мощности множеств
- •1.3.3. Функции и отображения
- •1.3.4. Операции
- •1.3.5. Гомоморфизмы и изоморфизмы
- •Вопросы для повторения
- •Резюме по теме
- •Глава 2. Математическая логика
- •Тема 2.1. Логика высказываний
- •2.1.1. Логические связки
- •2.1.2. Основные схемы логически правильных рассуждений
- •2.2.2. Булева алгебра
- •2.2.3. Эквивалентные преобразования
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.3. Полнота и замкнутость
- •2.3.1. Функционально полные системы
- •2.3.2. Алгебра Жегалкина и линейные функции
- •2.3.3. Замкнутые классы и монотонные функции
- •2.3.4. Теоремы о функциональной полноте
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.4. Нечеткая логика
- •2.4.1. Основные понятия теории нечетких множеств
- •2.4.2. Логические операции над нечеткими множествами
- •2.4.3. Свойства логических операций над нечеткими множествами
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.5. Нечеткие модели управления
- •2.5.1. Нечеткие операторы
- •2.5.2. Нечеткая и лингвистическая переменные
- •2.5.3. Нечеткий логический вывод
- •Вопросы для повторения
- •Резюме по теме
- •Тема 2.6. Логика предикатов
- •2.6.1. Предикаты. Основные понятия
- •2.6.2. Кванторы
- •2.6.3. Выполнимость и истинность
- •2.6.4. Эквивалентные соотношения. Префиксная нормальная форма
- •Вопросы для повторения
- •Резюме по теме
- •Глава 3. Комбинаторика
- •Тема 3.1. Комбинаторные конфигурации
- •3.1.1. Принципы сложения и умножения
- •3.1.2. Перестановки
- •3.1.3. Размещения
- •3.1.4. Сочетания
- •3.2.2. Полиномиальная формула
- •3.2.3. Формула включений и исключений
- •Вопросы для повторения
- •Резюме по теме
- •Глава 4. Теория графов
- •Тема 4.1. Основные понятия и операции на графах
- •4.1.1. Основные понятия
- •4.1.2. Способы задания графов
- •4.1.3. Операции над частями графа. Графы и бинарные отношения
- •Вопросы для повторения
- •Резюме по теме
- •Тема 4.2. Маршруты и деревья
- •4.2.1. Маршруты, пути, цепи, циклы
- •4.2.2. Дерево и лес
- •5.1.2. Способы задания автоматов
- •5.1.3. Взаимосвязь между моделями Мили и Мура
- •Вопросы для повторения
- •Резюме по теме
- •Тема 5.2. Детерминированные конечные автоматы
- •5.2.1.Основные понятия детерминированных конечных автоматов
- •5.2.2. Схема доказательства правильности конечного автомата
- •5.2.3. Произведение автоматов
- •5.3.2. Детерминизация нка
- •Вопросы для повторения
- •Резюме по теме
2.3.4. Теоремы о функциональной полноте
Будем искать свойства функций, позволяющие выразить через них булевы операции. Сначала сформулируем две леммы, позволяющие вывести соответствующие теоремы.
Лемма 1 (о немонотонных функциях). Если функция немонотонна, то подстановкой констант из неё можно получить отрицание.
Практически данная лемма является утверждением, противоположным теореме, обратной к теореме 3. Смысл её заключается в том, что для функции существует такая подстановка константы, что функция оставшейся одной переменной является отрицанием.
Лемма 2 (о нелинейных функциях). Если функция нелинейна, то с помощью подстановки констант и использования отрицаний из неё можно получить дизъюнкцию или конъюнкцию.
Иначе говоря, существует представление дизъюнкции и конъюнкции в виде суперпозиции констант, отрицаний и нелинейной функции .
Замечание. При традиционных обозначениях переменных в выражениях вида , где переменные расположены в естественном порядке индексов, эти индексы играют двоякую роль: они именуют переменные и нумеруют их места в функции. Эти роли следует различать.
Две указанные леммы позволяют получить все булевы операции с помощью немонотонных функций, нелинейных функций и констант. Это ещё не полнота в точном смысле слова, так как константы с самого начала предполагались данными. Однако такое предположение часто бывает оправданным в различных приложениях (прежде всего в синтезе логических схем). Поэтому есть смысл ввести ослабленное определение полноты.
Система функций называется функционально полной в слабом смысле, если любая логическая функция может быть представлена формулой над системой , то есть является суперпозицией констант и функций из системы .
Очевидно, что из обычной полноты системы следует её слабая полнота.
Теорема 5 (первая теорема о функциональной полноте). Для того, чтобы система функций была функционально полной в слабом смысле, необходимо и достаточно, чтобы она содержала хот бы одну немонотонную функцию и хотя бы одну нелинейную функцию.
Доказательство:
1) Необходимость. Классы монотонных и линейных функций замкнуты и содержат 0 и 1. Поэтому если не содержит немонотонных или нелинейных функций, то их нельзя получить с помощью суперпозиций функций из системы и констант.
2) Достаточность. Пусть содержит немонотонную и нелинейную функцию. Тогда по лемме 1 подстановкой констант из монотонной функции получаем отрицание, а затем по лемме 2 из нелинейной функции с помощью отрицаний и констант получаем дизъюнкцию и конъюнкцию.
Пример 5.
а) Система функционально полна в слабом смысле, так как операция нелинейна (как и конъюнкция), а операция (сложение по ) немонотонна.
б) В функционально полной системе единственная функция – штрих Шеффера – нелинейна и немонотонна.
Для формулировки необходимых и достаточных условий “cильной” полноты (в отличие от слабой) нужно ввести ряд определений, описывающих ещё три замкнутых класса функций.
Функция называется сохраняющей ноль, если выполняется и сохраняющей единицу, если выполняется .
Оба данных класса функций являются замкнутыми, что проверяется подстановкой констант в суперпозиции. Равным образом замкнутый класс образуют самодвойственные функции (такие, что ).
Теорема 6 (вторая – основная – теорема о функциональной полноте). Для того чтобы система функций была функционально полной (в сильном смысле), необходимо и достаточно, чтобы она содержала: 1) нелинейную функцию, 2) немонотонную функцию, 3) функцию, не являющуюся самодвойственной, 4) функцию, не сохраняющую ноль, 5) функцию, не сохраняющую единицу.