- •Введение в дискретный анализ
- •Глава 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.2. Алгебра Жегалкина и линейные функции
Алгебра над множеством логических функций с двумя бинарными операциями называется алгеброй Жегалкина.
Замечание. Операция вполне аналогична операции конъюнкции (логического умножения). Однако операция имеет совершенно другой математический смысл, чем дизъюнкция. Поэтому никак нельзя считать алгебру Жегалкина иной формой записи булевой алгебры.
В алгебре Жегалкина выполняются следующие соотношения (знак умножения опущен):
, , , . |
(1) (2) (3) (4) |
Кроме того, выполняются соотношения, ранее сформулированные булевой алгебры, относящиеся к конъюнкции и константам. Отрицание и дизъюнкция выражаются так:
5 , 6 . |
(5) (6) |
Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все упрощения по вышеуказанным соотношениям, то получится формула, имеющая вид суммы произведений, то есть полином (многочлен) по модулю 2. Такая формула называется полиномом Жегалкина для данной функции.
От булевой формулы всегда можно перейти к формуле алгебры Жегалкина, используя равенства (5) и (6), а также прямое следствие из равенства (6): если , то . Оно, в частности, позволяет заменять знак дизъюнкции знаком в случаях, когда исходная формула представляет собой СДНФ.
Пример 2.
Составить полиномы Жегалкина для данных функций:
а) ,
б) .
Заметим, что если в полученных полиномах Жегалкина произвести обратную замену функций, то получим упрощённые формулы булевой алгебры.
Теорема 2. Для всякой логической функции существует полином Жегалкина и притом единственный.
Существование такого полинома, по сути, уже доказано, а для доказательства его единственности достаточно показать существование взаимно однозначного соответствия между множеством всех функций переменных и множеством всех полиномов Жегалкина.
Функция, у которой полином Жегалкина имеет вид , где параметры равны нулю или единице, называется линейной.
Все функции от одной переменной линейны. Также линейными являются функции эквивалентность и сумма по модулю 2.
2.3.3. Замкнутые классы и монотонные функции
Множество логических функций называется замкнутым классом, если любая суперпозиция функций из множества снова принадлежит .
Всякая система логических функций порождает некоторый замкнутый класс, а именно класс всех функций, которые можно получить суперпозициями функций . Такой класс называется замыканием и обозначается . Если множество - функционально полная система, то .
Пример 3.
а) Множество всех дизъюнкций, то есть функций вида является замкнутым классом.
б) Множество всех линейных функций является замкнутым классом, так как подстановка формул вида после преобразований даёт формулу такого же вида.
Важнейшим примером замкнутого класса является класс монотонных функций, который будет рассмотрен далее.
Ранее рассматривалось отношение частичного порядка на множестве векторов одинаковой длины. Напомним, что для векторов и выполняется , если для любого выполняется . Здесь воспользуемся этим отношением для двоичных векторов.
Функция называется монотонной, если для любых двух двоичных наборов длины из того, что следует .
Пример 4.
а) Функция монотонна.
б) Дизъюнкция и конъюнкция любого числа переменных являются монотонными функциями.
в) Рассмотрим две функции от трёх переменных, заданных следующей таблицей.
|
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
Функция , очевидно, не является монотонной, так как, например , а . Монотонность функции легко установить непосредственной проверкой.
Проверка монотонности функции непосредственно по определению требует анализа таблицы функции и может оказаться достаточно трудоёмкой. Поэтому весьма полезной для установления монотонности является следующая теорема.
Теорема 3. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.
Из данной теоремы и того очевидного факта, что подстановка нескольких формул без отрицаний в формулу без отрицаний снова даёт формулу без отрицаний, вытекает следующая теорема.
Теорема 4. Множество всех монотонных функций является замкнутым классом.
Но поскольку всякая булева формула без отрицаний является суперпозицией дизъюнкций и конъюнкций, из данной теоремы непосредственно получаем следствие.
Следствие. Класс монотонных функций является замыканием системы функций .