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

Обычное арифметическое сложение выводит за пределы множества {0,1}, но можно рассмотреть сложение по модулю 2 (соответствует симметричной разности в теории множеств: или ). В результате возникает функция алгебры логики, которую будем обозначать через х + у.

Заметим, что

.

Проверяется по таблице истинности

Для введенного сложения и умножения (конъюнкции) имеют место все основные арифметические закономерности: коммутативность, ассоциативность, дистрибутивность умножения относительного сложения.

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

Пример: представить х + у в виде СДНФ и СКНФ,

найти (х + у)*.

1). Найдем СКНФ:

2). Преобразуем в СДНФ:

Замечание. Всякая функция алгебры логики может быть представлена арифметическим полиномом (по модулю 2). Для этого достаточно выразить при помощи арифметических операций конъюнкцию и отрицание. Но x^y = xy сама является арифметической операцией, а .

Выберем канонический вид полинома. В силу свойства

хх = х при n≥1, кроме того, х + х = 0. (*)

Определение 1. Полиномом Жегалкина называется полином, являющийся суммой константы и многочленов, в которые все переменные входят не выше, чем в первой степени , причем в каждом наборе (i₁, ..., i_k) все i_j различны, а суммирование ведется по некоторому множеству таких несовпадающих наборов.

Возможность преобразования произвольного арифметического полинома в полином Жегалкина следует из замечания.

Пример. Представить полиномом Жегалкина xvy.

Можно доказать, что представление булевых функций полиномами Жегалкина единственно.

Определение 2. Функции вида , где а – константа, называются линейными.

Их можно записывать в виде , где a_i, а₀ равны 0 или 1.

Примеры. (К доказательству теоремы Поста)

D. Доказать, что функция, представленная полиномом Жегалкина, существенно зависит от всех входящих в него переменных.

.

Решение.

Пусть x_i – такая переменная. Сгруппируем члены, в которые входит x_i. Получим:

.

Данное разложение можно представить как полином Жегалкина по переменной x_i с коэффициентами, зависящими от остальных переменных.

Здесь функция не равна тождественно нулю, так как в противном случае (в силу единственности полинома Жегалкина) x_i не входил бы в полином для f. Возьмем значения переменных x₂, ..., x_n, на которых φ = 1.

Тогда значение f будет зависеть от значения х₁.

E. Дана произвольная нелинейная функция. Нелинейную функцию от какого минимального числа переменных можно получить, отождествляя переменные данной функции?

Решение. Пусть f(x₁, ..., x_n) – нелинейная функция, и пусть для определенности переменная x_i входит в какой-либо многочлен выше первой степени ее полинома Жегалкина.

Рассмотрим (как и в D.) разложение:

.

Функция φ не равна тождественно ни нулю, ни единице. В противном случае переменная x_i не входила бы в члены выше первой степени. Обозначим через а значение φ на нулевом наборе: .В силу сказанного, найдется набор , на котором принимает другое значение: .

Разобьем переменные x₂, ...,x_n на две группы. В первую включим те переменные, для которых , во вторую – те переменные, для которых .

Отождествим переменные в каждой из двух групп. Получим функцию такую, что , . Аналогичное отождествление произведем у функции f. Тогда .

Функция будет нелинейной, так как не является тождественной константой. Поэтому х₁ будет входить в некоторый член полинома Жегалкина для в степени выше первой.

Полином Жегалкина для можно получить подстановкой полиномов для и .

Такитм образом, получена нелинейная функция от трех переменных.

Замечание 1. При рассмотрении функции φ мы могли начинать не с нулевого, а с единичного набора; существенно только то, что в нем все элементы равны.

Замечание 2. Мы фактически доказали, что необходимое и достаточное условие нелинейности функции f(x₁, ..., x_n) – это наличие такой переменной (допустим х₁), что , где функция φ не является тождественной константой.

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

Рассмотрим нелинейную функцию от трех переменных:

xy v yz v xz = xy + yz + xz.

Она симметрична относительно всех трех переменных. Отождествим, например, переменные х и у. Получаем

x v xz v xz = x, т.е. линейную функцию.

К аналогичному результату приводит отождествление любых двух переменных. Тем более не приводит к цели отождествление всех трех переменных.

F. Нелинейную функцию от какого минимального числа переменных можно получить, строя суперпозиции нелинейных функций и одной из констант?

Решение.

В тех+ же обозначениях, что и при решении предыдущей задачи, пусть у нас еще имеется константа 0 (если у нас имеется 1, то нужно в E начинать с единичного набора; см. Замечание 1).

Пусть, таким .образом,

и

.

Подставим вместо у₁ нуль:

.

Пусть , тогда , , т.е. не является константой.

Значит, - нелинейная функция от двух переменных (замечание 2 в E).

Дальнейшее уменьшение числа переменных невозможно, так как нелинейных функций от меньшего числа переменных не бывает.

G. Имеется какая-то одна нелинейная функция от двух переменных и отрицание. Доказать, что суперпозициями из них можно получить все нелинейные функции от двух переменных.

Решение.

Общий вид нелинейной функции от двух переменных:

.

Получим сначала конъюнкцию ху. Избавимся от членов первой степени.

Допустим, что = 1. подставим тогда вместо у:

.

Так как = 1, то + 1 = 0 и член с х уничтожается. Существенно, что при этом коэффициент при у не изменился.

Если = 1, то аналогично уничтожается и член у.

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

В результате останется лишь член ху.

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

H. К какому наименьшему числу переменных можно привести немонотонную функцию с сохранением немонотонности, отождествляя ее переменные?

Решение.

Пусть f(x₁, ..., x_n­) – немонотонная функция и наборы таковы, что

> , т.е. = 1; = 0.

Разобьем переменные х₁, x₂, ..., x_n на три группы:

1. Такие переменные x_i, что = 0, = 1.

2. Такие x_i, что = = 0.

3. Такие x_i, что = = 1.

Так как < , то не может быть, чтобы = 1, = 0.

Отождествим переменные внутри каждой из этих групп. Подставим вместо них переменные у₁, у₂, у₃ соответственно.

Получим немонотонную функцию от трех переменных

φ(у₁, у₂, у₃): φ(0,0,1) = 1, φ (1,0,1) =0.

Дальнейшее уменьшение числа переменных может быть невозможно, что видно на примере немонотонной функции от трех переменных х + у +z.

Любое отождествление переменных приводит к функции от одной переменной, совпадающей с аргументом (например, х), которая монотонна.

K. Показать, что суперпозицией любой немонотонной функции и констант можно получить отрицание.

Решение.

Подставим у₁ = 0, у₃ = 1 в аргументы функции φ(у₁, у₂, у₃), введенной в H:

φ(у₁, 0,1) = 1, если у₁ = 0 и φ(у₁, 0,1) = 0, если у₁ = 1, т.е.

φ(у₁, 0,1) = .