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

Определение:

Троичная или трёхзначная логика (англ. ternary logic) — один из видов многозначной логики, использующий три истинностных значения.

В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки [math]-[/math] и [math]+[/math]. Третьему (серединному) состоянию соответствует знак [math]0[/math]. Допустимо использование таких наборов знаков, как [math]\{0,1,2\}[/math], [math]\{-1,0,1\}[/math], [math]\{0,1/2,1\}[/math] [math]\{N,Z,P\}[/math], и др. Иногда используют обозначения И, Л, Н (истина, ложь и неизвестность).

Классическими примерами состояний такой логики являются знаки [math]\gt [/math], [math]\lt [/math] и [math]=[/math], — значения, которые может принимать компаратор двух объектов.

Определение:

Троичная функция (или тернарная функция) от [math]n[/math] переменных — это отображение [math]B^n[/math] → [math]B[/math], где [math]B = \{-, 0, +\}[/math].

Одноместные операции

По-аналогии с двоичной логикой, в троичной логике существует всего [math]3^{3^n}[/math] операций для [math]n[/math] аргументов. Таким образом, в троичной логике всего существует [math]3^{3^1}=27[/math] одноместных операций.

Инверсия

[math]NOT^-[/math],[math]NOT[/math] и [math]NOT^+[/math] — операторы инверсии, сохраняющие состояние [math]-[/math], [math]0[/math] и [math]+[/math] соответственно, когда оно соответствует типу оператора, или обращающие в значение, не равное исходному состоянию и не соответствующее типу оператора инверсии, то есть в оставшееся третье.

Например, если [math]a = (-)[/math], то [math]NOT^+a=0[/math]. Так как исходное состояние [math](-)[/math], тип инверсии [math]NOT^+[/math], то методом исключения можно прийти к результирующему состоянию [math]0[/math].

Все возможные варианты для данной одноместной операции приведены в таблице.

[math]\bf{a}[/math]	[math]\bf{NOT^-}[/math]	[math]\bf{NOT}[/math]	[math]\bf{NOT^+}[/math]
[math]\bf{-}[/math]	[math]-[/math]	[math]+[/math]	[math]0[/math]
[math]\bf{0}[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]0[/math]	[math]-[/math]	[math]+[/math]

Операция выбора

[math]S^-[/math], [math]S[/math] и [math]S^+[/math] — операторы выбора. Превращают состояние, соответствующее типу оператора в [math](+)[/math], в случае любого из остальных двух состояний переменная приобретает значение [math](-)[/math].

[math]\bf{a}[/math]	[math]\bf{S^-}[/math]	[math]\bf{S}[/math]	[math]\bf{S^+}[/math]
[math]\bf{-}[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]
[math]\bf{0}[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]

Модификация

[math]INC[/math] и [math]DEC[/math] — операторы модификации, соответственно увеличение и уменьшение трита на единицу по модулю три. При переполнении трита счёт начинается заново ([math]INC (+) = (-)[/math]).

[math]\bf{a}[/math]	[math]\bf{INC a}[/math]	[math]\bf{DEC a}[/math]
[math]\bf{-}[/math]	[math]0[/math]	[math]+[/math]
[math]\bf{0}[/math]	[math]+[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]-[/math]	[math]0[/math]

Пороговое увеличение и уменьшение

[math]\nearrow[/math], [math]\searrow[/math] — данные операторы работают аналогично операторам модификации лишь с тем отличием, что при переполнении трита цикл состояний не повторяется, и значение так и остаётся минимальным или максимальным.

[math]\bf{a}[/math]	[math]\bf{\nearrow a}[/math]	[math]\bf{\searrow a}[/math]
[math]\bf{-}[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{0}[/math]	[math]+[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]+[/math]	[math]0[/math]

Другие одноместные функции

• [math]+[/math], [math]0[/math] и [math]-[/math] — функции, не зависящие от аргумента [math]a[/math], они же вырожденные.

• Функция [math]a[/math] — тождественная и также вырожденная функция.

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

Двухместные операции

Легко видеть, что всего в троичной логике существует [math]3^{3^2}=19683[/math] двухместные операции. В таблице приведены самые основные и практически полезные из них.

[math]\bf{a}[/math]	[math]\bf{b}[/math]	[math]\bf{a \vee b}[/math]	[math]\bf{a \wedge b}[/math]	[math]\bf{a \cdot b}[/math]	[math]\bf{a \oplus b}[/math]	[math]\bf{a \mid b}[/math]	[math]\bf{a+b}[/math]	[math]\bf{a \Uparrow b}[/math]	[math]\bf{a \rightarrow b}[/math]	[math]\bf{a \equiv b}[/math]	[math]\bf{a \&_L b}[/math]	[math]\bf{a \rightarrow_L b}[/math]	[math]\bf{a \wedge_+ b}[/math]	[math]\bf{a \rightarrow_+ b}[/math]	[math]\bf{a \rightarrow_G b}[/math]	[math]\bf{a \rightarrow_M b}[/math]	[math]\bf{a \rightarrow b}[/math]	[math]\bf{a \equiv b}[/math]
[math]\bf{-}[/math]	[math]\bf{-}[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]	[math]0[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]
[math]\bf{-}[/math]	[math]\bf{0}[/math]	[math]-[/math]	[math]0[/math]	[math]0[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]0[/math]	[math]0[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{-}[/math]	[math]\bf{+}[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]0[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{0}[/math]	[math]\bf{-}[/math]	[math]-[/math]	[math]0[/math]	[math]0[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]	[math]-[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]	[math]-[/math]	[math]0[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{0}[/math]	[math]\bf{0}[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]	[math]+[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]
[math]\bf{0}[/math]	[math]\bf{+}[/math]	[math]0[/math]	[math]+[/math]	[math]0[/math]	[math]+[/math]	[math]-[/math]	[math]+[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]	[math]0[/math]	[math]0[/math]	[math]+[/math]	[math]+[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]\bf{-}[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]0[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]\bf{0}[/math]	[math]0[/math]	[math]+[/math]	[math]0[/math]	[math]+[/math]	[math]-[/math]	[math]+[/math]	[math]+[/math]	[math]0[/math]	[math]+[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]0[/math]	[math]-[/math]
[math]\bf{+}[/math]	[math]\bf{+}[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]	[math]+[/math]	[math]-[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]	[math]+[/math]

Ниже приведены названия этих функций.

Обозначение	Название
[math]\bf{a \vee b}[/math]	Дизъюнкция
[math]\bf{a \wedge b}[/math]	Конъюнкция
[math]\bf{a \cdot b}[/math]	Логическое умножение по модулю три
[math]\bf{a \oplus b}[/math]	Логическое сложение по модулю три
[math]\bf{a \mid b}[/math]	Функция Вебба
[math]\bf{a+b}[/math]	Пороговое сложение
[math]\bf{a \Uparrow b}[/math]	Исключающий максимум
[math]\bf{a \rightarrow b}[/math]	Среднее (Mean)
[math]\bf{a \equiv_{CMP} b}[/math]	Сравнение
[math]\bf{a \&_L b}[/math]	Сильная конъюнкция
[math]\bf{a \rightarrow_L b}[/math]	Импликация Лукасевича
[math]\bf{a \wedge_+ b}[/math]	Конъюнкция Клини
[math]\bf{a \rightarrow_+ b}[/math]	Импликация Клини
[math]\bf{a \rightarrow_G b}[/math]	Импликация Гейтинга (импликация Гёделя)
[math]\bf{a \rightarrow_M b}[/math]	Материальная импликация
[math]\bf{a \rightarrow_B b}[/math]	Функция следования Бруснецова
[math]\bf{a \equiv b}[/math]	Тождество

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

Все нижеперечисленные законы и свойства легко доказываются путём перебора всех значений входящих в них переменных. Алгебраический подход заключается в том, чтобы определить над множеством [math]\{-, 0, +\}[/math] двухместные ([math]\wedge[/math], [math]\vee[/math]) и одноместные ([math]'[/math], [math]S[/math], [math]\neg[/math]) операции с помощью законов, а оставшиеся свойства уже выводить из них алгебраически.

1. Свойства констант:

[math]a \wedge (+) = a[/math]

[math]a \wedge (-) = (-)[/math]

[math]a \vee (+) = (+)[/math]

[math]a \vee (-) = a[/math]

[math]\overline{(-)} = (+)[/math]

[math]\overline{(+)} = (-)[/math]

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

[math]\overline{\overline{a}}=a[/math]

[math]a'''=a[/math]

4. Буквальное определение циклического отрицания вытекает из следующих свойств:

[math](-) ' = 0[/math]

[math]0 ' = (+)[/math]

[math](+) ' = (-)[/math]

5. Имеет место быть неизменность третьего состояния ("0") при отрицании Лукаcевича:

[math]\overline{0} = 0[/math]

[math]\overline{(a \wedge 0)} = \overline{a} \vee 0[/math]

Для законов двоичной логики, не справедливых для троичной, существуют их троичные аналоги.

6. Закон несовместности состояний (аналог закона противоречия в двоичной логике):

[math]Sa \wedge Sa'' = (-)[/math]

[math]Sa' \wedge Sa'' = (-)[/math]

[math]Sa' \wedge Sa = (-)[/math]

7. Закон исключённого четвёртого (вместо закона исключённого третьего), он же закон полноты состояний:

[math]Sa' \vee Sa \vee Sa'' = (+)[/math], или

[math]S^-a \vee Sa \vee S^+a = (+)[/math]

8. Трёхчленный закон Блейка-Порецкого:

[math]a \vee Sa' \wedge b \vee Sa \wedge b = a \vee b[/math], или

[math]a \vee S^-a \wedge b \vee Sa \wedge b = a \vee b[/math]

9. Закон трёхчленного склеивания:

[math] a \wedge Sb' \vee a \wedge Sb \vee a \wedge Sb'' = a[/math], или

[math]a \wedge S^-b \vee a \wedge Sb \vee a \wedge S^+b = a[/math]

10. Закон обобщённого трёхчленного склеивания:

[math]a \wedge Sd' \vee b \wedge Sd \vee c \wedge Sd'' \vee a \wedge b \wedge c = a \wedge Sd' \vee b \wedge Sd \vee c \wedge Sd''[/math], или

[math]a \wedge S^-d \vee b \wedge Sd \vee c \wedge S^+d \vee a \wedge b \wedge c = a \wedge S^-d \vee b \wedge Sd \vee c \wedge S^+d[/math]

11. Антиизотропность отрицания Лукаcевича:

[math]a \leqslant b \Rightarrow \overline a \geqslant \overline b[/math]

Перспективы развития

Преимущества троичной системы счисления перед двоичной

Определение:

Троичная система счисления (англ. ternary numeral system) — позиционная система счисления с целочисленным основанием, равным [math]3[/math]. Существует в двух вариантах: несимметричная ([math]\{0,1,2\}[/math], [math]\{0,1/2,1\}[/math] и др.) и симметричная (обычно [math]\{-,0,+\}[/math] или [math]\{−1,0,1\}[/math]).

Троичная логика обладает рядом преимуществ перед двоичной. Ниже перечислены основные:

• Троичная СС позволяет вмещать больший диапазон чисел в памяти троичного компьютера, поскольку [math]3^n\gt 2^n[/math].

• Очевидно, что троичная СС использует меньше разрядов для записи чисел, по-сравнению с двоичной СС. Например:

[math]1110101_2=11100_3[/math]

[math]1000_2=22_3[/math]

Для троичной СС используется несимметричный набор [math]\{0,1,2\}[/math].

Эти два важных преимущества перед двоичной системой счисления говорят о большей экономичности троичной системы счисления.

Определение:

Экономичность системы счисления (англ. radix economy) — возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков.

Докажем экономичность троичной системы счисления математически.

Пусть [math]p[/math] – основание системы счисления, а [math]n[/math] – количество требуемых знаков. Для записи [math]n[/math] знаков потребуется [math]n/p[/math] разрядов, а количество чисел, которое при этом можно записать, будет равно [math]p^{n/p}[/math].

Рассмотрим функцию [math]f(p)=p^{n/p}[/math].

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

[math]f'(p)=n(p^{n/p - 2}) \ne 0 \Rightarrow 1 - \ln⁡ p = 0, \ln p = 1, p = e[/math]

[math]e \approx 2,71[/math], ближайшее число к [math]e[/math] — [math]3[/math]. Таким образом, троичная СС не только экономичнее двоичной, но и экономичнее любой другой СС.

• Троичная логика включает в себя почти все возможности двоичной логики.

• Компьютер, основанный на троичной логике, обладает большим быстродействием. Например, троичный сумматор и полусумматор в троичном компьютере при сложении тритов выполняет примерно в 1,5 раза меньше операций сложения по-сравнению с двоичным компьютером.

Проблемы реализации

Одним из барьеров, сдерживающих развитие и распространение троичной техники, является неверное представление о необычности и трудной постижимости трехзначной логики. Современная формальная логика (как традиционная, так и математическая) основана на принципе двузначности. Кроме того, электронные компоненты для построения логики, использующие более двух состояний, требуют больше материальных затрат на их производство, достаточно сложны в реализации, и потребляют больше электроэнергии, поэтому троичные компьютеры занимают очень малое место в истории. Использование двоичных компьютеров — более простых и дешёвых в реализации — практически полностью затмило применение троичных компьютеров.

Практические реализации

Говоря о будущем таких машин, как «Сетунь» (то есть троичных компьютеров), известный американский учёный Дональд Кнут, отмечал, что они занимают очень мало место в отрасли вычислительной техники, что объясняется массовым засильем двоичных компонентов, производимых в огромных количествах. Но, поскольку троичная логика гораздо эффектнее, а главное, эффективнее двоичной, не исключено, что в недалёком будущем к ней вернутся.

В настоящий момент, в условиях интегральной технологии и микроэлектроники привлекательность троичной техники увеличивается: сложность трехзначных вентилей теперь не так страшна, а сокращение количества соединений и уменьшение рассеиваемой мощности особенно ценны. Особо благоприятное влияние на развитие троичное логики оказало пришествие квантовых компьютеров — вычислительных устройств, работающих на основе квантовой механики, принципиально отличающихся от классических компьютеров, работающих на основе классической механики. Полноценный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики. Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит — квантовых аналогов битов. Используя в универсальных квантовых вентилях кутриты вместо кубитов, можно существенно снизить количество необходимых вентилей. Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении. Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.

См. также

• Булевые функции

Источники информации

• Заметки о троичной цифровой технике — часть 1

• «Сетунь» — единственный серийный троичный компьютер

• Википедия — Троичная логика

• Хабрахабр — Замена двоичной логики — увеличит ли это производительность?

• Жизнь сквозь решето сети — Третье состоянье

• Жизнь сквозь решето сети — Трёхзначная логика

• Традиция — Троичная логика