Каноническая форма представления функций троичной логики

[olegg]

Имеется 2 канонических формы: МaxMin и MinMax.

*** МaxMin

Для построения этой формы мы будем использовать следующие функции:
MAX(x,y), MIN(x,y), EQ(x,y).

EQ(x,y) определяется следующим образом:

EQ..| Y=N | Y=O | Y=P
---------------------------
X=N| ..P.. | ..N.. | ..N..
X=O| ..N.. | ..P.. | ..N..
X=P| ..N.. | ..N.. | ..P..

Определим EQP(x)=EQ(x,P), EQN(x)=EQ(x,N), EQO(x)=EQ(x,O).

Предположим, что мы имеем функцию F( x(1), x(2), , x(n) ) заданную таблично:
Значение функции f(i) = F( a(1,i), a(2,i), , a(n,i) ); для i=1, , N, где N=3^n.

Для каждого набора значений переменных ( a(1,i), a(2,i), , a(n,i) ) построим минтерм следующим образом:

MT(i) = MIN( T(x(1)), T(x(2)), , T(x(n)), f(i) );

Где T(x) определяется следующим образом:
T(x(j)) = EQP(x(j)), если a(j,i)=P
T(x(j)) = EQN(x(j)), если a(j,i)=N
T(x(j)) = EQO(x(j)), если a(j,i)=O

Тогда каноническая форма MaxMin будет иметь следующий вид:

F( x(1), x(2), , x(n) ) = MAX( MT(1), MT(2), , MT(N) )

Количество значимых минтермов в канонической форме равно количеству наборов значений параметров, на которых функция принимает значения отличные от N.

*** Пример:

..F...| Y=N | Y=O | Y=P
---------------------------
X=N| ..P.. | ..N.. | ..O..
X=O| ..N.. | ..P.. | ..N..
X=P| ..O.. | ..N.. | ..P..

Т.к. значения минтермов, соответствующих наборам значений параметров на которых функция принимает значение N всегда равны N, то мы не будем их строить. Мы построим только минтермы для наборов параметров, на которых функция не равна N.

MT(1)= MIN( EQN(x), EQN(y), P );
MT(3)= MIN( EQN(x), EQP(y), O );
MT(5)= MIN( EQO(x), EQO(y), P );
MT(7)= MIN( EQP(x), EQN(y), O );
MT(9)= MIN( EQP(x), EQP(y), P );

F(x,y) = MAX( MT(1), MT(3), MT(5), MT(7), MT(9) ) =
= MAX( MIN( EQN(x), EQN(y), P ), MIN( EQN(x), EQP(y), O ), MIN( EQO(x), EQO(y), P ),
MIN( EQP(x), EQN(y), O ), MIN( EQP(x), EQP(y), P ) )

*** MinМax

Определим

NEP(x) = EQ( EQ(x,P), N ) = NOT( EQP(x) ) = NOT( EQ(x,P) );
NEN(x) = EQ( EQ(x,N), N ) = NOT( EQN(x) ) = NOT( EQ(x,N) );
NEO(x) = EQ( EQ(x,O), N ) = NOT( EQO(x) ) = NOT( EQ(x,O) ).

Макстермы строятся следующим образом:

MT(i) = MAX( T(x(1), T(x(2)), , T(x(n)), f(i) )

Где T(x) определяется следующим образом:

T(x(j)) = NEP(x(j)), если a(j,i)=P
T(x(j)) = NEN(x(j)), если a(j,i)=N
T(x(j)) = NEO(x(j)), если a(j,i)=O

Тогда каноническая форма MinMax будет иметь следующий вид:

F( x(1), x(2), , x(n) ) = MIN( MT(1), MT(2), , MT(N) )

*** Пример:

..F...| Y=N | Y=O | Y=P
---------------------------
X=N| ..P.. | ..N.. | O
X=O| ..N.. | ..P.. | N
X=P| ..O.. | ..N.. | P

Т.к. значения макстермов, соответствующих наборам значений параметров на которых функция принимает значение P всегда равны P, то мы не будем их строить. Мы построим только мактермы для наборов параметров, на которых функция не равна P.

MT(2)= MAX( NEN(x), NEO(y), N );
MT(3)= MAX( NEN(x), NEP(y), O );
MT(4)= MAX( NEO(x), NEN(y), N );
MT(6)= MAX( NEO(x), NEP(y), N );
MT(7)= MAX( NEP(x), NEN(y), O );
MT(8)= MAX( NEP(x), NEO(y), N );

F(x,y) = MIN( MT(2), MT(3), MT(4), MT(6), MT(7), MT(8) ) =
= MIN( MAX( NEN(x), NEO(y), N ), MAX( NEN(x), NEP(y), O ), MAX( NEO(x), NEN(y), N ),
MAX( NEO(x), NEP(y), N ), MAX( NEP(x), NEN(y), O ), MAX( NEP(x), NEO(y), N ) )

*** Заключение

Любую функцию троичной логики можно построить при наличии функций MAX, MIN и EQ.

Иногда MaxMin форма может быть компактнее, чем MinMax.

Далеко не всегда каноническая форма является наиболее компактной формой представления троичных функций.

[Mac Buster]

Большое спасибо за интересный материал!

[sva]

о каких функцииях идет речь - арифметических или логических?

для логических функций отображение зависит от определения выражения X=O.
если
X=P эквивалентно "пациент жив"
X=N эквивалентно "пациент мертв"
то для X=O возможны разные варианты толкования:
1. "пациент может быть как жив так и мертв"
2. "пациент скорее жив чем мертв"
3. "пациент скорее мертв чем жив"
4. "о пациенте ничего не известно"
5. ...

и разные толкования приводят к разным таблицам истинности логических(!!!) функций.

[olegg]

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

В троичной логике в основном изучаются логические функции и поэтому речь идет о логических функциях троичной логики.

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

[sva]

2 olegg
хорошо, тогда чему равно отрицание/дополнение выражения X=P ?
не инверсия а именно дополнение (а это логическая функция)

[Shaos]

2 olegg
хорошо, тогда чему равно отрицание/дополнение выражения X=P ?
не инверсия а именно дополнение (а это логическая функция)

Как я понимаю для троичной логики (в смысле -1,0,+1) дополнение и инверсия суть одно и тоже...

[olegg]

2 olegg
хорошо, тогда чему равно отрицание/дополнение выражения X=P ?
не инверсия а именно дополнение (а это логическая функция)

Насколько я успел заметить в троичной логике большое разнообразие терминологий.
Например, arvi (http://arvi.livejournal.com/144259.html) не упоминает о дополнении совсем, хотя и претендует на полноту обзора троичной логики. Зато он упоминает 3 разных функции инверсии NOT-, NOT и NOT+.
А в WIKI (http://ru.wikipedia.org/wiki/%D0%A2%D1% ... 0%BA%D0%B0) термин дополнение применяется только к функциям и не применяется к параметрам функций.
Если взять определении функции x=p из Arvi (у него она называется операция тождества), и взять определение дополнения из WIKI, то тогда для данной функции ИНВЕРСИЯ(x=p) совпадает с ее ДОПОЛНЕНИЕ(x=p).
Если же пользоваться другими определениями, то и результат может оказаться другим.

[sva]

2 Shaos
это так только в двоичной логике
в троичной все зависит от толкования выражения (Х=О)

для примера:
пусть есть утверждение (X=P)
дополнение к нему есть ~(X=P) = U - (X=P), следовательно мы получим множество состоящее из (X=O) и (X=N)
это еще нагладнее если взять дополнение к (X=O)

поэтому вопрос толкования значения (X=O) является принципильным моментом для логических фугкций (для логических)

2 olegg
об этом я и говорю что для однозначного понимания логичеcкиx функций и исключения противоречий надо определить каким именно образом трактуется выражение (X=O)

[Shaos]

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

Если хочется пообсуждать проблемы программирования в терминах троичной логики - см. viewtopic.php?t=16

[sva]

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

логические функции неразрывно связаны с логикой суждений/высказываний и недопустимо рассматривать их отдельно.
потому что логические функции и минимаксные для поддержки арифметики - это ращные вещи.

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

а дополнение - это одна из базовых функций любой логики - поэтому я не представяю как вы собираетесь обходиться без него!

[Shaos]

и как скажите пожалуйста к примеру логические побитовые операции в любом современном микропроцессоре связаны с двоичной логикой суждений? да никак!...

[sva]

и как скажите пожалуйста к примеру логические побитовые операции в любом современном микропроцессоре связаны с двоичной логикой суждений? да никак!...

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

т.о. арифметические преобразования можно однозначно выразить через логичсекие.
в троичной логике это не совсем так - в общем случае она не обладет полнотой - простой пример дополнение утверждения Х=О.

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

[Shaos]

логические утверждения к таблицам истинности не имеют никакого отношения...

[Shaos]

Имеется 2 канонических формы: МaxMin и MinMax.

*** МaxMin

Для построения этой формы мы будем использовать следующие функции:
MAX(x,y), MIN(x,y), EQ(x,y).

EQ(x,y) определяется следующим образом:

EQ..| Y=N | Y=O | Y=P
---------------------------
X=N| ..P.. | ..N.. | ..N..
X=O| ..N.. | ..P.. | ..N..
X=P| ..N.. | ..N.. | ..P..

Определим EQP(x)=EQ(x,P), EQN(x)=EQ(x,N), EQO(x)=EQ(x,O).

Предположим, что мы имеем функцию F( x(1), x(2), , x(n) ) заданную таблично:
Значение функции f(i) = F( a(1,i), a(2,i), , a(n,i) ); для i=1, , N, где N=3^n.

Для каждого набора значений переменных ( a(1,i), a(2,i), , a(n,i) ) построим минтерм следующим образом:

MT(i) = MIN( T(x(1)), T(x(2)), , T(x(n)), f(i) );

Где T(x) определяется следующим образом:
T(x(j)) = EQP(x(j)), если a(j,i)=P
T(x(j)) = EQN(x(j)), если a(j,i)=N
T(x(j)) = EQO(x(j)), если a(j,i)=O

Тогда каноническая форма MaxMin будет иметь следующий вид:

F( x(1), x(2), , x(n) ) = MAX( MT(1), MT(2), , MT(N) )

Количество значимых минтермов в канонической форме равно количеству наборов значений параметров, на которых функция принимает значения отличные от N.

*** Пример:

..F...| Y=N | Y=O | Y=P
---------------------------
X=N| ..P.. | ..N.. | ..O..
X=O| ..N.. | ..P.. | ..N..
X=P| ..O.. | ..N.. | ..P..

Т.к. значения минтермов, соответствующих наборам значений параметров на которых функция принимает значение N всегда равны N, то мы не будем их строить. Мы построим только минтермы для наборов параметров, на которых функция не равна N.

MT(1)= MIN( EQN(x), EQN(y), P );
MT(3)= MIN( EQN(x), EQP(y), O );
MT(5)= MIN( EQO(x), EQO(y), P );
MT(7)= MIN( EQP(x), EQN(y), O );
MT(9)= MIN( EQP(x), EQP(y), P );

F(x,y) = MAX( MT(1), MT(3), MT(5), MT(7), MT(9) ) =
= MAX( MIN( EQN(x), EQN(y), P ), MIN( EQN(x), EQP(y), O ), MIN( EQO(x), EQO(y), P ),
MIN( EQP(x), EQN(y), O ), MIN( EQP(x), EQP(y), P ) )

Прикинул каково оно будет в железе - к примеру если взять первый вариант MaxMin, то получится некий аналог PAL/GAL-девайсов, но только троичных - при этом каждый троичный вход превращается в три двоичных сигнала (этакая "трёхпроводная троичность"), а именно EQP EQO EQN, которые могут быть получены таким образом:
http://www.hindawi.com/journals/vlsi/19 ... 6.abs.html
Взяв за основу PTI (функция PPN) и NTI (функция PNN), которые по сути уже являются двоичными сигналами в диапазоне -V...+V, можно получить нашу тройку EQP EQO EQP, а именно:
EQN=NTI
EQP=INV(PTI) - где INV это обычный двоичный CMOS-инвертор, запитанный от -V и +V
EQO=NOR(EQN,EQP) - где NOR это обычный двоичный CMOS-гейт NOR, запитанный от -V и +V
Далее, эти сигналы формируют вертикальные контактные линии нашей матрицы, а в качестве горизонтальных будут представлены 2 типа линий - P-линии (AND на диапазон -V...+V) и O-линии (AND на диапазон -V...0) - к ним мы и подключаем диоды в нужных местах, подтягивая P-линии к +V, а O-линии к 0 (земле) - не берём CMOS AND-гейты т.к. на O-линии может подаваться +V, что есть выше питающего напряжения (0 max). Это мы сделали MIN, далее объединяем нужные горизонтальные линии по MAX (или отдельно собрав O-линии и P-линии, можно их подключить к двоичным OR-гейтам с соответствующими диапазонами питания, однако затем их всё-равно надо будет пустить через диодный троичный MAX).

P.S. По сути это и есть то, каким способом господин Куликов на trinary.ru формировал сумматоры, полусумматоры и т.д. однако в отличие от его подхода тут предлагается иметь на входах и выходах чисто троичные (трёхуровневые) сигналы.

P.P.S. Всё равно на троичных мультиплексорах относительно небольшие схемы получаются компактнее (если считать количество ипользованных CMOS-транзисторов).

[Shaos]

Третьей "канонической" формой представления можно принять вариант, когда по умолчанию имеем O, а по AND собираем все P и все N - фактически к такой форме приводит BCT (Binary Coded Ternary - один трит передаётся двумя битами), но на входе матрицы каждый троичный вход опять же должен быть представлен тремя сигналами (теми же EQN, EQO, EQP), а на выходе - двумя (в данном случае EQN и EQP), которые могут быть преобразованы в троичный сигнал либо переданы далее как есть (в виде BCT). Однако на мультиплексорах схемы получаются компактнее (если считать кол-во CMOS-транзисторов). Например одноразрядный полный троичный сумматор на таком матричном подходе требует около 240 транзисторов, а на троичных мультиплексорах - 92. Теперь попробуем сравнить решение с одноразрядным полным двоичным сумматором, который состоит из 28 транзисторов. Чтобы получить число, равносильное одноразрядному троичному сумматору, умножим 28 на log2(3)=1.585 что нам даст 45 транзисторов. Как видим реализация на троичных мультиплексорах в 2 раза тяжелее равносильной двоичной схемы. Не говоря уже о матричном "трёхпроводном" преобразователе...