04.2. Функции K-значной логики
Пусть , где
.
Определение 4.7. Функцией K-значной логики, или k-значной функцией, от переменных при называется произвольное отображение
, K-значными функциями от 0 переменных называются функции-константы 0, 1, …, K – 1.
Обозначим через и
множества всех K-значных функций и K-значных функций от
переменных.
При изучении K-значных функций используются многие из терминов и обозначений, введенных при изучении булевых функций. В частности, аналогичным образом определяются равенство функций, существенные и несущественные переменные, функции от переменных, тождественно равны константам 0, 1, …, K – 1, подфункции и т. д.
Так как множество конечно, то K-значную функцию от
переменных можно задать таблицей её значений на всех наборах (или векторах) из
. При этом условимся записывать их в порядке возрастания как числа в конечной системе исчисления. Непосредственно из табличного значения видно, что различных K-значных функций равно
. При
табличное задание K-значных функций практически еще более трудно осуществимо.
В связи с этим важным вопросом является вопрос о разработке аналитических способов K-значных функций.
Множество можно рассматривать как кольцо вычетов
по модулю
, и потому можно считать определенными на
операции сложения и умножения по модулю
. Будем обозначать эти операции при
теми же значками
, что и операции над числами. Используя эти операции и функции-константы можно построить кольцо многочленов
от переменных
. Каждый многочлен из этого кольца представляет K-значную функцию от
переменных. При простом
, когда
есть поле, многочленами представляются все K-значные функции. При составном
— это не так.
Используя операции сложения и умножения, а также элементарные функции
Можно получить представление K-значной функции, сходное с совершенной дизъюнктивной нормальной формой для случая :
. (4.4)
Другими, часто используемыми операциями на являются аналоги дизъюнкции, конъюнкции и отрицания:
Для K-значных функций, как и в двоичном случае, можно ввести понятия операции, представления функций формулами над заданной системой функций, замыкания, замкнутой и полной системы функций и. т.д. Приведем примеры полных систем K-значных функций.
1. Из представления (4.4) следует, что полной является система функций .
2. Так как в разложении (4.4) операцию сложения можно заменить на дизъюнкцию (выбор максимума), то полной является также система функций .
3. Наряду с разложением (4.4) имеет место еще один аналог совершенной дизъюнктивной нормальной формы функции , где IA(X) = 1 как только X = A, и в остальных случаях равна 0. Отсюда следует, что полной является система функций
.
4. Система функций является полной системой функций.
Доказательство. С помощью суперпозиции из функции легко получить функции
. Из них получим константу
, а поэтому все функции константы
. Теперь нетрудно получить функции
:
.
Как следует из примера 3, остается построить функцию , т. е.
Для этого сначала построим функции
Теперь из них можно получить функции
И .
5. Аналогично функции Шеффера в K-значной логике является функция Вебба , которая одна образует систему, т. е. система
является полной.
Доказательство. Используя , при
имеем
. Далее получаем:
А так как
Отсюда имеем, что — полная система функций.
Утверждение 4.8. Все K-значные функции представляются многочленами над в том и только том случае, когда K — простое число, т. е.
Поле (без доказательства).
Утверждение 4.9. (Критерий полноты — критерий Слупецкого). Пусть система K-значных функций K содержит все функции одной переменной, причем . Тогда для полноты системы К необходимо и достаточно, чтобы К содержала функцию, существенно зависящую по меньшей мере от двух переменных и принимающую все
значений из
.
< Предыдущая | Следующая > |
---|