Алгебра структур сетей Петри
3.3. Алгебра структур сетей Петри
Рассмотрим совокупность тождеств-равенств, справедливых независимо от того, каков ранг структуры СП и какие именно СП входят в структуру. Первоначально введем теоретико-множественные операции над множествами СП-структур.
Объединением множеств СП L' и L'' будем называть множество, состоящее из всех тех и только тех СП, которые принадлежат L' или принадлежат L'' и среди которых нет ни одной пары изоморфных СП.
Пересечением множеств СП L' и L'' будем называть множество, состоящее из всех тех и только тех СП, которые принадлежат как множеству L' , так и множеству L''.
Очевидно, что пересечение множеств СП выделяет класс изоморфных СП.
Разностью множеств СП L' и L'' будем называть множество, состоящее из всех тех и только тех СП, которые принадлежат L' и не принадлежат L'' .
Множества СП L' и L'' будем считать равными, если для каждой СП N' О L' существует изоморфная СП N'' О L'' и для каждой СП N'' О L'' существует изоморфная СП N' О L' .
Определение 3.6. Пусть L' и L'' - множества СП, каждое с отношением ">=". Под кардинальной суммой (L' + L'') множеств L' и L'' будем понимать множество СП, получающееся в результате объединения L' и L'' и на котором отношение ">=" сохраняет свое значение. Под кардинальной разностью (L' - L'') множеств L' и L'' будем понимать множество СП, получающееся в результате разности множеств L' и L'' и на котором отношение ">=" сохраняет свое значение.
Определение 3.7. Под кардинальным произведением множеств СП L' и L'' (L'*L'') будем понимать множество всех пар СП (N',N''), где N'ОL', N''ОL'' и (N',N'')>=(N1', N1'') означает, что N' >= N1' в L' и N'' > N1'' в L'' .
Рекомендуемые материалы
Теорема 3.3.
Для любых множеств L' , L'' и L''' следующие равенства являются тождествами:
1) L' + (L''+L''') = (L'+L'') + L''';
2) L' + L'' = L'' + L';
3) L' * L'' = L'' * L';
4) L' * (L''*L''') = (L'*L'') * L''';
5) L'*(L'' + L''') = L'*L'' + L'*L''';
6) (L' + L'')*L''' = L'*L'' + L''*L''';
7) L' - (L''+L''') = (L'-L'') - L''' .
Докажем некоторые из данных тождеств.
Доказательство тождества 5.
Справедливость тождества 5 может быть показана доказательством соотношений:
А) L'*(L''+L''') Н L'*L'' + L'*L''' и
Б) L'*L'' + L'*L''' Н L'*(L''+L''') .
Доказательство соотношения А.
Пусть СП N О L'*(L''+L'''). Тогда в силу определения кардинального произведения N=(N', N''), где N' О L' , а N'' О L'' или N'' О L'''. Если N'' О L'', то (N',N'') О L'*L'', и, cледовательно, N О L'L'' + L'L'''. Если N'' О L''', то
(N',N'') О L'L''', а следовательно, N О L'L''' + L'L''.
В итоге, если N О L'(L''+L'''), то N О L'L'' + L'L'''.
Доказательство соотношения Б.
Пусть СП N О L'L'' + L'L''. Тогда N О L'L'' либо N О L'L'''. Так как N = (N',N''), то N' О L', а N'' О L'' либо N'' О L'''. Отсюда следует, что N'' О L'' + L'''. Следовательно, пара (N',N'') принадлежит множеству L'(L'' + L''').
В итоге, если N О L'L'' + L'L''', то N О L'(L''+L''').
Доказательство тождества 7.
А. L'-(L''+L''') = (L'-L')-L'''.
Пусть СП N О L'-(L''+L'''). Из этого следует, что N О L', но N П L'' и N П L'''. Отсюда N О L = L'-L'' и N О L - L''', т.е. N О (L' - L'') - L'''.
Б. (L'-L'') - L''' L' - (L''+L''').
Пусть СП N О (L'-L'')-L'''. Из этого следует, что N О L', но
N О L''' и N О L'', т.е. N О (L''+L'''). Тогда N О L'-(L''-L'''). Однако не все тождества, где используется операция кардинальной суммы, получаются в результате применения операции кардинальной разности. Например, выражения
L'(L''-L''') = L'L'' - L'L''' (3.2)
и (L'-L'')L''' = L'L''' - L''L''' (3.3)
не являются тождествами.
Для доказательства ложности выражения (3.3) рассмотрим следующий пример.
Пусть L'={N1, N2), L''={N2 ,N3}, L'''={N1, N3}. Тогда (L'-L'')L''' = {(N1, N1),(N1, N3)}, а (L'L'''-L''L''') = {(N1,N1)}, так как СП (N1, N3) является изоморфной СП (N3,N1). Отсюда (L'-L'')L''' № (L'L'''-L''L''').
Теорема 3.4. Для любой структуры L' и полной структуры Lm следующие равенства являются тождествами:
8) L' + Lm = Lm ;
9) L' - Lm = Ж .
Доказательство данной теоремы следует из определения полной структуры.
Теорема 3.5. Следующие предложения о произвольных структурах СП L' и L'' попарно эквивалентны:
1) L' Н L'' ;
2) L' - L'' = Ж ;
3) L' + L'' = L'' ,
т.е. L' Н L'' ® L'-L'' = Ж ® L'+ L'' = L'' ® L' Н L''.
Доказательство. Докажем утверждение: если L' Н L'' , то L'- L'' = Ж (L' Н L'' ® L'- L'' = Ж ) .
Так как для любых структур СП L'- L'' Н L', то справедливо, что L'- L'' Н L''. Это возможно только при L' - L'' = Ж , так как, если кардинальная разность (L'- L'') множеств L' и L'' содержит хотя бы один элемент, то он должен одновременно:
а) не принадлежать множеству L'' (по определению кардинальной разности);
Рекомендация для Вас - Разновидности желтого тела яичников.
б) принадлежать L'' в силу предположения L' Н L'' .
Докажем утверждение: L'- L'' = Ж ® L'+ L'' = L''.
Пусть L'-L'' = Ж , тогда L'+L'' = L'- L''+ L'' (доказывается с помощью диаграмм Эйлера-Венна). Отсюда L'- L''+L'' = Ж + L'' = L'' , что и требовалось доказать.
Докажем утверждение: L' + L'' = L'' ® L' Н L''.
Пусть L' + L'' = L'' . Из данного тождества и тождества L' Н L' + L'' следует, что L' Н L'' .
Теорема доказана.