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

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

, , , . (***)

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

, , .

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

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

.

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

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