31. Сети Петри. Основные понятия.

Формализм теории сетей Петри основан на понятии комплекта, явл. обобщенным понятием мн-ва, а комплект ,подобно мн-ву, явл. набором элементов, но в отличии от него допускает кратные вхождения эл-тов. В случае мн-ва эл-т может входить или не входить во мн-во, в случае комплекта – эл-т может входить в него целое неотриц. число раз . Взаимосвязь между эл-тами и мн-вом определяется ф-цией членства, принимающей значения 0 или 1.

Взаимосвязь между эл-тами и комплектом определяется ф-цией числа вхождений, обозначающейся #(x,B).

Из определения следует, что #(x,B)>=0, если х принадлежит В, то #(x,B)>0, если х не принадлежит В, то #(x,B)=0.

Комплект явл. по определению пустым, если для всякого x -> #(x,B)=0

Мощностью комплекта В наз |В| общее число вхождений эл-тов в комплект В, т.е.

|В|= СУММА по х #(x,B)

А наз подкомплектом В, если всякий эл-т А некот кол-во раз входит в В. Комплекты наз равными #(x,А)= #(x,B) для всех х. Из определения следует, что А=В тогда и только тогда, когда А явл подкомплектом В и В явл подкомплектом А. Из рав-ва А=В следует, что мощность комплектов А и В равны, а из того, что А подкомплект В – мощность А меньше или равна мощности В.

Комплект А строго включен в В, если А явл подкомплектом В, А неравно В, мощность А строго меньше В, но необязательно, что #(x,A) <#(x,B).

Сети Петри включают 4 комплекта: <P,T,I,O>, где Р={p1,p2,…pn}-мн-во позиций, n>=0; T={t1,t2,..tm}-мн-во переходов,I-входная ф-ция отображения переходов в комплекты позиций и позиций в комплекты переходов I: T->Pв степени бесконесности, P:->T в степени бесконечности; О-выходная ф-ция отображения переходов комплекта позиций и позиций в комплекты переходов O:T->Р в степени бесконечность, Р-> T в степени бесконечность.

Позиция Pi явл. входной для перехода Tj, если Pi принадлежит I(tj), и выходной, если Pi принадлежит О(tj).

Вход и выход перехода- это комплекты позиций. Кратность входной позиции Pi для перехода Tj – это число вхождений позиции во входной комплект, т.е. #(Pi, I(tj)); аналогично кратность выходной позиции Pi для перехода tj - #(Pi, O(tj)) – число вхождений позиций Pi в ф-ции выхода tj.

Граф явл двудольным тогда и только тогда, когда все его циклы имеют четкую длину, или же G(V1,V2) наз граф, мн-во вершин кот разбивается на два непересекающихся подмножества V1 и V2так, что каждое ребро в G соединяет две вершины из разных подмн-в.

Графическим представлением сети Петри C=(P,T,I,O) явл двудольный граф, мн-ва вершин кот образуют объединение Р и Т, а смежность вершин задается ф-цией I или О, причем позиции обозначаются кружками, а переходы- вертикальными палочками. Дуга соединяет позицию и переход, если позиция явл входной для перехода, и переход с позицией, если позиция чвл выходной для перехода.

Сеть Петри случае явл ориентированным двудольным мультиграфом.

32. Маркировка сети Петри, выполнение сети Петри.

Маркировка мю сети Петри C=(P,T,I,O)- это ф-ция, отображающая мн-во позиций Р в мн-ве неотриц целых N.

Маркировка присваивает каждой позиции некот, быть может, нулевое кол-во фишек. В графе фишки изображаются точками внутри позиций.

Сеть Петри с определенной маркировкой наз маркированной.

Маркировку мю можно определить как n-мерный вектор: мю=(мю1, мю2,..мюn), n=|P|; мю i принадлежит N, N- число фишек в позиции Pi, или как комплект, включающий мюi-раз в комплект Pi

Под выполнением сети Петри понимается последовательность запусков переходов, в рез-те кот удаляются фишки из входных и появляются в выходных позициях переходов.

Разрешенным наз переход, имеющий в каждой входной позиции число фишек неменее, чем число дуг, идущих из позиции в переход, т.е. такой переход tj, для кот справедливо мю (Pi)>= #(Pi,I(tj)), Pi принадлежит P

Запуск перехода удаляет все разрешающие фишки из входных позиций по одной на каждую дугу и помещает фишки в выходные позиции снова по одной на каждую дугу.

В общем случае запуск перехода заменяет маркировку мю сети Петри на новую маркировку мю со штрихом.

Запуск перехода Tj приведет к маркировке мю со штрихом, определяющейся как мю со штрихом (Pi)=мю (Pi)-#(Pi, I(tj))+#(Pi,O(tj)), либо мю со штрихом = мю-I(tj)+O(tj), если рассматривать мю, мю со штрихом, I(tj),O(tj)-как комплекты.

Состояние сети Петри определяется ее текущей маркировкой, запуск перехода вызывает смену состояния. На мн-ве все маркировок сеть Петри с n-позициями определяется ф-цией дельта. Ф-ция перехода дельта для сети Петри C=(P,T,I,O) с маркировкой определенной только для тех переходов tj принадлежащих T, для кот I(tj)<= мю, если рассматривать мю и I(tj) как комплекты. Если дельта (мю, Tj) определяется, то мю со шрихом = дельта (мю, tj)=мю-I(tj)+O(tj)

С выполнением сети Петри связаны 2 последовательности маркировки мю0, мю1 и мю2 и последовательность переходов tj0, tj1,tj2, они взаимосвязаны взаимоотношением дельта (мю k,tk)=мю k=1, k=0,1,2,…По данной последовательности переходов U(мю0) можно легко получить последовательность маркировок, но не всегда по данной послед-ти можно получить послед-ть переходов.

Можно говорить, что маркировка мю со штрихом непосредственно достижима из маркировки мю, если для некот перехода tj принадлежащего T ф-ция маркировки мю со шрихом =дельта(мю, tj).