Важнейшие замкнутые классы в р2

1) Т₀ - класс функций, сохраняющих константу 0.

Т₀ = { f(x₁, ...,x_nf(0, ..., 0) = 0,n= 1, 2, ...}. Покажем, чтоТ₀является собственным подмножествомР₂, т.е.Т₀ иТ₀ Р(не совпадает сР₂). Для этого достаточно привести примеры функций, входящих вТ₀, и примеры функций из Р₂, не входящих вТ₀:x₁&x₂,x₁x₂,xТ₀ и x₁|x₂,x₁x₂, Т₀. Покажем далее, что [Т₀] =Т₀. ВложениеТ₀ [ Т₀] очевидно, так как по определению формулы любая функция изТ₀является формулой надТ₀и, следовательно, принадлежит [Т₀]. Покажем, что [Т₀] Т₀. Для этого надо показать, чтоФ=f(f₁, ...,f_m)[ Т₀], если все функцииf,f₁,f₂,f₃, ...,f_m  Т₀. Надо заметить, что в формуле в качестве функцииf₁могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классуТ₀, поэтому достаточно показать, чтоФ=f(f ₁, ...,f_m) Т₀. Для этого рассмотрим следующую функцию:Ф(0, ..., 0) =f(f ₁(0, ..., 0),f ₂(0, ..., 0), ...) =f(0, ..., 0) = 0.

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

2) T₁ – класс функций, сохраняющих константу 1.

T₁ = {f(x₁, ...) f(1, 1, ...) = 1};x₁&x₂,x₁x₂,xT₁,х₁х₂,x₁x₂T₁, следовательноТ₁ – собственное подмножествоР₂.

Покажем, что [T₁]T₁, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит вТ₁, можно рассмотретьФ=f(f₁, ...,f_n)[T₁], гдеf,f₁, ...,f_n T₁. НайдемФ(1, ..., 1) =f(f₁(1, ..., 1), ...,f_n(1, ..., 1)) =f(1, ..., 1) = 1, следовательно,Ф=f(f₁, ...,f_n)T₁, отсюда следует [T₁] =T₁.

3) S – класс самодвойственных функций.

S= {f(x₁, ...)f* =f };x,,x₁x₂x₃S,x₁&x₂,x₁x₂,x₁x₂S, следовательно,S– собственное подмножествоР₂. |S(n)| =. Покажем, что [S]S.Ф=f(f₁, ...,f_n)[S], еслиf,f₁, ...,f_n S, а также, чтоФS. По принципу двойственности,Ф* =f*(f₁*, ...,f_n*) =f(f₁, ...,f_n) =Ф, отсюдаS– замкнутый класс.

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

L = {f(x₁, ...) f=c₀c₁x₁...c_nx_n}; очевидно,L, с другой стороны

LP₂, так какx₁&x₂ L. Заметим, что тождественная функция принадлежитLи |L(n)| = 2ⁿ⁺¹. Покажем, что [L]L. РассмотримФ=f(f₁, ...,f_m), гдеf,f₁, ...,f_n L. ТогдаФ=а₀ а₁(с₁₀ с₁₁х₁ ...c_1nx_n1)a₂(c₂₀ c₂₁x₁ c₂₂x₂...c_2nx_n2)...a_n(c_m0 c_m1x₁ ...c_mnx_nm) =в₀ в₁х₁ ...в_nх_nФL.

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

Определение.Набор =(₁, ...,_n) предшествует набору= (₁, ...,_n) и обозначается, если для 1in_i_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переменных. Пусть набор =₁, ...,_n),= (₁, ...,_n). РассмотримФ₁, ...,_n) =f(f₁₁, ...,_n), …,f_m₁, ...,_n)) иФ(₁, ...,_n) =f(f₁(₁, ...,_n), ...,f_m(₁, ...,_n)). Здесьf₁() f₁(), ...,f_m() f_m(), тогда набор (f₁(), ...,f_m())(f₁(), ...,f_m()), но тогдаФ() Ф(), так какfM, отсюдаФ=f(f₁, ..., ) – монотонная функция.

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

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

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

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

	T0	T1	L	S	M
x	+	+	+	+	+
	-	-	+	+	-
0	+	-	+	-	+
1	-	+	+	-	+
x1x2	+	+	-	-	+

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

Задачи

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

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