Структура сети Петри

Введение в теорию комплектов.

Сети Петри - инструмент исследования систем. Сети Петри делают возможным моделирование системы математическим представлением ее в виде сети Петри. Математическим аппаратом сетей Петри является теория комплектов. Теория комплектов представляет собой естественное расширение теории множеств. Как и множество, комплект является набором элементов из некоторой области. Однако в отличие от множества комплекты допускают наличие нескольких экземпляров одного и того же элемента. В отличие от множества, где элемент либо является элементом множества, либо нет, в комплект элемент может входить заданное число раз. Пусть область представляет собой {a,b,c,d}, тогда комплекты над этой областью будут иметь вид:

B1={a,b,c} B2={a} B3={a,b,c,c}

B4={a,a,a} B5={b,c,b,c} B6={c,c,b,b}

B7={a,a,a,a,a,a,b,b,b,b,b,c,d,d,d,d,d}

Основным понятием теории комплектов является функция числа экземпляров. Обозначение #(x,B) число х в В т.е. число экземпляров элемента х в В. Если ограничить число элементов в комплекте так, что 0 <= #(x,B) <= 1, то получим теорию множеств.

Элемент х является членом комплекта В, если #(x,B) > 0. Аналогично, если #(x,B) = 0 то х не принадлежит В.

Определим пустой комплект 0, не имеющий членов (для всех х: #(x,0) = 0). Под мощностью |В| комплекта В понимается общее число экземпляров в комплекте |B| = Sx #(x,B).

Комплект А является подкомплектом комплекта В (обозначается АÍВ), если каждый элемент А является элементом В по крайней мере не больше число раз, т.е. АÍВ тогда и только тогда, когда #(x,A) <= #(x,B) для всех х.

Два комплекта равны (А = В), если #(x,A) = #(x,B).

Комплект А строго включен в комплект В (АÍВ), если АÍВ и А не равно В. Над комплектами определены 4 операции. Операции для двух комплектов А и В:

1 объединение АÈВ: #(x,AÈB) = max (#(x,A),#(x,B));

2 пересечение А ÇВ: #(x,A ÇB) = min (#(x,A),#(x,B));

3 сумма А + В: #(x,A + B) = #(x,A)+#(x,B);

4 разность А - В: #(x,A - B) = #(x,A) - #(x,B);

Назовем множество элементов, из которых составляются комплекты, областью D. Пространство комплектов Dⁿ есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого В Î Dn:

а) из х Î В следует х Î D;

б) для любого х #(x,B) <= n.

Множество D^¥ есть множество всех комплектов над областью D, без какого либо ограничения на число экземпляров элемента в комплекте.

Сеть Петри состоит из 4 компонентов, которые и определяют ее структуру:

- множество позиций Р,

- множество переходов Т,

- входная функция I,

- выходная функция О.

Входная и выходная функции связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j), называемых входными позициями перехода. Выходная функция О отображает переход t_j в множество позиций О(t_j), называемых выходными позициями перехода. Т.е.

(I: T -> P¥)

(O: T -> P¥).

Определение 1. Сеть Петри С является четверкой С = (P,T,I,O) где

Р={p1,p2,...,pn} конечное множество позиций, n>=0.

T={t1,t2,...,tm} конечное множество переходов, m>=0.

Множества позиций и переходов не пересекаются.

I: T -> P¥ является входной функцией -

отображением из переходов в комплекты позиций.

O: T -> P¥ выходная функция - отображение из переходов в комплекты позиций.

Мощность множества Р есть число n, а мощность множества Т есть число m. Произвольный элемент Р обозначается символом p_i, i=1...n; а произвольный элемент Т - символом t_j, j=1...m.

рис. 1

Позиция p_i является входной позицией перехода t_j, в том случае, если p_i Î I(t_j);

p_i является выходной позицией перехода, если pi Î O(tj).

рис. 2

Входы и выходы переходов представляют комплекты позиций. Кратность входной позиции для перехода t_j есть число появлений позиции во входном комплекте перехода #(p_i,I(t_j)). Аналогично, кратность выходной позиции p_i для перехода t_j есть число появлений позиции в выходном комплекте перехода #(p_i,O(t_j)).

Определим, что переход t_j является входом позиции p_i, если p_i есть выход t_j (рис. 2). Переход t_j есть выход позиции p_i, если p_i есть вход t_j (рис. 1).

Определение 2. Определим расширенную входную функцию I и выходную функцию О таким образом, что #(t_j,I(p_i)) = #(p_i,O(t_j)); #(t_j,O(p_i)) = #(p_i,I(t_j));

Дата добавления: 2014-01-20