<<
>>

§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.

<< | >>
Источник: Дискретная математика. Лекции. 2016

Еще по теме §1.8. Функции -значной логики:

  1. Тема 1. ЛОГИЦИЗМ
  2. Конъюнкция
  3. Модальная логика
  4. ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ
  5. СЕМАНТИЧЕСКАЯ ТЕМАТИКА В МАРКСИСТСКОЙ ГНОСЕОЛОГИИ 
  6. § 40. Антропологизм в логике Б. Эрдманна
  7. КАК НУЖНО РАССУЖДАТЬ КОМПЬЮТЕРУ [†††††]
  8. 2.2. Слово «так» в функции частицы
  9. Математика, естествознание и логика (0:0 От Марк[с]а)
  10. АЛГЕБРА ЛОГИКИ
  11. ВЕРОЯТНОСТНАЯ ЛОГИКА
  12. ЛОГИКА
  13. ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  14. 1.2.2 Значение и смысл предложений
  15. 3.3.2 Ганс Рейхенбах