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

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

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

В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки „[math]-[/math]“ и „[math]+[/math]“. Третьему (серединному) состоянию соответствует знак "[math]0[/math]".

Классическими примерами состояний такой логики являются знаки ">", "<" и "=", состояние постоянного тока (движется в одну сторону, движется в другую сторону, отсутствует) и др.

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

Очевидно, что в троичной логике всего существует [math]3^3=27[/math] одноместных операций.

[math]NOT^-[/math],[math]NOT[/math] и [math]NOT^+[/math] — операторы инверсии. [math]NOT^-[/math] и [math]NOT^+[/math] сохраняют состояние "-" и "+" соответственно.

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

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

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

[math]a[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]
[math]f_0[/math]	-	-	-	[math]-[/math]
[math]f_1[/math]	-	-	0	[math]\searrow[/math]
[math]f_2[/math]	-	-	+	[math]S^+[/math]
[math]f_3[/math]	-	0	-
[math]f_4[/math]	-	0	0
[math]f_5[/math]	-	0	+	[math]a[/math]
[math]f_6[/math]	-	+	-	[math]S[/math]
[math]f_7[/math]	-	+	0	[math]NOT^-[/math]
[math]f_8[/math]	-	+	+
[math]f_9[/math]	0	-	-
[math]f_{10}[/math]	0	-	0
[math]f_{11}[/math]	0	-	+	[math]NOT^+[/math]
[math]f_{12}[/math]	0	0	-
[math]f_{13}[/math]	0	0	0	[math]0[/math]
[math]f_{14}[/math]	0	0	+	[math]a^+[/math]
[math]f_{15}[/math]	0	+	-	[math]INC[/math]
[math]f_{16}[/math]	0	+	0	[math]a^o[/math]
[math]f_{17}[/math]	0	+	+	[math]\nearrow[/math]
[math]f_{18}[/math]	+	-	-	[math]S^-[/math]
[math]f_{19}[/math]	+	-	0	[math]DEC[/math]
[math]f_{20}[/math]	+	-	+
[math]f_{21}[/math]	+	0	-	[math]NOT[/math]
[math]f_{22}[/math]	+	0	0	[math]a^-[/math]
[math]f_{23}[/math]	+	0	+
[math]f_{24}[/math]	+	+	-
[math]f_{25}[/math]	+	+	0
[math]f_{26}[/math]	+	+	+	[math]+[/math]

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

	[math]S^-[/math]	[math]S[/math]	[math]S^+[/math]
[math]NOT^-[/math]	[math]f_9[/math]	[math]f_3[/math]	[math]f_1[/math]
[math]NOT[/math]	[math]f_8[/math]	[math]f_{20}[/math]	[math]f_{24}[/math]
[math]NOT^-[/math]	[math]f_{22}[/math]	[math]f_{16}[/math]	[math]f_{14}[/math]
[math]INC[/math]	[math]f_4[/math]	[math]f_{10}[/math]	[math]f_{12}[/math]
[math]DEC[/math]	[math]f_{17}[/math]	[math]f_{23}[/math]	[math]f_{25}[/math]

Дизъюнкция и конъюнкция

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

В троичной логике более наглядно использование префиксной нотации для этих операций.

[math]a \vee b = max(a,b)[/math]

[math]a \wedge b = min(a,b)[/math]

Таблица результатов дизъюнкции двух переменных.

[math]max(a,b)[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]
[math]-[/math]	-	0	+
[math]0[/math]	0	0	+
[math]+[/math]	+	+	+

Таблица результатов конъюнкции двух переменных.

[math]max(a,b)[/math]	[math]-[/math]	[math]0[/math]	[math]+[/math]
[math]-[/math]	-	-	-
[math]0[/math]	-	0	0
[math]+[/math]	-	0	+

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

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

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

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

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

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

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

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

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

Также действует закон двойного отрицания (отрицания Лукашевича) и тройного (циклического) отрицания:

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

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

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

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

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

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

Третье состояние ("0") при отрицании Лукашевича неизменно:

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

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

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

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

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

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

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

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

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

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

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

[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]

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

[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]

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

[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]

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

[math]a \leq b \Rightarrow \overline a \geq \overline b[/math]

См. также

• Троичная функциональная схема

Источники

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

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

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

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