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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники)
Строка 4: Строка 4:
 
}}
 
}}
  
В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки <tex>-</tex> и <tex>+</tex>. Третьему (серединному) состоянию соответствует знак <tex>0</tex>. Допустимо использование таких наборов знаков, как {0,1,2}, {-1,0,1}, {0,1/2,1} {N,Z,P}, {Л,Н,И} и др.
+
В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки <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>, <tex><</tex> и <tex>=</tex>, состояние постоянного тока (движется в одну сторону, движется в другую сторону, отсутствует) и др.
Строка 12: Строка 12:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Троичная система счисления''' — позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: '''несимметричная''' ({0,1,2}, {0,1/2,1} и др.) и '''симметричная''' (обычно {−,0,+} или {−1,0,1}).
+
'''Троичная система счисления''' (англ. ''Ternary numeral system'')— позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: '''несимметричная''' ({0,1,2}, {0,1/2,1} и др.) и '''симметричная''' (обычно {−,0,+} или {−1,0,1}).
 
}}
 
}}
 
Троичная логика обладает рядом преимуществ перед двоичной. Ниже перечислены основные:
 
Троичная логика обладает рядом преимуществ перед двоичной. Ниже перечислены основные:
Строка 29: Строка 29:
 
{{Определение
 
{{Определение
 
|definition =  
 
|definition =  
'''Экономичность системы счисления''' —  возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков.
+
'''Экономичность системы счисления''' (англ. ''Radix economy'') —  возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков.
 
}}
 
}}
 
</p>
 
</p>
 +
 +
Докажем экономичность троичной системы счисления математически.
 +
 +
Пусть <tex>p</tex> – основание системы счисления, а <tex>n</tex> – количество требуемых знаков. Для записи <tex>n</tex> знаков потребуется <tex>\dfrac n p</tex> разрядов, а количество чисел, которое при этом можно записать, будет равно <tex>p^{\frac n p}</tex>.
 +
 +
Рассмотрим функцию <tex>f(p)=p^{\dfrac n p}</tex>.
 +
 +
Для того, чтобы определить максимальное значение функции, найдем ее производную:
 +
 +
<tex>f'(p)=n(p^{\dfrac n {p-2}}) \ne 0 \Rightarrow 1 - \ln⁡ p = 0, \ln p = 1, p = e</tex>
 +
 +
<tex>e \approx 2,71</tex>, ближайшее число к <tex>e</tex> — <tex>3</tex>.
  
 
* Троичная логика включает в себя почти все возможности двоичной логики.
 
* Троичная логика включает в себя почти все возможности двоичной логики.
Строка 42: Строка 54:
 
Использование двоичных компьютеров — более простых и дешёвых в реализации — практически полностью затмило применение троичных компьютеров.
 
Использование двоичных компьютеров — более простых и дешёвых в реализации — практически полностью затмило применение троичных компьютеров.
  
==Перспективы развития==
 
  
Говоря о будущем таких машин, как «Сетунь» (то есть троичных компьютеров), известный американский учёный Дональд Кнут, отмечал, что они занимают очень мало место в отрасли вычислительной техники, что объясняется массовым засильем двоичных компонентов, производимых в огромных количествах. Но, поскольку троичная логика гораздо эффектнее, а главное, эффективнее двоичной, не исключено, что в недалёком будущем к ней вернутся.
 
 
В настоящий момент, в условиях интегральной технологии и микроэлектроники привлекательность троичной техники увеличивается: сложность трехзначных вентилей теперь не так страшна, а сокращение количества соединений и уменьшение рассеиваемой мощности особенно ценны. Особо благоприятное влияние на развитие троичное логики оказало пришествие квантовых компьютеров.
 
{{Определение
 
|definition =
 
'''Квантовый компьютер''' — вычислительное устройство, работающее на основе квантовой механики. Принципиально отличается от классических компьютеров, работающих на основе классической механики.
 
}}
 
Полноценный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики.
 
Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 ''кубит'' — квантовых аналогов битов.
 
Используя в универсальных квантовых вентилях кутриты вместо кубитов, можно существенно снизить количество необходимых вентилей.
 
Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении.
 
Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.
 
  
 
==Одноместные операции==
 
==Одноместные операции==
Строка 112: Строка 111:
 
</table>
 
</table>
  
==Дизъюнкция и конъюнкция==
+
==Двухместные операции==
  
 
Всего в троичной логике существует <tex>3^{3^2}=19683</tex> двухместные операции. Для реализации любой из них при использовании сколь угодного числа переменных достаточно использовать операции выбора и наиболее простые двухместные операции: '''дизъюнкция''' и '''конъюнкция'''.  
 
Всего в троичной логике существует <tex>3^{3^2}=19683</tex> двухместные операции. Для реализации любой из них при использовании сколь угодного числа переменных достаточно использовать операции выбора и наиболее простые двухместные операции: '''дизъюнкция''' и '''конъюнкция'''.  
Строка 217: Строка 216:
 
<li>'''Антиизотропность отрицания Лукашевича''':</li>
 
<li>'''Антиизотропность отрицания Лукашевича''':</li>
  
<tex>a \leq b \Rightarrow \overline a \geq \overline b</tex>
+
<tex>a \leqslant b \Rightarrow \overline a \geqslant \overline b</tex>
  
 
</ol>
 
</ol>
 +
 +
==Перспективы развития==
 +
 +
Говоря о будущем таких машин, как «Сетунь» (то есть троичных компьютеров), известный американский учёный Дональд Кнут, отмечал, что они занимают очень мало место в отрасли вычислительной техники, что объясняется массовым засильем двоичных компонентов, производимых в огромных количествах. Но, поскольку троичная логика гораздо эффектнее, а главное, эффективнее двоичной, не исключено, что в недалёком будущем к ней вернутся.
 +
 +
В настоящий момент, в условиях интегральной технологии и микроэлектроники привлекательность троичной техники увеличивается: сложность трехзначных вентилей теперь не так страшна, а сокращение количества соединений и уменьшение рассеиваемой мощности особенно ценны. Особо благоприятное влияние на развитие троичное логики оказало пришествие квантовых компьютеров — вычислительных устройств, работающих на основе квантовой механики, принципиально отличающихся от классических компьютеров, работающих на основе классической механики.
 +
}}
 +
Полноценный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики.
 +
Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 ''кубит'' — квантовых аналогов битов.
 +
Используя в универсальных квантовых вентилях кутриты вместо кубитов, можно существенно снизить количество необходимых вентилей.
 +
Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении.
 +
Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.
  
 
==См. также==
 
==См. также==
 +
 +
* [[Функциональные схемы]]
  
 
* [[Троичная функциональная схема]]
 
* [[Троичная функциональная схема]]
Строка 227: Строка 240:
 
==Источники информации==
 
==Источники информации==
  
* [http://www.computer-museum.ru/histussr/12-1.htm Заметки о троичной цифровой технике - часть 1]
+
* [http://www.computer-museum.ru/histussr/12-1.htm Заметки о троичной цифровой технике часть 1]
  
* [http://unidevices.blogspot.ru/2011/11/blog-post.html «Сетунь» - единственный серийный троичный компьютер]
+
* [http://unidevices.blogspot.ru/2011/11/blog-post.html «Сетунь» единственный серийный троичный компьютер]
  
 
* [https://ru.wikipedia.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 Википедия — Троичная логика]
 
* [https://ru.wikipedia.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 Википедия — Троичная логика]

Версия 23:13, 17 декабря 2014

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


В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки [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], состояние постоянного тока (движется в одну сторону, движется в другую сторону, отсутствует) и др.

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

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

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

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

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

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

(для троичной СС используется несимметричный набор {0,1,2}.

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

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

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

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

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

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

[math]f'(p)=n(p^{\dfrac 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 раза меньше операций сложения по-сравнению с двоичным компьютером.

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

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


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

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

[math]NOT^-[/math],[math]NOT[/math] и [math]NOT^+[/math] — операторы инверсии. [math]NOT^-[/math] и [math]NOT^+[/math] сохраняют состояние [math]-[/math] и [math]+[/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]-00
[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]00-
[math]f_{13}[/math]000[math]0[/math]
[math]f_{14}[/math]00+[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]+00[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]00+
[math]+[/math]+++

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

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

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

  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. Закон двойного отрицания (отрицания Лукашевича) и тройного (циклического) отрицания:
  5. [math]\overline{\overline{a}}=a[/math]

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

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

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

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

  8. Имеет место быть неизменность третьего состояния ("0") при отрицании Лукашевича:
  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. Антиизотропность отрицания Лукашевича:
  12. [math]a \leqslant b \Rightarrow \overline a \geqslant \overline b[/math]

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

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

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

См. также

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