ГЛАВА ДЕВЯТАЯ. ТРЕХЗНАЧНАЯ ЛОГИКА

9-1. ОСНОВНЫЕ ПОНЯТИЯ

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

Функции, определяемые этими таблицами, мы будем обозначать обычным образом, используя символику, введенную нами для функций алгебры логики:

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

Функции конъюнкции, дизъюнкции и инверсии связаны между собой формулами де Моргана.

Из этой таблицы следует:

Кроме тоге,

Рассмотрим таблицу задания функции следующего вида:

Отсюда вытекает, что

Из соотношений (9-2), (9-4) и формул де Моргана вытекает теорема о полноте системы Поста в трехзначной логике.

Теорема 9-1. Любая троичная функция может быть выражена через дизъюнкцию и циклическое отрицание.

Теорема 9-2. Функции Вебба образуют полную систему (систему Вебба).

Справедливость этого утверждения вытекает из того, что

и

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

Теорема 9-3. Функции сложения по модулю три, умножения по модулю три и константа единица образуют полную систему (эта система есть модульная логика).

Для доказательства отметим, что

Теперь рассмотрим таблицу следующего вида:

В этой таблице

и

Из рассмотренной таблицы следует, что

Теорема доказана.

В полных системах Поста, Вебба и модульной системе аналитическое выражение функций трехзначной логики получается довольно громоздким и менее прозрачным, чем в системе Россера, Тьюкетта или при представлении функции в виде ТДСНФ или ТКСНФ.

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

где , а — некоторая функция одного переменного.

Когда принимает последовательно значения принимает значения. При этом в соответствии с (8-28) имеем

Этому условию удовлетворяют 18 трехзначных функций одной переменной, представленные в следующей таблице:

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

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

Нетрудно показать, что можно определить производные другим, эквивалентным (9-6) способом:

Для любого выбора из 18 указанных функций имеет место разложение в ряд типа (8-34), а для случая для которых выполняется условие имеет место разложение вида (8-35).

Как уже отмечалось в гл. 8, для трехзначной логики С. В. Яблонским был найден критерий полноты. Для того чтобы сформулировать этот критерий, введем. 18 специальных классов троичных функций:

1. Класс состоящий из монотонных функций, которых при сравнении наборов аргументов принято, что (см. § 1-6).

2. Класс состоящий из монотонных функций, для аргументов которых принят порядок

3. Класс монотонных функций для аргументов которых принят порядок

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

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

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

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

8. Класс содержащий функции, сохраняющие константу нуль.

9. Класс состоящий из функций, сохраняющих константу 1.

10. Класс состоящий из функций, сохраняющих константу 2.

11. Функции класса относящиеся к этому классу, обладаюг следующим свойством. Пусть - некоторый набор значений аргументов, состоящий только из 1 и 2.

Зафиксируем его. Рассмотрим все возможные такие, что На множестве этих наборов функция может принимать значении 1 и 2, но не значение 0.

12. Класс Формируетси аналогично классу но с заменой 1 на 0 и 0 на 1.

13. Класс Формируется аналогично классу но с заменой 2 на 0 и 0 на 2.

14. Класс Функция принадлежит этому классу, если для любых чисел на всех наборах аргументов таких, что

функция либо принимает лишь значения 0 или 1, либо тождественно равна 2.

15. Класс Формируется аналогично классу но с заменой

2 на 1 и 1 на 2.

16. Класс Формируется аналогично классу но с заменой 2 на 0 и 0 на 2.

17. Класс состоящий из линейных функций.

18. Класс состоящий из самодвойственных функций. Функция является самодвойственной класса если имеет место равенство

Теорема 9-4. Для того чтобы система функций была полна в трехзначной логике, необходимо и достаточно, чтобы эта система не содержалась целиком ни в одном из вышеуказанных классов.

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