9.7. МНОГОЗНАЧНЫЕ ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ

Рассмотренные двоичные переключательные функции допускают прямое обобщение на множество значений истинности

Определение. Многозначной (m-значной) переключательной функ цией называется функция принимающая значение из множества причем ее аргументы тоже принимают значения из .

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

Рис. 9.4

Рис. 9.5

различных функций — Все они образуют множество Рт. Число функций с ростом тип увеличивается очень быстро. Достаточно сказать» что -значных функций, зависящих от двух аргументов (напомним, что двузначных — всего 16). Многозначные функции задаются таблицами истинности, которые удобно представлять в виде матриц. Например, таблица истинности для функции из представлена на рис. 9.4.

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

Большой вклад в решение этой проблемы внесен С. В. Яблонским, в частности, для им найдены все предполные классы (их оказалось 27). Некоторые из них обобщают двоичные классы: классы сохранения констант и подмножеств констант, классы линейных, монотонных и самодвойственных функций. В более общих случаях для определения функциональной полноты пользуются различными критериями. Приведем несколько примеров функционально полных систем

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

Легко видеть, что при эта система превращается в систему И, ИЛИ, НЕ. Знаки дизъюнкции и конъюнкции здесь использованы для того, чтобы легче было иллюстрировать возможность образования канонической формы, которую с успехом можно назвать совершенной -значной дизъюнктивной нормальной формой:

где, очевидно

Пример. Записать СДНФ функции, заданной таблицей истинности, представленной на рис. 9.5.

Как и в двоичном случае, исходя из общей формы, выписываем СДНФ, обращая внимание лишь на ненулевые наборы:

Существуют методы минимизации рассмотренной СДНФ, однако они далеко не всегда так эффективны, как в двоичном случае. Это можно объяснить тем, что в двоичном случае в нашем распоряжении имеются все одноместные операции.

В заключение следует отметить, что -значные функции можно с успехом моделировать совокупностью двоичных. Очевидно, число двоичных функций не должно быть меньше и каждая из них зависит не менее чем от переменных — ближайшее, не меньшее а, натуральное число). Например, десятичная функция двух переменных может быть реализована двоичными функциями переменных. Понятно, что двоичные функции будут частично определенными.