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

Anika, 03.05.2004 21:27:26 :

Монтажное "И" без ОК - это нарушение всех правил

 

Ну, в общем, да. Вот, на Схемотехника прямо говорят, что транзисторы не рассчитаны на постоянный сквозной ток через ограничивающий резистор, но, с другой стороны, я это не экспериментально открыл, а вычитал лет 15 назад в какой-то из своих тогдашних книжек по цифровым схемам. Точных цифр уже не помню, сколько "единиц" держит один "ноль" для 155-й серии, но факт, что схемы с таким объединением были.

Хотя, как я отмечал выше, если микросхемы не имели Z-состояния на выходе, я предпочитал подключение к шине через диодную логику

Balancer>Затем, что бинарную логику всё равно придётся использовать даже на тринарном железе И лучше будет, если она будет не эмулироваться, а работать как есть. Т.е. принимаем два из трёх значений за "0" и "1" и все операции для этих величин соответствуют аналогичным бинарным.

ну, предположим, этого потребовать можно.

а дальше зависит от семантики третьего значения.

это может быть null как неопределённость.
0*null=null (это and a-la жигалкин)
1*null=null
null*null=null
0+null=null (это xor a-la жигалкин)
1+null=null
null+null=null
0 or null=null
1 or null=1
null or null=null
not null=null
и так далее

но если это будет не null, а 2, то логика сильно поменяется.
там где было
1+null=null ( (1+null) mod 2 = null )
станет 1+2=0 ( (1+2) mod 3 = 0 )

но если интерпретация операции "сложение по модулю два" была другая - "исключающее или", то
0 xor 2 = уже вовсе нетривиальна.

или опять же xor имеет третью интерпретацию - "не эквивалентно" с булевым (двоичным) выхлопом.
0 neqv 0 = 0
0 neqv 1 = 1
0 neqv 2 = 1
1 neqv 0 = 1
1 neqv 1 = 0
1 neqv 2 = 1
2 neqv 0 = 1
2 neqv 1 = 1
2 neqv 2 = 0

а может быть
0 neqv null = null
1 neqv null = null
null neqv null = null - здесь видна разница результата операции с третьим значеним операндов (по сравнению с выше указанным 2 neqv 2 = 0).

так что построение троичной логики произвольно зависит от интерпретации интуитивно понятных базовых двоичных операций, а так же от семантики третьего вводимого символа алфавита, будь это
{0, 1, 2} в целочисленной трактовке
{false, true, null} в логической
{-1, 0, 1} в натуральной численной
{<, =, >} в весовой (так фортрановский IF работает)
и так далее.

так вы, как я понял, рассматриваете двоичную арифметику и говорите о логичном переходе на троичную. совершенно согласен.
если мы конечно в какой-то момент согласимся, что двоичная логика это двоичная арифметика.

надо только предварительно договориться, что двоичная логика рассматривается с точки зрения жигалкина , то есть как арифметика с * и + по модулю 2 (ну и другие расширенные операции), после чего мы очень естественно переходим на троичную арифметику.

значит оператор A xor B мы на тернарную логику не распространяем (боимся ).
мы рассматриваем вместо этого оператор (A + B ) mod 2, который легко переходит в троичную систему как (A + B ) mod 3.

в принципе это то, что я говорил.

---

но двоичная логика она того... это понятие включает в себя больше, чем реализация пространства бинарных арифметических операторов на поле бинарных чисел

иногда есть смысл рассмотреть именно A xor B или A neqv B кроме A + B.
в двоичной логике эти операторы совпадают, а в троичной уже могут и не совпадать.

---

вот пример из жизни.
булева логика как она введена в реляционных базах данных.
там для любого типа данных существует значение null ("не определено" или "пусто").

по стандарту ANSI все операции, в которые аргументом входит null (кроме < и > *), должны возвращать null. будь то 13+null или true or null.
сразу же производители бросились для удобства клиента нарушать стандарт.
например от документированных и переключаемых настроек бд MS SQL Server зависит
будет ли 10 + 20 + null равно null или 30,
а так же NULL or TRUE равно TRUE или NULL.
опция называется strict ANSI NULLs.

тернарная логика на алфавите null, false, true? да. даже целых два диалекта.

а вы говорите двоичная арифметика
_________________________

• null определяется как самое маленькое значение - для сортировки.

Хм. Провоцирую тут, на свою голову...

2 Anika
Чтобы вас поправить, нужно хотя бы вас понять. Мне не везде это удалось. Для логики имеет смысл ИМХО говорить лишь об одноразрядной функции. Многоразрядные уже можно будет получать тупым распараллеливанием.

Насчет базиса не уяснил. Как я понял, в бинарной логике минимальные базисы: гейт И-НЕ, ИЛИ-НЕ. Как вы получили минимальный тернарный б-с я не понял. Как и последовавшую за этим большую таблицу.

2 AllxorBalancer
У кого-нить есть претензии к моим измышлизмам насчет тернарного XOR-а?

2 All
У меня пока придумался лишь один вменяемый троичный гейт. Он не ахти какой логический. Обзовем его Major. Механизм таков(таблицу истинности писать не буду): если из 3-х поступаемых сигналов любые 2 имеют значения + или -, то Major принимает значение + или - соответственно. Во всех остальных случаях он должен давать 0. Идея, конечно, очевидна. 'Бытовой' смысл тоже.

Буду думать дальше. Кстати, забыл про 3нарное расширение операции импликации. Расширить ее легко, но сама по себе она уродская - у нее переменные не равноценны. Пока такие операции придумывать не буду.

P.S. Наверняка это уже дааавноооооо все придумано. Но изобретать велосипед все равно интересно.

[Сергей:],04.05.2004 20:05:49

На самом деле, складывается впечатление, что "особость" бинарной логики в программировании принимается следуемой из бинарности элементарных ячеек памяти.

 

Бинарная логика родилась задолго до появления самой идеи ячеек памяти Так, для напоминания, она носит имя ещё Аристотеля А первое мне известное именование тринарной - носит имя уже только Фон Неймана

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

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

AidarM, 05.05.2004 11:02:06 :

Насчет базиса не уяснил. Как я понял, в бинарной логике минимальные базисы: гейт И-НЕ, ИЛИ-НЕ.

 

Кстати, не хватит ли для тринарной логики базиса из трёх функций?

>У кого-нить есть претензии к моим измышлизмам насчет тернарного XOR-а?

Хм. Кажется, я пропустил. (И сейчас навскидку не нашёл).

>Кстати, не хватит ли для тринарной логики базиса из трёх функций?

Я пока не знаю.

>Хм. Кажется, я пропустил. (И сейчас навскидку не нашёл).

Как? :o Я ж XOR по вашему запросу сочинял! В начале топика... 2-я страница.

XOR - 'найди отличия'.

>Таковая "особость" проистекает из того, что в программировании мы используем методы формальной логики

Тьфу, я отвечал невнимательно прочитав. Так что мой позапрошлый ответ стоит считать поспешным и частично неуместным

AidarM, если б ты освежил мысль и повторил без опечаток, то можно было бы посмотреть на твой xor
а импликация - бинарная операция "⊆" и "≤" (если утф проглючит, то читать как "<=")

AidarM, 05.05.2004 11:14:26 :

Как? :o Я ж XOR по вашему запросу сочинял! В начале топика... 2-я страница.

 

А, я думал, что во втором пришествии этой темы ты писал, так что старые сообщения и не смотрел

В целом возражений нет
Но - надо думать

Кстати, уже поднимали этот вопрос, но повторюсь, что не менее важно определить и правильный NOT

2 -exec-
А самый первый вариант без опечаток. Я его из головы писал. А глюки появились уже впоследствии, когда я на бумажку переписал неаккуратно, а потом стал по бумажке опровергать то, с чего переписывал. Первоначальный вариант полностью верен.

-exec-, 05.05.2004 11:16:59 :

бинарная операция "⊆" и "≤" (если утф проглючит, то читать как "<=")

 

В Опере оба символа - ок. В IE, как всегда, проглючило. Первый - квадратик, второй - ок

а какова семнтика третьей буквы?

в двоичной вроде всё понятно.
это {0, 1}, {ложь, истина} или {отсутствие, наличие}.
причём пространства, построенные на бинарных функциях над этими тремя алфавитами, изоморфны.

вы что третьим добавлять замышляете?

Импликацию я обозначаю как IMP или => .

C Not- ом тоже все ясно.

A NotA
- +
0 0
+ -

Я там же и объяснил почему. 0 мы обозначаем как неопределенное множество. Неизвестное. Т.е. оно заведомо включает в себя пустое (-) - это единственное, что можно про него сказать. Но оно именно неконтролируемое. Неконкретное. Неопределенное принципиально.

Т.е. 0 xor 0 = 0, а не -.
Причину я также объяснял.
Вот тут 16.09.2003 10:31:31 возникала кривизна Not, если 0 - конкретное множество.

2 Cпецы по цифровым микросхемам и железу вообще.

Поясняйте свои профессиональные обозначения, плииииииз.

Первое небольшое резюмирование

На данный момент встретились три интерпритации тринарной логики:

А. "Электрическая"
логика уровней сигналов.
0, "+", "-".
Базовая логика, железо будет работать на ней, так что сбрасывать со счетов смысла нет

Б. Логика Фон Неймана
К обычным бинарным 0 и 1 вводится неопределённость (null, скажем)
Имеет смысл рассматривать как классику жанра.
Имеет недостаток в том, что null, ИМХО, не очень функционально расширяет логику.

В. Логика "арифметическая"
0/1/2 - тут всё понятно. Очень удобно для арифметических операторов.

Базис, которого, считаю, нужно придерживаться:
1. При отбрасывании одного определённого уровня должна получаться бинарная логика. (Для случая Б. это получается атоматически, для остальных - оказывает влияние на формирование операций)
2. Должны работать масочные операции, слишком часто требуется в реальной жизни. Не явялется подпунктом 1., т.к. эти операции должны корректно работать и над тринарным представлением одного из операндов. Т.е, скажем:

1. 012012012 AND
2. 000111222 =
3. 000012???

при представлении 0 и 1 как "бинарного" подмножества.

Что ещё?

2 Balancer

012012012 AND
000111222 =
000012???

Разжуйте, плз. А то я как баран перед воротами...
Мой случай - случай Б. И где она(логика) не очень функциональна - непонятно. Но любопытно. Я изобразил механизм того, как сам думаю. И мне оччень лестно, что фон Нейман думал так же. Глюки возникают в требуемом вами базисе? Если да - буду проверять и огрызаться.

Давайте считать так.
На время выведения тринарной логики как надмножества бинарной, будем считать два из трёх значений "0" и "1". Третье - придумаем потом (для разных логик это может быть "null", "-1" или "2"). Пока его обозначем просто как "N".

Тогда выходит так:

1. 01N01N01N OR
2. 000111NNN =
3. 01?11????

1. 01N01N01N AND
2. 000111NNN =
3. 00?01????

1. 01N NOT =
2. 10?

Исходя из совместимости работы с масками, выходит, что:

1. 01N01N01N OR
2. 000111NNN =
3. 01N11????

1. 01N01N01N AND
2. 000111NNN =
3. 00001N???

Из соображений элементарной симметрии:

1. 01N01N01N OR
2. 000111NNN =
3. 01N111???

также:

1. 01N01N01N XOR
2. 000111NNN =
3. 01?10????

"по маскам":

1. 01N01N01N XOR
2. 000111NNN =
3. 01N10????

Что ещё из этого можно вывести?

AidarM, 05.05.2004 11:41:52 :

2 Balancer

012012012 AND
000111222 =
000012???

Разжуйте, плз.

 

0 и 0 дают 0
1 и 0 дают 0
0 и 1 дают 0
1 и 1 дают 1

это, типа, бинарный базис

теперь пробуем расширять смысл для совместимости с масочными операциями.
x AND 0 сбрасывает состояние операнда в "0" (рассматривать результат в зависимости от "x" в этом контексте - лишняя сущность )
Т.е.
N AND 0 = 0 ("N" - "null", "-1" или "2" в зависимости от интерпретации)

Аналогично,
x OR 1 = 1 - установка трита
N OR 1 = 1

Кстати, с "неопределённой" интерпретацией это тоже совместимо
("неизвестное" ИЛИ "истина" = "истина",
"неизвестное" И "ложь" = "ложь").

Ещё, правда, возможна другая интерпретация, сразу упустил, это вариант -exec-'а - "неприменимо", "запрещено" и т.п. - вот тогда э

ИМХО, многозначная логика не должна противоречить бинарной. Иначе шизой начинает попахивать. Я имею в виду именно логику - рассуждения об абстрактных вещах, к-рые приложимы и к реальности.

Если я правильно понял смысл таблиц, то рискну ими воспользоваться, дабы кратко записать свое видение 3-логики.

01N NOT =
10N

01N01N01N OR
000111NNN =
01N111N1N

01N01N01N AND
000111NNN =
00001N0NN

01N01N01N XOR
000111NNN =
01N10NNNN

Что значит 'работа по маскам' я не понимаю.

В общем, "бинарный базис" в случае Б. будет такой:

NOT║0│1│N
═══╬═╪═╪═
   ║1│0│N

OR║0│1│N  AND║0│1│N  XOR║0│1│N
 ═╬═╪═╪═    ═╬═╪═╪═    ═╬═╪═╪═
 0║0│1│N    0║0│0│0    0║0│1│?
 ─╫─┼─┼─    ─╫─┼─┼─    ─╫─┼─┼─
 1║1│1│1    1║0│1│N    1║1│0│?
 ─╫─┼─┼─    ─╫─┼─┼─    ─╫─┼─┼─
 N║N│1│N    N║0│N│N    N║?│?│?

>это, типа, бинарный базис

Спасибо, я сообразил таки. первая строка - первый операнд, вторая - второй. Третья - результат операции, обозначаемой справа, верно? ОК.

>Не хватает уже знания матаппарата, чтобы правильнее высказаться.
Теорию множеств юзайте. Все измышлизмы, в т.ч. и в компьютерной области должны идти оттуда. ИМХО. Дж. Буль так учил. (Меня учили, что он так учил.)

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

>Хм... Чёрт, этот вариант мне всё больше нравится, хотя от железа он оторван дальше.

Ощущаете вменяемость фон Неймана(и мою)! Это железо становится странным. ИМХО, компьютерщики могут путать логику как таковую и требуемые им операции.

AidarM, 05.05.2004 12:06:21 :

ИМХО, многозначная логика не должна противоречить бинарной. Иначе шизой начинает попахивать.

 

Ну, шиза в науке не должна быть контраргументом. Вспомни Эйнштейна, Лобачевского, Римана, Гейзенберга

>Если я правильно понял смысл таблиц, то рискну ими воспользоваться, дабы кратко записать свое видение 3-логики.

Кажется, 100% совпадение с тем, что только что записал я

>Ну, шиза в науке не должна быть контраргументом. Вспомни Эйнштейна, Лобачевского, Римана, Гейзенберга

Это не та шиза. Wyvern кажется постил, что шизой обзывают разные вещи. Я говорю о наборе утверждений, к-рые противоречат друг другу. ИМХО, перечисленные вами люди таким пороком не страдали.

>Кажется, 100% совпадение с тем, что только что записал я
Дык это... А как же иначе?

Короче, пора изобретать трехвходные операции с присвоением им универсального (и 'бытового' ) логико-математического смысла.

Major - первая попытка. Пока выхожу. Вечером попробую еще чего-нибудь сваять.

пока занят работой. закидываю удочку: A OR B интерпретировать как MAX{A, B}. для двоичной логики абсолютно корректная интерпретация.