Троичная логика — различия между версиями
Romanosov (обсуждение | вклад) (→Двухместные операции) |
Romanosov (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
'''Троичная''' или '''трёхзначная логика''' (англ. ''ternary logic'') — исторически первая многозначная логика, разработанная Яном Лукасевичем в 1920 г. Является простейшим расширением двузначной логики. | '''Троичная''' или '''трёхзначная логика''' (англ. ''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>, и др. Иногда используют обозначения И, Л, Н (истина, ложь и неизвестность). | ||
| Строка 459: | Строка 458: | ||
<li>Для конъюнкции и дизъюнкции в троичной логике сохраняются '''коммутативный''', '''ассоциативный''' и '''дистрибутивный законы''', '''закон идемпотентности'''.</li> | <li>Для конъюнкции и дизъюнкции в троичной логике сохраняются '''коммутативный''', '''ассоциативный''' и '''дистрибутивный законы''', '''закон идемпотентности'''.</li> | ||
| − | <li>Закон '''двойного отрицания''' (отрицания | + | <li>Закон '''двойного отрицания''' (отрицания Лукаcевича) и '''тройного (циклического) отрицания''':</li> |
<tex>\overline{\overline{a}}=a</tex> | <tex>\overline{\overline{a}}=a</tex> | ||
| Строка 473: | Строка 472: | ||
<tex>(+) ' = (-)</tex> | <tex>(+) ' = (-)</tex> | ||
| − | <li>Имеет место быть '''неизменность третьего состояния''' ("0") при отрицании | + | <li>Имеет место быть '''неизменность третьего состояния''' ("0") при отрицании Лукаcевича:</li> |
<tex>\overline{0} = 0</tex> | <tex>\overline{0} = 0</tex> | ||
| Строка 516: | Строка 515: | ||
<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>'''Антиизотропность отрицания Лукаcевича''':</li> |
<tex>a \leqslant b \Rightarrow \overline a \geqslant \overline b</tex> | <tex>a \leqslant b \Rightarrow \overline a \geqslant \overline b</tex> | ||
Версия 20:02, 24 декабря 2014
| Определение: |
| Троичная или трёхзначная логика (англ. ternary logic) — исторически первая многозначная логика, разработанная Яном Лукасевичем в 1920 г. Является простейшим расширением двузначной логики. |
В традиционной трёхзначной логике "лжи" и "истине" соответствуют знаки и . Третьему (серединному) состоянию соответствует знак . Допустимо использование таких наборов знаков, как , , , и др. Иногда используют обозначения И, Л, Н (истина, ложь и неизвестность).
Классическими примерами состояний такой логики являются знаки , и , состояние постоянного тока (движется в одну сторону, движется в другую сторону, отсутствует) и др.
Содержание
Преимущества перед двоичной логикой
| Определение: |
| Троичная система счисления (англ. ternary numeral system)— позиционная система счисления с целочисленным основанием, равным 3. Существует в двух вариантах: несимметричная (, и др.) и симметричная (обычно или ). |
Троичная логика обладает рядом преимуществ перед двоичной. Ниже перечислены основные:
- Троичная СС позволяет вмещать больший диапазон чисел в памяти троичного компьютера, поскольку .
-
Очевидно, что троичная СС использует меньше разрядов для записи чисел, по-сравнению с двоичной СС. Например:
(для троичной СС используется несимметричный набор .
Эти два важных преимущества перед двоичной системой счисления говорят о большей экономичности троичной системы счисления.
| Определение: |
| Экономичность системы счисления (англ. radix economy) — возможность представления как можно большего количества чисел с использованием как можно меньшего общего количества знаков. |
Докажем экономичность троичной системы счисления математически.
Пусть – основание системы счисления, а – количество требуемых знаков. Для записи знаков потребуется разрядов, а количество чисел, которое при этом можно записать, будет равно .
Рассмотрим функцию .
Для того, чтобы определить максимальное значение функции, найдем ее производную:
, ближайшее число к — . Таким образом, троичная СС не только экономичнее двоичной, но и экономичнее любой другой СС.
- Троичная логика включает в себя почти все возможности двоичной логики.
- Компьютер, основанный на троичной логике, обладает большим быстродействием. Например, троичный сумматор и полусумматор в троичном компьютере при сложении тритов выполняет примерно в 1,5 раза меньше операций сложения по-сравнению с двоичным компьютером.
Проблемы реализации
Одним из барьеров, сдерживающих развитие и распространение троичной техники, является неверное представление о необычности и трудной постижимости трехзначной логики. Современная формальная логика (как традиционная, так и математическая) основана на принципе двузначности. Кроме того, электронные компоненты для построения логики, использующие более двух состояний, требуют больше материальных затрат на их производство, достаточно сложны в реализации, и потребляют больше электроэнергии, поэтому троичные компьютеры занимают очень малое место в истории. Использование двоичных компьютеров — более простых и дешёвых в реализации — практически полностью затмило применение троичных компьютеров.
Одноместные операции
По-аналогии с двоичной логикой, в троичной логике существует всего операций для аргументов. Таким образом, в троичной логике всего существует одноместных операций.
Инверсия
, и — операторы инверсии, сохраняющие состояние , и соответственно, когда оно соответствует типу оператора, или обращающие в значение, не равное исходному состоянию и не соответствующее типу оператора инверсии, то есть в оставшееся третье.
Например, если , то . Так как исходное состояние , тип инверсии , то методом исключения можно прийти к результирующему состоянию .
Все возможные варианты для данной одноместной операции приведены в таблице.
Операция выбора
, и — операторы выбора. Превращают состояние, соответствующее типу оператора в , в случае любого из остальных двух состояний переменная приобретает значение .
Модификация
и — операторы модификации, соответственно увеличение и уменьшение трита на единицу по модулю три. При переполнении трита счёт начинается заново ().
Пороговое увеличение и уменьшение
, — данные операторы работают аналогично операторам модификации лишь с тем отличием, что при переполнении трита цикл состояний не повторяется, и значение так и остаётся минимальным или максимальным.
Другие одноместные функции
- , и — функции, не зависящие от аргумента , они же вырожденные.
- Функция — тождественная и также вырожденная функция.
- Остальные функции от одной переменной образуются путём сочетания операторов выбора с операторами инверсии и модификации, поэтому они не имеют собственных названий.
Двухместные операции
Легко видеть, что всего в троичной логике существует двухместные операции. В таблице приведены самые основные и практически полезные из них.
Ниже приведены названия этих функций.
| Обозначение | Название |
|---|---|
| Дизъюнкция | |
| Конъюнкция | |
| Логическое умножение по модулю три | |
| Логическое сложение по модулю три | |
| Функция Вебба | |
| Пороговое сложение | |
| Исключающий максимум | |
| Среднее (Mean) | |
| Сравнение | |
| Сильная конъюнкция | |
| Импликация Лукасевича | |
| Конъюнкция Клини | |
| Импликация Клини | |
| Импликация Гейтинга (импликация Гёделя) | |
| Материальная импликация | |
| Функция следования Бруснецова | |
| Тождество |
Алгебраические свойства
Все нижеперечисленные законы и свойства легко доказываются путём перебора всех значений входящих в них переменных. Алгебраический подход заключается в том, чтобы определить над множеством двухместные (, ) и одноместные (, , ) операции с помощью законов, а оставшиеся свойства уже выводить из них алгебраически.
- Свойства констант:
- Для конъюнкции и дизъюнкции в троичной логике сохраняются коммутативный, ассоциативный и дистрибутивный законы, закон идемпотентности.
- Закон двойного отрицания (отрицания Лукаcевича) и тройного (циклического) отрицания:
- Буквальное определение циклического отрицания вытекает из следующих свойств:
- Имеет место быть неизменность третьего состояния ("0") при отрицании Лукаcевича:
Для законов двоичной логики, не справедливых для троичной, существуют их троичные аналоги.
- Закон несовместности состояний (аналог закона противоречия в двоичной логике):
- Закон исключённого четвёртого (вместо закона исключённого третьего), он же закон полноты состояний:
- Трёхчленный закон Блейка-Порецкого:
- Закон трёхчленного склеивания:
- Закон обобщённого трёхчленного склеивания:
- Антиизотропность отрицания Лукаcевича:
, или
, или
, или
, или
Перспективы развития
Говоря о будущем таких машин, как «Сетунь» (то есть троичных компьютеров), известный американский учёный Дональд Кнут, отмечал, что они занимают очень мало место в отрасли вычислительной техники, что объясняется массовым засильем двоичных компонентов, производимых в огромных количествах. Но, поскольку троичная логика гораздо эффектнее, а главное, эффективнее двоичной, не исключено, что в недалёком будущем к ней вернутся.
В настоящий момент, в условиях интегральной технологии и микроэлектроники привлекательность троичной техники увеличивается: сложность трехзначных вентилей теперь не так страшна, а сокращение количества соединений и уменьшение рассеиваемой мощности особенно ценны. Особо благоприятное влияние на развитие троичное логики оказало пришествие квантовых компьютеров — вычислительных устройств, работающих на основе квантовой механики, принципиально отличающихся от классических компьютеров, работающих на основе классической механики. }} Полноценный квантовый компьютер является пока гипотетическим устройством, сама возможность построения которого связана с серьёзным развитием квантовой теории в области многих частиц и сложных экспериментов; эта работа лежит на переднем крае современной физики. Канадская компания D-Wave заявила в феврале 2007 года о создании образца квантового компьютера, состоящего из 16 кубит — квантовых аналогов битов. Используя в универсальных квантовых вентилях кутриты вместо кубитов, можно существенно снизить количество необходимых вентилей. Ланьон утверждает, что компьютер, который в обычном случае использовал бы 50 традиционных квантовых вентилей, сможет обойтись всего девятью, будучи основанным на троичном представлении. Также, согласно некоторым исследованиям, использование кутритов вместо кубитов позволит упростить реализацию квантовых алгоритмов и компьютеров.
