- •Раздел 1. Алгебраические структуры Тема 1.1. Бинарные операции и их свойства
- •Тема 1.2. Алгебраические структуры
- •Тема 1.3. Основные свойства групп
- •Тема 1.4. Поля и кольца
- •Раздел 2. Алгебра множеств Тема 2.1. Основные определения теории множеств
- •Тема 2.2. Подмножество, понятие универсального множества
- •Тема 2.3. Операции над множествами
- •Раздел 3. Основные теоремы комбинаторики
- •Тема 3.1. Метод математической индукции
- •Тема 3.2. Основные принципы комбинаторики
- •Раздел 4. Комбинаторные объекты Тема 4.1. Сочетания
- •Тема 4.2. Размещения и перестановки
- •Раздел 5. Полиномиальные тождества Тема 5.1. Бином Ньютона
- •Тема 5.2. Понятие о методе рекуррентных соотношений
- •Тема 5.3. Метод производящих функций
- •Тема 5.4. Метод траекторий
- •Тема 5.5. Примеры комбинаторных задач
- •Раздел 6. Соответствие, отношение, отображение Тема 6.1. Понятие кортежа. Декартово произведение множеств
- •Тема 6.2. Определения и свойства
- •Тема 6.3. Типы отношений
- •Пересечение и объединение отношений
- •Композиция отображений и отношений
- •Тема 6.5. Решётки
- •Тема 6.4. Верхняя и нижняя границы множества.
- •Раздел 7. Операции булевой алгебры Тема 7.1.Понятие высказывания, простые и составные высказывания
- •Тема 7.2.Операции на множестве высказываний
- •Отрицание
- •Конъюнкция
- •Дизъюнкция
- •«Исключающее или»
- •Импликация
- •Эквивалентность
- •Штрих Шеффера
- •Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры
- •Тема 8.2.Законы и тождества Булевой алгебры
- •Тема 8.3.Составление формулы по заданной таблице истинности
- •Тема 8.4. Двойственность
- •Тема 8.5.Булева алгебра и теория множеств
- •Тема 8.6.Днф, интервалы и покрытия
- •Раздел 9. Функциональная полнота. Алгебра Жегалкина
- •Тема 9.1.Функционально полные системы
- •Тема 9.2.Алгебра Жегалкина и линейные функции
- •Тема 9.3.Замкнутые классы. Монотонные функции
- •Тема 9.4.Теоремы о функциональной полноте
- •Раздел 10. Хорновские формулы
- •Тема 10.1.Задача получения продукции
- •Тема 10.2.Решение задачи о продукции
- •Алгоритм замыкание(X,f)
- •Алгоритм ПрямаяВолна(X,y,f)
- •Алгоритм БыстроеЗамыкание(X,f)
- •Раздел 11. Теория релейно-контактных схем Тема 11.1.Основные понятия
- •Тема 11.2.Основные задачи теории релейно-контактных схем
- •Тема 11.3.Построение машины голосования
- •Тема 11.4.Двоичный сумматор
- •Тема 11.5.Методы упрощения логических выражений. Методы решения логических задач
- •Раздел 12. Логика предикатов Тема 12.1.Определение предиката
- •Тема 12.2.Логические операции над предикатами
- •Тема 12.3.Кванторы
- •Тема 12.4. Истинные формулы и эквивалентные соотношения
- •Тема 12.5.Доказательства в логике предикатов
- •Раздел 13. Теория графов
- •Тема 13.1.Основные определения теории графов
- •Тема 13.2. Способы задания графов
- •Тема 13.3. Отношения порядка и эквивалентности на графе
- •Тема 13.4. Числовые характеристики графа
- •Тема 13.5.Изоморфизм графов
- •Раздел 14. Проблемы достижимости на графах Тема 14.1.Граф достижимости
- •Тема 14.2.Взаимная достижимость, компоненты сильной связности и базы графа
- •Раздел 15. Некоторые классы графов Тема 15.1.Деревья
- •Тема 15.2. Обход графа
- •Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.
- •Раздел 16. Машина Тьюринга
- •Тема 16.1. Формальное описание машины Тьюринга
- •Тема 16.2. Примеры построения машины Тьюринга
- •Тема 16.3. Свойства машины Тьюринга как алгоритма
- •Раздел 17. Машина Поста
- •Тема 17.1. Теоретическая часть. Состав машины Поста
- •Тема 17.2. Применимость программ. Определение результата выполнения программ
- •Раздел 18. Основные понятия теории автоматов Тема 18.1. Общие подходы к описанию устройств, предназначенных для обработки дискретной информации
- •Тема 18.2. Способы задания конечного автомата
- •Тема 18.3. Эквивалентные автоматы
- •Тема 18.4. Автоматы Мура и Мили
- •Тема 18.5. Примеры синтеза автоматов
Тема 9.2.Алгебра Жегалкина и линейные функции
Определение:Алгебра над множеством логических функций с двумя бинарными операцияминазываетсяалгеброй Жегалкина.
В алгебре Жегалкина выполняются следующие соотношения:
;
;
;
.
Кроме того, выполняются соотношения, ранее сформулированные булевой алгебры, относящиеся к конъюнкции и константам. Отрицание и дизъюнкция выражаются так:
;
;
.
Если в произвольной формуле алгебры Жегалкина раскрыть скобки и произвести все упрощения по вышеуказанным соотношениям, то получится формула, имеющая вид суммы произведений, то есть полином (многочлен) по модулю 2. Такая формула называется полиномом Жегалкинадля данной функции.
От булевой формулы всегда можно перейти к формуле алгебры Жегалкина.
Пример 9.2:Составить полиномы Жегалкина для данных функций:
а) ,
б) .
Заметим, что если в полученных полиномах Жегалкина произвести обратную замену функций, то получим упрощённые формулы булевой алгебры.
Теорема:Для всякой логической функции существует полином Жегалкина и притом единственный.
Доказательство:Существование такого многочлена следует из того, что для любой ДНФ или КНФ можно с помощью указанных эквивалентностей найти эквивалентный многочлен Жегалкина: приведённые формулы позволяют заменять все вхожденияи отрицания наи, и перемножать получившиеся после такой замены многочлены.
Для доказательства единственности представления подсчитаем число различных многочленов Жегалкина от переменных. Каждая положительная элементарная конъюнкция имеет вид, где. Таких конъюнкций столько же, сколько подмножеств множества, т.е.. (Конъюнкция, соответствующая пустому подмножеству переменных равна 1). Упорядочим их произвольным образом (например, лексикографически):. Тогда каждый многочлен Жегалкина единственным образом можно представить как сумму
где каждый из коэффициентов равен 0 или 1. Следовательно, число многочленов Жегалкина равно, т.е. числу всех булевых функций отпеременных. Поэтому каждая функция задаётся в точности одним многочленом Жегалкина.
Если функция задана таблично, то для построения реализующего её многочлена Жегалкина можно применить метод неопределённых коэффициентов. Сопоставим-ому набору значений переменныхв таблице положительную конъюнкциюпеременных, равных 1 в этом наборе. Тогда для получения нужного многочлена Жегалкина достаточно определить все коэффициенты,в выражении
Подставляя в это равенство значения переменных из набора ,, мы получимлинейных уравнений относительнонеизвестных коэффициентов. Решив эту систему, получим требуемый многочлен Жегалкина. Эта система треугольная и легко решается «сверху – вниз»: каждоеопределяется по значениямиз уравнения, соответствующего набору.
Пример 9.3:Рассмотрим в качестве примера функцию, заданную следующей таблицей.
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1. |
1 |
1 |
Многочлен Жегалкина для неё (как и для любой функции от 3-х переменных) представляется в виде:
(Для сокращения записи в формуле опущены конъюнкции).
В этом представлении в индексах у коэффициентов перечислены переменные, входящие в соответствующие конъюнкции.
Последовательно подставляя значения переменных и функции из таблицы, получаем:
Следовательно, функция представляется многочленом Жегалкина:
Определение. Функция, у которой полином Жегалкина имеет вид, где параметрыравны нулю или единице, называетсялинейной.
Все функции от одной переменной линейны. Также линейными являются функции эквивалентность и исключающее или.