Парадигма развития науки (стр. 13 )

- для суммы комплектов

А и В # (х, А + В) = #,(х, А) + # (х, В);

- для разности комплектов А и В

# (х, А - В) = # (х, А)- # (х, А В).

Если М - множество, то Мп — множество всех таких комплектов, построенных из элементов М, что

# (х, В) ≤ п, ВМп;

М∞ — множество всех комплектов, построен­ных из элементов М без ограничения на число экземпляров элемента в комплекте.

Сеть Петри — это четверка

С=(Р, Т, I, О),

где Р — конечное множество позиций, Т—конечное множество переходов, I: Т→Р∞ — входная функция (воздействие), отображающая переходы в комплекты позиций, О: Т→Р∞ — выходная функция (реакция), отображающая переходы в комплекты позиций. Графически сеть Петри изображают в виде мультиграфа с вершинами двух видов: кружки соот­ветствуют позициям, планки — пере­ходам. Функции I и О пред­ставляются дугами (рис. 19.7).

Рис. 19.7.

Позиции, дуги из которых ведут в переход tj, называются вход­ными для tj, аналогично, позиции, в которые ведут дуги из перехода tj, называются выходными для tj. Мно­жество входных позиций обозначают I(tj), а выходных — O(tj). В сети Петри, изображенной на рис. 19.7, I(t1) = { р1, р1, р1}, O(t1) = {р3, р4, р4}. Функции I и О удобно обобщить и на отображение из позиций в комплекты переходов

(Р→Т∞), что позволяет обозначать множества входных и выходных переходов позиции pi, определяемые аналогично множествам входных и выходных позиций перехода, соответственно как I(pi) и О(pi). В сети Петри, изображенной на рис. 19.7, I(p3) = {t1, t2}, O(p3) = {t2, t4}.

Введенные понятия относятся к статической структуре сети Петри. Динамические свойства сети Петри определяются с помощью понятия

маркировки.

Маркировка μ сети Петри С=(Р, Т, I, О) — это функция, отображающая множество позиций Р в множество неотрицательных целых чисел N.

Маркировка изображается с помощью помещаемых внутрь позиций фишек (точек). Так, маркировка сети Петри, приве­денной на рис. 19.7, определяется как μ(p1)=μ(p3)=1, μ(p2)=μ(p4)=μ(p5)=0.

Удобно представлять маркировку как п-вектор μ =(μ1, μ2, ..., μn) (где

п =| P |), каждый элемент которого μi есть μ(pi), а также как комплект μ, в который входят позиции сети pi P и # (pi, μ) = μ (pi). Сеть Петри С с определенной в ней маркировкой μ называется маркированной сетью Петри.

Маркировка сети может изменяться в результате запуска перехо­дов. Переход tj маркированной сети Петри С с маркировкой μ называется разрешенным, если I(tj)μ, т. е. в каждой входной пози­ции tj находится не меньше фишек, чем из этой позиции исходит дуг в tj. Всякий разрешенный переход может запуститься. В резуль­тате запуска перехода tj маркировка сети μ изменяется на новую: μ'=μ—I(tj)+О(tj), т. е. из всякой входной позиции pi перехода ti удаляется столько фишек, сколько дуг ведет из pi в tj, а в каждую выходную позицию рk помещается столько фишек, сколько дуг ведет из tj в рk. Последовательность запусков переходов называется выпол­нением сети Петри.

Рассмотрим выполнение сети Петри, изображенной на рис. 19.7. В началь­ной маркировке разрешен только переход t2. При его запуске фишка удалится из р3, а затем в позиции р2 и р3 добавится по фишке, т. е. в результате запуска в новой маркировке μ' появится фишка еще и в р2. Теперь становятся разрешенными переходы t2, t4. Поскольку запуститься может любой разре­шенный переход, предположим, что запускается переход t4. После его запуска из позиции р2 и р3 фишки удалятся, а в позиции р5 появится одна фишка. В получившейся маркировке μ" не разрешен ни один переход. На этом выполнение сети Петри заканчивается.

Рассмотрим маркировку μ сети Петри С = (Р, Т, I, О). Маркировка μ' называется непосредственно достижимой из μ, если найдется такой переход tj Т, разрешенный в μ, что при его запуске получается марки­ровка μ'; в этом случае пара (μ, μ') принадлежит отношению непосред­ственной достижимости, определенному на Р∞. Транзитивное замыка­ние этого отношения называется отношением достижимости. Марки­ровки μ' такие, что (μ, μ') принадлежат отношению достижимости, называются достижимыми из μ. Множество достижимых из μ марки­ровок сети Петри С называется множеством достижимости и обозна­чается R (С, μ).

Интерпретация сетей Петри основана на понятиях условия и собы­тия.

Состояние системы научных исследований описывается совокупностью условий.

Функцио­нирование системы научных исследований состоит в осуществлении последовательности опре­деленных действий (исследовательских операций), т. е. событий.

Для возникновения события необ­ходимо выполнение некоторых условий, называемых предусловиями. Возникновение события может привести к нарушению предусловий и к выполнению некоторых других условий, называемых постусловия­ми. В сети Петри условия моделируются позициями, события — пере­ходами. Предусловия события представляются входными позициями соответствующего перехода, постусловия — выходными позициями. Воз­никновение события моделируется запуском перехода. Выполнение условий представляется наличием фишек в соответствующих позициях, невыполнение — их отсутствием.

Рассмотрим, например, простую систему научных исследований, последо­вательно обрабатывающую мсследовательские операции (задания), которые поступают во входную очередь. Когда процессор свободен и во входной очереди имеется исследовательское задание, оно обрабатывается процессором, затем выводится. Эту систе­му можно промоделировать сетью Петри, изображенной на рис. 19.8.

Рис. 19.8

Установим, какие особенности систем учитывают сети Петри. Это прежде всего асинхронность. В сети Петри отсутствует понятие вре­мени. Время возникновения событий никак не указывается, но тем не менее структура сети Петри устанавливает частичный порядок возникновения событий. Далее, поскольку возникновение событий пред­ставляется запуском переходов, предполагается, что события происхо­дят мгновенно. Если же моделируемое событие имеет отличную от нуля длительность, как, например, событие «задание обрабатывается» (рис. 19.8), и это существенно, то оно представляется в виде двух мгновенных событий типа «начало события», «конец события» и усло­вия «событие происходит» (рис. 19.9).

Рис. 19.9

Кроме того, считается, что со­бытия происходят неодновременно (мгновенные события не могут про­исходить одновременно). Действительно, если допустить одновремен­ное возникновение некоторых событий i и j, которым в сети Петри соответствуют переходы ti и tj, то можно ввести дополнительный переход tij с

I(tij)=I(ti)+I(tj),

О(tij)=О(ti)+О(tj),

интерпретирую­щийся как одновременное возникновение событий i и j. В этом случае переходы можно запускать последовательно.

Другим важным свойством сетей Петри, как инструмента модели­рования систем научных исследований, является их способность представлять параллелизм и конфликт­ные ситуации.

Параллелизм двух событий представляется двумя разре­шенными переходами, множества входных позиций которых не пере­секаются (рис. 19.10), конфликт — переходами с общей входной позицией (рис. 19.11).