Главная | Обратная связь
МегаЛекции

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





 

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

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

Пример 1.

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

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] = P2.

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

 

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

 

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

Т0 = { f(x1, ..., xn | f(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т0 является собственным подмножеством Р2, т.е. Т0 ¹ Æ и Т0 Ì Р (не совпадает с Р2). Для этого достаточно привести примеры функций, входящих в Т0, и примеры функций из Р2, не входящих в Т0: x1&x2, x1Úx2, xÎТ0 и x1|x2, x1 x2, ÏТ0. Покажем далее, что [Т0] = Т0. Вложение Т0 Í [ Т0] очевидно, так как по определению формулы любая функция из Т0 является формулой над Т0 и, следовательно, принадлежит [Т0]. Покажем, что [Т0 Т0. Для этого надо показать, что Ф = f(f1, ..., fm) Î [ Т0], если все функции f, f1, f2, f3, ..., fm Î Т0. Надо заметить, что в формуле в качестве функции f1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т0, поэтому достаточно показать, что Ф = f (f 1, ..., fm) Î Т0. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.



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

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

T1 = {f(x1, ...) |f(1, 1, ...) = 1}; x1&x2, x1Úx2, xÎT1, х1Åх2, x1 x2ÏT1, следовательно Т1 – собственное подмножество Р2.

Покажем, что [T1] Í T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) Î [T1], где f, f1, ..., fn Î T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) Î T1, отсюда следует [T1] = T1.

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

S = {f(x1, ...)|f* = f }; x, , x1Åx2Åx3ÎS, x1&x2, x1Úx2, x1Åx2ÏS, следовательно, S – собственное подмножество Р2. |S(n)| = . Покажем, что [SS. Ф = f(f1, ..., fn) Î [S], если f, f1, ..., fn Î S, а также, что Ф Î S. По принципу двойственности, Ф* = f*(f1*, ..., fn*) = f(f1, ..., fn) = Ф, отсюда S – замкнутый класс.

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

L = {f(x1, ...)| f = c0Åc1x1Å...Åcnxn}; очевидно, L ¹ Æ, с другой стороны

L ¹ P2, так как x1&x2 Ï L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2n+1. Покажем, что [L] Í L. Рассмотрим Ф = f(f1, ..., fm), где f, f1, ..., fn Î L. Тогда Ф = а0 Å а1(с10 Å с11х1 Å...Å c1nxn1) Å a2(c20 Å c21x1 Å c22x2Å ...Å c2nxn2)Å...Å an(cm0 Åcm1x1 Å ... Å cmnxnm) = в0 Å в1х1 Å ...Å вnхn Þ ФÎL.

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

Определение. Набор = (a1, ..., an) предшествует набору = (b1, ..., bn) и обозначается , если для 1£i£n ai£bi, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования ( ) является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.

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

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

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

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

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

N = {f1, f2, ...fs, ...} полна в Р2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T0, T1, L, S, M. Докажем от противного, пусть N Í Q, очевидно, [N] Í [Q] = Q, но [N] = P2, т.к. N – полна в Р2, отсюда Р2=Q, но это не так. Необходимость доказана.

Докажем достаточность. Пусть F = {f0, f1, fL, fm, fs}, где f0ÏT0, f1ÏT1, fLÏL, fsÏS и fmÏM. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x1&x2, }.

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

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

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

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

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

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

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

Определение.Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1 x2 x3} – базис.





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.