остальные функции системы на принадлежность этому классу можно не проверять. Если при проверке окажется, что все функции системы принадлежат данному классу, то проверку надо закончить, т.к. по теореме Поста такая система не будет полной.
Пример 10. Проверить на полноту следующую систему функций: fx1 ! x2; x1^x2g. Для проверки составим следующую таблицу (см. предыдущие примеры и упражнения).
Таблица 5
f |
T0 |
T1 |
S |
M |
L |
! |
|
+ |
|
|
|
^ |
+ |
+ |
|
+ |
|
В данной таблице знак + означает, что функция принадлежит соответствующему классу, а знак , что не принадлежит. Из таблицы видно, что все функции данной систе-
мы принадлежат классу 1. Следовательно, по теореме Поста данная система функций не является полной.
Пример 11. Проверить на полноту следующую систему функций: fx1; x1 _ x2g. Решение. Функция x не сохраняет 0, не сохраняет 1 и не является монотонной.
Функция x1 _ x2 не является ни самодвойственной, ни линейной. Из этого следует, что в данной системе функций есть хотя бы одна функция, не принадлежащая каждому из пяти замкнутых классов. Следовательно, данная система функций полна.
Замечание 4. Можно показать, что если функция не принадлежит классам T0, T1 и S, то она не принадлежит и классам M и L. Следовательно, по теореме Поста любая
система, содержащая хотя бы одну такую функцию, полна.
Упражнение 14 (д/з). Исследовать на полноту следующие системы функций: а) fx; 1g, б) fx1 ^ x2; x1 _ x2g, â) fx1 x2; x1g.
6