Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

44 s 1 s 1 1 s i i i i i i n 1 x x f x x ... ) ,..., ( ) ,..., ( ...    . В силу нелинейности полинома в нем найдется член, содержащий не менее двух множителей. Пусть это x 1 и x 2 . Тогда полином можно записать следующим образом ) ,..., ( ) ,..., ( ) ,..., ( ) ,..., ( ... ) ,..., ( ... n 4 3 n 2 3 3 i i n 1 2 3 n 1 2 1 3 i i i i f x x x f x x x x x x f x x x f x x s 1 s 1 s 1        , причем f x x 0 n 1 3  ) ,..., ( . Выберем такие , ,..., n 3   чтобы 1 f n 1 3  ) ,..., (   . Тогда , ) ,..., ( , ) ( , ,            2 1 1 2 n 1 2 3 1 2 x x x x f x x x x где    , , – константы, равные 0 или 1 . Рассмотрим функцию ( , ) 1 2 x x  , получаемую из ( , ) 1 2 x x  следующим образом: . ) , ( , ) (            2 1 1 2 x x x x Воспользуемся явным выражением для функции ( , ) 1 2 x x  , чтобы вычислить 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ( , ) ( )( ) ( ) ( ) x x x x x x x x x x x x x x                                                   . Следовательно, 1 2 1 2 x x x x  ( , )  . В заключение отметим, что классы T 0 ,T 1 ,S,M и L попарно различны, что видно из таблицы. Таблица 8.1. T 0 T 1 S M L 0 + - - + + 1 - + - + + x - - + - + Теорема (о функциональной полноте). Для того, чтобы система функций F={f 1 ,…,f n } была полной, необходимо и