Тема 3.6 Важнейшие замкнутые классы.

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

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

Пример:

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 ^{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. Доказать, что объединение двух замкнутых классов не всегда замкнуто

Тема 3.7 Теорема Поста.

 

Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов 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
x 1 x 2	+	+	-	+	-
	+	-	+	+	-
	-	+	+	+	-
x 1Å x 2Å x 3	+	+	+	-	+

 

 

x 1 x 2 x 3	x 1Å x 2Å x 3
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
x 1| x 2	-	-	-	-	-

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

	Т 0	Т 1	L	M	S
	+	-	+	+	-
	-	+	+	+	-
x 1 x 2	+	+	-	+	-
x 1Å x 2	+	-	+	-	-

Согласно критериальной таблице, полной является и система {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 T 1	-	+	+	-	-
S \ T 0	-	-	-	+	-

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

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

 

Контрольная работа

Вариант I

1. Составить таблицу истинности для булевой функции:

2. Составить СДНФ и СКНФ для:

3. Найти минимальную (сокращённую) ДНФ для в.ф. ы

4. Определить является ли следующая система функций полной {0,1,x, }

5. Дана формула . Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)

 

Вариант II

1. Составить таблицу истинности для булевой функции:

2. Составить СДНФ и СКНФ для:

3. Найти минимальную (сокращённую) ДНФ для в.ф. ы

4. Определить является ли следующая система функций полной

5. Дана формула . Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)