Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
Симметрия означает, что для (х, y)^R выполняется (у, x)^R.)
Пример 4.10
Рассмотрим случай многозначной логики, определенной на множестве шести
элементов S={a, Ь, с, d, е, /}. Тогда отношением эквивалентности является
следующее отношение:
R = {(a, с); (с, е); (а, е); (е, а); (с, а); (а, а); (с, с); (е, е)\ (b,
d); (¦d, /); (b, /); (/, b)\ (f, d)\ (d, b); (b, b)- (d, d); (/, f)}.
5. Центральное отношение на k. |7г-Арное отношение является центральным,
тогда и только тогда, когда оно строго рефлек-
136
Часть II. Многозначная и пороговая логика
сивно, строго симметрично и его центр не является ни пустым, ни самим
множеством k. Отношение R является строго рефлексивным, если оно содержит
все h членов в (s,, s2, ..., sh) , таких, что при некоторых iV=/ две
компоненты равны, т. е. s, = s;-. (Заметим, что R может содержать много
других элементов, но оно должно включать по меньшей мере эти.) /г-Арное
отношение является строго симметричным, если для (sb s2, ..., Sh)^R
выполняется (sp(1), sp(2), sp(h))^R для каждой перестановки Р,
действующей на {1, /г}. Центр /г-арного отношения R
на k определяется как c={s|(sb s2, ..., Sh-i, s)^R и (sb s2, ... ..., Sh-
i)Заметим, что любое единичное отношение на k, не являющееся пустым и не
содержащее само k, является центральным.]
Пример 4.11
Рассмотрим случай трехуровневой логики на множестве {а, Ь, с}. Бинарное
отношение R = {(a, а), (b, Ь), (с, с), (a, b), (b, а), (а, с), (с, а)}
является центральным. Является ли оно строго рефлексивным? Да, (а, а),
(b, b), (с, c)^R. Строго симметричным? Для бинарного отношения имеется
только одна перестановка, отличная от тождественной, а именно [ 2 1 ] ¦
Непосредственно проверяется, что (a, b), (Ъ, a)^R и (а, с), (с, а)е еД. В
заключение вычислим центр. Справедливо ли оеС? Да, поскольку (а, а), (b,
а), (с, a)^R. Справедливо ли йеС? Нет, (с, Ь) не принадлежит множеству.
Справедливо ли сеС? Нет, (Ъ, с) не принадлежит множеству. Следовательно,
С={а}, которое не является ни пустым, ни k, отсюда R является
центральным.
6. Любое отношение %т, определяемое h-упорядоченным классом Т
эквивалентных отношений на k (с h>2). (Класс эквивалентных отношений Т =
{до, 01, •••, 0m-i} является /г-упорядочен-ным, если он удовлетворяет
двум условиям. Во-первых, каждое 0/ должно иметь h классов
эквивалентности (0^/^m-1). Во-вторых, оно должно представлять тот случай,
что пересечение П?о' е/, где е,е0/, не является пустым (е/ выбирают
произвольно). Отношение, определяемое Т, представляет собой отношение %т,
состоящее из всех (а0, аи ..., ап~\)^кн, обладающих тем свойством, что по
крайней мере два элемента эквивалентны по 0/ для всех Ог^/г^т-1.)
Пример 4.12
Рассмотрим случай многозначной логики, имеющей девять уровней, т. е. k =
9. Пусть й = 3 и т = 2. Согласно одной из основных теорем арифметики,
любое число а/ на множестве {0, 1, ..., 8} может быть представлено в виде
ay = ao/+3ai/ так, как показано в табл. 4.7. Для {0, 1} определим
Глава 4. Многозначная логика в оптических вычислениях
>137
0,- = {a;- = ai по 0г, если ац - ац}
0о= {(0,3,6), (1,4,7), (2,5,8)}, 0, = |{(О, 1,2), (3,5,4), (6, 7,8)}, Т=
{0о, 0|}, Кт является отношением на 9X9X9, так что два элемента должны
быть эквивалентными по 0О и два элемента должны быть эквивалентными по 0ь
Список Хт весьма длинен, и здесь будет представлено только несколько
примеров. (0, 6, 7), (8, 6, 5), (6, 8, 0) и (6, 3, 7) принадлежат Хт, в
то время как (0, 1, 2), (0, 3, 6), (0, 4, 8) и (5, 7, 0) не принадлежат
Хт.
Следующая теорема принадлежит Розенбергу [22].
Теорема
Множество многозначных элементарных логических функций F является полным
тогда и только тогда, когда для каждого отношения, принадлежащего одному
из заданных выше шести типов, существует по крайней мере один член
множества F, который не сохраняет его.
Данная теорема указывает на то, что поиск множества логически полных
элементарных операций для совокупности оптических явлений должен быть в
наибольшей степени связан с явлениями, разрушающими алгебраические
структуры. Это находится в резком противоречии со случаем аналоговых
вычислений, в которых операции сохраняют структуру в смысле линейной
алгебры и линейных операторов. Детали конкретных видов алгебраических
структур, которые должны быть разрушены, содержатся в шести типах
отношений. Имеет ли данная теорема какой-нибудь практический смысл? И да,
и нет. Она вполне полезна, если надо показать, что конкретные множества
не являются полными. Для этого достаточно одного противоположного случая.
Теорема также полезна для выработки подхода к вопросу, какие структуры
надо разрушать.
Теорема, однако, имеет небольшое значение при определении полноты
конкретного множества. Так, для пяти уровней следует проверить более 600
отношений; для 8 уровней число отношений превышает 500 миллиардов.
(Подробное изложение данного вопроса можно найти в [22].) Часто для того,
чтобы показать, что множество функций является полным, оказывается
