Warning: session_start(): open(C:\Windows\temp\sess_q01patgh72v617vnneofuqt4g7, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 15 Warning: session_commit(): open(C:\Windows\temp\sess_q01patgh72v617vnneofuqt4g7, O_RDWR) failed: No space left on device (28) in C:\www\lemma4.1php\login.php on line 36 Warning: session_commit(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (C:\Windows\temp) in C:\www\lemma4.1php\login.php on line 36 Сети Петри: модификации и расширения

Введем понятие базовой сети (сети) ЭСС.

Определение 8  Базовой сетью будем называть сеть  N=(B,E,F), где

  • B — множество  условий (B);
  • E — множество  событий (E, BE=);
  • F(B×E)(E×B)отношение  инцидентности.

Теперь рассмотрим отношение смены состояний, которое приведет нас к понятию ЭСС. Начнем с более простого случая, когда смена состояний — результат реализации некоторого события. Пусть N=(B,E,F) — сеть, cB и eE. На вопрос, когда событие e может произойти, теория ЭСС дает следующий ответ: событие e может произойти при наборе выполненных условий c, если и только если все предусловия этого события выполнены, т.е. принадлежат набору c, и ни одно его постусловие не выполнено, т.е. не принадлежит набору c. Другими словами, событие e может произойти при c, если ec и ec=. В качестве примера рассмотрим сеть, изображенную на рис. 2.1, вместе с набором c={b1,b2} ее выполненных условий (отмеченных наличием фишек). Событие e1 может произойти при c, поскольку все его предусловия выполнены при c, а постусловия — нет.

На вопрос, как выглядит результат того, что некоторое событие произошло, теория ЭСС дает следующий ответ: после того, как событие e произошло при наборе выполненных условий c, его предусловия больше не выполняются, а постусловия, наоборот, начинают выполняться, и оставшаяся часть сети остается без изменения. Как следствие результирующий набор выполненных условий c' имеет вид c'=(c\e)e. Например, в сети на рис. 2.1 после того, как событие e1 произойдет, результирующий набор выполненных условий имеет вид c'={b2,b3}.

Пусть N=(B,E,F) — сеть, cB и uE. На вопрос, когда события из множества u могут произойти параллельно, теория ЭСС дает следующий ответ: шаг u может произойти при наборе выполненных условий c, если и только если каждое событие из u может произойти индивидуально при c, не влияя на реализацию других событий из u. Требование того, что каждое событие из u не мешало бы другим событиям, формально можно записать следующим образом: e1,e2u    e1e2(e1e1)(e2e2)=. Например, в сети на рис. 2.1 при состоянии {b1,b2} шаги {e1,e4} и {e3,e4} могут произойти, тогда как множество {e1,e3} не является шагом.

При этом результат реализации шага u при наборе выполненных условий c должен быть суммой результатов реализаций индивидуальных событий из u при c. Таким образом, реализация шага u при наборе выполненных условий c приводит к результирующему набору выполненных условий c'=(c\u)u. Например, в сети на рис. 2.1 результатом реализации шага {e1,e4} является набор выполненных условий c'={b3,b5}, при котором оба события e1 и e2 могут произойти, однако множество {e1,e2} не является шагом.

Дадим формальные определения рассмотренных выше понятий.

Пусть N=(B,E,F) — сеть и uE. Тогда Ind(u)e1,e2u    e1e2(e1e1)(e2e2)=. Запись Ind(u) означает тот факт, что u представляет собой множество попарно независимых событий.

Определение 9  Пусть  N=(B,E,F)сеть, cB  и  uE. Тогда шаг  uE может произойти при c, если и только если Ind(u), uc  и  uc=. Запись  c[u>  означает тот факт, что u может произойти при c. Если  u={e}, то будем писать  c[e>  вместо  c[{e}>.

Далее P(Y) будет обозначать множество всех подмножеств множества Y. Пусть N=(B,E,F) — сеть. Тогда NP(B)×P(E)×P(B) обозначает отношение перехода, связанное с N и определяемое следующим образом:

N={(c,u,c')|c[u>Nc'=(c\u)u}.

В дальнейшем часто будем писать c[u>N вместо (c,u,c')N. Иногда мы будем опускать нижний индекс N и писать просто c[u>, если из контекста ясно, что речь идет о сети N. Как и раньше, если u={e}, то будем писать c[e> вместо c[{e}>. Рассмотрим следующий интересный факт.

Утверждение 2  Пусть  N=(B,E,F)сеть, cB  и  eE  такие, что  c[e>. Тогда  ee=.

Доказательство.  Непосредственно следует из того, что если c[e>, то ec и ec=. □

Введем понятие элементарной сетевой системы.

Определение 10  Элементарная сетевая система (ЭСС) — это четверка  N=(B,E,F,cin), где  (B,E,F) — базовая сеть и  cin — начальное состояние.

На рис. 2.1 показан пример ЭСС с начальным состоянием, отмеченным наличием фишек в соответствующих условиях.

Пусть N=(B,E,F,cin) — ЭСС. Тогда будем использовать BN (EN, FN, XN) для обозначения множества условий (событий, отношения инцидентности, элементов) ЭСС N.

Определение 11  Пусть  N=(B,E,F,cin)ЭСС. Тогда:

  • CN  обозначает множество  состояний ЭСС N и определяется как наименьшее подмножество множества  P(B), удовлетворяющее следующим условиям:
    • cinCN,
    • если  cCN , uE  и  c'B  такие, что  (c,u,c')N, то  c'CN;
  • UN  обозначает множество  шагов ЭСС N и определяется следующим образом: UN={uE|&exists;c,c'CN    (c,u,c')N};
  • Nотношение  смены состояний, определяемое как ограничение отношения  N  на множество  CN×UN×CN.

Тот факт, что шаги могут быть разбиты на подшаги, устанавливает следующая

Теорема 1  Пусть N — ЭСС и  (c,u,c')N. Пусть  {u1,u2}разбиение u. Тогда верно: &exists;c''CN    (c,u1,c'')(c'',u2,c')N.

Доказательство  непосредственно следует из определения CN.  □