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

L = { f (x ₁,...)| f = c ₀Å c ₁ x ₁Å...Å c_nx_n }; очевидно, L ¹ Æ, с другой стороны

L ¹ P ₂, так как x ₁& x ₂ Ï L. Заметим, что тождественная функция принадлежит L и | L (n)| = 2 ^{n +1}. Покажем, что [ L ] Í L. Рассмотрим Ф = f (f ₁,..., f_m), где f, f ₁,..., f_n Î L. Тогда Ф = а ₀ Å а ₁(с ₁₀ Å с ₁₁ х ₁ Å...Å c _{1 n}x_{n 1}) Å a ₂(c ₂₀ Å c ₂₁ x ₁ Å c ₂₂ x ₂Å...Å c _{2 n}x_{n 2})Å...Å a_n (c_{m 0} Å c_{m 1}x₁ Å... Å c_mnx_nm) = в ₀ Å в ₁ х ₁ Å...Å в_nх_n Þ Ф Î L.

5) М – класс монотонных функций.

Определение. Набор = (a ₁,..., a_n) предшествует набору = (b ₁,..., b_n) и обозначается , если для 1£ i £ n a_i £ b_i, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

Определение. Функция f (x ₁,..., x_n) называется монотонной, если для двух наборов и , таких что , выполняется f () f (). Функции 0, 1, x, x ₁& x ₂, x ₁ Ú x ₂ Î M, x ₁¯ x ₂, x ₁ Å x ₂, x ₁ ~ x ₂ Ï M.

Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М замкнутый класс. Рассмотрим функцию Ф Î [ M ], Ф = f (f ₁,..., f_m), где f, f ₁,..., f_m Î M, причем можем считать, что все они зависят от n переменных. Пусть набор = (a ₁,..., a_n), = (b ₁,..., b_n). Рассмотрим Ф (a ₁,..., a_n) = f (f ₁(a ₁,..., a_n), …, f_m (a ₁,..., a_n)) и Ф (b ₁,..., b_n) = f (f ₁(b ₁,..., b_n),..., f_m (b ₁,..., b_n)). Здесь f ₁(a) f ₁(b),..., f_m (a) f_m (b), тогда набор (f ₁(a),..., f_m (a)) (f ₁(b),..., f_m (b)), но тогда Ф (a) Ф (b), так как f Î M, отсюда Ф = f (f ₁,...,) – монотонная функция.

Определение. Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.

Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.

Доказательство. Пусть f (x ₁,..., x_n) – немонотонная функция. Тогда существуют наборы и , для которых но Пусть i ₁, …, i_k есть все те номера аргументов, для которых , p =1, …, k. На всех остальных аргументных местах j имеем a_j = b_j. В выражении заменим нули на местах i ₁, …, i_k на x. В результате получим функцию g (x), для которой g (0) = f () = 1 и g (1) = f () = 0. Функция g (x) является отрицанием.

Классы T ₀, T ₁, L, S, M пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.

	T 0	T 1	L	S	M
x	+	+	+	+	+
	-	-	+	+	-
	+	-	+	-	+
	-	+	+	-	+
x 1 x 2	+	+	-	-	+

A ={ x, , 0, 1, x ₁ x ₂) не является полной системой функций так как всегда есть функции Î Р ₂ не входящие в эти классы.

Задачи

1. Доказать, что пересечение любых двух замкнутых классов замкнуто.

2. Доказать, что объединение двух замкнутых классов не всегда замкнуто.