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

Набор  = (₁,...,_n) предшествует набору  = (₁,...,_n), если _i  _i (i=1,2,...,n). Этот факт обозначаем как  ≼ . Наборы, которые находятся в отношении ≼, называются сравнимыми.

Функция f (x₁,...,x_n) называется монотонной, если для любой пары наборов  = (₁,...,_n) и  = (₁,...,_n) таких, что  ≼ , f ()  f().

Например, функции x₁x₂, x₁ ٧x₂, x – монотонные, аx  немонотонная.

Лемма 5. Из монотонных функций с помощью суперпозиции можно получить только монотонные функции.

Доказательство. Пусть функции f (y₁,...,y_m), f₁ (x₁,...,x_n),...,f_m (x₁,...,x_n) монотонные. Надо показать, что

Φ(x₁,...,x_n) = f (f₁ (x₁,...,x_n),...,f_m (x₁,...,x_n))  монотонная функция.

Пусть  ≼ , тогда f_i ()  f_i () (i=1,...,m). Отсюда

Φ() = f (f₁ (),...,f_m ())  f (f₁ (),...,f_m ()) = Φ().

Следствие. Полная система функций должна содержать хотя бы одну немонотонную функцию.

Лемма 6. Из немонотонной функции путём подстановки констант 0, 1 и функции x можно получитьx.

Доказательство. Пусть дана немонотонная функция f (x₁,...,x_n), т.е. для неё существуют наборы  = (₁,...,_n) и  = (₁,...,_n) такие, что

 ≼, а f () > f (). Рассмотрим функцию (x), которая получается из функции f (x₁,...,x_n) подстановкой констант 0, 1 и функции x. Подстановку определим следующим образом: вместо x_i будем подставлять _i, если _{i =} _i, и x, если _i_i. Рассмотрим функцию (x).

 (0) = f (₁,..., _n) > f (₁,..., _n) = (1).

Следовательно,(x) =x.

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

Функция f (x₁,...,x_n) называется линейной, если полином этой функции имеет вид

f (x₁,...,x_n) = a₀a₁x₁ ...a_nx_n ,гдеa_i {0,1} (i=0,1,...,n).

Например: x,x – линейны, x₁x₂  нелинейна.

Лемма 7.Из линейных функций суперпозицией можно получить только линейные функции.

Доказательствоочевидно.

Следствие.Полная система функций должна содержать хотя бы одну нелинейную функцию.

Лемма 8. Из нелинейной функции f (x₁,...,x_n), констант 0, 1 и функций x,x, y суперпозицией можно получить конъюнкцию двух переменных xy.

Доказательство. Так как функция f (x₁,...,x_n) нелинейна, её полином по модулю 2 содержит хотя бы один член с конъюнкцией двух переменных x_i и x_j. Члены полинома, представляющего функцию f (x₁,...,x_n) можно перегруппировать следующим образом:

f (x₁,...,x_n) = x_i x_j f₁ (x₁,...,x_i-1 ,x_i+1,...,x_j-1, x_j+1,..., x_n) 

 x_i f₂ (x₁,...,x_i-1, x_i+1,...,x_j-1, x_j+1,..., x_n) 

 x_j f₃ (x₁,...,x_i-1, x_i+1,...,x_j-1, x_j+1,..., x_n) 

 f₄ (x₁,..., x_i-1 ,x_i+1,..., x_j-1 , x_j+1,..., x_n),

где функция f₁(x₁,..., x_i-1 ,x_i+1,..., x_j-1 , x_j+1,..., x_n) ≢ 0, т.е. существует набор (₁,...,  _i-1,  _i+1 ,..., _j-1, _j+1,..., _n) такой, что

f (₁,...,  _i-1,  _i+1 ,..., _j-1, _j+1,..., _n) = 1.

Подставляя этот набор в f (x₁,...,x_n), получим функцию (x_i, x_j):

 (x_i, x_j) = f (₁,...,_i-1, x_i,_i+1 ,...,_j-1, x_j,_j+1,...,_n) = x_ix_j x_ix_j ,

где

= f₂ (₁,...,_i-1,_i+1,...,_j-1,_j+1,...,_n),

= f₃ (₁,...,_i-1,_i+1,...,_j-1,_j+1,...,_n),

 = f₄ (₁,..., _i-1, _i+1,..., _j-1, _j+1,..., _n).

Рассмотрим функцию F (x, y) =  (x , y ) = xy    .

Она получена суперпозицией  (x_i, x_j), x, y и x (x = x  1).

Если    = 0, то F (x, y) = xy,

аесли   = 1, тоF (x, y) = xy.

Критерий полноты системы булевых функций дает теорема 4 (приведем ее без доказательства).

Теорема 4 (о полноте). Для того чтобы система булевых функций {f₁ (x₁₁,..., x_1p1),..., f_s (x_s1,..., x_sps),…} была полна, необходимо и достаточно, чтобы она содержала функцию, не сохраняющую 0; функцию, не сохраняющую 1; несамодвойственную функцию; немонотонную функцию; нелинейную функцию.

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

(табл. 3.6).

Таблица 3.6 – Свойства функций двух переменных

Обозначение функции	Наименование функции	Свойства функции
		Сохраняющая 0	Сохраняющая 1	Самодвойственность	Монотонность	Линейность
f1 = 0	Нулевая функция	+	-	-	+	+
f2 = x1 x2	Конъюнкция	+	+	-	+	-
f3 = x1  x2	Запрет x1
f4 = x1	Повторение x1
f5 = x2  x1	Запрет x2
f6 = x2	Повторение x2
f7 = x1  x2	Сложение по |2|
f8 = x1 ٧x2	Дизъюнкция
f9 = x1  x2	Стрелка Пирса
f10 = x1  x2	Эквивалентность
f11 =x2	Отрицание x2
f12 = x2  x1	Импликация x2 в x1
f13 =x1	Отрицание x1
f14 = x1  x2	Импликация x1 в x2
f15 = x1 | x2	Штрих Шеффера
f16 = 1	Единичная функция