Оптические вычисления - Арратуна Р.
Скачать (прямая ссылка):
упорядоченных наборов из й элементов множества k). Унарные отношения на
k, таким образом, являются просто подмножествами; широко известными
примерами бинарных отношений являются отношения порядка и отношения
эквивалентности. Множество {00, 11, 01, 10, 10, 01, 11, 00} является 4-
арным отношением и бинарным отношением на {0,1} X {0,1}, которое часто
фигурирует при проверке полноты в случае двоичных элементарных логических
функций.
Определение 4.2
Функция f(xо, Хи хп-1) сохраняет й-арное отношение R на
k тогда и только тогда, когда из
($0,1> (r)0, 2> •••) (r)0, h) ? R> Slj2> •••> ,h)?R, ...
• • • t (->71-1,1" ^71-1, 2" • • • > ->71-1, h) ^ R
следует, что V.
(/(*0,1* Slil> •••> S7l-I,i)> / ((r)0,2" (r)lj2> •••> (r)71-1,г)) ...
• • . i / (figj a" At • • • t a)) E
Глава 4. Многозначная логика в оптических вычислениях
133
Если аккуратно проследить за индексами, то можно увидеть, что определение
эквивалентно такому утверждению: если задана матрица с h строками и п
столбцами элементов k, такими, что каждый столбец является элементом R,
тогда f, определенная для каждой строки, должна дать значение столбца,
являющегося элементом R. Теперь рассмотрим случай самодвойствен-ности для
двоичных функций. (Рассмотрим многозначный случай в рамках определения
соответствующих отношений.) Положим f функцией трех переменных, как
определено в табл. 4.1 (см. разд. 4.2). Положим, что, так же как и ранее,
R будет бинарным отношением на {0,1} X {0,1} и 4-арным отношением на
{0,1}. Тогда образуем следующие матрицы.
Пример 4.6
f f f
101 1 100 0 001 0
110 1 010 0 001 0
010 0 011 1 110 1
001 0 101 1 110 1
Можно проверить, что столбец для f всегда дает элемент R, и, таким
образом, определить, что /, в самом деле, сохраняет R. Закономерно, что f
не обладает сильной полнотой. Теперь приступим к определению шести типов
отношений, представляющих интерес в случае многозначной логики.
1. Отношения порядка с минимальным и максимальным элементом. Бинарное
отношение R является отношением порядка, если оно обладает
рефлексивностью, транзитивностью и антисимметрично. Рефлексивность
означает (х, х) еR для всех хе&. Транзитивность означает, что из (х, y)^R
и (у, z)^R следует (х, z)^R для всех х, у, z^R. Антисимметричность
означает, что из (х, y)^R и (у, x)^R следует х = у.
Пример 4.7
Рассмотрим случай четырехуровневой логики на множестве s = = {а, Ь, с,
d). Тогда следующее множество /?={(хь х2)} является отношением порядка на
s:
x1 - abcdaaabbc'\
\x2 - abcdbcdcdd)'
или, более кратко, a>b>c>d.
2. Бинарные отношения вида (х, Р(х)), где Р является перестановкой k с
периодом kip, где р - длина, причем р является простым числом.
Пример 4.8
Рассмотрим случай шестиуровневой логики на множестве {а, Ь, с, d, е, [} и
перестановки
134
Часть 11. Многозначная и пороговая логика
Таблица 4.6. Коммутативная группа G, изоморфная
к Z2XZ2XZ2
Таблица 4.7. Многозначная таблица логических значений, обсуждаемая в
примере 4.12.
+ а ь с d e f g h 0 = 0+3-0
1 = 1 + 3-0
а Ь а Ь b а с d d с e f f e g h h g 2 = 2 + 3-0
с с d а b g h e f 3 = 0+3-1
d- d с b a h g f e 4= 1+3-1
е е f g h a b с d 5 = 2+3-1
f f е h g b a d с 6 = 0+3 ¦ 2
g g h e f с d a b 7= 1+3-2
h h g h e d с b a
8 = 2+3 • 2
а b с d е / b с а е / d Результатом явится х1 а b с d е /
R
х2 b с а е / d
3. Если k = pm для ряда m и р, являющихся простыми числами, тогда
определим 4-арные отношения для выражения
R = {(x1, хг, х3, +,) ^ S41 sx + s2 = s3 +s4},
где S, -f- является коммутативной группой, в которой все элементы имеют
порядок р, или р-злементарной абелевой группой. (Напомним, что группой
называется множество с определенной на элементах этого множества бинарной
операцией, такой, что она является замкнутой, содержит единичный элемент
I и для каждого элемента имеется обратный член. Коммутативная группа- это
группа, в которой ab = ba для а, b - из группы, р-Элементарная группа -
это группа, являющаяся изоморфной к ZpxZpX ... XZp, где Zp является
периодической группой порядка р.)
Пример 4.9
Рассмотрим случай многозначной логики, имеющей восемь значений из
множества {а, Ъ, с, d, е, f, g, h}, и рассмотрим коммутативную группу G,
определенную табд. 4.6. Эта группа изоморфна к Z2xZ2xZ2 и фактически была
образована из нее при естественной идентификации букв. Данная группа
образует 4-арное отношение при установленной ранее процедуре сложения;
ниже показано, как образовать это отношение.
Глава 4. Многозначная логика в оптических вычислениях
135
В отношении имеются 4 члена:
b-\-b = b-\-b с+с=с+с
h 4- h = h + h a-\-b = b-\-a a-\-b - c-\-d a -j- b = d -j- с
u -f-b - h-\-g f с -f- d = e + /
u -f- с - с -J- a
a -\-h
h -\-a
g -I- b = / -f с
Данный набор содержит все возможные Х1-\-х2 = Хг-\-Х4, заданные в табл.
4.6. Каждое уравнение порождает функцию (х\Х2х3хД четырех переменных.
4. Нетривиальные отношения эквивалентности. (Напомним, что отношения
эквивалентности есть отношения рефлексивные, симметричные и транзитивные.
