Тема 3.6 Важнейшие замкнутые классы.
Пусть MIР2. Замыканием М называется множество всех функций из P2, которые можно выразить формулами над М. Замыкание М обозначается [M].
Множество функций М называется замкнутым классом, если [M]=M.
Пример:
1) P2 – замкнутый класс. 2) Множество {1,x1Ax2} не является замкнутым классом. Его замыканием будет класс линейных функций: [{1, x1 A x2}] = {f(x1, ..., xn) = c0 A c1x1 A ... A cnxn}. Действительно, по определению формулы над М, функция f(G1, x3), где f – есть сумма по модулю 2, G1 – функция х1 A х2, будет формулой над М: f(G1, x3) = (x1 A x2) A 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 A x2, g2(x) = x ÎA. Возьмем g2(g1(x1, x2)) = x1 A x2 Î [A], g2(g1(1, 1)) = 1 A 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, x1Ux2, xÎТ0 и x1|x2, x1
x2, 
ÏТ0. Покажем далее, что [Т0] = Т0.
Число функций, зависящих от n переменных и принадлежащих Т0, будет равно 
2) T1 – класс функций, сохраняющих константу 1.
T1 = {f(x1, ...) |f(1, 1, ...) = 1}; x1&x2, x1Ux2, xÎT1, х1Aх2, x1x2ÏT1, следовательно Т1 – собственное подмножество Р2. 
Покажем, что [T1] I 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, 
, x1Ax2Ax3ÎS, x1&x2, x1Ux2, x1Ax2ÏS, следовательно, S – собственное подмножество Р2. |S(n)| = 
. Покажем, что [S]IS. Ф = f(f1, ..., fn) Î [S], если f, f1, ..., fn Î S, а также, что Ф Î S. По принципу двойственности, Ф* = f*(f1*, ..., fn*) = f(f1, ..., fn) = Ф, отсюда S – замкнутый класс.
L = {f(x1, ...)| f = c0Ac1x1A...Acnxn}; очевидно, L ? ?, с другой стороны
L ? P2, так как x1&x2 Ï L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2n+1. Покажем, что [L] I L. Рассмотрим Ф = f(f1, ..., fm), где f, f1, ..., fn Î L. Тогда Ф = а0 A а1(с10 A с11х1 A...A c1nxn1) A a2(c20 A c21x1 A c22x2A ...A c2nxn2)A...A an(cm0 Acm1x1 A ... A cmnxnm) = в0 A в1х1 A ...A вnхn ? ФÎL. 5) М – класс монотонных функций.
Набор 
= (a1, ..., an) предшествует набору 
= (b1, ..., bn) и обозначается 
, если для 1£i£n ai£bi, например: = (0010), = (0110), тогда 
. Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.
Функция f(x1, ..., xn) называется монотонной, если для двух наборов и , таких что , выполняется f()f().
Для числа монотонных функций, зависящих от 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 | + | + | + | + | + |
 | - | - | + | + | - |
| 0 | + | - | + | - | + |
| 1 | - | + | + | - | + |
| x1x2 | + | + | - | - | + |
A={x, , 0, 1, x1x2) не является полной системой функций так как всегда есть функции Î Р2 не входящие в эти классы. Задачи
1. Доказать, что пересечение любых двух замкнутых классов замкнуто.
2. Доказать, что объединение двух замкнутых классов не всегда замкнуто