8-3. ПОЛНЫЕ СИСТЕМЫ ФУНКЦИЙ В k-ЗНАЧНОЙ ЛОГИКЕ

Проблема полноты для многозначной логики при в настоящее время еще не решена. Если для двухзначной логики имеется критерий полноты, сформулированный нами в виде теоремы 1-10, то для -значной логики А. В. Кузнецовым получен следующий результат.

Теорема 8-1. В -значной логике можно эффективно построить систему замкнутых классов каждый из которых целиком не содержится ни в каком другом классе, такую, что система функций является полной тогда и только тогда, когда она целиком не содержится ни в одном из построенных классов.

Для двоичной логики классы были указаны в формулировке теоремы 1-10. Для -значной логики, за исключением случая эти классы пока не удалось построить. Поэтому теорема Кузнецова носит скорее теоретический, нежели практический характер.

Имеет место следующая теорема.

Теорема 8-2. Для того чтобы система функций в -значной логике, содержащая все функции одного переменного, выпускающие хотя бы одно значение, была полна, необходимо и достаточно, чтобы эта система содержала функцию, существенно зависящую более чем от одного аргумента и принимающую значений.

Для порождения множества всех функций одной переменной можно воспользоваться функциями, предложенными Пикаром.

Теорема 8-3. Все функции одной переменной могут быть порождены тремя функциями:

Вместо функций Пикара можно воспользоваться системой функций, определяемой следующей теоремой.

Теорема 8-3. Все функции одной переменной могут быть получены из системы следующих функций:

Кроме этих общих теорем о полноте, можно указать еще на целый ряд результатов, принадлежащих А. Саломаа, Е. Ю. Захаровой и другими авторами. Однако для наших целей более интересно рассмотрение конкретных систем, которые являются базисами в любой -значной логике.

Число различных базисов в Л-значной логике бесконечно, а число простых базисов (определение простого базиса дано в § 1-8) ограничено сверху величиной

Поэтому, аналогично тому как это мы сделали в двоичном случае, ограничимся рассмотрением только таких базисов и полных систем, которые оказались удобными для представления функций в многозначной логике и для синтеза схем,

Важнейшие и наиболее интересные с точки зрения практики системы такого типа следующие;

1) Система Поста. Постом показано, что в любой А-значной логике полна система, состоящая из дизъюнкции и цикла.

2) Система Россера и Тьюкетта. Полную систему функций в А-значной логике составляют характеристические функции, функции конъюнкции, дизъюнкции, функции константы.

3) Система Вебба. Полную систему составляет для любой -значной логики функция Вебба.

4) Модульная логика. Если простое число, то функции сложения по модулю к и умножения по модулю образуют в -значной логике полную систему.

Н. Н. Айзенбергом и З. Л. Рабиновичем была предложена полная система, состоящая из следующих функций:

и циклического отрицания, определяемого соотношением (8-5). Ими же была предложена полная система, состоящая из функций (8-8), константы единица и сложения по модулю Для -значной логики можно определить полиномиальные представления, аналогичные тем, которые рассматривались нами в § 2-8 для двоичной

логики. В настоящей книге мы ограничимся рассмотрением лишь системы Россера и Тьюкетта, первой из систем Н. Н. Айзенберга и 3. Л. Рабиновича и полиномиальными представлениями. Остальные полные системы могут быть исследованы аналогичными методами.