Ways of implementing ternary logic functions

Giniyatullin Vakhit Mansurovich PhD in Technical Science Associate Professor of the Department of Computer Science and Engineering Cybernetics at the Ufa State Oil Technical University 450062, Rossiya, Ufa, ul. Kosmonavtov, d. 1 fentazer@mail.ru Other publications by this author     Arslanov Ismagil Ganievich Doctor of Technical Science Professor of the Department of Computer Science and Engineering Cybernetics at the Ufa State Oil Technical University 450062, Rossiya, Ufa, ul. Kosmonavtov, d. 1 tnsfloat@mail.ru Other publications by this author     Bogdanova Polina Dinarovna undergraduate student, Ufa State Oil Technical University 450062, Rossiya, Ufa, ul. Kosmonavtov, d. 1 tnsfloat@mail.ru Other publications by this author     Gabitov Rustam Nailovich Assistant of the Department of Computer Science and Engineering Cybernetics at the Ufa State Oil Technical University 450062, Russia, Ufa, ul. Kosmonavtov, d. 1 tnsfloat@mail.ru Other publications by this author

Salikhova Marina Akhatovna Senior Lecturer of the Department of Computer Science and Engineering Cybernetics at the Ufa State Oil Technical University 450062, Russia, Ufa, ul. Kosmonavtov, d. 1 tnsfloat@mail.ru Other publications by this author

Возможность использования троичной логики в научной литературе дискутируется уже достаточно давно. Применительно к реляционной теории баз данных встречаются прямо противоположные мнения. В работе ^[1] обсуждаются троичные модификации существующих операторов «…мы вводим операцию MAYBE THETA JOIN (тета-соединение "может быть"…)». В книге ^[2] утверждается, что этого делать нельзя «…по нашему мнению, null-значения – и целая теория трехзначной логики, на которой они базируются, – являются фундаментальным заблуждением и не должны иметь места в чистой формальной системе, такой какой подразумевается реляционная модель».

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

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

Рисунок 1 – Трехмерный аналог XOR

На рисунке 1 значение ИСТИНА логической функции обозначается квадратными маркерами, ЛОЖЬ – круглыми. Значение ИСТИНА аргументов x_i кодируется числом +1, ЛОЖЬ кодируется числом -1 (биполярная система координат). Буквами α, β, γ обозначаются разделяющие плоскости.

Приведенное расположение разделяющих плоскостей может быть и несколько иным, но в любом случае, можно выписать следующие нормальные формы дизъюнктивную и конъюнктивную (ДНФ/КНФ) соответственно:

[(выше α) AND (ниже β)] OR [(выше γ)]=TRUE (1)

[(ниже α) OR (выше β)] AND [(ниже γ)]=FALSE (2)

Из уравнений разделяющих плоскостей

α: -x+y+z-1,5=0

β: x-y-z=0

γ: -x+y+z+1,5=0

составим матрицы весов персептрона скрытого слоя:

(3)

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

Формальный нейрон реализует операцию «взвешенное суммирование», которое всегда дает знаковый результат. Поэтому в качестве функции активации будем использовать пороговую функцию следующего вида:

`f_a={(+1 if x>=0),(-1 if x<0):}` (4)

Вектор весов нейрона, реализующего булеву функцию AND из (1 ) и (2):

`v_i=((1),(1),(-1)) ` (5)

Вектор весов нейрона, реализующего булеву функцию OR из (1 ) и (2):

`q_i=((1),(1),(1))` (6)

На рисунке 2 приведена структура неполносвязной искусственной нейронной сети (ИНС), реализующей трехмерный аналог функции XOR.

Рисунок 2 – Персептрон с двумя скрытыми слоями

Вектор u_i – результат скалярного умножения матрицы весов w_ij (3) на вектор входов x_i. Вектор t_i – результат применения пороговой функции активации (4) к вектору u_i. Скаляр r – результат скалярного умножения вектора весов v_i (5) на вектор t_i и знаковой функции активации. Скаляр p – результат скалярного умножения вектора весов q_i (6) на вектор, составленный из скаляра r, первого индекса вектора t₁ и смешения. Скаляр s – это выход сети, полученный из скаляра p с помощью знаковой функции активации.

Таблица 1 – Результат работы персептрона с двумя скрытыми слоями

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

С помощью алгоритма Back Propagation структуру персептрона, реализующего трехмерный XOR, можно упростить. Например, свободно распространяемая программа Multiple Back-Propagation ^[3] формирует персептрон с двумя нейронами в одном скрытом слое, и функцией активации – гиперболический тангенс. На рисунке 3 приведен снимок экрана, содержащий результаты обучения такого персептрона, а в таблице 2 приведены: матрица весов скрытого слоя W_ij и вектор весов выходного слоя V_i.

Рисунок 3 – Результат работы Multiple Back-Propagation

Таблица 2 – Матрицы весов персептрона

В таблице 3 приведена последовательность преобразований входных сигналов в полносвязном персептроне с одним скрытым слоем.

Таблица 3 – Результат работы персептрона с одним скрытым слоем и гиперболической функцией активации

Вектор u_i – результат скалярного умножения входного вектора x_i на матрицу весов скрытого слоя W_ij. Вектор t_i – результат использования гиперболической функции активации. Скаляр p – результат скалярного умножения вектора t_i на вектор весов выходного слоя V_i. Выход сети – скаляр s, есть результат использования гиперболической функции активации, округляя который до целых получаем, требуемый результат.

Заменим тангенциальную функцию активации на троичную с двумя порогами, следующего вида:

`f_a={(-1 if u_i<-0.5),(0 if -0.5>=u_i<=0.5),(+1 if u_i>0.5):}` (7)

тогда получим следующие результаты работы, приведенные в таблице 4.

Таблица 4 – Результат работы персептрона с одним скрытым слоем и пороговой функцией активации

Обращает на себя внимание тот факт, что один из нейронов скрытого слоя реализует трехмерную логическую функцию, аргументы которой двоичные, а результат троичный. Далее, применительно к таким функциям, будет использоваться термин смешанная двоично-троичная логика. Выходной нейрон реализует функцию из другой смешанной логики, её аргументы троичные, а результат двоичный. Далее, применительно к таким функциям, будет использоваться термин смешанная 3-2 логика.

Кроме того, входной вектор x_i – это все восемь вершин трехмерного куба, образующие линейно неразделимое множество, а вектор t_i – выход скрытого слоя – это четыре из девяти возможных знакомест двумерного троичного пространства, образующих разделимое множество. Таким образом, нейроны скрытого слоя преобразуют трехмерное пространство двоичных входов в двумерное троичное пространство, меньшей заселенности, а выходной нейрон преобразует троичное пространство в двоичный скаляр.

Следовательно, можно утверждать, что при упрощении структуры персептрона в целом, происходит усложнение его составных частей.

` `

В смешанных двоично-троичных логиках любой мерности есть функции, которые вырождаются в булевые, т.к. в значениях функции одновременно присутствуют только два из трех возможных значений. Например, в двумерном случае имеется функция, 45 из них вырождены, а оставшиеся 36 в качестве результата могут выдавать троичные значения. Среди них наибольший интерес представляют функции, изображенные на рисунке 4.

Рисунок 4 – XOR-подобные функции двоично-троичной логики

Внешне эти функции похожи на исключающее ИЛИ, поэтому для них используется термин «XOR-подобные». Аргументы функций бинарные и могут принимать значения ±1, значение логической функции троично, и может принимать значения -1, 0, +1, на рисунке 4 они обозначены соответственно.

Реализация таких функций в виде искусственной нейронной сети (ИНС) приводит к необходимости проводить разделяющие линии через «нулевые» вершины и использовать функции активации следующего вида:

`f_a={(-1 if <0),(0 if =0),(-1 if > 0):}` (8)

Можно утверждать, что XOR-подобные функции есть во всех двоично-троичных логиках, произвольной мерности. На рисунке 5 приведен один из возможных вариантов.

Рисунок 5 – Трехмерная XOR-подобная функция

Из геометрической интерпретации, функции изображенной на рисунке 5 следует, что n-мерные XOR-подобные функции реализуют дизъюнкции для всех трех возможных результатов. Поэтому на основе этих функций можно сформировать дизъюнктивные формы следующего вида:

if [ ( x1 = 1 ) AND ( x2 = 1 ) AND ( x3 = 1 ) OR

( x1 = 1 ) AND ( x2 = 1 ) AND ( x3 = -1 )] = TRUE

else if [( x1 =-1 ) AND ( x2 = -1 ) AND ( x3 = -1 ) OR (9)

( x1 =-1 ) AND ( x2 = -1 ) AND ( x3 = 1 )] = FALSE

else = ZERO.

В работе ^[4] дается подробное описание паракомплексных нейронов, которые единообразно реализуют все `(2^3)^2=2^9=512` функций двумерной 3-2 логики.

В дизъюнктивной форме (9) в круглых скобках используются функции одномерной 3-2 логики, всего их существует `(2^3)^1=2^3=8` штук. Аргумент этих функций троичен и может принимать значения -1, 0, +1, а результат бинарен. На рисунке 6 значение функции FALSE обозначено символом ○, а значение функции TRUE символом `darr` .

Рисунок 6 – Функции одномерной 3-2 логики

Первая и последняя функции «тождественная ЛОЖЬ» и «тождественная ИСТИНА» не интересны, оставшиеся 6 функций:

• «эквивалентность единице»;
• «эквивалентность нулю»;
• «не равенство минусу»;
• «эквивалентность минусу»;
• «не равенство нулю»;
• «не равенство единице»,

иногда называют переходниками в двоичность ^[5].

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

Рисунок 7 – Трехмерная троичная функция

Выпишем дизъюнктивную форму для трехмерной троичной функции, изображенной на рисунке 7:

if [ ( x1 = 1 ) AND ( x2 =-1 ) AND ( x3= 0 ) OR

( x1 = 1 ) AND ( x2 = 1 ) AND ( x3= 0 ) OR

( x1 = 1 ) AND ( x2 = 1 ) AND ( x3= 1 ) OR

( x1 = 0 ) AND ( x2 = 1 ) AND ( x3= 1 )] = TRUE

else if [(x1 = 1) AND ( x2 =-1 ) AND ( x3= 1 ) OR

( x1 = 1 ) AND ( x2 = 0 ) AND ( x3= 1 ) OR

( x1 = 1 ) AND ( x2 = 1 ) AND ( x3=-1 ) OR

( x1 = 0 ) AND ( x2 =-1 ) AND ( x3= 0 ) OR

( x1 = 0 ) AND ( x2 = 0 ) AND ( x3= 1 ) OR

( x1 = 0 ) AND ( x2 = 1 ) AND ( x3=-1 ) OR

( x1 = 0 ) AND ( x2 = 1 ) AND ( x3= 0 ) OR

( x1 =-1 ) AND ( x2 =-1 ) AND ( x3= 0 ) OR

( x1 =-1 ) AND ( x2 =-1 ) AND ( x3= 1 ) OR

( x1 =-1 ) AND ( x2 = 0 ) AND ( x3= 1 ) OR

( x1 =-1 ) AND ( x2 = 1 ) AND ( x3= 0 ) ] = FALSE

else = ZERO.

Конструкция if […] else if […] else эквивалентна двумерной функции двоично-троичной логики (рисунок 4), булевы функции OR в конце строк имеют размерность 4 для ветки TRUE и 11 для ветки FALSE, булевы функции AND между круглых скобок имеют размерность 3 для всех строк. На рисунке 8 приведена нейронная сеть, реализующая эту дизъюнктивную форму.

Рисунок 8 – Реализация дизъюнктивной формы нейронной сетью

Первый слой нейронов реализует одномерные функции 3-2 логики, он преобразует троичные входы в бинарный вектор. Затем следует два слоя нейронов, реализующих многомерные двоичные функции. Верхние четыре AND и следующий за ними OR («зеленые») обрабатывают положительный сигнал (TRUE) и отсутствие сигнала (ZERO), нижние одиннадцать AND и следующий за ними OR («красные») обрабатывают отрицательный сигнал (FALSE) и отсутствие сигнала (ZERO). Выходной нейрон реализует двоично–троичную функцию, он формирует выходной троичный сигнал.

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

Персептроны с одним скрытым слоем, также могут реализовывать функции троичной логики. С помощью программы Multiple Back-Propagation обучим персептрон, для троичной функции (рисунок 7). Он содержит три нейрона в скрытом слое и гиперболические функции активации, все нейроны и выходного и скрытого слоя реализуют трехмерные троичные линейно разделимые функции. В таблице 5 приведены матрицы весов обученного персептрона.

Таблица 5 – Матрицы весов персептрона для троичной функции.

В таблице 6 приведена последовательность преобразований троичных входных сигналов. Результат гиперболической функции активации в столбцах t_i и s округлены до целых.

Таблица 6 – Результат работы персептрона для троичной функции

На рисунках 9, 10, 11 и 12 приведены геометрические интерпретации троичных функций, которые реализуют нейроны скрытого и выходного слоев.

Рисунок 9 – Разделяющая плоскость и результат работы 1-го нейрона

Рисунок 10 – Разделяющая плоскость и результат работы 2-го нейрона

Рисунок 11 – Разделяющая плоскость и результат работы 3-го нейрона

Рисунок 12 – Разделяющая плоскость и результат работы выходного нейрона

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

Результатом операции «взвешенное суммирование» – является мера близости точки n–мерного пространства к разделяющей гиперплоскости. Следовательно, вводя функции активации с m порогами можно реализовывать функции (m+1)значной логики. Например, если для аппроксимации некоторой непрерывной функции удалось обучить персептрон, то результат его работы будет дискретным. Его единственный выходной нейрон реализует одну гиперплоскость, а функция активации многозначную логику, значность логики определяется погрешностью процедуры обучения. Другими словами проводиться множество параллельных разделяющих гиперплоскостей.

Для реализации произвольных n–мерных функций троичной логики можно использовать дизъюнктивные формы вида (9). Такой способ реализации эквивалентен запоминанию полной таблицы истинности. Термин «дизъюнктивная форма» используется по аналогии с двоичной логикой. Методам построения троичных дизъюнктивных нормальных форм, троичных совершенных дизъюнктивных нормальных форм, троичных минимальных дизъюнктивных нормальных форм будут посвящены следующие работы.

В работе показано, что:

1. минимизация количества нейронов в скрытом слое персептрона, в неявном виде, приводит к использованию многозначных логик;
2. некоторые функции двоично – троичной логики можно использовать для формирования дизъюнктивных форм;
3. существует взаимно однозначный способ преобразования ДНФ в ИНС и обратно;
4. в одномерной 3 – 2 логике имеется всего 8 функций и все они перечислены;
5. предложенная структура ИНС может реализовывать любую функцию троичной логики произвольной мерности.