Пусть , где .
Определение 4.2.1. Функцией k-значной логики, или k-значной функцией, от переменных при называется произвольное отображение k-значными функциями от 0 переменных называются функции- константы 0,1,…,к-1.
Обозначим через и множества всех k-значных функций и k-значных функций от переменных.
При изучении k-значных функций используются многие из терминов и обозначений, введенных при изучении булевых функций. В частности, аналогичным образом определяются равенство функций, существенные и несущественные переменные, функции от переменных, тождественно равны константам 0,1,…,к-1, подфункции и т.д.
Так как множество конечно, то k-значную функцию от переменных можно задать таблицей её значений на всех наборах (или векторах) из . При этом условимся записывать их в порядке возрастания как числа в конечной системе исчисления. Непосредственно из табличного значения видно, что различных k-значных функций равно . При табличное задание k-значных функций практически еще более трудно осуществимо.
|
|
В связи с этим важным вопросом является вопрос о разработке аналитических способов k-значных функций.
Множество можно рассматривать как кольцо вычетов по модулю , и потому можно считать определенными на операции сложения и умножения по модулю . Будем обозначать эти операции при теми же значками , что и операции над числами. Используя эти операции и функции-константы можно построить кольцо многочленов от переменных . Каждый многочлен из этого кольца представляет k-значную функцию от переменный. При простом , когда - есть поле, многочленами представляются все k-значные функции. При составном - это не так.
Используя операции сложения и умножения, а так же элементарные функции
можно получить представление k-значной функции сходное с совершенной дизъюнктивной нормальной формой для случая .
(4.2.2)
Другими, часто используемыми операциями на являются аналоги дизъюнкции, конъюнкции и отрицания:
.
Для k-значных функций, как и в двоичном случае, можно ввести понятия операции, представления функций формулами над заданной системой функций, замыкания, замкнутой и полной системы функций и.т.д. Приведем примеры полных систем k-значных функций.
1. Из представления (4.2.2) следует, что полной является система функций
2. Так как в разложении (4.2.2) операцию сложения можно заменить на дизъюнкцию(выбор максимума), то полной является также система функций
3. Наряду с разложением (4.2.2) имеет место еще один аналог совершенной дизъюнктивной нормальной формы функции , где . Отсюда следует, что полной является система функций .
4. Система функций является полной системой функций.
|
|
Доказательство. С помощью суперпозиции из функции легко получить функции . Из них получим константу , а поэтому все функции константы . Теперь нетрудно получить функции :
.
Как следует из примера 3, остается построить функцию , т.е. Для этого сначала построим функции
Теперь из них можно получить функции и .
5. Аналогично функции Шеффера в k-значной логике является функция Вебба , которая одна образует систему, т.е. система является????????
Доказательство. Используя при имеем . Далее получаем:
А так как . Отсюда имеем, что - полная система функций.
Утверждение 4.2.3. Все k-значные функции представляются многочленами над в том и только том случае, когда к- простое число, т.е. -поле.
(без доказательства).
Утверждение 4.2.4. (критерий полноты- Критерий?????Слунецкого??).
Пусть система k-значных функций K содержит се функции одной переменной, причем . Тогда для полноты системы К необходимо и достаточно, чтобы К содержала функцию, существенно зависящую по меньшей мере от двух переменных и принимающую все значений из .