Теорема Поста о функциональной полноте
09.10.2011 |Теорема Поста: система функций из P2 функционально полна ⇔ система содержит:
1) Функцию, не сохраняющую константу 0.
2) Функцию, не сохраняющую константу 1.
3) НЕсамодвойственную функцию
4) НЕмонотонную функцию
5) НЕлинейную функцию
Доказательство ⇒ (прямое): Пусть система функций F из P2 полна (в P2), допустим, что в системе F нет одной из указанных функций, например немонотонной. Тогда все функции в F монотонны, т.к. класс монотонных функций замкнут относительно суперпозиции, то мы не можем получить ни одной немонотонной функции. Потому система F полной в P2 не является. Противоречие с полнотой F. Следовательно, система F содержит все 5 указанных функций.
Доказательство ⇐ (обратное): Пусть F содержит все 5 функций: f1(x1, x2,…,xn) – не сохраняет константу 0, f2(x1, x2,…,xn) – не сохраняет константу 1, f3(x1, x2,…,xn) – несамодвойственная функция, f4(x1, x2,…,xn) – немонотонная функция, f5(x1, x2,…,xn) – нелинейная функция.
Покажем, что суперпозицией функций системы F можно получить полную систему G{xy,¬x}
1. Пусть g(x) = f1(x1, x2,…,xn), тогда g(0) = f(0,…,0) = 1 далее возможны два случая:
А) g(1) = 1. ⇒ g(x) ≡1. Функция h(x) = f2(g1(x),g2(x),…,gn(x)) = f2(1,..,1) = 0. Т.е. h(x) ≡ 0 получили константы 0 и 1.
Б) g(1) =0 ⇒ g(x) = ¬x. По лемме о несамодвойственной функции суперпозицией над {f3,¬x} можно получить одну из констант, например 0. f1(0,…,0) =1 есть другая константа. В обоих случаях получили обе константы.
2. По лемме о немонотонной функции суперпозицией над {f4,0,1} можно получить отрицание х.
3. По лемме о нелинейной функции суперпозицией над {f5,1,¬x} можно получить конъюнкцию.
Функции системы G найдены {x&y, ¬x} суперпозицией функций над системой F. Следовательно, F – есть полная система в P2. чтд.
Предполные классы
Определение: Замкнутый класс функций К из Р2 предполон, если класс K не является полным, но для любой функции f не из K система k∨{ f } полна.
Теорема: Следующие замкнутые классы функций предполны:
1) Класс T0, не сохраняющий константу 0.
2) Класс T1, не сохраняющий константу 1.
3) Класс M монотонных функций.
4) Класс L линейных функций.
5) Класс S самодвойственных функций.
Теорема (перефразировка теоремы Поста в терминах предполных классов.): Система функций F полна ⇔ когда F не содержится целиком ни в одном из пяти предполных классов Т0, Т1, М, L, S.
Замечание: Пост описал все замкнутые классы алгебры логики и все их базисы, которые оказались конечными. Число замкнутых классов счетно и множество замкнутых классов образует решетку относительно включения множеств. Эта решетка имеет наибольший класс P2 (он же максимум) и три минимальных элемента 01 = [{x}], 02 = [{1}], 03 = [{ 1 }]. Наименьшего элемента решетка не имеет.
