§1.8. Функции -значной логики

Рассмотрим множество .

Функция называется функцией -значной логики от переменных.

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

Табл. 1.12

0	0		0	0
0	0		0	1
0	0		0
0	0		1	0
0	0

Имея в виду стандартное расположение наборов (в соответствии с увеличением их номера), наборы представляют собой разложения в -ичной системе счисления чисел .

Обозначим через множество всех функций -значной логики от переменных, а множество всех функций -значной логики.

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

Теорема. .

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

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

.

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

Рассмотрим примеры некоторых считаемых элементарными функций .

1) – константы.

2) , где представляет собой обобщение отрицания в смысле “циклического” сдвига значений – отрицание Поста.

3) , где (часто обозначают ) представляет собой обобщение отрицания в смысле “зеркального” отображения значений, – отрицание Лукашевича.

4) – характеристическая функция (первого рода) числа .

5) – характеристическая функция (второго рода) числа .

6) – обобщение конъюнкции (другие обозначения: , ) – минимум и .

7) – другое обобщение конъюнкции – произведение и по модулю .

8) – обобщение дизъюнкции (другое обозначение: ) – максимум и .

9) – сумма и по модулю .

10) – усеченная разность.

11)

– разность и по модулю (функция Вебба).

12) – импликация.

Следующие равенства вводятся по определению.

По аналогии с булевой алгеброй в -значной логике:

– вводится понятие формулы над множеством функций ;

– каждой формуле ставится в соответствие функция и говорится, что формула реализует функцию ;

– формулы и считаются эквивалентными, если соответствующие им функции и равны.

Обратим внимание на то, что

1. в -значной логике сохраняются многие свойства и результаты, которые имеют место в двузначной логике;

2.

Так, имеют место равенства:

1. Коммутативность

, где .

2. Ассоциативность

, где .

3. Дистрибутивность умножения относительно сложения

.

4. Дистрибутивность операции относительно операции

.

5. Дистрибутивность операции относительно операции

.

6. Идемпотентность операций и

.

7. Аналоги правил де Моргана в

.

Следующее важное тождество, доказываемое непосредственной проверкой, представляет собой аналог СДНФ

.

Приведем примеры отличия -значной логики (при ) от двузначной:

1.

2. , но

Класс функций из называется (функционально) полным, если любая функция из может быть представлена в виде формулы над .

Пример. Система полная.

Теорема. Система функций

является полной в .

Доказательство. Пусть – произвольная функция .

Для нее имеет место разложение

.

Данная формула (правая часть) построена из функций, входящих в систему . Такое представление функции называется первой формой.

Для функций из справедливо еще одно представление, называемое второй формой

.

Если простое число, то, как и в случае двузначной логики, каждая функция представима, и притом единственным образом, в виде полинома Жегалкина

где а операции сложения и умножения производятся по модулю символ понимается в обычном смысле:

Наконец, если где простое число, то можно установить взаимно однозначное соответствие между множеством и полем (из элементов). Отождествим соответствующие элементы множеств и т.е. будем считать, что на множестве заданы операции сложения и умножения, превращающие это множество в поле из элементов (эти операции не следует путать со сложением и умножением по модулю , ведь кольцо не является полем). Теперь мы можем представлять функции в виде полиномов Жегалкина

где а операции такие, как в поле .

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

в СДНФ и в виде полинома Жегалкина.

Решение. Составим таблицу значений функции:

Табл. 1.13

0	0	0
0	1	0
0	2	0
1	0	1
1	1	0
1	2	0
2	0	2
2	1	2
2	2	0

Рассматривая только те строки таблицы, где , получаем:

Полином Жегалкина имеет вид . Запишем это выражение в матричной форме:

Подставляя значения и используя таблицу, получим:

.

Решая это матричное уравнение, будем иметь

.

Это означает, что Задачи для самостоятельного решения

1. Представить функцию трёхзначной логики в виде полинома Жегалкина.

2. Представить функцию

4-значной логики в виде СДНФ.

3. Назовём функцию k-значной логики симметричной, если для любой перестановки переменных Найти количество симметричных функций от двух переменных в k-значной логике. Ответы

1. 2. . 3.