Замыкание и замкнутые классы

 

Определение 1. Пусть MÍ Р₂. Замыканием М называется множество всех функций из P₂, которые можно выразить формулами над М. Замыкание М обозначается [M].

Определение 2. Множество функций М называется замкнутым классом, если [M]=M.

Пример 1.

1) P₂ – замкнутый класс.

2) Множество {1, x₁Å x₂} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x₁ Å x₂}] = {f(x₁, ..., x_n) = c₀ Å c₁x₁ Å ... Å c_nx_n}. Действительно, по определению формулы над М, функция f(G₁, x₃), где f – есть сумма по модулю 2, G₁ – функция х₁ Å х₂, будет формулой над М: f(G₁, x₃) = (x₁ Å x₂) Å x₃.

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

М – полная система, если [M] = P₂.

3) A = {f(x₁, ..., x_n)| f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g₁, ..., g_n Î A, т.е. f(1, 1, ..., 1) = 0, g₁(1, 1, ..., 1) = 0, тогда f(g₁, ..., g_n) Î [A]. Посмотрим, принадлежит ли функция f(g₁, ..., g_n) множеству А. f(g₁(1, ..., 1), g₂(1, ..., 1), ..., g_n(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0. Действительно, пусть g₁(x₁, x₂) = x₁ Å x₂, g₂(x) = x Î A. Возьмем g₂(g₁(x₁, x₂)) = x₁ Å x₂ Î [A], g₂(g₁(1, 1)) = 1 Å 1 = 0, следовательно, g₂(g₁(x₁, x₂)) Ï A, отсюда [A] ¹ A и А – незамкнутый класс.

 

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

 

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) М – класс монотонных функций.

Определение. Набор = (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 пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.

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

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

Задачи

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

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

Теорема Поста о полноте

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T₀, T₁, L, S, M.

Доказательство. Докажем необходимость этого условия. Пусть система

N = {f₁, f₂, ...f_s, ...} полна в Р₂, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T₀, T₁, L, S, M. Докажем от противного, пусть N Í Q, очевидно, [N] Í [Q] = Q, но [N] = P₂, т.к. N – полна в Р₂, отсюда Р₂=Q, но это не так. Необходимость доказана.

Докажем достаточность. Пусть F = {f₀, f₁, f_L, f_m, f_s}, где f₀Ï T₀, f₁Ï T₁, f_LÏ L, f_sÏ S и f_mÏ M. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x₁& x₂, }.

1. Пусть g(x) = f₀(x, …, x). Тогда g(0) = f( 0, …, 0) = 1. Далее возможны два случая:

g(1) = 1. Тогда g(x) º 1. Функция h(x) = f₁(g(x), …, g(x)) = f₁(1, …, 1) = 0, т.е. h(x) º 0. Получили константы 0 и 1;

g(1) = 0. Тогда g(x) = . По лемме о несамодвойственной функции суперпозицией над {f_s, } можно получить одну из констант, например, 0. Тогда f₀(0, …, 0) = 1 есть другая константа.

В обоих случаях получили обе константы.

2. По лемме о немонотонной функции суперпозицией над {f_m, 0, 1} можно получить отрицание.

3. По лемме о нелинейной функции суперпозицией над {f_L, 1, } можно получить конъюнкцию. Теорема доказана.

Следствие. Всякий замкнутый класс функций из Р₂, не совпадающий с Р₂ содержится, по крайней мере, в одном из замкнутых классов T₀, T₁, L, S, M. Действительно, если N не является подмножеством Q, то [N] = P₂, что неверно.

Примеры использования теоремы Поста.

1. Покажем, что система функций {f₁ =x₁x₂, f₂ =0, f₃ =1, f₄ = x₁Å x₂Å x₃} полна в Р₂. Составим таблицу, которая называется критериальной:

	Т0	Т1	L	M	S
x1x2	+	+	-	+	-
	+	-	+	+	-
	-	+	+	+	-
x1Å x2Å x3	+	+	+	-	+

 

 

x1 x2 x3	x1Å x2Å x3
0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

 

Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы, которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус».

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f₂, f₃, f₄}Ì L, {f₁, f₃, f₄}Ì T₁, {f₁, f₂, f₄}Ì T₀, {f₁, f₂, f₃}Ì M.

2. Мы знаем, что система {x₁|x₂} – полна в Р₂. Какова для нее критериальная таблица? x₁|x₂= = x₁x₂Å 1.

	Т0	Т1	L	M	S
x1|x2	-	-	-	-	-

3. Составим критериальную таблицу для другой полной системы функций из Р₂: {0, 1, x₁x₂, x₁Å x₂}.

	Т0	Т1	L	M	S
	+	-	+	+	-
	-	+	+	+	-
x1x2	+	+	-	+	-
x1Å x2	+	-	+	-	-

Согласно критериальной таблице, полной является и система {1, x₁x₂, x₁Å x₂}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где а равны 0, если члены х х ...х , в полиноме отсутствуют.

4. Выясним, полна ли система . Составим критериальную таблицу, очевидно . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям. Если f S\T₀, то f(0, ..., 0) = 1, f(1, ..., 1)=0, следовательно, f M, f T₁. Рассмотрим функцию h = x₁x₂ x₂x₃ x₁x₃=1, набор ее значений (11101000), h S\T₀, но h L. Следовательно, критериальная таблица имеет вид:

	Т0	Т1	L	M	S
L T1	-	+	+	-	-
S\T0	-	-	-	+	-

и А – полная система функций.

Определение. Система функций {f₁, ..., f_s, ...} называется базисом в Р₂, если она полна в Р₂, но любая ее подсистема не будет полной. Например, система функций {x₁& x₂, 0, 1, x₁ x₂ x₃} – базис.

⇐ Предыдущая3456789101112Следующая ⇒

Поделиться:

Популярное:

1. Aбстрактные классы, используемые при работе с коллекциями
2. Аттестация судей. Квалификационные классы судей.
3. Базовые классы для работы с потоками
4. График оператора. Замкнутые операторы
5. Задач по математике. Все типы задач курса начальной школы. Учимся считать деньги. 1-4 классы
6. Квалиф. аттестация судей. Их Квалиф. классы.
7. Квалификационная аттестация судей. Квалификационные классы судей. Органы квалификационной аттестации и порядок их деятельности
8. Квалификационные классы судей и порядок их присвоения.
9. Классы Calendar и GregorianCalendar
10. Классы Reader и Writer и их наследники
11. Классы TextComponent, TextField, TextArea