DM3
.pdf6.АÈВ; # (x, АÈВ) = max{#(x, A), #(x, B)}; 7.AÇB; #(x, AÇB) = min{#(x, A), #(x, B)}; 8.A+B; # (x, А+B) = # (x, А) +#(x, B); 9.A-B; # (x, А-B) = # (x, А) - #(x, AÇB)
Под пространством комплектов X-n понимают множество всех таких комплектов, элементы которых принадлежат Х и ни один из них не входит в комплект более n раз:
{BÎX-n}Û{xÎB xÏX; #(x,B) £ n, "xÎX}.
Мощностью комплекта В называется общее число повторений элементов в комплекте.
B |
|
= ∑ # ( x , B ), |
x X . |
|
|||
|
|
x |
|
Сетью Петри (С) называется дискретная детерминированная модель, состоящая из четырех элементов
|
|
С = (P, T, I, 0), |
где Р = {р1, р2,…, |
рn} – |
конечное множество позиций n ³ 0. |
T = {t1, t2,…, t |
m} – |
конечное множество переходов m ³ 0, PÇT = Æ. |
I : T®P∞- входная функция, отображающая множество переходов в комплекты событий.
0 : Т→P∞ - выходная функция из Т в P∞. Позиция рi является входной позицией перехода tj в том случае, если piI(tj) и выходной, если pi0(tj).
Расширенными входными и выходными функциями сетей Петри соответственно называются отображения:
|
I : P →T∞; 0 : P →T∞ |
для которых |
#(tj, I(pi)) = #(pi, 0(tj)); #(tj, 0(pi)) = #(pi, I(tj), |
Пример. Пусть структура сети Петри имеет вид: С = (P, T, I, 0); P = {p1, p2, p3, p4, p5}; T = {t1, t2, t3, t4};
I(t1) = {p1} |
0(t1) = {p2, p3, p5} |
I(t2) = {p2, p3, p5} |
0(t2) = {p5} |
I(t3) = {p3} |
0(t3) = {p4} |
I(t4) = {p4} |
0(t4) = {p2, p3} |
Расширенными входной и выходной функциями данной сети являются:
I(p1) = { } |
0(p1) = {t1} |
I(p2) = {t1, t4} |
0(p2) = {t2} |
I(p3) = {t1, t4} |
0(p3) = {t2, t3} |
I(p4) = {t3} |
0(p4) = {t4} |
I(p5) = {t1, t2} |
0(p5) = {t2} |
Проиллюстрируем пример графически.
Элементами графа служат кружки, обозначающие позиции сети, и планки, обозначающие ее переходы. Ориентированные дуги соединяют позиции и переходы в обоих направлениях.
|
P2 |
|
t1 |
t2 |
t4 |
|
|
P4 |
P1 |
P5 |
|
|
|
|
|
P3 |
t3 |
Рисунок 5.1
Граф G сети Петри – двудольный ориентированный мультиграф G = (V, A), где V = {v1, v2, … , vs} – множество вершин V = P T;
A = {a1, a2,…., a r} – комплект направленных дуг
аi = <vj, vk>, vj, vk V.
Комплект направляющих дуг А вводится следующим образом:
#((pit), A) = #(pi, I(tj)), piP, tjT; #((tj, pi), A = #(pi, 0(tj));
Сеть можно выполнить. Для выполнения сети применяют маркировку, представляющую присвоение позициям сети фишек, количество и положение которых при выполнении сети могут изменяться.
Маркировкой μ сети Петри С = (P, T, I, 0) называется функция, ото-
бражающая множество позиций р в множество натуральных чисел N: μ : P → N
Под маркировкой можно подразумевать n-вектор
μ = (μ1, μ2,…, μn), где n = |P|, μiN, i =1,n,
который определяет для каждой позиции сети Рi количество фишек (μi) в этой позиции. На графе сети Петри фишки изображаются точками в кружке соответствующей позиции, если число точек невелико, и в противном случае указывается натуральное число μi для данной позиции. Приведем пример маркировки для сети заданной рис……
|
P2 |
|
|
.. |
|
|
t4 |
|
. |
S1 |
|
P4 |
||
|
||
P1 |
P5 |
|
|
||
|
t3 |
|
|
P3 |
Рисунок 5.2 Фишки во входной позиции, допускаюзщие переход, носят название
разрешающих фишек.
Переход tiÎT в маркированной сети Петри С = (P, T, I, 0) с маркировкой m разрешен, если
mi = m(рi) ³ # (рi,I(ti)), " рi ÎP.
Пример маркировки m = (1, 2, 0, 51, 0) (рис.5.2). Переход допускается удалением всех разрешающих фишек из его входных позиций и последующим помещением в каждую из его выходных позиций по одной фишке для каждой дуги.
Запуск перехода в целом заменяет маркировку m сети Петри на новую маркировку m’.
Переход ti в маркированной сети Петри с маркировкой m может быть запущен, если он разрешен.
Маркировка m’ для разрешенного перехода ti образуется по правилу
μ’ (рi) = μ( рi) - #( рi, I(ti)) + #(рi, 0(ti)).
Рассмотрим следующий пример. Задана сеть Петри (рис.5.3). Маркировка сети μ = (1, 0, 0, 2, 1). При такой маркировке разрешены три перехода t1, t3, t4. Переход t2 не разрешен, поскольку две из трех входных позиций не содержит
|
P |
|
t1 |
|
|
t2 |
|
t4 |
. |
|
. |
P |
|
P |
|
.. |
|
|
P |
t3 |
|
|
Рисунок 5.3 ни одной фишки. Любой из разрешенных переходов может быть запу-
щен. Запустим переход t4. Фишка удалится из р5, одна фишка переместится в позицию р3 и одна – в р4. В результате сеть Петри будет выглядеть:
|
|
|
|
|
P3 |
||
|
|
t1 |
. |
|
|
||
|
|
|
|
|
|||
|
|
|
|
t2 |
|
|
t4 |
. |
|
P2 |
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
P1 |
|
|
|
|
... |
|
P5 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t3 |
|
|
|
|
|
P4 |
Рисунок 5.4
Пространство состояний сети Петри, обладающей конечным числом позиций (n), есть множество всех маркировок. Изменение в состоянии, вызванное запуском очередного перехода, осуществляется с помощью функции следующего состояния.
Функция следующего состояния d : Nn x T ® Nn для сети Петри С с маркировкой m и переходом tjÎT определена тогда, и только тогда, когда
m (pi) ³ #(pi, I(tj)), "piÎP.
В случае определения функции δ осуществляется отображение
δ(μ, tj) = μ’,
где
μ (pi) = μ (pi) - (pi, I(tj)) + (pi, 0(tj)), pi P
При выполнении сети Петри получаются две последовательности: по-
следовательность маркировок {μ0, μ1, …} |
и последовательность пере- |
ходов, которые были запущены {tjo, tj1,…}, |
связанные отношением: |
δ(μk, tjk) = μk+1, k = 0, 1, 2, …
Для сети Петри С = (P, T, I, 0) с маркировкой μ маркировка μ’ называется непосредственно достижимой из μ, если переход tj Т, такой, что δ(μ, tj) = μ’.
Множеством достижимости R(C, μ) для сети Петри с маркировкой μ называется наименьшая последовательность маркировок, таких что:
1)μ R(C, μ);
2)если μ’ R(C, μ) и μ’’ = δ(μ, tj), для tj Т, μ’’ R(C, μ).
Приведем в качестве примера следующую сеть Петри.
t1 |
t2 |
|
|
P3 |
P1 |
P2 |
Рисунок 5.5
Для этой сети с начальной маркировкой μ = (1, 0, 0). Непосредственно достижимым являются две маркировки:
μ1 = (0, 1, 0) и μ2 = (1, 0, 1)
из μ1 нельзя достичь ни одной маркировки. Из μ2 можно получить (0, 1, 1) и (1, 0, 2). Продолжая процесс можно получить (1, 0, n) и (0, 1, n), n ≤ 0.