Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
входных и оптических выходных сигналов. В этом случае умножение можно
интер-
Глава 6. Многозначная пороговая логика
163
претировать как операцию в заданном интервале непрерывных значений
логических переменных. Это обстоятельство и убеждает в пользе изучения
электрооптической многозначной пороговой логики, где по сравнению со
случаем непрерывных значений переменных не стоит так остро проблема
идентификации "соседних" логических уровней. Такой подход может открыть
новые альтернативы для развития оптических вычислений.
Соответственно в разд. 6.2 излагаются теоретические основы многозначной
пороговой логики. Этот параграф завершается критическими оценками ее
преимуществ и ограничений.
В разд. 6.3 описаны мультилинейно-разделяющиеся функции и предлагается
архитектура, ориентирующаяся на реализацию с помощью электрооптических
устройств.
Глава завершается обсуждением результатов, включающим предложения по
дальнейшим исследованиям.
6.2. Многозначная пороговая логика
6.2.1. Теоретические основы
Исследования многозначной пороговой логики возникли в начальный период
исследований пороговой логики. За важной работой [7] по описанию свойств
пороговых (двоичных) функций последовали пионерские работы [8, 9] по
троичной пороговой логике. На протяжении последующего десятилетия
основное внимание исследователей привлекла именно троичная пороговая
логика, что определялось, вероятно, появлением возможности для ее
приборной реализации на основе дискретных полупроводниковых компонент. В
числе наиболее важных результатов данного периода можно упомянуть работы,
посвященные описанию свойств троичных пороговых функций [10, И], подсчету
и классификации всех трехместных троичных пороговых функций [12, 13],
откуда следует, что существует 85 629 таких функций (в то время как рядом
авторов независимо указывалось на существование 471 двухместных троичных
пороговых функций), а также табличный метод реализации троичных пороговых
функций с числом переменных, достигающим трех [13, 14].
Первыми публикациями по многозначной пороговой логике (за исключением
троичной), по-видимому, являются работы [15-17]. Интересно заметить, что
в [15] набор р корней единицы был использован в качестве области
определения р-знач-ных функций, а для исследования пороговых функций
использовались методы гармонического анализа функций. Данный подход,
однако, не получил дальнейшего развития в последующей литературе. С
другой стороны, в [16] в качестве области
И*
164
Часть П. Многозначная и пороговая логика
определения р-значной функции были использованы первые р неотрицательные
корня, а также были введены понятия характеристического вектора
многозначной пороговой функции и даны необходимые и достаточные условия
того, что р-значная функция являлась пороговой функцией.
Следующее определение представляет собой упрощенный вариант материала,
изложенного в работе [17].
Определение 6.1
Пусть V={0, 1, ..., р-1}. Функция f: V11-+V является "-местной р-значной
пороговой функцией, если только существуют действительный вектор W=(wi,
w2, . ¦wn), называемый весовым вектором, и действительный вектор Т = (С,
t2, .. .,tp~i), называемый пороговым вектором, такие что
W-X^tP_1^f(X) = p-1, tP_1>W-X>tP_2^f(X) = p-2, (6.1)
tL>W-X<*-f(X) = о,
где Х=(х\, х2, ..., хп) и W-Х обозначает внутреннее произведение W и X.
Становится ясно, что, если система (6.1) имеет решение, тогда она имеет
бесконечно много решений. Большая их часть удовлетворяет более жесткой
системе неравенств со знаком ">" вместо "^".
Следует отметить, что определение не требует, чтобы функция устанавливала
фактически многооднозначное соответствие. Если / не принимает заданного
значения k в V, это только означает, что в Vй существуют X, такие что
f(X)=k, и в (6.1) выражение 4-н>W-X^th'^=>f(X) =k все еще является
формально правильным, но не имеет решений. (Функция /: А-+В устанавливает
нестрогое многооднозначное соответствие1', если для любого существует
по крайней мере одно аеЛ,
такое что / (а) =Ь.)
*> Согласно словарю по логике - Кондаков Н. Н. Логический словарь-
справочннк. - М.: Наука, 1975 - многооднозначное соответствие в строгом
смысле подразумевает, что каждому элементу А соответствует только один
элемент В, но каждому из элементов В соответствует более одного элемента
из А. Следует заметить, что в данном случае автор гл, 6 дает
интерпретацию более строгого понятия сюрьективной функции, определение
которой приведено, например, в [Кук Д., Бейз Г. Компьютерная математика:
Пер. с англ.- М.: Наука, 1990, гл, 3J. - Прим. перев.
Глава 6. Многозначная пороговая логика
165
Определение 6.2
Пусть /-1 (и) = (Д|/(Д) = и}, "eV. Тогда / является пороговой функцией,
если только существует набор "-мерных параллельных гиперплоскостей в Vn,
разделяющих /_1(1)... от 1).
Рассмотрим пример троичной пороговой функции на рис. 6.1. Введем
следующее обозначение. Если/ - пороговая функция с весовым вектором W и
пороговым вектором Т, то запишем /: (IE; Т) и назовем {W-, Т) структурой
