Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



 

Определение 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, ..., ) – монотонная функция.

Определение. Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M.

Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции.

Доказательство. Пусть f(x1, ..., xn) – немонотонная функция. Тогда существуют наборы и , для которых но Пусть i1, …, ik есть все те номера аргументов, для которых , p=1, …, k. На всех остальных аргументных местах j имеем aj = bj. В выражении заменим нули на местах i1, …, ik на x. В результате получим функцию g(x), для которой g(0) = f( ) = 1 и g(1) = f( ) = 0. Функция g(x) является отрицанием.

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

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

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

Задачи

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

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

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

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

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

1. Покажем, что система функций {f1 =x1x2, f2 =0, f3 =1, f4 = x1Å x2Å x3} полна в Р2. Составим таблицу, которая называется критериальной:

  Т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

 

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4L, {f1, f3, f4T1, {f1, f2, f4T0, {f1, f2, f3M.

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

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

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

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

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

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

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

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

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


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-04-09; Просмотров: 1618; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.028 с.)
Главная | Случайная страница | Обратная связь