Теория вычислительных процессов Введение в теорию комплектов Преподаватель: Веретельникова Евгения Леонидовна 1
Сети Петри - инструмент исследования систем. Сети Петри делают возможным моделирование системы математическим представлением ее в виде сети Петри. Математическим аппаратом сетей Петри является теория комплектов. Теория комплектов представляет собой естественное расширение теории множеств. Как и множество, комплект является набором элементов из некоторой области. Однако в отличие от множества комплекты допускают наличие нескольких экземпляров одного и того же элемента. В отличие от множества, где элемент либо является элементом множества, либо нет, в комплект элемент может входить заданное число раз. 2
Пусть область представляет собой {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, то получим теорию множеств. 3
Элемент х является членом комплекта В, если #(x,B) > 0. Аналогично, если #(x,B) = 0 то х не принадлежит В. Определим пустой комплект 0, не имеющий членов ( для всех х : #(x,0) = 0 ). Под мощностью |В| комплекта В понимается общее число экземпляров в комплекте |B| = Sx #(x,B). Комплект А является подкомплектом комплекта В (обозначается АÍВ ), если каждый элемент А является элементом В по крайней мере не больше число раз, т.е. АÍВ тогда и только тогда, когда #(x,A)
Комплект А строго включен в комплект В (АÍВ), если АÍВ и А не равно В. Над комплектами определены 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. Пространство комплектов Dn есть множество всех таких комплектов, что элементы их принадлежат D и ни один из элементов не входит в комплект более n раз. Иначе говоря, для любого В Î Dn : а) из х Î В следует х Î D; б) для любого х #(x,B)