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

Определение. Набор = (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 пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.

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. Составим таблицу, которая называется критериальной :

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

Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {F2, F3, F4}ÌL, {F1, F3, F4}ÌT1, {F1, F2, F4}ÌT0, {F1, F2, F3}ÌM.

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

3. Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, 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. Следовательно, критериальная таблица имеет вид:

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

Определение. Система функций {F1, ..., FS, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {X1&X2, 0, 1, X1 X2 X3} – базис.

Теорема о достаточности четырех функций.

Из любой полной в Р2 системы функций можно выделить полную подсистему, состоящую не более чем из четырех функций.

Доказательство. Пусть {F0, F1, FL, FM, FS} – полная система функций, тогда она не лежит целиком ни в одном из классов T0, T1, L, M, S. Следовательно, в системе есть функции F0ÏT0, F1ÏT1, FLÏL, FS ÏS и FMÏM. Система {F0, F1, FL, FM, FS} Í P2 и образует полную систему в Р2. Рассмотрим функцию F0: F0(0, ..., 0) = 1.

Если F0(1, ..., 1) = 0, то F0ÏT1 и F0ÏM, тогда {F0, FS, FL} – полная система из трех функций.

Если F0(1, ..., 1) = 1, то F0ÏS и {F0, F1, FL, FM } образует полную систему из четырех функций.

Пример 1, приведенный выше, показывает, что цифру 4 в общем случае уменьшить нельзя, из полной системы {X1X2,0,1,X1ÅX2ÅX3} нельзя выделить полную подсистему.

Следствие. Базис в Р2 может состоять максимум из четырех функций.