Троичная логика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Преимущества перед двоичной логикой)
м (rollbackEdits.php mass rollback)
 
(не показано 28 промежуточных версий 3 участников)
Строка 1: Строка 1:
{{Определение
+
'''Троичная''' или '''трёхзначная логика''' (англ. ''ternary logic'') — один из видов многозначной логики, использующий три истинностных значения.
|definition =
 
'''Троичная''' или '''трёхзначная логика''' (англ. ''ternary logic'') — исторически первая многозначная логика, разработанная Яном Лукасевичем в 1920 г. Является простейшим расширением двузначной логики.
 
}}
 
  
 
В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки <tex>-</tex> и <tex>+</tex>. Третьему (серединному) состоянию соответствует знак <tex>0</tex>. Допустимо использование таких наборов знаков, как <tex>\{0,1,2\}</tex>, <tex>\{-1,0,1\}</tex>, <tex>\{0,1/2,1\}</tex> <tex>\{N,Z,P\}</tex>, и др. Иногда используют обозначения И, Л, Н (истина, ложь и неизвестность).
 
В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки <tex>-</tex> и <tex>+</tex>. Третьему (серединному) состоянию соответствует знак <tex>0</tex>. Допустимо использование таких наборов знаков, как <tex>\{0,1,2\}</tex>, <tex>\{-1,0,1\}</tex>, <tex>\{0,1/2,1\}</tex> <tex>\{N,Z,P\}</tex>, и др. Иногда используют обозначения И, Л, Н (истина, ложь и неизвестность).
  
Классическими примерами состояний такой логики являются знаки <tex>></tex>, <tex><</tex> и <tex>=</tex>, состояние постоянного тока (движется в одну сторону, движется в другую сторону, отсутствует) и др.
+
Классическим примером состояний такой логики является множество <tex>\{>, <, =\}</tex>, — значения, которые может принимать компаратор двух объектов.
 
 
==Преимущества перед двоичной логикой==
 
 
 
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Троичная система счисления''' (англ. ''Ternary numeral system'')— позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: '''несимметричная''' (<tex>\{0,1,2\}</tex>, <tex>\{0,1/2,1\}</tex> и др.) и '''симметричная''' (обычно <tex>\{−,0,+\}</tex> или <tex>\{−1,0,1\}</tex>).
+
'''Троичная функция''' (или '''тернарная функция''') от <tex>n</tex> переменных — это отображение <tex>T^n</tex> <tex>T</tex>, где <tex>T = \{-, 0, +\}</tex>.
 
}}
 
}}
Троичная логика обладает рядом преимуществ перед двоичной. Ниже перечислены основные:
 
 
* Троичная СС позволяет вмещать больший диапазон чисел в памяти троичного компьютера, поскольку <tex>3^n>2^n</tex>.
 
  
* <p>Очевидно, что троичная СС использует меньше разрядов для записи чисел, по-сравнению с двоичной СС. Например:
+
==Одноместные операции==
  
<tex>1110101_2=11100_3</tex>
+
По-аналогии с [[Определение_булевой_функции | двоичной логикой]], в троичной логике существует всего <tex>3^{3^n}</tex> операций для <tex>n</tex> аргументов. Таким образом, в троичной логике всего существует <tex>3^{3^1}=27</tex> одноместных операций.
  
<tex>1000_2=22_3</tex>
+
===Инверсия===
  
(для троичной СС используется несимметричный набор {0,1,2}.
+
<tex>NOT^-</tex>,<tex>NOT</tex> и <tex>NOT^+</tex> — операторы '''инверсии''', сохраняющие состояние <tex>-</tex>, <tex>0</tex> и <tex>+</tex> соответственно, когда оно соответствует типу оператора, или обращающие в значение, не равное исходному состоянию и не соответствующее типу оператора инверсии, то есть в оставшееся третье.  
  
Эти два важных преимущества перед двоичной системой счисления говорят о большей '''экономичности''' троичной системы счисления.
+
Например, если <tex>a = (-)</tex>, то <tex>NOT^+a=0</tex>. Так как исходное состояние <tex>(-)</tex>, тип инверсии <tex>NOT^+</tex>, то методом исключения можно прийти к результирующему состоянию <tex>0</tex>.
{{Определение
 
|definition =  
 
'''Экономичность системы счисления''' (англ. ''Radix economy'') —  возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков.
 
}}
 
</p>
 
  
Докажем экономичность троичной системы счисления математически.
+
Все возможные варианты для данной одноместной операции приведены в таблице.
  
Пусть <tex>p</tex> – основание системы счисления, а <tex>n</tex> – количество требуемых знаков. Для записи <tex>n</tex> знаков потребуется <tex>\dfrac n p</tex> разрядов, а количество чисел, которое при этом можно записать, будет равно <tex>p^{\frac n p}</tex>.
+
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| <tex>\bf{a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{NOT^-}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{NOT}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{NOT^+}</tex>
  
Рассмотрим функцию <tex>f(p)=p^{\dfrac n p}</tex>.
+
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|}
  
Для того, чтобы определить максимальное значение функции, найдем ее производную:
+
===Операция выбора===
  
<tex>f'(p)=n(p^{\dfrac n {p-2}}) \ne 0 \Rightarrow 1 - \ln⁡ p = 0, \ln p = 1, p = e</tex>
+
<tex>S^-</tex>, <tex>S</tex> и <tex>S^+</tex> — операторы '''выбора'''. Превращают состояние, соответствующее типу оператора в <tex>(+)</tex>, в случае любого из остальных двух состояний переменная приобретает значение <tex>(-)</tex>.
  
<tex>e \approx 2,71</tex>, ближайшее число к <tex>e</tex> <tex>3</tex>.
+
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| <tex>\bf{a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{S^-}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{S}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{S^+}</tex>
  
* Троичная логика включает в себя почти все возможности двоичной логики.
+
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|}
  
* Компьютер, основанный на троичной логике, обладает большим быстродействием. Например, [[троичный сумматор]] и полусумматор в троичном компьютере при сложении тритов выполняет примерно в 1,5 раза меньше операций сложения по-сравнению с двоичным компьютером.
+
===Модификация===
  
==Проблемы реализации==
+
<tex>INC</tex> и <tex>DEC</tex> — операторы '''модификации''', соответственно увеличение и уменьшение трита на единицу по модулю три. При переполнении трита счёт начинается заново (<tex>INC (+) = (-)</tex>).
  
Одним из барьеров, сдерживающих развитие и распространение троичной техники, является неверное представление о необычности и трудной постижимости трехзначной логики. Современная формальная логика (как традиционная, так и математическая) основана на принципе двузначности. Кроме того, электронные компоненты для построения логики, использующие более двух состояний, требуют больше материальных затрат на их производство, достаточно сложны в реализации, и потребляют больше электроэнергии, поэтому троичные компьютеры занимают очень малое место в истории.  
+
{| style="background-color:#CCC;margin:0.5px"
Использование двоичных компьютеров — более простых и дешёвых в реализации — практически полностью затмило применение троичных компьютеров.
+
!style="background-color:#EEE"| <tex>\bf{a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{INC a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{DEC a}</tex>
  
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|}
  
 +
===Пороговое увеличение и уменьшение===
  
==Одноместные операции==
+
<tex>\nearrow</tex>, <tex>\searrow</tex> — данные операторы работают аналогично операторам модификации лишь с тем отличием, что при переполнении трита цикл состояний не повторяется, и значение так и остаётся минимальным или максимальным.
 
 
По-аналогии с двоичной логикой, в троичной логике существует всего <tex>3^{3^n}</tex> операций для <tex>n</tex> аргументов. Таким образом, в троичной логике всего существует <tex>3^{3^1}=27</tex> одноместных операций.
 
 
 
<tex>NOT^-</tex>,<tex>NOT</tex> и <tex>NOT^+</tex> — операторы '''инверсии'''. <tex>NOT^-</tex> и <tex>NOT^+</tex> сохраняют состояние <tex>-</tex> и <tex>+</tex> соответственно.
 
  
<tex>S^-</tex>, <tex>S</tex> и <tex>S^+</tex> — операторы '''выбора'''. Превращают одно из трёх состояний (<tex>(-)</tex>, <tex>0</tex> и <tex>(+)</tex>, соответственно) в <tex>(+)</tex>, а остальные два приобретают значение <tex>(-)</tex>.
+
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| <tex>\bf{a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{\nearrow a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{\searrow a}</tex>
  
<tex>INC</tex> и <tex>DEC</tex> — операторы '''модификации''', соответственно увеличение и уменьшение трита на единицу по модулю три. При переполнении трита счёт начинается заново (<tex>INC (+) = (-)</tex>).
+
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#EEE;padding:2px 30px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 30px"| <tex>0</tex>
 +
|}
  
"<tex>+</tex>", " <tex>0</tex> " и "<tex>-</tex>" — функции, не зависящие от аргумента <tex>a</tex>.
+
===Другие одноместные функции===
<table border="1" width="20%" text-align="center">
 
<tr><td><tex>a</tex></td><td><tex>-</tex></td><td><tex>0</tex></td><td><tex>+</tex></td><td></td></tr>
 
<tr><td><tex>f_0</tex></td><td>-</td><td>-</td><td>-</td><td><tex>-</tex></td></tr>
 
<tr><td><tex>f_1</tex></td><td>-</td><td>-</td><td>0</td><td><tex>\searrow</tex></td></tr>
 
<tr><td><tex>f_2</tex></td><td>-</td><td>-</td><td>+</td><td><tex>S^+</tex></td></tr>
 
<tr><td><tex>f_3</tex></td><td>-</td><td>0</td><td>-</td><td></td></tr>
 
<tr><td><tex>f_4</tex></td><td>-</td><td>0</td><td>0</td><td></td></tr>
 
<tr><td><tex>f_5</tex></td><td>-</td><td>0</td><td>+</td><td><tex>a</tex></td></tr>
 
<tr><td><tex>f_6</tex></td><td>-</td><td>+</td><td>-</td><td><tex>S</tex></td></tr>
 
<tr><td><tex>f_7</tex></td><td>-</td><td>+</td><td>0</td><td><tex>NOT^-</tex></td></tr>
 
<tr><td><tex>f_8</tex></td><td>-</td><td>+</td><td>+</td><td></td></tr>
 
<tr><td><tex>f_9</tex></td><td>0</td><td>-</td><td>-</td><td></td></tr>
 
<tr><td><tex>f_{10}</tex></td><td>0</td><td>-</td><td>0</td><td></td></tr>
 
<tr><td><tex>f_{11}</tex></td><td>0</td><td>-</td><td>+</td><td><tex>NOT^+</tex></td></tr>
 
<tr><td><tex>f_{12}</tex></td><td>0</td><td>0</td><td>-</td><td></td></tr>
 
<tr><td><tex>f_{13}</tex></td><td>0</td><td>0</td><td>0</td><td><tex>0</tex></td></tr>
 
<tr><td><tex>f_{14}</tex></td><td>0</td><td>0</td><td>+</td><td><tex>a^+</tex></td></tr>
 
<tr><td><tex>f_{15}</tex></td><td>0</td><td>+</td><td>-</td><td><tex>INC</tex></td></tr>
 
<tr><td><tex>f_{16}</tex></td><td>0</td><td>+</td><td>0</td><td><tex>a^o</tex></td></tr>
 
<tr><td><tex>f_{17}</tex></td><td>0</td><td>+</td><td>+</td><td><tex>\nearrow</tex></td></tr>
 
<tr><td><tex>f_{18}</tex></td><td>+</td><td>-</td><td>-</td><td><tex>S^-</tex></td></tr>
 
<tr><td><tex>f_{19}</tex></td><td>+</td><td>-</td><td>0</td><td><tex>DEC</tex></td></tr>
 
<tr><td><tex>f_{20}</tex></td><td>+</td><td>-</td><td>+</td><td></td></tr>
 
<tr><td><tex>f_{21}</tex></td><td>+</td><td>0</td><td>-</td><td><tex>NOT</tex></td></tr>
 
<tr><td><tex>f_{22}</tex></td><td>+</td><td>0</td><td>0</td><td><tex>a^-</tex></td></tr>
 
<tr><td><tex>f_{23}</tex></td><td>+</td><td>0</td><td>+</td><td></td></tr>
 
<tr><td><tex>f_{24}</tex></td><td>+</td><td>+</td><td>-</td><td></td></tr>
 
<tr><td><tex>f_{25}</tex></td><td>+</td><td>+</td><td>0</td><td></td></tr>
 
<tr><td><tex>f_{26}</tex></td><td>+</td><td>+</td><td>+</td><td><tex>+</tex></td></tr>
 
</table>
 
  
 +
* <tex>+</tex>, <tex>0</tex> и <tex>-</tex> — функции, не зависящие от аргумента <tex>a</tex>, они же вырожденные.
  
 +
* Функция <tex>a</tex> — тождественная и также вырожденная функция.
  
Остальные функции образуются путём сочетания операторов выбора с операторами инверсии и модификации.
+
* Остальные функции от одной переменной образуются путём [[Суперпозиции | сочетания операторов]] выбора с операторами инверсии и модификации, поэтому они не имеют собственных названий.
 
 
<table border="1" width="15%">
 
<tr><th>&nbsp;</th><th><tex>S^-</tex></th><th><tex>S</tex></th><th><tex>S^+</tex></th></tr>
 
<tr><th><tex>NOT^-</tex></th><td><tex>f_9</tex></td><td><tex>f_3</tex></td><td><tex>f_1</tex></td></tr>
 
<tr><th><tex>NOT</tex></th><td><tex>f_8</tex></td><td><tex>f_{20}</tex></td><td><tex>f_{24}</tex></td></tr>
 
<tr><th><tex>NOT^-</tex></th><td><tex>f_{22}</tex></td><td><tex>f_{16}</tex></td><td><tex>f_{14}</tex></td></tr>
 
<tr><th><tex>INC</tex></th><td><tex>f_4</tex></td><td><tex>f_{10}</tex></td><td><tex>f_{12}</tex></td></tr>
 
<tr><th><tex>DEC</tex></th><td><tex>f_{17}</tex></td><td><tex>f_{23}</tex></td><td><tex>f_{25}</tex></td></tr>
 
</table>
 
  
 
==Двухместные операции==
 
==Двухместные операции==
  
Всего в троичной логике существует <tex>3^{3^2}=19683</tex> двухместные операции. Для реализации любой из них при использовании сколь угодного числа переменных достаточно использовать операции выбора и наиболее простые двухместные операции: '''дизъюнкция''' и '''конъюнкция'''.  
+
Легко видеть, что всего в троичной логике существует <tex>3^{3^2}=19683</tex> двухместные операции. В таблице приведены самые основные и практически полезные из них.
  
В троичной логике более наглядно использование префиксной нотации для этих операций.
+
{| style="background-color:#CCC;margin:0.5px"
 +
!style="background-color:#EEE"| <tex>\bf{a}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \wedge b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \vee b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \cdot b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \oplus b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \mid b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a+b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \Uparrow b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \rightarrow b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a\ cmp\ b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \&_L b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \rightarrow_L b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \wedge_+ b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \rightarrow_+ b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \rightarrow_G b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \rightarrow_M b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \rightarrow_B b}</tex>
 +
!style="background-color:#EEE"| <tex>\bf{a \equiv b}</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{-}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{0}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|-
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 6px"| <tex>\bf{+}</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>-</tex>
 +
|style="background-color:#FFF;padding:2px 20px;text-align: center;"| <tex>0</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
 +
|style="background-color:#FFF;padding:2px 20px"| <tex>+</tex>
  
<tex>a \vee b = max(a,b)</tex>
+
|}
  
<tex>a \wedge b = min(a,b)</tex>
+
Ниже приведены названия этих функций.
  
Таблица результатов '''дизъюнкции''' двух переменных.
+
{| style="background-color:#CCC;margin:0.5px"
<table border="1">
+
!style="background-color:#EEE;padding:2px 8px"| '''Обозначение'''
<tr><td><tex>max(a,b)</tex></td><td><tex>-</tex></td><td><tex>0</tex></td><td><tex>+</tex></td></tr>
+
!style="background-color:#EEE;padding:2px 8px"| '''Название'''
<tr><td><tex>-</tex></td><td>-</td><td>0</td><td>+</td></tr>
+
|-
<tr><td><tex>0</tex></td><td>0</td><td>0</td><td>+</td></tr>
+
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \wedge b}</tex>
<tr><td><tex>+</tex></td><td>+</td><td>+</td><td>+</td></tr>
+
|style="background-color:#FFF;padding:2px 8px"| Конъюнкция
</table>
+
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \vee b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Дизъюнкция
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \cdot b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Логическое умножение по модулю три
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \oplus b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Логическое сложение по модулю три
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \mid b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Функция Вебба
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a+b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Пороговое сложение
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \Uparrow b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Исключающий максимум
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \rightarrow b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Среднее (''Mean'')
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a\ cmp\ b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Сравнение
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \&_L b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Сильная конъюнкция
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \rightarrow_L b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Импликация Лукасевича
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \wedge_+ b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Конъюнкция Клини
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \rightarrow_+ b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Импликация Клини
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \rightarrow_G b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Импликация Гейтинга (импликация Гёделя)
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \rightarrow_M b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Материальная импликация
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \rightarrow_B b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Функция следования Бруснецова
 +
|-
 +
|style="background-color:#FFF;padding:2px 8px"| <tex>\bf{a \equiv b}</tex>
 +
|style="background-color:#FFF;padding:2px 8px"| Тождество
  
Таблица результатов '''конъюнкции''' двух переменных.
+
|}
<table border="1">
 
<tr><td><tex>max(a,b)</tex></td><td><tex>-</tex></td><td><tex>0</tex></td><td><tex>+</tex></td></tr>
 
<tr><td><tex>-</tex></td><td>-</td><td>-</td><td>-</td></tr>
 
<tr><td><tex>0</tex></td><td>-</td><td>0</td><td>0</td></tr>
 
<tr><td><tex>+</tex></td><td>-</td><td>0</td><td>+</td></tr>
 
</table>
 
  
 
==Алгебраические свойства==
 
==Алгебраические свойства==
 +
 +
Все нижеперечисленные законы и свойства легко доказываются путём перебора всех значений входящих в них переменных.
 +
Алгебраический подход заключается в том, чтобы определить над множеством <tex>\{-, 0, +\}</tex> двухместные (<tex>\wedge</tex>, <tex>\vee</tex>) и одноместные (<tex>'</tex>, <tex>S</tex>, <tex>\neg</tex>) операции с помощью законов, а оставшиеся свойства уже выводить из них алгебраически.
  
 
<ol>
 
<ol>
Строка 157: Строка 414:
 
<li>Для конъюнкции и дизъюнкции в троичной логике сохраняются '''коммутативный''', '''ассоциативный''' и '''дистрибутивный законы''', '''закон идемпотентности'''.</li>
 
<li>Для конъюнкции и дизъюнкции в троичной логике сохраняются '''коммутативный''', '''ассоциативный''' и '''дистрибутивный законы''', '''закон идемпотентности'''.</li>
  
<li>Закон '''двойного отрицания''' (отрицания Лукашевича) и '''тройного (циклического) отрицания''':</li>
+
<li>Закон '''двойного отрицания''' (отрицания Лукаcевича) и '''тройного (циклического) отрицания''':</li>
  
 
<tex>\overline{\overline{a}}=a</tex>
 
<tex>\overline{\overline{a}}=a</tex>
Строка 171: Строка 428:
 
<tex>(+) ' = (-)</tex>
 
<tex>(+) ' = (-)</tex>
  
<li>Имеет место быть '''неизменность третьего состояния''' ("0") при отрицании Лукашевича:</li>
+
<li>Имеет место быть '''неизменность третьего состояния''' (<tex>0</tex>) при отрицании Лукаcевича:</li>
  
 
<tex>\overline{0} = 0</tex>
 
<tex>\overline{0} = 0</tex>
Строка 214: Строка 471:
 
<tex>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</tex>
 
<tex>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</tex>
  
<li>'''Антиизотропность отрицания Лукашевича''':</li>
+
<li>'''Антиизотропность отрицания Лукаcевича''':</li>
  
 
<tex>a \leqslant b \Rightarrow \overline a \geqslant \overline b</tex>
 
<tex>a \leqslant b \Rightarrow \overline a \geqslant \overline b</tex>
Строка 221: Строка 478:
  
 
==Перспективы развития==
 
==Перспективы развития==
 +
 +
===Преимущества троичной системы счисления перед двоичной===
 +
 +
{{Определение
 +
|definition =
 +
'''Троичная система счисления''' (англ. ''ternary numeral system'') — позиционная система счисления с целочисленным основанием, равным <tex>3</tex>. Существует в двух вариантах: '''несимметричная''' (<tex>\{0,1,2\}</tex>, <tex>\{0,1/2,1\}</tex> и др.) и '''симметричная''' (обычно <tex>\{-,0,+\}</tex> или <tex>\{-1,0,1\}</tex>).
 +
}}
 +
Троичная логика обладает рядом преимуществ перед двоичной. Ниже перечислены основные:
 +
 +
* Троичная СС позволяет вмещать больший диапазон чисел в памяти троичного компьютера, поскольку <tex>3^n>2^n</tex>.
 +
 +
* <p>Очевидно, что троичная СС использует меньше разрядов для записи чисел, по-сравнению с двоичной СС. Например:
 +
 +
<tex>1110101_2=11100_3</tex>
 +
 +
<tex>1000_2=22_3</tex>
 +
 +
Для троичной СС используется несимметричный набор <tex>\{0,1,2\}</tex>.
 +
 +
Эти два важных преимущества перед двоичной системой счисления говорят о большей '''экономичности''' троичной системы счисления.
 +
{{Определение
 +
|definition =
 +
'''Экономичность системы счисления''' (англ. ''radix economy'') —  возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков.
 +
}}
 +
</p>
 +
 +
Докажем экономичность троичной системы счисления математически.
 +
 +
Пусть <tex>p</tex> – основание системы счисления, а <tex>n</tex> – количество требуемых знаков. Для записи <tex>n</tex> знаков потребуется <tex>n/p</tex> разрядов, а количество чисел, которое при этом можно записать, будет равно <tex>p^{n/p}</tex>.
 +
 +
Рассмотрим функцию <tex>f(p)=p^{n/p}</tex>.
 +
 +
Для того, чтобы определить максимальное значение функции, найдем ее производную:
 +
 +
<tex>f'(p)=-n(p^{n/p - 2})(\ln p - 1) \Rightarrow \ln⁡ p - 1 = 0, \ln p = 1, p = e</tex>
 +
 +
<tex>e \approx 2,71</tex>, ближайшее число к <tex>e</tex> — <tex>3</tex>. Таким образом, троичная СС не только экономичнее двоичной, но и экономичнее любой другой СС.
 +
 +
* Троичная логика включает в себя почти все возможности двоичной логики.
 +
 +
* Компьютер, основанный на троичной логике, обладает большим быстродействием. Например, [[Троичная_функциональная_схема |троичный сумматор]] и полусумматор в троичном компьютере при сложении тритов выполняет примерно в 1,5 раза меньше операций сложения по-сравнению с двоичным компьютером.
 +
 +
===Проблемы реализации===
 +
 +
Одним из барьеров, сдерживающих развитие и распространение троичной техники, является неверное представление о необычности и трудной постижимости трехзначной логики. Современная формальная логика (как традиционная, так и математическая) основана на принципе двузначности. Кроме того, электронные компоненты для построения логики, использующие более двух состояний, требуют больше материальных затрат на их производство, достаточно сложны в реализации, и потребляют больше электроэнергии, поэтому троичные компьютеры занимают очень малое место в истории.
 +
Использование двоичных компьютеров — более простых и дешёвых в реализации — практически полностью затмило применение троичных компьютеров.
 +
 +
===Практические реализации===
  
 
Говоря о будущем таких машин, как «Сетунь» (то есть троичных компьютеров), известный американский учёный Дональд Кнут, отмечал, что они занимают очень мало место в отрасли вычислительной техники, что объясняется массовым засильем двоичных компонентов, производимых в огромных количествах. Но, поскольку троичная логика гораздо эффектнее, а главное, эффективнее двоичной, не исключено, что в недалёком будущем к ней вернутся.
 
Говоря о будущем таких машин, как «Сетунь» (то есть троичных компьютеров), известный американский учёный Дональд Кнут, отмечал, что они занимают очень мало место в отрасли вычислительной техники, что объясняется массовым засильем двоичных компонентов, производимых в огромных количествах. Но, поскольку троичная логика гораздо эффектнее, а главное, эффективнее двоичной, не исключено, что в недалёком будущем к ней вернутся.
  
 
В настоящий момент, в условиях интегральной технологии и микроэлектроники привлекательность троичной техники увеличивается: сложность трехзначных вентилей теперь не так страшна, а сокращение количества соединений и уменьшение рассеиваемой мощности особенно ценны. Особо благоприятное влияние на развитие троичное логики оказало пришествие квантовых компьютеров — вычислительных устройств, работающих на основе квантовой механики, принципиально отличающихся от классических компьютеров, работающих на основе классической механики.
 
В настоящий момент, в условиях интегральной технологии и микроэлектроники привлекательность троичной техники увеличивается: сложность трехзначных вентилей теперь не так страшна, а сокращение количества соединений и уменьшение рассеиваемой мощности особенно ценны. Особо благоприятное влияние на развитие троичное логики оказало пришествие квантовых компьютеров — вычислительных устройств, работающих на основе квантовой механики, принципиально отличающихся от классических компьютеров, работающих на основе классической механики.
}}
 
 
Полноценный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики.  
 
Полноценный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики.  
 
Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 ''кубит'' — квантовых аналогов битов.  
 
Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 ''кубит'' — квантовых аналогов битов.  
Используя в универсальных квантовых вентилях кутриты вместо кубитов, можно существенно снизить количество необходимых вентилей.
+
Используя в универсальных [[Квантовые_гейты | квантовых вентилях]] кутриты вместо кубитов, можно существенно снизить количество необходимых вентилей.
 
Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении.
 
Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении.
 
Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.
 
Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.
Строка 234: Строка 538:
 
==См. также==
 
==См. также==
  
* [[Функциональные схемы]]
+
* [[Определение_булевой_функции | Булевые функции]]
 
 
* [[Троичная функциональная схема]]
 
  
 
==Источники информации==
 
==Источники информации==
Строка 251: Строка 553:
  
 
* [http://arvi.livejournal.com/144849.html Жизнь сквозь решето сети — Трёхзначная логика]
 
* [http://arvi.livejournal.com/144849.html Жизнь сквозь решето сети — Трёхзначная логика]
 +
 +
* [http://traditio-ru.org/wiki/%D0%A2%D1%80%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BB%D0%BE%D0%B3%D0%B8%D0%BA%D0%B0 Традиция — Троичная логика]
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Булевы функции]]

Текущая версия на 19:21, 4 сентября 2022

Троичная или трёхзначная логика (англ. 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 , \lt , =\}[/math], — значения, которые может принимать компаратор двух объектов.

Определение:
Троичная функция (или тернарная функция) от [math]n[/math] переменных — это отображение [math]T^n[/math][math]T[/math], где [math]T = \{-, 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 \wedge b}[/math] [math]\bf{a \vee 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\ 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]\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 \wedge b}[/math] Конъюнкция
[math]\bf{a \vee 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\ 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. Свойства констант:
  2. [math]a \wedge (+) = a[/math]

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

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

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

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

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

  3. Для конъюнкции и дизъюнкции в троичной логике сохраняются коммутативный, ассоциативный и дистрибутивный законы, закон идемпотентности.
  4. Закон двойного отрицания (отрицания Лукаcевича) и тройного (циклического) отрицания:
  5. [math]\overline{\overline{a}}=a[/math]

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

  6. Буквальное определение циклического отрицания вытекает из следующих свойств:
  7. [math](-) ' = 0[/math]

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

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

  8. Имеет место быть неизменность третьего состояния ([math]0[/math]) при отрицании Лукаcевича:
  9. [math]\overline{0} = 0[/math]

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

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

  1. Закон несовместности состояний (аналог закона противоречия в двоичной логике):
  2. [math]Sa \wedge Sa'' = (-)[/math]

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

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

  3. Закон исключённого четвёртого (вместо закона исключённого третьего), он же закон полноты состояний:
  4. [math]Sa' \vee Sa \vee Sa'' = (+)[/math], или

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

  5. Трёхчленный закон Блейка-Порецкого:
  6. [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]

  7. Закон трёхчленного склеивания:
  8. [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]

  9. Закон обобщённого трёхчленного склеивания:
  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евича:
  12. [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})(\ln p - 1) \Rightarrow \ln⁡ p - 1 = 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 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении. Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.

См. также

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