 |
Замыкание и замкнутые классы
|
|
|
|
Определение 1. Пусть M Í Р 2. Замыканием М называется множество всех функций из P 2, которые можно выразить формулами над М. Замыкание М обозначается [ M ].
Определение 2. Множество функций М называется замкнутым классом, если [ M ]= M.
Пример 1.
1) P 2 – замкнутый класс.
2) Множество {1,x1Åx2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 Å x2}] = {f(x1,..., xn) = c0 Å c1x1 Å... Å cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 Å х2, будет формулой над М: f(G1, x3) = (x1 Å x2) Å x3.
З амечание. В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному:
М – полная система, если [ M ] = P 2.
3) A = { f (x 1,..., xn)| f (1, 1,..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g 1,..., gn Î A, т.е. f (1, 1,..., 1) = 0, g 1(1, 1,..., 1) = 0, тогда f (g 1,..., gn) Î [ A ]. Посмотрим, принадлежит ли функция f (g 1,..., gn) множеству А. f (g 1(1,..., 1), g 2(1,..., 1),..., gn (1,..., 1) = f (0,..., 0)), но f (0,..., 0) не обязано быть равным 0. Действительно, пусть g 1(x 1, x 2) = x 1 Å x 2, g 2(x) = x Î A. Возьмем g 2(g 1(x 1, x 2)) = x 1 Å x 2 Î [ A ], g 2(g 1(1, 1)) = 1 Å 1 = 0, следовательно, g 2(g 1(x 1, x 2)) Ï A, отсюда [ A ] ¹ A и А – незамкнутый класс.
Важнейшие замкнутые классы в Р2
1) Т0 - класс функций, сохраняющих константу 0.
Т 0 = { f (x 1,..., xn | f (0,..., 0) = 0, n = 1, 2,...}. Покажем, что Т 0 является собственным подмножеством Р 2, т.е. Т 0 ¹ Æ и Т 0 Ì Р (не совпадает с Р 2). Для этого достаточно привести примеры функций, входящих в Т 0, и примеры функций из Р2, не входящих в Т 0: x 1& x 2, x 1Ú x 2, x Î Т 0 и x 1| x 2, x 1 
x 2, 
Ï Т 0. Покажем далее, что [ Т 0] = Т 0. Вложение Т 0 Í [ Т 0] очевидно, так как по определению формулы любая функция из Т 0 является формулой над Т 0 и, следовательно, принадлежит [ Т 0]. Покажем, что [ Т 0]Í Т 0. Для этого надо показать, что Ф = f (f 1,..., fm) Î [ Т 0], если все функции f, f 1, f 2, f 3,..., f m Î Т 0. Надо заметить, что в формуле в качестве функции f 1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т 0, поэтому достаточно показать, что Ф = f (f 1,..., fm) Î Т 0. Для этого рассмотрим следующую функцию: Ф (0,..., 0) = f (f 1(0,..., 0), f 2(0,..., 0),...) = f (0,..., 0) = 0.
|
|
|
Число функций, зависящих от n переменных и принадлежащих Т 0, будет равно 
2) T 1 – класс функций, сохраняющих константу 1.
T 1 = { f (x 1,...) | f (1, 1,...) = 1}; x 1& x 2, x 1Ú x 2, x Î T 1, х 1Å х 2, x 1 x 2Ï T 1, следовательно Т 1 – собственное подмножество Р 2. 
Покажем, что [ T 1] Í T 1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т 1, можно рассмотреть Ф = f (f 1,..., fn) Î [ T 1], где f, f 1,..., fn Î T 1. Найдем Ф (1,..., 1) = f (f 1(1,..., 1),..., fn (1,..., 1)) = f (1,..., 1) = 1, следовательно, Ф = f (f 1,..., fn) Î T 1, отсюда следует [ T 1] = T 1.
3) S – класс самодвойственных функций .
S = { f (x 1,...)| f * = f }; x, 
, x 1Å x 2Å x 3Î S, x 1& x 2, x 1Ú x 2, x 1Å x 2Ï S, следовательно, S – собственное подмножество Р 2. | S (n)| = 
. Покажем, что [ S ]Í S. Ф = f (f 1,..., fn) Î [ S ], если f, f 1,..., fn Î S, а также, что Ф Î S. По принципу двойственности, Ф * = f *(f 1*,..., fn *) = f (f 1,..., fn) = Ф, отсюда S – замкнутый класс.
4) L – класс линейных функций .
L = { f (x 1,...)| f = c 0Å c 1 x 1Å...Å cnxn }; очевидно, L ¹ Æ, с другой стороны
L ¹ P 2, так как x 1& x 2 Ï L. Заметим, что тождественная функция принадлежит L и | L (n)| = 2 n +1. Покажем, что [ L ] Í L. Рассмотрим Ф = f (f 1,..., fm), где f, f 1,..., fn Î L. Тогда Ф = а 0 Å а 1(с 10 Å с 11 х 1 Å...Å c 1 nxn 1) Å a 2(c 20 Å c 21 x 1 Å c 22 x 2Å...Å c 2 nxn 2)Å...Å an (cm 0 Å cm 1x1 Å... Å cmnxnm) = в 0 Å в 1 х 1 Å...Å вnхn Þ Ф Î L.
5) М – класс монотонных функций.
Определение. Набор 
= (a 1,..., an) предшествует набору 
= (b 1,..., bn) и обозначается 
, если для 1£ i £ n ai £ bi, например: = (0010), 
= (0110), тогда 
. Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.
|
|
|
Определение. Функция f (x 1,..., xn) называется монотонной, если для двух наборов 
и 
, таких что 
, выполняется f (
) f (
). Функции 0, 1, x, x 1& x 2, x 1 Ú x 2 Î M, x 1¯ x 2, x 1 Å x 2, x 1 ~ x 2 Ï M.
Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М замкнутый класс. Рассмотрим функцию Ф Î[ M ], Ф = f (f 1,..., fm), где f, f 1,..., fm Î M, причем можем считать, что все они зависят от n переменных. Пусть набор 
= (a 1,..., an), 
= (b 1,..., bn). Рассмотрим Ф (a 1,..., an) = f (f 1(a 1,..., an), …, fm (a 1,..., an)) и Ф (b 1,..., bn) = f (f 1(b 1,..., bn),..., fm (b 1,..., bn)). Здесь f 1(a) f 1(b),..., fm (a) fm (b), тогда набор (f 1(a),..., fm (a)) (f 1(b),..., fm (b)), но тогда Ф (a) Ф (b), так как f Î M, отсюда Ф = f (f 1,...,) – монотонная функция.
Теорема Поста о полноте
Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T 0, T 1, L, S, M.
Доказательство. Докажем необходимость этого условия. Пусть система
N = { f 1, f 2,... fs,...} полна в Р 2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T 0, T 1, L, S, M. Докажем от противного, пусть N Í Q, очевидно, [ N ] Í [ Q ] = Q, но [ N ] = P 2, т.к. N – полна в Р 2, отсюда Р 2= Q, но это не так. Необходимость доказана.
Докажем достаточность. Пусть F = { f 0, f 1, fL, fm, fs }, где f 0Ï T 0, f 1Ï T 1, fL Ï L, fs Ï S и fm Ï M. Покажем, что суперпозицией функций системы F можно получить полную систему G = { x 1& x 2, 
}.
1. Пусть g (x) = f 0(x, …, x). Тогда g (0) = f (0, …, 0) = 1. Далее возможны два случая:
g (1) = 1. Тогда g (x) º 1. Функция h (x) = f 1(g (x), …, g (x)) = f 1(1, …, 1) = 0, т.е. h (x) º 0. Получили константы 0 и 1;
g(1) = 0. Тогда g (x) = 
. По лемме о несамодвойственной функции суперпозицией над { fs, 
} можно получить одну из констант, например, 0. Тогда f 0(0, …, 0) = 1 есть другая константа.
В обоих случаях получили обе константы.
2. По лемме о немонотонной функции суперпозицией над { fm, 0, 1} можно получить отрицание.
|
|
|
3. По лемме о нелинейной функции суперпозицией над { fL, 1, 
} можно получить конъюнкцию. Теорема доказана.
Следствие. Всякий замкнутый класс функций из Р 2, не совпадающий с Р 2 содержится, по крайней мере, в одном из замкнутых классов T 0, T 1, L, S, M. Действительно, если N не является подмножеством Q, то [ N ] = P 2, что неверно.
Определение. Система функций { f 1,..., fs,...} называется базисом в Р 2,если она полна в Р 2, но любая ее подсистема не будет полной. Например, система функций { x 1& x 2, 0, 1, x 1 
x 2 x 3} – базис.
|
|
|
