- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
Конъюнкция x^y = xy в булевой алгебре {0,1} совпадают с арифметической операцией умножения над числами 0 и 1.
x |
y |
x ~ y |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
Заметим, что
.
Проверяется по таблице истинности
Для введенного сложения и умножения (конъюнкции) имеют место все основные арифметические закономерности: коммутативность, ассоциативность, дистрибутивность умножения относительного сложения.
Поэтому будем использовать, не оговаривая этого специально, все обычные упрощения в записи арифметических выражений.
Пример: представить х + у в виде СДНФ и СКНФ,
найти (х + у)*.
1). Найдем СКНФ:
2). Преобразуем в СДНФ:
Замечание. Всякая функция алгебры логики может быть представлена арифметическим полиномом (по модулю 2). Для этого достаточно выразить при помощи арифметических операций конъюнкцию и отрицание. Но x^y = xy сама является арифметической операцией, а .
Выберем канонический вид полинома. В силу свойства
хх = х при n≥1, кроме того, х + х = 0. (*)
Определение 1. Полиномом Жегалкина называется полином, являющийся суммой константы и многочленов, в которые все переменные входят не выше, чем в первой степени , причем в каждом наборе (i1, ..., ik) все ij различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов.
Возможность преобразования произвольного арифметического полинома в полином Жегалкина следует из замечания.
Пример. Представить полиномом Жегалкина xvy.
Можно доказать, что представление булевых функций полиномами Жегалкина единственно.
Определение 2. Функции вида , где а – константа, называются линейными.
Их можно записывать в виде , где ai, а0 равны 0 или 1.
Примеры. (К доказательству теоремы Поста)
D. Доказать, что функция, представленная полиномом Жегалкина, существенно зависит от всех входящих в него переменных.
.
Решение.
Пусть xi – такая переменная. Сгруппируем члены, в которые входит xi. Получим:
.
Данное разложение можно представить как полином Жегалкина по переменной xi с коэффициентами, зависящими от остальных переменных.
Здесь функция не равна тождественно нулю, так как в противном случае (в силу единственности полинома Жегалкина) xi не входил бы в полином для f. Возьмем значения переменных x2, ..., xn, на которых φ = 1.
Тогда значение f будет зависеть от значения х1.
E. Дана произвольная нелинейная функция. Нелинейную функцию от какого минимального числа переменных можно получить, отождествляя переменные данной функции?
Решение. Пусть f(x1, ..., xn) – нелинейная функция, и пусть для определенности переменная xi входит в какой-либо многочлен выше первой степени ее полинома Жегалкина.
Рассмотрим (как и в D.) разложение:
.
Функция φ не равна тождественно ни нулю, ни единице. В противном случае переменная xi не входила бы в члены выше первой степени. Обозначим через а значение φ на нулевом наборе: .В силу сказанного, найдется набор , на котором принимает другое значение: .
Разобьем переменные x2, ...,xn на две группы. В первую включим те переменные, для которых , во вторую – те переменные, для которых .
Отождествим переменные в каждой из двух групп. Получим функцию такую, что , . Аналогичное отождествление произведем у функции f. Тогда .
Функция будет нелинейной, так как не является тождественной константой. Поэтому х1 будет входить в некоторый член полинома Жегалкина для в степени выше первой.
Полином Жегалкина для можно получить подстановкой полиномов для и .
Такитм образом, получена нелинейная функция от трех переменных.
Замечание 1. При рассмотрении функции φ мы могли начинать не с нулевого, а с единичного набора; существенно только то, что в нем все элементы равны.
Замечание 2. Мы фактически доказали, что необходимое и достаточное условие нелинейности функции f(x1, ..., xn) – это наличие такой переменной (допустим х1), что , где функция φ не является тождественной константой.
Теперь покажем, что, вообще говоря, нельзя отождествлением переменных получить нелинейную функцию от двух переменных.
Рассмотрим нелинейную функцию от трех переменных:
xy v yz v xz = xy + yz + xz.
Она симметрична относительно всех трех переменных. Отождествим, например, переменные х и у. Получаем
x v xz v xz = x, т.е. линейную функцию.
К аналогичному результату приводит отождествление любых двух переменных. Тем более не приводит к цели отождествление всех трех переменных.
F. Нелинейную функцию от какого минимального числа переменных можно получить, строя суперпозиции нелинейных функций и одной из констант?
Решение.
В тех+ же обозначениях, что и при решении предыдущей задачи, пусть у нас еще имеется константа 0 (если у нас имеется 1, то нужно в E начинать с единичного набора; см. Замечание 1).
Пусть, таким .образом,
и
.
Подставим вместо у1 нуль:
.
Пусть , тогда , , т.е. не является константой.
Значит, - нелинейная функция от двух переменных (замечание 2 в E).
Дальнейшее уменьшение числа переменных невозможно, так как нелинейных функций от меньшего числа переменных не бывает.
G. Имеется какая-то одна нелинейная функция от двух переменных и отрицание. Доказать, что суперпозициями из них можно получить все нелинейные функции от двух переменных.
Решение.
Общий вид нелинейной функции от двух переменных:
.
Получим сначала конъюнкцию ху. Избавимся от членов первой степени.
Допустим, что = 1. подставим тогда вместо у:
.
Так как = 1, то + 1 = 0 и член с х уничтожается. Существенно, что при этом коэффициент при у не изменился.
Если = 1, то аналогично уничтожается и член у.
После этих подстановок свободный член изменился. Если он окажется равным 1, то нужно поставить отрицание над всей функцией.
В результате останется лишь член ху.
В общем случае переход от одной нелинейной функции от двух переменных к другой осуществляется аналогичным образом.
H. К какому наименьшему числу переменных можно привести немонотонную функцию с сохранением немонотонности, отождествляя ее переменные?
Решение.
Пусть f(x1, ..., xn) – немонотонная функция и наборы таковы, что
> , т.е. = 1; = 0.
Разобьем переменные х1, x2, ..., xn на три группы:
1. Такие переменные xi, что = 0, = 1.
2. Такие xi, что = = 0.
3. Такие xi, что = = 1.
Так как < , то не может быть, чтобы = 1, = 0.
Отождествим переменные внутри каждой из этих групп. Подставим вместо них переменные у1, у2, у3 соответственно.
Получим немонотонную функцию от трех переменных
φ(у1, у2, у3): φ(0,0,1) = 1, φ (1,0,1) =0.
Дальнейшее уменьшение числа переменных может быть невозможно, что видно на примере немонотонной функции от трех переменных х + у +z.
Любое отождествление переменных приводит к функции от одной переменной, совпадающей с аргументом (например, х), которая монотонна.
K. Показать, что суперпозицией любой немонотонной функции и констант можно получить отрицание.
Решение.
Подставим у1 = 0, у3 = 1 в аргументы функции φ(у1, у2, у3), введенной в H:
φ(у1, 0,1) = 1, если у1 = 0 и φ(у1, 0,1) = 0, если у1 = 1, т.е.
φ(у1, 0,1) = .