:: Some Elementary Notions of the Theory of Petri Nets
:: by Waldemar Korczy\'nski
::
:: Received August 10, 1990
:: Copyright (c) 1990-2016 Association of Mizar Users
:: (Stowarzyszenie Uzytkownikow Mizara, Bialystok, Poland).
:: This code can be distributed under the GNU General Public Licence
:: version 3.0 or later, or the Creative Commons Attribution-ShareAlike
:: License version 3.0 or later, subject to the binding interpretation
:: detailed in file COPYING.interpretation.
:: See COPYING.GPL and COPYING.CC-BY-SA for the full text of these
:: licenses, or see http://www.gnu.org/licenses/gpl.html and
:: http://creativecommons.org/licenses/by-sa/3.0/.
environ
vocabularies RELAT_1, XBOOLE_0, TARSKI, ZFMISC_1, SUBSET_1, SETFAM_1, NET_1,
STRUCT_0, PETRI;
notations TARSKI, XBOOLE_0, ZFMISC_1, SUBSET_1, SETFAM_1, RELAT_1, PARTIT_2,
STRUCT_0, PETRI;
constructors TARSKI, SUBSET_1, RELAT_1, STRUCT_0, PETRI, PARTIT_2;
registrations XBOOLE_0, SUBSET_1, RELAT_1;
requirements SUBSET, BOOLE;
begin
definition let P be PT_net_Str;
func Flow P -> set equals
:: NET_1:def 1
(the S-T_Arcs of P) \/ the T-S_Arcs of P;
end;
registration let P be PT_net_Str;
cluster Flow P -> Relation-like;
end;
::The above definition describes a "structure of a Petri net" which
::is a kind of relational system.
reserve x,y for set;
reserve N for PT_net_Str;
definition
let N be PT_net_Str;
attr N is Petri means
:: NET_1:def 2
the carrier of N misses the carrier' of N & (
Flow N) c= [:the carrier of N, the carrier' of N:] \/ [:the
carrier' of N, the carrier of N:];
end;
:: A Petri net is defined as a triple of the form
:: N = (carrier, carrier', Flow)
:: with carrier and carrier' being disjoint sets and
:: Flow c= (carrier' x carrier) U (carrier x carrier')
:: It is allowed that both sets carrier and carrier' are empty.
:: A Petri net is here described as a predicate defined in the set
:: (on the mode) PT_net_Str.
definition
let N be PT_net_Str;
func Elements(N) -> set equals
:: NET_1:def 3
(the carrier of N) \/ (the carrier' of N);
end;
theorem :: NET_1:1
Elements(N) <> {} implies (x is Element of Elements(N) implies x is
Element of the carrier of N or x is Element of the carrier' of N);
theorem :: NET_1:2
x is Element of the carrier of N & the carrier of N <> {} implies x is
Element of Elements(N);
theorem :: NET_1:3
x is Element of the carrier' of N & the carrier' of N <> {}
implies x is Element of Elements(N);
registration
cluster PT_net_Str (#{}, {}, {}({},{}), {}({},{})#) -> Petri;
end;
:: This lemma is of rather "technical" nature. It allows a definition
:: of a "subtype" of the type PT_net_Str. (see the following definition of the
:: type Pnet).
registration
cluster strict Petri for PT_net_Str;
end;
definition
mode Pnet is Petri PT_net_Str;
end;
:: The above definition defines a Petri net as a TYPE of the structure
:: PT_net_Str. The type is not empty.
theorem :: NET_1:4
for N being Pnet holds not (x in the carrier of N & x in the carrier' of N);
:: This lemma is of rather "technical" character. It will be used in the
:: proof of the correctness of a definition of a function bellow. (See
:: the definition of the functions Enter and Exit.)
theorem :: NET_1:5
for N being Pnet holds [x,y] in Flow N & x in the
carrier' of N implies y in the carrier of N;
theorem :: NET_1:6
for N being Pnet holds [x,y] in Flow N & y in the
carrier' of N implies x in the carrier of N;
theorem :: NET_1:7
for N being Pnet holds [x,y] in Flow N & x in the carrier of N
implies y in the carrier' of N;
theorem :: NET_1:8
for N being Pnet holds [x,y] in Flow N & y in the carrier of N
implies x in the carrier' of N;
definition
let N be Pnet;
let x,y;
pred pre N,x,y means
:: NET_1:def 4
[y,x] in Flow N & x in the carrier' of N;
pred post N,x,y means
:: NET_1:def 5
[x,y] in Flow N & x in the carrier' of N;
end;
definition
let N be PT_net_Str;
let x be Element of Elements(N);
func Pre(N,x) -> set means
:: NET_1:def 6
for y being object holds y in it iff y in Elements(N) & [y,x] in Flow N;
func Post(N,x) -> set means
:: NET_1:def 7
for y being object holds y in it iff y in Elements(N) & [x,y] in Flow N;
end;
theorem :: NET_1:9
for N being Pnet for x being Element of Elements(N) holds Pre(N,
x) c= Elements(N);
theorem :: NET_1:10
for N being Pnet for x being Element of Elements N holds Pre(N,x) c=
Elements N;
theorem :: NET_1:11
for N being Pnet for x being Element of Elements(N) holds Post(N
,x) c= Elements(N);
theorem :: NET_1:12
for N being Pnet for x being Element of Elements N holds Post(N,x) c=
Elements N;
theorem :: NET_1:13
for N being Pnet for y being Element of Elements(N) holds y in the
carrier' of N implies (x in Pre(N,y) iff pre N,y,x);
theorem :: NET_1:14
for N being Pnet for y being Element of Elements(N) holds y in the
carrier' of N implies (x in Post(N,y) iff post N,y,x);
definition
let N be Pnet;
let x be Element of Elements(N);
assume
Elements(N) <> {};
func enter(N,x) -> set means
:: NET_1:def 8
(x in the carrier of N implies it = {x}) & (x in
the carrier' of N implies it = Pre(N,x));
end;
theorem :: NET_1:15
for N being Pnet for x being Element of Elements(N) holds
Elements(N) <> {} implies enter(N,x) ={x} or enter(N,x) = Pre(N,x);
theorem :: NET_1:16
for N being Pnet for x being Element of Elements(N) holds
Elements(N) <> {} implies enter(N,x) c= Elements(N);
theorem :: NET_1:17
for N being Pnet for x being Element of Elements N holds Elements N <>
{} implies enter(N,x) c= Elements N;
definition
let N be Pnet;
let x be Element of Elements(N);
assume
Elements(N) <> {};
func exit(N,x) -> set means
:: NET_1:def 9
(x in the carrier of N implies it = {x})
& (x in the carrier' of N implies it = Post(N,x));
end;
theorem :: NET_1:18
for N being Pnet for x being Element of Elements(N) holds
Elements(N) <> {} implies exit(N,x) ={x} or exit(N,x) = Post(N,x);
theorem :: NET_1:19
for N being Pnet for x being Element of Elements(N) holds
Elements(N) <> {} implies exit(N,x) c= Elements(N);
theorem :: NET_1:20
for N being Pnet for x being Element of Elements N holds Elements N <>
{} implies exit(N,x) c= Elements N;
definition
let N be Pnet;
let x be Element of Elements(N);
func field(N,x) -> set equals
:: NET_1:def 10
enter(N,x) \/ exit(N,x);
end;
definition
let N be PT_net_Str;
let x be Element of the carrier' of N;
func Prec(N,x) -> set means
:: NET_1:def 11
for y being object holds
y in it iff y in the carrier of N & [y,x] in Flow N;
func Postc(N,x) -> set means
:: NET_1:def 12
for y being object holds
y in it iff y in the carrier of N & [x,y] in Flow N;
end;
definition
let N be Pnet;
let X be set;
func Entr(N,X) -> set means
:: NET_1:def 13
x in it iff x c= Elements N & ex y being
Element of Elements N st y in X & x = enter(N,y);
func Ext(N,X) -> set means
:: NET_1:def 14
x in it iff x c= Elements N & ex y being Element
of Elements N st y in X & x = exit(N,y);
end;
theorem :: NET_1:21
for N being Pnet for x being Element of Elements(N) for X being
set holds Elements(N) <> {} & x in X implies enter(N,x) in Entr(N,X);
theorem :: NET_1:22
for N being Pnet for x being Element of Elements(N) for X being
set holds Elements(N) <> {} & x in X implies exit(N,x) in Ext(N,X);
definition
let N be Pnet;
let X be set;
func Input(N,X) -> set equals
:: NET_1:def 15
union Entr(N,X);
func Output(N,X) -> set equals
:: NET_1:def 16
union Ext(N,X);
end;
theorem :: NET_1:23
for N being Pnet for x for X being set holds X c= Elements(N) implies
(x in Input(N,X) iff ex y being Element of Elements(N) st y in X & x in enter(N
,y));
theorem :: NET_1:24
for N being Pnet for x for X being set holds X c= Elements(N) implies
(x in Output(N,X) iff ex y being Element of Elements(N) st y in X & x in exit(N
,y));
theorem :: NET_1:25
for N being Pnet for X being Subset of Elements(N) for x being Element
of Elements(N) holds Elements(N) <> {} implies (x in Input(N,X) iff (x in X & x
in the carrier of N or ex y being Element of Elements(N) st y in X & y in the
carrier' of N & pre N,y,x));
theorem :: NET_1:26
for N being Pnet for X being Subset of Elements(N) for x being Element
of Elements(N) holds Elements(N) <> {} implies (x in Output(N,X) iff (x in X &
x in the carrier of N or ex y being Element of Elements(N) st y in X & y in the
carrier' of N & post N,y,x));