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



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

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

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

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

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

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

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

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

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

  • ¬ 1 ¯ = 1 {displaystyle lnot {ar {1}}=1}
  • ¬ ( x ∧ 1 ¯ ) = ¬ x ∨ 1 {displaystyle lnot (xland {ar {1}})=lnot xlor 1}

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

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

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

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

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

Логики

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

Ниже показаны таблицы истинности для логических операций «Сильной логики неопределённости» (strong logic of indeterminacy) Стивена Клини и «Парадоксальной логики» (logic of paradox, LP) Грэма Приста. Обе логики имеют три логических значения — «ложь», «неопределённость» (в логике Приста — «парадокс») и «истина», которые в логике Клини обозначаются буквами F (false), U (unknown), T (true), а в логике Приста числами −1, 0 и 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) логические операции эквивалентны следующим численным операциям:

X ¯ = − X ; {displaystyle {ar {X}}=-X;} X ∨ Y = m a x ( X , Y ) ; {displaystyle Xlor Y=max(X,Y);} X ∧ Y = m i n ( X , Y ) . {displaystyle Xland Y=min(X,Y).}

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

X → Y   = d e f X ¯ ∨ Y {displaystyle X ightarrow Y {overset {underset {mathrm {def} }{}}{=}}{ar {X}}lor Y} .

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

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

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

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