Троичная логика

Трои́чная ло́гика (трёхзначная логика или тернарная логика) — один из видов (многозначной логики), предложенный (Яном Лукасевичем) в 1920 году. Трёхзначная логика — исторически первая^[](многозначная логика), является простейшим расширением (двузначной логики).

Классификация

Различают чёткую ТЛ, в которой все три значения определяются как конкретные числовые значения (например, ${\displaystyle \{0,1,2\}}$, ${\displaystyle \{-1,0,+1\}}$, ${\displaystyle \{0,{}^{1}\!/_{2},1\}}$), а также ряд нечётких троичных логик с одним, двумя и тремя нечёткими логическими значениями (выражаемые числами как диапазоны значений).

Нечёткая троичная логика с одним нечётким значением дополняет значения ${\displaystyle 0}$ («ложь») и ${\displaystyle 1}$ («истина») нечётким значением «неопределённость», занимающую (в сравнении с (вероятностной логикой)) весь интервал ${\displaystyle (0,1)}$. Примером значений ТЛ с двумя нечёткими значениями можно назвать («меньше», «равно», «больше»), («отрицательно», 0, «положительно»).

Высокий практический интерес представляет ТЛ с тремя нечёткими значениями, так как любая измеряемая (например, посредством датчиков) информация верна лишь с определенным допуском, то есть в некотором диапазоне значений. Примерами значений таких логик могут быть тройки («меньше», «равно, в пределах допуска», «больше»), («уклон влево», «прямо, в допустимых пределах», «уклон вправо»), («холодно», «прохладно», «жарко») и другие.

Алгебраические свойства

Троичная логика, в отличие от двоичной, не (булево кольцо) и обладает собственным математическим аппаратом. Он состоит из системы аксиом, которые определяют над множеством {«1», «0», «1»} одноместные и двухместные операции, а также выводимые из них свойства.

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

Несколько свойств образуются благодаря особенности отрицания Лукасевича:

• ${\displaystyle \lnot {\bar {1}}=1}$
• ${\displaystyle \lnot (x\land {\bar {1}})=\lnot x\lor 1}$

Однако из-за наличия третьего состояния некоторые законы двоичной логики оказываются неверными, для них сформулированы троичные аналоги. Так, вместо (закона противоречия) стали применять , вместо (закона исключённого третьего) — (), вместо неверного закона Блейка—Порецкого применяют трёхчленный .

Физическая реализация

При физической реализации троичным функциям в троичной логике соответствуют троичные (логические элементы), в общем случае не обязательно электронные.

Схемы с 3-4-значной логикой дают возможность сократить количество используемых логических и запоминающих элементов, а также межэлементных соединений. Схемы трёхзначной логики легко реализуются на (КМОП)-технологии. Трёхзначная логика обладает большей выразительностью, чем двухзначная.

На основе троичных элементов — троичной ферритодиодной ячейки разработки (Николая Брусенцова) — в 1959 году в (вычислительном центре МГУ) спроектирована малая ЭВМ «(Сетунь)», выпущена в 46 экземплярах.

Логики

Логики Клини и Приста

Ниже показаны таблицы истинности для логических операций «Сильной логики неопределённости» (strong logic of indeterminacy) (Стивена Клини) и «Парадоксальной логики» (logic of paradox, LP) ^[англ.]. Обе логики имеют три логических значения — «ложь», «неопределённость» (в логике Приста — «парадокс») и «истина», которые в логике Клини обозначаются буквами F (false), U (unknown), T (true), а в логике Приста числами −1, 0 и 1.

F: false, U: unknown, T: true NOT(A) A ¬ A F T U U T F (AND)(A, B) A ∧ B B F U T A F F F F U F U U T F U T OR(A, B) A ∨ B B F U T A F F U T U U U T T T T T

−1: false, 0: «paradoxical», +1: true NEG(A) A ¬ A −1 +1 0 0 +1 −1 (MIN)(A, B) A ∧ B B −1 0 +1 A −1 −1 −1 −1 0 −1 0 0 +1 −1 0 +1 (MAX)(A, B) A ∨ B B −1 0 +1 A −1 −1 0 +1 0 0 0 +1 +1 +1 +1 +1

Значение U в логике Клини присваивается выражениям, которые реально имеют значение T или F, но в данный момент это значение по каким-то причинам неизвестно, в результате чего возникает неопределённость. Тем не менее, результат логической операции с величиной U может оказаться определённым. Например, поскольку T & F = F и F & F = F, то и U & F = F. В более общем виде: если для некоторой логической операции oper выполняется соотношение
oper(F,F)=oper(F,T), то oper(F,U)=oper(F,F)=oper(F,T);
аналогично, если
oper(T,F)=oper(T,T), то oper(T,U)=oper(T,F)=oper(T,T).

В отличие от логики Клини, в логике Приста значение 0 определено и считается одновременно и истинным, и ложным (парадоксальным). Разница заключается в определении тавтологий. Тогда как в логике Клини только одно выделенное истинностное значение — это T, в логике Приста оба значения — 1 и 0 — являются выделенными.

При численном обозначении логических значений (-1, 0, 1) логические операции эквивалентны следующим численным операциям:

${\displaystyle {\bar {X}}=-X;}$

${\displaystyle X\lor Y=max(X,Y);}$

${\displaystyle X\land Y=min(X,Y).}$

Операция импликации в логиках Клини и Приста определяется формулой, аналогичной формуле двоичной логики:

${\displaystyle X\rightarrow Y\ {\overset {\underset {\mathrm {def} }{}}{=}}{\bar {X}}\lor Y}$.

Таблицы истинности для неё

IMPK(A, B), OR(¬A, B) A → B B T U F A T T U F U T U U F T T T

IMPK(A, B), MAX(−A, B) A → B B +1 0 −1 A +1 +1 0 −1 0 +1 0 0 −1 +1 +1 +1

Это определение отличается от определения импликации, принятого в логике Лукасевича.

Функциональный подход

Назовём функцию ${\displaystyle y=f(x_{1},\;x_{2},\;\ldots ,\;x_{n})}$ функцией трёхзначной логики, если все её переменные принимают значения из множества {0,1,2} и сама функция принимает значения из этого же множества. Примеры функций: max(x, y), min(x, y), x+1 (mod 3). Обозначим ${\displaystyle P_{3}}$ множество всех функций трёхзначной логики. Под операцией над функциями будем понимать суперпозицию. Класс функций K из ${\displaystyle P_{3}}$ назовём замкнутым, если любая суперпозиция функций из K принадлежит K. Система функций класса K называется полной, если любая функция из K может быть представлена суперпозицией функций этой системы. (Полная система) называется базисом, если никакая функция из этой системы не может быть представлена суперпозицией остальных функций этой системы. Доказано, что в ${\displaystyle P_{3}}$ существует конечный базис (в частности, состоящий из одной функции). Замкнутый класс K называется предполным, если он не совпадает с ${\displaystyle P_{3}}$, но добавление любой функции, ему не принадлежащей, порождает ${\displaystyle P_{3}}$. С. В. Яблонским доказано, что в ${\displaystyle P_{3}}$ существует 18 (предполных классов). Также доказано, что все они имеют конечные базисы, в частности, состоящие из функций, зависящих не более чем от двух переменных. Ю. И. Янов и (А. А. Мучник) доказали, что в ${\displaystyle P_{3}}$ существуют классы функций, не имеющие базиса, и классы функций, имеющие бесконечный базис. Отсюда следует, что множество замкнутых классов в ${\displaystyle P_{3}}$ имеет мощность континуума. Этим трёхзначная (и любая многозначная) логика существенно отличается от двухзначной, где, как доказано Постом, все замкнутые классы имеют конечный базис и множество замкнутых классов счётно.

Использование в базах данных

В некоторых системах управления базами данных используется специальное значение UNKNOWN, которое может быть результатом логической операции, наряду со значениями TRUE и FALSE.

Смысл значения UNKNOWN — «неизвестность», то есть неопределённый результат операции. Значение UNKNOWN может использоваться тогда, когда в применяемой системе разработки программного обеспечения используется специальное значение (NULL). Операция сравнения возвращает значение UNKNOWN, если один или оба из её операндов равны NULL, а также некоторые логические операции, если одним из их операндов является значение UNKNOWN. Условными операторами языков программирования значение UNKNOWN обрабатывается аналогично FALSE, то есть конструкция вида:

 if UNKNOWN then a := 1 else a := 2 

приведёт к присваиванию переменной a значения 2.

Правила операций с UNKNOWN

• Любая операция сравнения любого значения с NULL или UNKNOWN даёт в результате UNKNOWN.
• not UNKNOWN = UNKNOWN
• TRUE and UNKNOWN = UNKNOWN
• FALSE and UNKNOWN = FALSE
• TRUE or UNKNOWN = TRUE
• FALSE or UNKNOWN = UNKNOWN
• TRUE xor UNKNOWN = UNKNOWN
• FALSE xor UNKNOWN = UNKNOWN

См. также

• (Троичные функции)
• (Троичный триггер)
• (Троичная ЭВМ)
• (Сетунь (компьютер))
• (Многозначная логика)
• Аймара (язык)

Примечания

1. В оригинальной публикации 1979 года от 23 мая 2021 на Wayback Machine — буквами f, p и t соответственно.
2. Яблонский С. И. Функциональные построения в k-значной логике, Труды Математического института им. В. А. Стеклова, 51, 1958
3. Гниденко В. М., Нахождение порядков предполных классов в трёхзначной логике, сб. Проблемы кибернетики, вып 8, М., 1962
4. Янов Ю. И., Мучник А. А., О существовании k-значных замкнутых классов, не имеющих конечного базиса, ДАН СССР, 127, № 1, 1959
5. Post E.L. Two-valued iterative systems, Аnn Math. Studies, 5, № 1, 1941

Литература

• D. C. Rine (ed.), Computer Science and Multiple-Valued Logic. Theory and Applications. Elsevier, 1977, 548p.
• Васильев Н. И. Воображаемая логика. — М.: Наука, 1989.
• Карпенко А. С. Многозначные логики // Логика и компьютер. Вып. №4. — М.: Наука, 1997.
• Кэррол Льюис. Символическая логика // Льюис Кэррол. История с узелками. — М.: Мир, 1973.
• Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики. — М.: Иностранная литература, 1959.
• (Слинин Я. А.) Современная модальная логика. — Л.: Издательство Ленинградского университета, 1976.
• Стяжкин Н. И. Формирование математической логики. — М.: Наука, 1967.
• Гетманова А. Д. Учебник по логике. — М.: Владос, 1995. — С. 259—268. — 303 с. — .
• Толковый словарь по вычислительным системам / Под ред. В. Иллингуорта и др.. — М.: Машиностроение, 1990. — 560 с. — .
• Яблонский С. И. Функциональные построения в k-значной логике, Труды Математического института им. В. А. Стеклова, 51, 1958
• Янов Ю. И., Мучник А. А., О существовании k-значных замкнутых классов, не имеющих конечного базиса, ДАН СССР, 127, № 1, 1959
• Гниденко В. М., Нахождение порядков предполных классов в трёхзначной логике, сб. Проблемы кибернетики, вып 8, М., 1962
• Post E.L. Two-valued iterative systems, Аnn Math. Studies, 5, № 1, 1941
• Гектор Гарсиа-Молина, Джеффри Д. Ульман, Дженнифер Уидом «Системы баз данных. Полный курс»

Ссылки

• Практическое применение троичной логики и её преимущества над двоичной
• Сайт TernaryComp Брусенцова Николая Петровича (НИЛ ВЦ МГУ)