Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
достаточным проявить небольшую изобретательность и сформировать из
элементарных функций одну универсальную.
Логическая элементарная функция f{xо, ..., xn-t) является универсальной,
если она образует функционально полное множество. В данном изложении
теорема Руссо интерпретируется согласно работам Дэвио. Однако следует
сделать несколько предварительных замечаний. Можно рассматривать пару (k,
/), где k является произвольным множеством, в качестве алгебры. Под
субалгеброй (k, /) подразумевается подмножество k' множества k, такое что
/: (k')n-*~k
Дадим определение автоморфизма. Рассмотрим однозначное
138
Часть II. Многозначная и пороговая логика
отображение ф множества А само в себя: А-^-А, Ф - автоморфизм, если
/(<p(*o), <p(*i), •••, cp(jc"-j)) = ф(/(лго, X], ..., Xn-i)). Наконец,
нам необходимо понятие конгруэнтности на (k, /). Пусть Re является
эквивалентным отношением на k. Тогда Re является конгруэнтным на (k, /),
если для любого множества {(ctj, Ь})\ (ajbj)^R для - 1} справедливо
(/(a&, ait ...
• a"-i), f(b0, bi,..., b"-t))^R.
Теперь можно сформулировать теорему:
Логическая функция / является универсальной на k тогда и только тогда,
когда:
1. Не существует соответствующей субалгебры на (k, f).
2. Не существует нетривиального автоморфизма на (k, /).
3. Не существует нетривиальной конгруэнтности на (k, /).
Две хорошо известные универсальные функции k являются
функциями Уэбба и определяются так:
1x4-1 mod k для х - ц,
W(x, У)- п J
(О, хфу,
а также S-функцня имеет вид S (х, у) = sup(x, у)1 (mod k).
Доказательства не представляют большой сложности, но в случае затруднений
следует обратиться к работе [2].
Другим аналогичным двоичному случаю является случай слабой полноты
множества элементарных логических функций. Множество элементарных
логических функций является слабо полным на k, если сложение с k
постоянными функциями делает его полным. К сожалению, проверка слабой
полноты требует ненамного меньшего объема работы, чем проверка полноты.
Из шести заданных выше классов только второй можно полностью охватить
постоянными функциями. При проверке остальных пяти классов, несомненно,
не следует учитывать унарных отношений.
На этом изложение типов функций, искомых для получения полноты
многозначной логики, завершено. Однако следует упомянуть раннюю теорему
Слупецкого [33], так как она часто дает более простые тесты, чем теорема
Розенберга. Изложение дается так, как в работе [2].
Логическая функция k переменных f{xо, ..., хп~\) является существенной
функцией тогда и только тогда, когда она явно зависит по крайней мере от
двух переменных и принимает все значения {0, 1, ..., h-1}. Теорема
Слупецкого устанавливает, что если F является множеством логических
функций и позволяет определить все унарные функции, то F является полным
тогда и только тогда, когда оно содержит по крайней мере одну
существенную функцию. Заметим, что это не требует по-
Глава 4. Многозначная логика в оптических вычислениях
139
строения унарных функций, однако в большинстве методик это было бы
принято в качестве функции памяти.
4.6. Краткое изложение и выводы
После краткого введения в вопросы полноты множеств двоичных элементарных
логических функций была рассмотрена слабая полнота систем элементов,
составленных из операций сложения и умножения по модулю р, являющемуся
простым числом, и называемых арифметикой ССОК. Было бы разумно на базе
этих компонентов непосредственно реализовать заданную переключающую
функцию, хотя алгоритмы минимизации числа элементов в системе вычислений
отсутствуют. Выполнение переключающих функций особенно привлекательно в
ССОК благодаря широкому разнообразию методов их оптической реализации.
Более того, характерной чертой почти всех оптических методов является
возможность параллельной обработки в больших оптических апертурах. Этот
факт указывает на огромные возможности параллельных вычислений для
оптической многозначной логики. В то время как существуют аналоговые
оптические методы для оптически закодированных периодических величин,
таких, как фаза и поляризация, в большинстве методик оптического
кодирования в качестве метода кодирования и управления модульными
величинами используется пространственная координатная модуляция.
Модуляция пространственного положения определяет величину динамического
диапазона в области пространственных частот. Оптические системы могут
достигать больших диапазонов пространственных частот. Можно рассматривать
оптические многозначные логические системы как с электрической, так и с
оптической адресацией. Большие достижения, полученные в последнее время в
области волоконной и интегральной оптики, а также пико- и фемтосекундной
оптики, показывают, что в ближайшем будущем могут стать жизненными
оптические Многозначные логические системы.
Последняя часть данной главы предназначена для инженеров или ученых,
хорошо разбирающихся в вопросах теории и анализирующих физическую систему
