DM3

6.АÈВ; # (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.