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

Задумался тут чисто теоретически над троичной логикой (в том виде, вкаком она на "Сетуни" была реализована).

С арифметикой всё просто. ноль остаётся нулём, а разряды становятся знаковыми. Вместо 0 и 1 двоичныйх появляются 0, +1 и -1 трочиные. Для простоты - 0/+/-. Тогда и никаких проблем с раширением знаков, и смена знака просто сменой знаков операндов делается...

А вот как быть с логикой? Поскольку троичных логик полно разных, то лучше, наверное, сперва определиться с "наиболее естественными" результатами вычислений, а потом уже под это дело подгонять одну из трёхзначных логик. Что очевидно:

Логическое умножение:

1. 0 and 0 = 0
2. 0 and + = 0
3. 0 and - = 0
4. + and + = +
5. - and - = -

А что делать с

1. + and - = ?

Логическое сложение:

1. 0 or 0 = 0
2. 0 or + = +
3. 0 or - = -
4. + or + = +
5. - or - = -

А что делать с

1. + or - = ?

Я постарался соблюсти правило not(a and b)=not(a) or not(b).

Единственный случай, когда его удаётся соблюсти, найденый мною, это такой, при котором

1. not(0) = 0
2. not(+) = -
3. not(-) = +

Т.е. просто смена знака...
Тогда

1. + and - = -
2. + or - = +

Ну и какую логику под это дело можно притянуть?
Фон-Нейман? Да/Нет/Неопределено == ± 0?

1. да and да = да
2. нет and нет = нет
3. да and нет = нет
4. да and неопр = неопр
5. нет and неопр = неопр
6. да or да = да
7. нет or нет = нет
8. да or нет = да
9. да or неопр = да
10. нет or неопр = нет
11. not да = нет
12. not нет = да
13. not неопр = неопр

Похоже?

Кстати, кто-то в курсе, почему в математике считается самой оптимальной система счисления с основанием e? Что-то связанное с максимальной информационной плотностью? Тогда выходит, что троичная система счисления - самая оптимальная из целочисленных...

Ром, а классиков, например "Искусстве программирования для ЭВМ" Кнута, почитать? У него кое-что по троичной логике есть. Тут штука простая, математика, как аксиомы определим, так и будет.

А пр число e- лучше матан подвспомнить, ну не читаь же здесь лекции по нему

Владимир Малюх, 14.09.2003 09:20:51:

Ром, а классиков, например "Искусстве программирования для ЭВМ" Кнута, почитать?

 

Я б, может, и почитал, коли б был Единственный раз когда я видел их в продаже, у меня даже близко с собой таких денег не было (кажется, баксов 100 за три тома)

У него кое-что по троичной логике есть. Тут штука простая,  математика, как аксиомы определим, так и будет.

 

Понятно

А пр число e- лучше матан подвспомнить, ну не читаь же здесь лекции по нему

 

Увы, у нас на матане такого раздела не было

Balancer, 14.09.2003 16:30:54:

Я б, может, и почитал, коли б был Единственный раз когда я видел их в продаже, у меня даже близко с собой таких денег не было (кажется, баксов 100 за три тома)

 

Дожили! Счастье!!! За покупками - (из Москвы) в Новосибирск!!!

Victor Blinov, 15.09.2003 06:40:29:

Дожили! Счастье!!! За покупками - (из Москвы) в Новосибирск!!!

 

Что, у вас свободно?
Кстати, поглядел в "Озоне" - есть. Том1 - 438руб, Том2 - 876руб, Том3 - тоже 876руб. Итого - 2190руб. $73. Подешевел. Заказ в течении 7-10 дней... Т.е. на складе у них нет.

В "компьютерном музее" есть почти всё!

[html_a href='http://www.computer-museum.ru/histussr/12-2.htm' target='_blank']http://www.computer-museum.ru/histussr/12-2.htm

Alesandro, 15.09.2003 11:27:04:

В "компьютерном музее" есть почти всё!

 

Арифметика троичная там банальная, а про логику - никакой конкретики.

Я бы своей был бы доволен, но у меня по XOR не работает классический обмен двух переменных без использования третьей... Да оно и понятно - бит "неопределённости" всё херит. Можно, конечно, для такой цели и обычное вычитание использовать, но у меня идефикс сделать логику, обратно совместимую с бинарной

Так что-то мне подсказывает, что на выходе XOR не должно быть неопределённости. Потому как результат операции - истина, когда оба операнда одинаковы, в остальных случаях - ложь.
То есть XOR(+,0) = -
XOR (0,0) = +
XOR (-,0) = -

Хех. А что в троичной системе истина, а что ложь? Я принял, что "-" - ложь, "+" - истина Ну а любая операция с неопределённостью - неопределённость:

1. XOR
2.   - 0 +
3. - - 0 +
4. 0 0 0 0
5. + + 0 -

кроме того, эта таблица получается и по стандартной формуле
a XOR b = a AND NOT(b) OR b AND NOT(a).

Кстати... Только что внимательно твоё сообщение прочёл. Ты XOR и OR перепутал XOR - это исключающее ИЛИ. В бинарной логике:

1. XOR
2.   0 1
3. 0 0 1
4. 1 1 0

Т.е. это "несовпадение" операндов.

Balancer, 15.09.2003 12:27:30:

Кстати... Только что внимательно твоё сообщение прочёл. Ты XOR и OR перепутал

 

Я перепутал,:) но не с OR, а с NXOR.

Уж с OR я перепутать никак не могу. Даже во сне.

Alesandro, 15.09.2003 12:47:34:

NXOR

 

А это кто??

А это NotXOR.

0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 1

То есть, как я и писал , единица, когда оба операнда совпадают.

[quote|Balancer, 15.09.2003 14:26:48:] Кстати, поглядел в "Озоне" - есть. Том1 - 438руб, Том2 - 876руб, Том3 - тоже 876руб. Итого - 2190руб. $73.
[/QUOTE]
Тома 2 - и 3 - 600.00 руб. Тоже, конечно, не даром, но есть. (Дня 3 назад видел, стоят на полке)

>А это NotXOR.

В доке по Бейсику, поставляемой вместе с БК0010 эта операция обзывалась EQV. А по основному вопросу - непонятно, для какой задачи разрабатывается. Если интересна логика, то почему именно троичная? А то ведь операций с таблицами истинности можно легко насочинять.

  Гы. Я в свое время тоже этой темой немного увлекался. Никакого ксора в троичной логике нет и быть не может: ксор - понятие "чисто конкретно" из двоичной логики. Попробую пояснить:
  Работа двухвходового элемента описывается матрицей. В двоичной логике - матрица 2х2, всего-то 16 вариантов. Для удобства они легко разбиваются на 4 группы: "0", "И", "ИЛИ", "КСОР", а остальные варианты получаются из них инверсией выхода или одного из входов.
  В троичной логике вариантов матрицы 3⁹=19683. Это уже на несколько групп не разобьешь... Я так и рисовал - матрицами. Помнится, из двух двухвходовых или одного трехвходового элемента получались довольно забавные триггеры, из них - регистры, счетчики...

AidarM, 15.09.2003 16:33:31:

непонятно, для какой задачи разрабатывается.

 

Я же писал - чисто теоретически. Т.е. без всякой практической подоплёки

Если интересна логика, то почему именно троичная?

 

Потому что её проще всего реализовать в железе после двоичной. Что, собственно, и реализовывалось когда-то на машинах "Сетунь" и "Сетунь-70"

А то ведь операций с таблицами истинности можно легко насочинять.

 

Чтобы без взаимных противоречий? И чтобы с возможностью практического использования? Например, битики (точнее, тритики) по маске вырезать?

Anika, 15.09.2003 16:42:36:

ксор - понятие "чисто конкретно" из двоичной логики.

 

Пояснение принято. Однако ж можно "навесить" на XOR простой "бытовой смысл" - несовпадение аргументов. Вот его-то я и реализовал в троичной логике

Balancer, 15.09.2003 16:57:40:

...с возможностью практического использования? Например, битики (точнее, тритики) по маске вырезать?

 

Тогда уж инвертировать по маске! Если подойти с этой точки зрения, и "притянуть за уши логику" то, исходя их того, что Not(-) = +, а not(0)=0, получается:

XOR (-,+) = +
XOR (-, -) = -
XOR (+,+) = -
XOR (+, -) = +
Хм. Остаётся, понять, что есть ситуация 0? Надо инвертировать или нет? Наверное, надо увести в ноль, но тогда "взаимности" операция не получится никак.

Balancer, 15.09.2003 16:02:10:

Пояснение принято. Однако ж можно "навесить" на XOR простой "бытовой смысл" - несовпадение аргументов. Вот его-то я и реализовал в троичной логике

 

А-а, вот при поисках бытового смысла и начинается философия - в чем смысл "нуля"? Варианты:
- неопределенность (неизвестность)
- нейтральность (невмешательство, Z-состояние)
- цифровой ноль (тот, что получается декрементом "плюса")
- ну и еще можно напридумывать.
Матрица ксора в каждом случае будет своя. Может быть, лучше не придумывать ярлыков с размытым смыслом?

Alesandro, 15.09.2003 17:09:18:

not(0)=0
[...]

Хм. Остаётся, понять, что есть ситуация 0? Надо инвертировать или нет?

 

Так пофиг же

но тогда "взаимности" операция не получится никак

 

Угу. XOR для полноценной обратимости должен быть с чётным числом возможных значений аргументов.

А мне непонятно, какие элементы мышления машина должна симулировать. Точнее, какой образ мыслей. С бинарной логикой - то все понятно.





Ну и посмотрите тогда таблицы истинности для тамошних логич. команд.



Есть набор всевозможных комбинаций сигналов на входе - им поставлена в соответствие нек. функция, способная принимать одно из трех значений. И где там место противоречиям?

Кстати, вот простейший (и из-за этого неполноценный - не умеет хранить 0) троичный триггер. Надеюсь, принцип работы понятен.

[quote|AidarM, 15.09.2003 17:32:36:] А мне непонятно, какие элементы мышления машина должна симулировать. Точнее, какой образ мыслей. С бинарной логикой - то все понятно.
[/QUOTE]
Ну так и трёхзначных логик полно.
Да/Нет/Неизвестно
Да/Нет/Неопределено
Да/Нет/ДаНет

Ну и посмотрите тогда таблицы истинности для  тамошних логич. команд.

 

Там только арифметика была.

Есть набор всевозможных комбинаций сигналов на входе - им поставлена в соответствие нек. функция, способная принимать одно из трех значений. И где там место противоречиям?

 

Ну, например, чтобы логические операции легко обращались друг в друга. Скажем:
A OR B = NOT(NOT(A) OR NOT(b))
A XOR B = a AND NOT(b) OR b AND NOT(a)

А на кой вообще, Рома, это надо? Так, спортинтерес?

>A OR B = NOT(NOT(A) OR NOT(b))

Неправильно.

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

Дано универсальное множество А.
Пусть + - все множество, - - пустое множество, а 0 - неполное, но и не нулевое подмножество, причем неизвестно, какие элементы А в него входят (криво-то как).

Операция AND - пересечение, OR - объединение.

Насчет XOR непонятно, т.к. лично я всегда понимал под ее смыслом не ИСКЛЮЧАЮЩЕЕ ИЛИ, а ИСКЛЮЧИТЕЛЬНО ИЛИ. Правда, это для бинарной логики. В многозначной переопределять все равно придется.

Т.е. XOR был еще и тестом на неравнозначность. В этом смысле непонятно, считать ли, например, 0 XOR 0 равным -, т.е. 0 - неопределенное, но конкретное подмножество А, равнозначное самому себе. Или же мы считаем 0 XOR 0 = 0, т.е. 0 как бы неанализируем в принципе. Лично мне последнее больше нравится, так что я буду лепить операции для второго случая. Переопределим для такого случая 0 как неопределенное множество , могущее быть как пустым, так и содержать все элементы А.

Поехали... (с) Гагарин Ю.А.
Дополним таблицу NOT записью: NOT(0) = 0.

- AND - = - ( пустые множества перекрывают друг друга в известной области)
- AND 0 = - (пустота и х.з. что обязательно имеют нечто общее)
- AND + = - (в списке всех благ есть и фигу)

0 AND 0 = 0 (черт знает, где они пересекаются, и все три нуля тут разные)
0 AND + = 0 (очевидно, что...(с) Ландау Л.Д.,Лифшиц Е.М.)

+ AND + = + (тут по старинке)

---

- OR - = - (сколько поле ни квантуй...)
- OR 0 = 0 (все равно получишь неопределенность)
- OR + = + (все, или ничего: что выбираем?)

0 OR 0 = 0 (объединение двух непонятностей... кэрроловская Алиса отдыхает)
0 OR + = + (очевидно)

+ OR + = + (На выборах президента Путина шла захватывающая борьба претендента)

---

А вот тут интереснее. Определим XOR как 'найди отличия'
- XOR - = - (сова об пень и пень об сову)
- XOR 0 = 0 (чем отличается пустое множество от неопределенного)
- XOR + = + (по традиции)

0 XOR 0 = 0 (чем отличаются неопределенные множества не определено)
0 XOR + = 0 (да и чем определенное от неопределенного тоже)

+ XOR + = - (в лоб и по лбу)