Классы монотонных и линейнных функций.

Класс линейных функций

Определение

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

 

Пример

 

Класс линейных функций

Класс линейных функций замкнут:

Тождественная функция является линейной.

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

…

 

Лемма о нелинейной функции

Пусть TL тогда замыкание класса содержит коньюнкцию.

 

Доказательство

Любая функция может быть задана полиномом Жегалкина. Так как fTL, то существует хотя бы одно слагаемое, которое содержит конъюнкцию по крайне мере двух переменных. Для определенности пусть это будутx1иx2. Тогда все слагаемые можно разделить на 4 группы:

- содержащие x1x2 ;

- содержащие x1;

- содержащие x2;

- не содержащие x1 иx1.

В первой группе вынесем за скобки x1x2 , во второй - x1, в третьей - x2 .

В результате получим:

.

Причём .

Следовательно, существуют такие значения переменных -, что.

Пусть

,b,c,d  (0,1)э

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

 

Класс монотонных функций

Определение

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

тогда и только тогда когда

Пример

, .

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

 

(1,1,1)

 

(1,0,1)

(1,1,0) (0,1,1)

(0,0,1) (0,1,0) (0,0,1)

 

(0,0,0)

 

 

Если в какой-то вершине диаграммы функция принимает значение 1, то всюду выше монотонная функция также должна принимать значение 1.

В нашем случае f(1,1,0)=1,af(1,1,1)=0,cледовательно функция не монотонная.

 

Класс монотонных функций

Покажем, что класс монотонных функций замкнут

1) Тождественная функция

2. Пусть и- новые переменные.

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

2. Пусть . Рассмотрим функцию

Возьмем два набора значений переменных : и , таких что .

Обозначим значения

….

….

В силу монотонности функций ,i= 1,…,nимеем,i= 1,…,n.

=

=, то есть.

 

Лемма о немонотонной функции

Пусть . Тогда замыкание классасодержит отрицание.

 

Доказательство

Так как то существуют такие наборы и , что , а.

Если , то для любого i - или, а.

, следовательно, . Тогда существуеттакой, что для, а . Другими словамиJ – это множество индексов, для которых .

Рассмотрим функцию где, еслии, если.

Тогда , то есть

, а , значит.