Luận văn Mạng vị trí / chuyển và một số tính chất của mạng Petri

2.4.2: (Wolfgang Reisig, [8]) Giả sử  và ’ là hai hệ điều kiện - biến cố tƣơng đƣơng. 1. Hệ  là chu trình  hệ ’ là chu trình. 2. Hệ  là sống  hệ ’ là sống. Hệ điều kiện - biến cố tuần tự với các trƣờng hợp bao gồm chỉ một điều kiện tƣơng ứng với các ôtômat hữu hạn. Với hai hệ nhƣ thế sự tƣơng đƣơng trùng với sự đẳng cấu. 1.2.5. Các hệ mạng an toàn và đầy đủ hóa hệ điều kiện – biến cố Trong phần trƣớc chúng ta đã chỉ ra rằng biến cố sẽ không đƣợc kích hoạt trong tình trạng không an toàn. Tình trạng nhƣ thế có thể loại trừ đƣợc nhờ một phép biến đổi tƣơng đƣơng trên các hệ điều kiện - biến cố. Để làm việc này, ta thêm vào cho mỗi điều kiện b một điều kiện bù của nó  b để trong mỗi trƣờng hợp của hệ thì hoặc b hoặc  b đƣợc thoả mãn. Định nghĩa 1.2.5.1: Giả sử  là hệ điều kiện - biến cố và b, b’ là các điều kiện trong B. 1. Điều kiện b’ đƣợc gọi là bù của điều kiện b khi và chỉ khi b = b’ và b  = b’. 2. Hệ  là đầy đủ nếu mỗi điều kiện b trong B đều có điều kiện bù b’ cũng trong B. Định nghĩa 1.2.5.2: Giả sử  là hệ điều kiện - biến cố và ký hiệu B là tập các điều kiên trong B không có bù. Với mỗi điều kiện b trong B ta thêm vào điều kiện mới b . Đặt quan hệ F = { (e,b ) b  B  (b, e)  F }  { (b , e) b  B  (e, b)  F }. 16 Với c  C đặt (c) = c  {b b  B  b  c}. Khi đó hệ điều kiện - biến cố   = ( B  {b b  B}, E ; F  F, ( C) ) đƣợc gọi là đầy đủ của hệ . Mỗi điều kiện b không có bù trong  thì đã có bù trong   . Định lý 1.2.5.1: (Wolfgang Reisig, [8]) Giả sử  là hệ điều kiện - biến cố và trƣờng hợp c  C . 1.   =   2.  b  B ,  c  C : b  (c)  b  (c) 3. c = (c)  B . Định lý 1.2.5.2: (Wolfgang Reisig, [8]) Giả sử  là hệ điều kiện - biến cố và tập G  E và B là tập các điều kiện không có bù trong B . a) –G = G  {b  b  B  b  G } và G – = G   {b b  B  b  G } b) G = –G  B , G  = G –  B . Bây giờ ta có thể chỉ ra rằng việc làm đầy đủ một hệ điều kiện - biến cố sẽ cho ta một hệ điều kiện - biến cố an toàn tƣơng đƣơng. Ví dụ: Σ   Σ’     Hình 10. Hệ mạng  và hệ mạng đầy đủ tƣơng ứng ’ 17 Định nghĩa 1.2.5.3: Giả sử  là hệ điều kiện - biến cố. Hệ  đƣợc gọi là an toàn (safe) nếu với mỗi biến cố e  E và mỗi trƣờng hợp c  C : 1. e  c  e  B \ c , nghĩa là e   c =  2. e  c  e  B \ c , nghĩa là  e  c = . Chú ý rằng, trong định nghĩa trên mệnh đề 2. không phải bao giờ cũng suy đƣợc từ mệnh đề 1. Chẳng hạn, xét hệ đơn giản sau đây:  Định lý 1.2.5.3: (Wolfgang Reisig, [8]) 1) Mọi hệ điều kiện - biến cố đầy đủ là an toàn. 2) Với mỗi hệ điều kiện - biến cố có một hệ an toàn tƣơng đƣơng. 3) Nếu hệ  là an toàn thì:  e  E :  e    e  . Không phải mọi hệ điều kiện - biến cố an toàn nào cũng đầy đủ. Ví dụ: b1 b3 b4 b5b6 b2 e1 e2 e3  Hình 11. Hệ mạng an toàn nhƣng không đầy đủ 1.2.6. Đồ thị các trƣờng hợp Để có cái nhìn tổng quát tất cả các trƣờng hợp của một hệ điều kiện - biến cố, ta xây dung đồ thị các trƣờng hợp của hệ này. Các đỉnh của đồ thị là các trƣờng hợp còn các cung chính là các bƣớc trên hệ. Định nghĩa 1.2.6.1: Giả sử  là một hệ điều kiện - biến cố và G là tập tất cả các bƣớc của hệ này. Đặt: 18 P = { (c1, G , c2)  C  G  C c1[ G > c2 } Đồ thị  = (C , P) đƣợc gọi là đồ thị các trường hợp của . Định lý 1.2.6.1: (Wolfgang Reisig, [8]) Hệ điều kiện - biến cố  là chu trình nếu đồ thị các trƣờng hợp của nó là liên thông mạnh. Định lý 1.2.6.2: (Wolfgang Reisig, [8]) Hệ điều kiện - biến cố  là sống khi và chỉ khi với mỗi trƣờng hợp c0  C và với mỗi biến cố e  E đều có đƣờng đi c0 l1 c1 ln cn trong đồ thị  mà nhãn ln = {e}. Ví dụ: b3 e1 b1 b2 e4 e2 e3 b5 e5 b4 {b1} {b2,b3} {b4,b5} {b3,b4} {b2,b5} {e1} {e2} {e5} {e4} {e3} {e3} {e4} {e3,e4} Hình 12. Hệ điều kiện biến cố và đồ thị các trƣờng hợp tƣơng ứng Hệ này là chu trình và đồ thị các trƣờng hợp của nó là liên thông mạnh. Định lý 1.2.6.3: (Wolfgang Reisig, [8]) Hai hệ điều kiện - biến cố là tƣơng đƣơng khi và chỉ khi đồ thị các trƣờng hợp của chúng là đẳng cấu với nhau. Không phải mọi đồ thị định hƣớng đều có thể thể hiện nhƣ đồ thị các trƣờng hợp của các hệ điều kiện - biến cố. Xét đồ thị định hƣớng sau đây: 19 c1 c2 c3 c4 e1 e2 e3 Hình 13. Đồ thị có hƣớng Theo đồ thị trên thì hai biến cố e1 và e2 đều đƣợc trƣờng hợp c1 kích hoạt. Nếu trong c1 có xung đột giữa e1 và e2 thì c2 không thể kích hoạt e2. Khi đó, trong đồ thị phải bỏ cung (c2,{e2}, c4). Ngƣợc lại, nếu trong c1 không có xung đột giữa e1 và e2 thì c3 có thể kích hoạt e1. Vậy thì, trong đồ thị phải thêm cung (c3, {e1}, c4). Đồ thị các trƣờng hợp trở nên rất phức tạp đối với các hệ tƣơng tranh mạnh. Chẳng hạn, một bƣớc chứa n biến cố sẽ sinh ra 2n cung trong đồ thị các trƣờng hợp. Định lý sau đây sẽ thể hiện điều đó. Định lý 1.2.6.4: (Wolfgang Reisig, [8]) Giả sử  là hệ điều kiện - biến cố và c1, c2, c3  C , G1, G2  E . 1. Nếu c1 G1 c2 G2 c3 là đƣờng đi trong đồ thị  thì G1  G2 = . 2. Giả sử G1  G2 = . Nếu c1 (G1  G2) c2 là một cung trong  thì tồn tại c  C sao cho c1 G1 c G2 c3 là đƣờng đi trong đồ thị  . 1.2.7. Các quá trình của hệ điều kiện – biến cố Có thể định nghĩa quá trình của hệ điều kiện - biến cố nhƣ là một đƣờng đi trong đồ thị các trƣờng hợp của nó. Song đƣờng đi nhƣ thế không mô tả chính xác đƣợc cái mà ta hiểu trực quan từ quá trình. Thứ tự tổng thể của các phần tử của nó cũng không cho ta một thông tin nào về sự xuất hiện trƣớc sau của các biến cố hay liệu chúng có độc lập với nhau hay không. Thứ tự bộ phận mà trong đó các biến cố xuất hiện chỉ đƣợc biểu diễn gián tiếp trong đồ thị các trƣờng hợp bởi tập tất cả các khả năng xuất hiện kế tiếp của các bƣớc. 20 Bởi vậy, chúng ta muốn tìm một cách mô tả thích hợp hơn cho quá trình. Đặc biệt là, nó phải rõ ràng và chỉ ra đƣợc một cách tƣờng minh rằng các biến cố có xuất hiện một cách đồng thời đƣợc không. Mô tả nhƣ thế đƣợc xem nhƣ là bản ghi sự xuất hiện của các biến cố và sự thay đổi của các điều kiện. Các phần tử của bản ghi này đƣợc sắp thứ tự bộ phận nhờ quan hệ “a là điều kiện tiên quyết cho b”. Hơn nữa, sự lặp lại của chính biến cố hay chính điều kiện này đƣợc ghi lại nhƣ một phần tử mới. Có một biểu diễn thực sự đúng đắn cho các bản ghi nhƣ thế lại chính là một mạng. Để có thể điều khiển các quá trình đƣợc mô tả nhƣ thế, chẳng hạn “mạng đƣợc sắp thứ tự bộ phận”, ta cần phải xét một số tính chất của tập có thứ tự bộ phận và sau đó xét các mạng hiện. Đó là các mạng đƣợc sắp thứ tự bộ phận và thích hợp để mô tả các quá trình. Sau đó, ta trình bày khái niệm quá trình và chỉ ra rằng các quá trình có thể hợp thành và phân rã nhƣ thế nào. Đồng thời, ta cũng nghiên cứu mối liên hệ của chúng với đồ thị các trƣờng hợp. 1.2.7.1. Tập có thứ tự bộ phận Các quan hệ độc lập hay phụ thuộc thƣờng là đối xứng, phản xạ nhƣng nói chung là không bắc cầu. Trƣớc tiên, ta xét quan hệ tƣơng tự. Định nghĩa 1.2.7.1.1: Giả sử A là một tập hợp. Quan hệ nhị nguyên   A  A đƣợc gọi là quan hệ tương tự nếu: 1.  a  A : (a, a)   (tính phản xạ) 2.  a, b  A : (a, b)    (b, a)   (tính đối xứng). Tập con B  A đƣợc gọi là một vùng của quan hệ tƣơng tự  nếu: a)  a, b  B : (a, b)   (tính đầy đủ) b)  a  A \ B ,  b  B : (a, b)   (tính cực đại). Định lý 1.2.7.1.1: (Wolfgang Reisig, [8]) Giả sử A là một tập hợp và  là một quan hệ tƣơng tự trên A. 1. Mỗi phần tử của A phải thuộc vào một vùng của . 2. Các vùng của tập không rỗng A là khác rỗng và không có vùng nào là tập con thực sự của một vùng khác. 21 3. Nếu  là quan hệ tƣơng đƣơng thì các vùng của  chính là các lớp tƣơng đƣơng của nó. Biểu diễn đồ thị: Một quan hệ tƣơng tự trên tập hữu hạn A có thể biểu diễn nhƣ một đồ thị vô hƣớng: A đƣợc xem nhƣ là tập các đỉnh và: K = { (a, b)  a  b  (a, b)   } là tập các cạnh. Bây giờ ta xét tập hợp có thứ tự bộ phận, nghĩa là tập hợp mà trên nó có một quan hệ không phản xạ và bắc cầu. Hai quan hệ li và co đƣợc định nghĩa nhƣ sau: Định nghĩa 1.2.7.1.2: Giả sử A là tập có thứ tự bộ phận < . 1. Quan hệ li  A  A đƣợc xác định nhƣ sau: (a, b)  li  a < b  b < a  a = b. 2. Quan hệ co  A  A đƣợc xác định nhƣ sau: (a, b)  co   (a < b)  a = b. Định lý 1.2.7.1.2: (Wolfgang Reisig, [8]) Giả sử A là tập có thứ tự bộ phận và a, b  A. 1. (a, b)  li  (a, b)  co , 2. (a, b)  li  (a, b)  co  a = b. Định lý 1.2.7.1.3: (Wolfgang Reisig, [8]) Với mỗi tập có thứ tự bộ phận A thì li và co là các quan hệ tƣơng tự. Định nghĩa 1.2.7.1.3: Giả sử A là tập có thứ tự bộ phận và tập con B  A. 1. Tập con B đƣợc gọi là một đường nếu B là một vùng của quan hệ li. 2. Tập con B đƣợc gọi là một nhát cắt nếu B là một vùng của quan hệ co. Định lý 1.2.7.1.4: (Wolfgang Reisig, [8]) Giả sử A là tập có thứ tự bộ phận và tập con B  A. 1. Tập con B là một đƣờng nếu: i)  a, b  B : a < b  b < a  a = b và ii)  a  A \ B ,  b  B :  (a < b  b < a) . 2. Tập con B là một nhát cắt nếu: 22 i)  a, b  B :  (a < b  b < a) và ii)  a  A \ B ,  b  B : a < b  b < a . Khái niệm tập bị chặn và tập trƣớc đƣợc định nghĩa nhƣ sau: Định nghĩa 1.2.7.1.4: Giả sử A là tập có thứ tự bộ phận và giả sử B và C là các tập con của tập A. 1. Tập A là bị chặn nếu có một số nguyên n  N sao cho mọi đƣờng đi L trong A đều thoả mãn: | L |  n . 2. Tập con B đƣợc gọi là trước tập con C (ta viết: B  C) nếu:  b  B ,  c  C : b < c  b co c . ( B < C có nghĩa là: B  C  B  C ). 3. Ta ký hiệu: B - = {a  A  {a}  B} và B+ = {a  A  B  {a}} - đƣợc gọi là tập trước và tập sau của B.  B = {b  B  b’ B : b co b’  b < b’} và B  = {b  B  b’ B : b’ co b  b’ < b} . Cụ thể là, B bao gồm các phần tử ”cực tiểu” của B và B bao gồm các phần tử ”cực đại” của B. Định lý 1.2.7.1.5: (Wolfgang Reisig, [8]) Nếu A là tập có thứ tự bộ phận bị chặn thì các tập con A và A là các nhát cắt. Định lý 1.2.7.1.6: (Wolfgang Reisig, [8]) Giả sử A là tập có thứ tự bộ phận, L là một đƣờng và D là một nhát cắt trong A. Khi đó: | L  D | = 1. Tính K-trù mật của một tập có thứ tự bộ phận đƣợc định nghĩa nhƣ sau: Định nghĩa 1.2.7.1.5: Tập có thứ tự bộ phận A đƣợc gọi là K-trù mật nếu mỗi đƣờng và mỗi một nhát cắt trong A đều có giao khác rỗng. Tuy nhiên, không phải tập có thứ tự bộ phận nào cũng là K-trù mật. Chẳng hạn, 23 a b đƣờng L = {c, b} , nhát cắt D = {a, d} và L  D =  c d 1.2.7.2. Mạng hiện Mạng hiện là một mạng phi chu trình với các S-phần tử là không rẽ nhánh. Thế thì, ta sẽ có một thứ tự bộ phận trên các phần tử của mạng. Ta sẽ chỉ ra rằng các mạng hiện là K-trù mật. Do vậy, mạng hiện thƣờng đƣợc dùng để biểu diễn các quá trình trên một hệ điều kiện - biến cố. Định nghĩa 1.2.7.2.1: Mạng K = (SK, TK; FK) đƣợc gọi là một mạng hiện nếu: 1.  a, b  K : a FK + b   (b FK + a) (mạng K là phi chu trình). 2.  s  SK : | s |  1  | s |  1 (S-phần tử không rẽ nhánh). Định lý 1.2.7.2.1: (Wolfgang Reisig, [8]) Giả sử K là một mạng hiện. Quan hệ < đƣợc định nghĩa nhƣ sau:  a, b  K : a < b  a FK + b là một thứ tự bộ phận trên K. Vậy thì, các khái niệm liên quan đến thứ tự bộ phận nhƣ: đƣờng, nhát cắt, tính bị chặn, K-trù mật đều có thể áp dụng cho các mạng hiện. Định nghĩa 1.2.7.2.2: Nhát cắt của mạng hiện K chỉ chứa các S-phần tử đƣợc gọi là một lát cắt. Ký hiệu: sl(K) là tập tất cả các lát cắt của mạng hiện K. Định lý 1.2.7.2.2: (Wolfgang Reisig, [8]) Mọi mạng hiện không rỗng bị chặn đều là K-trù mật. Chú ý rằng, mạng hiện không bị chặn chƣa chắc đã là K-trù mật. 1.2.7.3. Các quá trình Bây giờ chúng ta định nghĩa các quá trình của một hệ điều kiện - biến cố bằng cách sử dụng các mạng hiện bị chặn. Vì mỗi hệ điều kiện - biến cố đều có thể biến đổi thành một hệ điều kiện - biến cố an toàn tƣơng đƣơng, nên ta sẽ chỉ định nghĩa quá trình cho các hệ điều kiện - biến cố an toàn. 24 Các quá trình sẽ đƣợc mô tả nhƣ các ánh xạ từ các mạng hiện bị chặn vào hệ điều kiện - biến cố an toàn thoả mãn hai yêu cầu sau đây: 1. Mỗi lát cắt đƣợc ánh xạ 1 - 1 vào một trƣờng hợp. 2. Ánh xạ mỗi T-phần tử vào một biến cố và phải bảo toàn môi trƣờng của biến cố này. Định nghĩa 1.2.7.3.1: Giả sử K là một mạng hiện bị chặn và  là một hệ điều kiện - biến cố an toàn. Một ánh xạ p : K   đƣợc gọi là một quá trình của  nếu với mỗi lát cắt D của K và mỗi phần tử t  TK thoả mãn: 1. pD là ánh xạ 1 - 1 và p(D)  C . 2. p(t) = p(t) và p(t) = p(t) . Trong biểu diễn đồ thị của quá trình p : K   , mỗi phần tử x của K đƣợc gán nhãn bởi ảnh p(x) của nó. Tính K-trù mật của các mạng hiện bị chặn là một tính chất quan trọng để sử dụng mạng hiện trong mô tả các quá trình không tuần tự. Mỗi đƣờng biểu diễn dãy các phần tử mà chúng phụ thuộc nhân quả lẫn nhau, thể hiện nhƣ một quá trình con tuần tự. Tính K-trù mật của mạng hiện đảm bảo rằng mỗi quá trình con tuần tự đƣợc. Định lý 1.2.7.3.1: (Wolfgang Reisig, [8]) Giả sử p : K   là một quá trình và tập con T  TK thoả mãn  t1, t2  T : t1 co t2. Thế thì,  c1, c2  C : c1 [ p(T) > c2 . Định nghĩa 1.2.7.3.2: Hai quá trình p1 : K1   và p2 : K2   của cùng một hệ điều kiện - biến cố  đƣợc gọi là đẳng cấu nếu mạng hiện K1 là -đẳng cấu với mạng hiện K2 và:  x  K1 : p1(x) = p2((x)). Dƣới đây ta không phân biệt các quá trình đẳng cấu mà ta có thể hiểu hoặc là lớp các tƣơng đƣơng các quá trình đẳng cấu với nhau hoặc là một đại diện nào đó của lớp này. 25 Một quá trình p : K   thƣờng đƣợc biểu diễn bởi tập hợp các cặp {(x, p(x)) x  K}. Các hệ điều kiện - biến cố an toàn đƣợc đặc trƣng một cách đầy đủ bởi tập các quá trình của chúng. Định lý 1.2.7.3.2: (Wolfgang Reisig, [8]) Giả sử 1, 2 là hai hệ điều kiện - biến cố an toàn và giả sử Pi là tập các quá trình của i (i = 1, 2). Khi đó thì: P1 = P2  1 = 2 . 1.2.7.4 Sự hợp thành của các quá trình Với hai quá trình p1, p2 mà p1 kết thúc ở chính trƣờng hợp mà từ đó p2 bắt đầu thì ta có thể định nghĩa phép toán hợp thành trên các quá trình này. Bổ đề 4.23: Nếu p : K   là một quá trình thì tập K và K là các lát cắt của K. Bổ đề 4.24: Giả sử pi : Ki   , i = 1, 2 là hai quá trình với p1(K1  ) = p2(  K2). Thế thì có đúng một mạng hiện K sai khác một đẳng cấu, với lát cắt D và quá trình p : K   thoả mãn: pD- = p1 và pD+ = p2 , trong đó D - và D+ là tập trƣớc và tập sau của D. Định nghĩa 1.2.7.4.1: Giả sử p1, p2 và p là các quá trình thoả mãn các yêu cầu của Bổ đề 4.24 ở trên. Khi đó, quá trình p đƣợc gọi là hợp thành của các quá trình p1 và p2 và ta ký hiệu p = p1  p2 . Định lý 1.2.7.4.1: (Wolfgang Reisig, [8]) Giả sử p : K   là một quá trình và giả sử D là một lát cắt của mạng hiện K. Giả sử p- = pD- và p + = pD+ . Thế thì, p - và p+ cũng là các quá trình của hệ  và p = p-  p+ . Định lý 1.2.7.4.2: (Wolfgang Reisig, [8]) Giả sử p1, p2, p3 là các quá trình mà hợp thành p1  p2 và p2  p3 xác định. Khi đó thì: p1  (p2  p3) và (p1  p2)  p3 là hai quá trình đẳng cấu với nhau. Ta gọi một quá trình là cơ sở nếu nó mô tả một bƣớc. Mỗi quá trình có thể phân tích thành hợp thành của một số hữu hạn quá trình cơ sở. 26 Định nghĩa 1.2.7.4.2: Quá trình p : K   đƣợc gọi là cơ sở nếu SK =  K  K . Định lý 1.2.7.4.3: (Wolfgang Reisig, [8]) 1) Quá trình p : K   là cơ sở  p(K) [ p(TK) > p(K ) là một bƣớc trên . 2) Nếu quá trình p : K   là cơ sở thì:  t1, t2  TK : t1 co t2 . Định nghĩa 1.2.7.4.3: Quá trình p : K   đƣợc gọi là rỗng nếu TK =  . Định lý 1.2.7.4.4: (Wolfgang Reisig, [8]) 1. Mọi quá trình rỗng đều là cơ sở. 2. Nếu p’ là một quá trình rỗng và p  p’ (hoặc p’  p) xác định thì p = p  p’ (hoặc p = p  p’) một cách tƣơng ứng. Định lý 1.2.7.4.5: (Wolfgang Reisig, [8]) Với mọi quá trình p : K   đều tồn tại một số hữu hạn quá trình cơ sở p1, p2, ... , pn sao cho p = p1  p2  ...  pn . 1.2.7.5. Các quá trình và đồ thị các trƣờng hợp Trong phần này chúng ta nghiên cứu mối quan hệ giữa các quá trình và đƣờng đi trong đồ thị các trƣờng hợp của một hệ điều kiện - biến cố. Trƣớc hết, ta chỉ ra rằng các quá trình cơ sở tƣơng ứng với các cung trong đồ thị các trƣờng hợp. Sau đó ta tìm các đƣờng đi trong đồ thị mô tả các quá trình đơn. Ta sẽ thấy rằng tất cả các đƣờng đi đó có thể biến đổi lẫn nhau nhờ “phân tích” hay ”hợp nhất” các cung của chúng. Bổ đề 4.33: Giả sử  là một hệ điều kiện - biến cố an toàn. Quá trình p : K   là cơ sở khi và chỉ khi có một cung v = (c1, G, c2) trong đồ thị các trƣờng hợp  sao cho p(  K) = c1 , p(K  ) = c2 và p(TK) = G. Bổ đề này thiết lập một sự tƣơng ứng duy nhất giữa các quá trình cơ sở và các cung của đồ thị các trƣờng hợp. Do vậy, ta định nghĩa: Định nghĩa 1.2.7.5.1: Giả sử  là một hệ điều kiện - biến cố an toàn. 27 1) Nếu v là một cung trong  thì ta ký hiệu v là quá trình cơ sở tƣơng ứng với v, xác định theo Bổ đề trên. v đƣợc gọi là quá trình của cung v và v đƣợc gọi là cung của quá trình v. 2) Giả sử v1, v2, , vn là các cung của đồ thị  và giả sử w = v1 v2 vn là một đƣờng đi trong  . Thế thì, w = v1  v2   vn đƣợc gọi là quá trình của w còn w đƣợc gọi là đƣờng đi của quá trình w. 3) Với cung v = (c1, G, c2) và biến cố e  G, đặt t(v,e) = v -1 (e) và (v) = {t(v,e) e  G}. Định nghĩa 1.2.7.5.2: Giả sử  là một hệ điều kiện - biến cố và giả sử c1, c2, c3  C và G1, G2  E . 1) Nếu u1 = c1 G1 c2 , u2 = c2 G2 c3 và v = c1 (G1  G2) c3 là các cung trong đồ thị  thì đƣờng đi u1u2 đƣợc gọi là phân tách của v và v đƣợc gọi là hợp thành của u1 và u2. 2) Giả sử w, w’ là các đƣờng đi trong đồ thị  , w’ đƣợc gọi là hoán vị của w nếu tồn tại các đƣờng đi w1, w2, w3, w4 sao cho w = w1 w2 w3 và w’ = w1 w4 w3 và w4 là phân tách hoặc hợp nhất của w2 . 3) Giả sử w1, w2, ... , wn là các đƣờng đi trong đồ thị  . (w1, w2, ... , wn) đƣợc gọi là một dãy hoán vị nếu với mỗi i = 1, 2, ..., n thì wi+1 là hoán vị của wi . Định lý 1.2.7.5.1: (Wolfgang Reisig, [8]) Giả sử  là một hệ điều kiện - biến cố và giả sử c1, c2, c3  C và hai tập con G1, G2  E không rỗng và rời nhau. 1. Nếu v = c1 (G1  G2) c3 là một cung trong đồ thị  thì tồn tại một phân tách của v có dạng c1 G1 c G2 c3 với trƣờng hợp c nào đó thuộc C . 2. Giả sử u1 = c1 G1 c3 và u2 = c3 G2 c2 là các cung trong đồ thị  và giả sử u1  u2 : K   là một quá trình của hệ  . Thế thì:  t1, t2  TK : t1 co t2  c1 (G1  G2) c3 là một cung trong đồ thị  . Bổ đề 4.37: 28 Giả sử w là một đƣờng đi của quá trình không rỗng nào đó w : K  . Khi đó, tồn tại một đƣờng đi w’ và một cung v sao cho (v) = {t  TK  t  K} và có một dãy các hoán vị từ w tới w’. Định lý 1.2.7.5.2: (Wolfgang Reisig, [8]) Hai đƣờng đi w và w’ tƣơng ứng với cùng một quá trình khi và chỉ khi có một dãy hoán vị từ w tới w’. Ngƣợc lại, nếu u1u2 là một phân tách của cung v thì các quá trình của u1u2 và của v là một. Vậy nếu w’ là hoán vị của w thì w và w’ là các đƣờng đi của cùng một quá trình. Do vậy, mọi thành phần của một dãy hoán vị là các đƣờng đi của cùng một quá trình. Kết luận chƣơng 1: Nội dung của Chƣơng này trình bày các khái niệm cơ bản về lý thuyết mạng, mạng Petri cơ sở và phân loại các lớp mạng Petri. Chƣơng này cũng nghiên cứu khái niệm về các trƣờng hợp, các bƣớc của hệ điều kiện – biến cố và các quá trình của hệ điều kiện – biến cố. Đây là những lý thuyết cơ sở trong mô hình tƣơng tranh. 29 Chƣơng 2 – MẠNG VỊ TRÍ/CHUYỂN VÀ MỘT SỐ TÍNH CHẤT CỦA MẠNG PETRI Sau khi mô hình hóa các hệ thống nhƣ một mạng Petri, một câu hỏi đƣợc đặt ra là ta có thể làm gì với chúng? Mạng Petri đƣợc xem nhƣ là một công cụ hỗ trợ phân tích các tính chất của hệ thống và các vấn đề liên quan đến hệ thống đã đƣợc mô hình hóa. Do đó, ta cần thiết nghiên cứu các tính chất của bản thân mạng Petri. Có hai nhóm tính chất của mạng Petri liên quan đến bộ đánh dấu đầu tiên đó là: các tính chất phụ thuộc vào bộ đánh dấu đầu tiên và các tính chất không phụ thuộc vào bộ đánh dấu đầu tiên này. Tuy nhiên, các nghiên cứu về mạng Petri thƣờng quan tâm nhiều hơn đến các tính chất phụ thuộc bộ đánh dấu đầu tiên. Trong nội dung Chƣơng này, Chúng ta xem xét mạng vị trí/ chuyển và một số tính chất của mạng Petri liên quan đến bộ đánh dấu đầu tiên trên mạng vị trí/ chuyển này. 2.1. Mạng vị trí chuyển 2.1.1. Khái niệm mạng vị trí chuyển Mạng vị trí chuyển (mạng Petri) là một trong những mô hình tốt để biểu diễn các hệ tƣơng tranh. Mạng bao gồm hai đối tƣợng là vị trí và chuyển cùng với các cung có hƣớng liên hệ giữa chúng. Các vị trí mang thông tin mô tả trạng thái địa phƣơng, các chuyển thể hiện các hành động. Trong mạng Petri, chuyển t có thể cháy nếu các vị trí vào chứa đủ số dấu (token) cần thiết cho chuyển đó và không làm tràn sức chứa ở mọi vị trí. Sau khi một chuyển cháy, nó lấy đi token ở vị trí vào và thêm token trong mỗi vị trí ra. Trƣớc hết, chúng ta xét một hệ thống sản xuất bao gồm một nhà sản xuất và hai ngƣời tiêu thụ với các ràng buộc nhƣ sau: 1. Kho của xƣởng sản xuất chứa đƣợc nhiều nhất là 5 sản phẩm. 2. Mỗi lần sản xuất, nhà sản xuất làm đƣợc 3 sản phẩm. 3. Có bộ đếm đếm số lần sản xuất. 4. Tại mỗi thời điểm chỉ có thể một ngƣời tiêu thụ vào lấy hàng. 5. Mỗi lần lấy hàng, ngƣời tiêu thụ đều mua 2 sản phẩm. Quá trình sản xuất và tiêu thụ sản phẩm trên có thể mô tả bằng mạng sau đây: 30 t1 . . . . . . . . . . . Nhà sản xuất Nhà tiêu dùng Bộ đếm Kho k = ω k = 5 k = 1 k = 1 s1 s2 t2 3 2 k = 1 k = 2 k = 2t3 t4 t5 s3 s4 s5 s6 s7 Hình 14. Mô hình quá trình sản xuất và tiêu thụ Định nghĩa mạng vị trí /chuyển: Bộ sáu N = (S, T; F, K, M0, W) đƣợc gọi là một mạng vị trí /chuyển (P/T - net) nếu: 1) Bộ ba (S, T; F) là một mạng hữu hạn, các phần tử của tập S đƣợc gọi là các vị trí còn các phần tử của tập T đƣợc gọi là các chuyển. 2) K : S   {} , hàm cho dung lượng (có thể vô hạn) trên mỗi vị trí. 3) W : F  \ {0} , hàm gắn một trọng số dƣơng vào mỗi cung của mạng. 4) M0: S   {} là bộ đánh dấu đầu tiên của mạng phù hợp với dung lƣợng, có nghĩa là:  s  S : M0 (s)  K(s). Trong biểu diễn đồ thị của mạng vị trí /chuyển Các vị trí đƣợc ký hiệu: Các chuyển đƣợc ký hiệu: Định nghĩa bộ đánh dấu: Ánh xạ M : S  {} đƣợc gọi là một bộ đánh dấu của mạng N nếu:  s  S: M(s)  K(s). Điều kiện để kích hoạt: Giả sử M là một bộ đánh dấu của mạng vị trí /chuyển N. Chuyển t  T đƣợc gọi là M-kích hoạt nếu:  s  t : M(s)  W(s, t) và  s  t :M(s)  K(s) - W(t, s). Xác định bộ đánh dấu kế tiếp: 31 Một chuyển t  T đƣợc M-kích hoạt hoạt động và sẽ cho ta bộ đánh dấu kế tiếp M’ của M nhƣ sau: M’(s) =           )( ),(),()( ),()( ),()( sM stWtsWsM stWsM tsWsM Ta nói rằng t hoạt động và dẫn M tới M’ và ký hiệu: M [ t > M’. Định nghĩa: Bộ đánh dấu đạt đƣợc R(M) đƣợc gọi là tập các bộ đánh dấu đạt được từ M nếu R(M) là tập nhỏ nhất các bộ đánh dấu thoả mãn hai điều kiện: 1) M  R(M) và 2)Nếu M1 R(M) và với chuyển t nào đó mà M1 [ t > M2 thì M2  R(M). Trong biểu diễn đồ thị của một mạng vị trí/chuyển, cung p  F đƣợc gán nhãn W(p) nếu W(p) > 1. Dung lƣợng tại vị trí s đƣợc thể hiện bởi “k = K(s)”; nếu dung lƣợng bằng  thì bỏ qua không viết. Bộ đánh dấu M đƣợc biểu diễn bởi M(s) dấu chấm hay ký hiệu  trên các vị trí s. Ví dụ: Chuyển đƣợc kích hoạt và hoạt động H2 O2 H2O t 2 2 H2 O2 H2O t 2 2 Hình 15. Sơ đồ chuyển kích hoạt và hoạt động , nếu s  t \ t , nếu s  t \ t , nếu s  t  t các trƣờng hợp còn lại 32 Chuyển không đƣợc kích hoạt: . . . . . 2 2 t k= 3 k = 2 Hình 16. Sơ đồ chuyển không đƣợc kích hoạt Mỗi một hệ điều kiện - biến cố có thể xem nhƣ là một mạng vị trí chuyển mà dung lƣợng của các vị trí và trọng số của các cung trên mạng bằng 1. Ngƣợc lại, mỗi một mạng vị trí chuyển với dung lƣợng của các vị trí và trọng số của các cung bằng 1 hoạt động giống nhƣ một hệ điều kiện - biến cố. Một hệ điều kiện - biến cố liên quan tới một lớp các trƣờng hợp, còn một mạng vị trí chuyển chỉ nhận một bộ đánh dấu đầu tiên. Bộ đánh dấu đầu tiên M có thể dẫn chuyển t tới tình trạng không an toàn nếu t bị mất tính M-kích hoạt chỉ vì các vị trí trong tập t không đủ dung lƣợng. 2.1.2. Mạng an toàn và quá trình chuyển mạng về mạng an toàn Định nghĩa 2.1.2.1: Mạng vị trí/chuyển N = (S, T; F, K, M, W) đƣợc gọi là an toàn nếu với mọi M  R(MN) và với mọi t  T :