Линейные функции. Монотонные функции.

 

Рассмотрим систему функций:

, , , . (***)

Суперпозицию функций системы (***) можно преобразовать, пользуясь правилами элементарной алгебры и специальными правилами:

, , .

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

Теорема 1: Для любой функции алгебры логики существует многочлен Жегалкина, задающий эту функцию.

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

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

Определение 1: Функция называется линейной, если имеет место соотношение: .

Теорема 2: Функция, представленная многочленом Жегалкина, существенно зависит от всех входящих в него переменных.

Доказательство: Пусть, например, – переменная, о которой идёт речь в условии теоремы. Сгруппируем члены, и вынесем за скобки. Получим:

,

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

Теорема 3: Суперпозицией из произвольной нелинейной функции и одной из констант можно получить нелинейную функцию от 2-х переменных.

Доказательство: Докажем сначала, что отождествляя переменные из произвольной нелинейной функции можно получить нелинейную функцию от трех переменных. Пусть – нелинейная функция, и пусть для определенности переменная входит в какой-либо одночлен выше первой степени ее многочлена Жегалкина. Рассмотрим разложение, как и в теореме 2:

.

Функция не равна тождественно ни нулю, ни единице (см. доказательство теоремы 2). Обозначим через значение на нулевом наборе: . Тогда найдется набор , на котором принимает другое значение: . Разобьем переменные на две группы. В первую включим те переменные, для которых , во вторую – те переменные, для которых . Отождествим переменные в каждой из этих групп. Получим функцию , такую что . Аналогичное отождествление произведем для переменной функции . Далее, . Функция будет нелинейной, т. к. не является тождественной константой, а потому будет входить в некоторый член многочлена Жегалкина для выше первой степени. Итак, мы получим нелинейную функцию от трех переменных.

Замечание: Фактически мы доказали, что необходимое и достаточное условие нелинейности функции – это наличие такой переменной (допустим ), что , где функция не является тождественной константой.

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

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

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

Теорема 4: Суперпозицией из нелинейной функции от двух переменных и отрицания можно получить конъюнкцию.

Нелинейная функция от двух переменных имеет вид: .

Избавимся от членов первой степени следующим образом. Допустим, что . Тогда подставим вместо переменной :

.

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

Замечание: Множество всех линейных функций составляет замкнутый класс.

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

, , .

Далее будет рассмотрен класс функций, обладающих несколько иными свойствами.

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

Определение 2: Пусть — двоичные наборы. Будем говорить, что предшествует (обозначение: ), если для всех , причем, по крайней мере, для одного , имеет место строгое неравенство. Будем писать: , если или наборы и совпадают.

Это упорядочение является только частичным, так как не всякие наборы можно сравнивать.

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

Например, нетрудно заметить, что константы, конъюнкция, дизъюнкция являются монотонными функциями.

Теорема 5: Множество всех монотонных функций образует замкнутый класс.

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

.

Рассмотрим два произвольных набора таких, что . В этом случае , где . Следовательно,

и, значит, в силу монотонности функции имеет место неравенство: . Теорема доказана.

Теорема 6: Суперпозициями любой немонотонной функции и констант можно получить отрицание.

Доказательство: Покажем сначала, что, отождествляя переменные, можно из любой немонотонной функции получить немонотонную функцию, содержащую не более трех переменных. Действительно, пусть — немонотонная функция и наборы таковы, что выполнено условие: , т.е. . Разобьем переменные на три группы. В первую группу включим такие переменные , что . Во вторую включим такие переменные , что , в третью — такие , что . Так как, по условию , то не может быть, чтобы . Отождествим переменные внутри каждой из этих групп (подставим вместо них переменные соответственно).

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

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

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