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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



 

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

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

Пример 2.19

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

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

Определение 2.14. Функция 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( ) f1( ), ..., fm( ) fm( ), тогда набор (f1( ), ..., fm( )) (f1( ), ..., fm( )), но тогда Ф( ) Ф( ), так как fÎM, отсюда Ф = f(f1, ..., ) – монотонная функция.

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

Таблица 2.22

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

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

 



Последнее изменение этой страницы: 2016-07-14; просмотров: 82; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.81.89.248 (0.007 с.)