Embed Size (px)
Citation preview
Chap 6 1
Chapitre 6
Réseaux de Petri
et logique temporelle
w3.uqo.ca/luigi/
INF6001 Chap 6 2
Réseaux de Petri
Formalisme pour la spécification de systèmes répartisInventé au début des années 1960 par un chercheur
allemand, Carl Adam Petri Un des informaticiens les plus cités En même temps un des moins productifs en termes de
nombre de publications!A été énormément étudié et développé, et l’est encore
aujourd’hui, surtout en Europe, et surtout en FranceEn principe très simple, mais
Un très grand nombre de variations a été étudiéBeaucoup de ressources Web, cours en ligne, etc.
INF6001 Chap 6 3
Places, transitions et tire - modèle de base
Places
Transitions
Arcs
Quand toutes les places d’entrée à une transition sont marquées avec des jetons, la transition peut tirer et alors les jetons sont retirés des places d’entrée et ajoutés à toutes les places de sortie.
Jeton ou Marque
Tire!
INF6001 Chap 6 4
Observez la différence...
Après la transition, des jetons seront mis dans les deux places suivantes et il y aura traitement parallèle dans les deux directions
Après la transition, un seul jeton sera mis dans une seule des deux places suivantes (l’une ou l’autre) et une seule branche sera exécutée
Nous avons deux jetons, donc deux transitions sont possibles: ceci serait ou bien l’une et l’autre ou bien deux fois une des deux
INF6001 Chap 6 5
Exemple
p1
p2
p3 t0
t1
t2
t3
Marquage initial: 1 0 0
Y a-t-il une transition qui peut tirer?
INF6001 Chap 6 6
Deux transitions qui peuvent tirer, t1 et t3
Marq.
initial
p1
p2
p3t1
t3
(1 0 0)(0 1 0)
(0 0 1)
t0
t1
t2
t3
t0
t2
INF6001 Chap 6 7
Analyse d’accessibilité pour les réseaux de Petri
Un réseau de Petri avec 3 états (= marquages) accessibles
Marq.
initial
p1
p2
p3t1
t3
t2
t0(1 0 0)(0 1 0)
(0 0 1)
t0
t1
t2
t3
t0
t2
INF6001 Chap 6 8
Vecteurs de marquages
Les états peuvent être représentés par des vecteurs de marquages (1 0 0) = jeton sur p1, pas de jeton sur p2 ou p3, etc.
Le réseau peut être vu comme une machine à états (graphe de marquage)
(1 0 0)
(0 0 1)
(0 1 0)
t1
t0
t3 t2Marq.
initial
p1
p2
p3t1
t3
t2
t0(1 0 0)(0 1 0)
(0 0 1)
t0
t1
t2
t3
t0
t2
INF6001 Chap 6 9
Il est aussi possible d’obtenir un RP à partir d’une machine à états
15
2010
5
10
vend 15¢ bonbon
10
55
10
5
vend 20¢ bonbon
0
5
Figures provenant de http://www.cs.unc.edu/~montek/teaching/fall-07/lectures/index.html
Machine à états
INF6001 Chap 6 10
Réseau de Petri équivalentchaque transition a seul. 1 entrée et 1 sortie
510
vend 15¢ bonbon
10
5
5
10
5
vend 20¢ bonbon
INF6001 Chap 6 11
Représentation de parallélisme
Les Réseaux de Petri sont plus synthétiques que les machines à états pour la représentation du parallélisme
Pour représenter ce réseau, une machine à états doit donner l’entrelacement de t2 et t3
t2
t3
t1 t4
INF6001 Chap 6 12
Machine à états correspondante
t2
t3
t1 t4
p1
p2
p3
p4
p5
(1 1 0 0 0)
(1 0 0 1 0)
(0 0 1 1 0)
(0 0 0 0 1)
(0 1 1 0 0)
t2
t2
t3
t3
t4
t1
Mais s’il y avait plus de transitions à entrelacer…
INF6001 Chap 6 13
Le même chose en LOTOS 1ère possibilité(à contrôler comme exercice)
A := B |[t4,t1]| CwhereB := t2; t4; t1; BC := t3; t4; t1; C
t2
t2
t3
t3
t4
t1
INF6001 Chap 6 14
Même chose en LOTOS 2ème possibilité(Exercice)
A:= (t2; exit ||| t3; exit) >> BB:= t4; t1; A
Aspect de LOTOS qui n’a pas été expliqué: L’opérateur >> cause une synchronisation entre les exit
qui résulte dans une action interne i, suivie par le comportement B
t2 t3
t3 t2i
t4
t1
INF6001 Chap 6 15
Explosion d’états dans graphes de marquage
t1
t2
t3p1
p2
p3
p5
p4 t4
1 1 0 0 0 0
0 1 1 0 0 0t1
t3 0 1 0 0 1 0
0 0 1 1 0 0
t2
t2
t2
t4
t3
t4
t4t3
etc.Exercice: compléter ceci
p5
p6
INF6001 Chap 6 16
Modélisation de flux de données(utilisée pour la conception d’architecture de matériel)
a
a
b
b
a+b
a-b
+
-
/
≠0
=0
x
Erreur
copy
copy
x = (a+b)/(a-b)
a
b
INF6001 Chap 6 17
Modélisation de protocoles: envoi et attente
prêt à env.
attenteacquitt.
acq.reçu
msg.reçu
acq.envoyé
prêt à rec.
tampon plein
tampon pleinenv.
msg.
rec.acq.
recevoir
env.acquitt.
proc.1 proc.2
INF6001 Chap 6 18
Exercice: calculer le graphe de marquage
p1
p2
p3
p7
p8
p6
p5
p4
t1
t2
t4
t5
t3 t6
Service Transport OSI en RP: phase connexion
INF6001 Chap 6 19
http://pagesperso-systeme.lip6.fr/Cedric.Besse/IMG/pdf/Cours_Ing.pd
INF6001 Chap 6 20
Modélisation des files
Les files d’attente sont modélisées par le fait qu’une place peut contenir plus d’un jeton Cependant dans les RP de base les jetons dans une place n’ont pas d’ordre
Cas limite:
t1
t2
p1
p2
p3
p1 a un jeton et est capable de tirer t1 un nombre arbitraire de fois; cependant p3 n’a pas de jeton donc un nombre arbitraire de jetons pourra s’accumuler dans p2 sans jamais tirer t2
INF6001 Chap 6 21
Modélisation de files, cas plus normal…
t1
p1
p2
p3
Supposons que t3 tire beaucoup plus rapidement que t1. Si p2 se trouve à être vide, un nombre arbitraire de jetons peut s’accumuler dans p3, cependant dès que p2 aura un jeton, t2 tirera
(symétrique pour t1 et t3)
t2
t3p4
INF6001 Chap 6 22
Poids aux transitions
Les arcs peuvent avoir un poids, ce qui permet d’exprimer concisément des situations plus compliquées Jusqu’à présent, tous les arcs avaient poids 1
2 2
Il faut 2 jetons sur la place de haut pour causer le tir
Réseaux de Petri colorés
Les ‘couleurs’ identifient des types de données différentes
Une place peut contenir des jetons de différents couleurs, p.ex. 1 jeton rouges et 2 verts
Une règle de tirage pourrait être comme suit: Pour tirer, il faut consommer au moins un jeton rouge et un
vert, et le résultat sera trois jetons bleus dans la place suivante
INF6001 Chap 6 23
INF6001 Chap 6 24
Différentes possibilités avec Petri Netsséquence
choixparallélisme
synchronisation
Confusion: P peut faire tirer A ou B (ce dernier avec Q) mais s’il fait tirer A, B devient impossible
A B C
P Q
Fusion
Les trois transitions ne sont pas obligées d’être simultanées, la place a besoin d’un seul jeton pour procéder
B
Q
Priorité/inhibition: le cercle indique que s’il y a un jeton dans Q, la transition B ne peut pas tirer
INF6001 Chap 6 25
Réseau de Petri pour bit alterné
[Tanenbaum]
INF6001 Chap 6 26
Autre bit alterné (problématique dans certains aspects)
BA unidirectionnel Communication directe (synchrone)
entre les deux stations Et sans erreur! DT0 est envoyé et reçu ACK0 est envoyé et reçu DT1 est envoyé et reçu ACK1 est envoyé et reçu Retour au début… t0 remet le jeton dans SS0, car il en
aura besoin pour t2 Cependant ce mécanisme peut causer
accumulation d’un nombre arbitrairement grand de jetons dans DT0 et DT1[Sarikaya]
Récepteur état initial
Émetteur état initial
SS0 RS0
DT0
ACK0
SS1
DT1
ACK1
RS1
t0
t1
t2
p0
p1
p2
p3
p4p5
p6
p7
t3
t4
t5
INF6001 Chap 6 27
Variétés de Réseaux de Petri
Ces idées de base a été développées grandement et nous avons: RP colorés RP temporisés: temps associé aux transitions RP stochastiques RP Markoviens RP numériques RP emboîtés RP orientés objet Etc, etc…
INF6001 Chap 6 28
V&V avec Réseaux de Petri
Un grand nombre de techniques de vérification sont associées aux RP Principalement basées sur la manipulation des vecteurs de marquage et
de matrices reliéesQuestions de vérification
Accessibilité: nous avons vu comment faire l’analyse d’accessibilité avec les RP
n-borné: dans aucune place on ne peut jamais avoir plus de n jetons Vivacité (liveness): une transition est vivace si elle peut être tirée à partir
de l’état initial (directement ou indirectement) Absence de blocage: impossibilité d’arriver à un état final
diwww.epfl.ch/w3lco/pub/racloz/ ps9798/LesProprietes.fm.psCes questions sont adressée avec des algorithmes basés
sur la manipulation des vecteurs de marquage
INF6001 Chap 6 29
Propriétés des RP avec exemples
Borné: qu’aucune place ne puisse avoir un nombre arbitrairement grand de jetons
Vivace: toute transition peut être tirée (directement ou indirectement) à partir de n’importe quel marquage Donc il n’y a pas d’impasse
Réversible si pour toute transition t il existe une transition t’ qui en renverse les effets
C. Girault and R. Valk, Petri Nets for Systems Engineering, Springer Verlag, 2003
INF6001 Chap 6 30
Comment vérifier les différentes propriétés B, L, R?
Technique de base: calculer le graphe de marquage
Exercice: faire ceci pour quelques uns des RP précédents
INF6001 Chap 6 31
Critique des RP
Les RP permettent de représenter des systèmes entiers Notation naturelle pour le parallélisme
Le problème majeur est que pour représenter un système réel il faut remplir des énormes graphes, sans aucune structure!
Aussi difficulté d’en comprendre le fonctionnement Plusieurs méthodes existent pour remédier à cette situation, mais la
notation devient plus complexe et les chercheurs ne sont pas d’accord sur les meilleurs méthodes
Cependant les RP sont utiles comme représentation interne associée à une autre technique qui est utilisée par l’usager P. ex. l’outil Caesar/Aldébaran transforme LOTOS en RP Il y a des outils qui transforment SDL en RP Les méthodes de vérification pour les RP deviennent donc disponibles aux
utilisateurs de SDL, LOTOS, etc. On appelle ceci Petrification!
Présentations la semaine prochaine
INF6001 Chap 6 32
Présentations préliminaires des projets
Yaovi Ahadjitse: Vérification de propriétés du protocole AODV utilisant l’outil Promela-Spin
Nora Belghazi: Utiliser le navigateur Use Case Maps pour illustrer un scenario de conditions routières des véhicules a l’entrée d’une autoroute
Christian Deschamplain: Amélioration d’un protocole de routage ad hoc sans fils pour l’équité des flux et la QdS avec vérifications et tests
Boné Maboudou: Techniques de réduction de l´explosion d´états dans les machines a états finis.
INF6001 Chap 6 33
Pour la semaine prochaine
Chacun doit faire une présentation préliminaire mais informative de son propre projet:
Approx 15 transparents, 20 mins chaqueChacun aussi doit me donner un rapport préliminaire
de la longueur d’approx 5 pages, voir spécifications dans: http://w3.uqo.ca/luigi/INF6001/index.html#_Page_des_projet
s Je peux attendre jusqu’à vendredi 2 mars pour ce rapport
INF6001 Chap 6 34
INF6001 Chap 6 36
Model checking??
INF6001 Chap 6 37
Histoire: logique modale, logique temporelle, modèle
Les concepts de logique modale, logique temporelle et modèle furent développés par les philosophes Prior, Meredith et Kripke autour des années 1960 Mais ils étaient déjà connus en philosophie avant ça
La logique modale est un système logique où on utilise des opérateurs additionnels pour spécifier des modalités P.ex. les opérateurs ‘nécessité’ et ‘possibilité’ en ajout aux opérateurs logiques
conventionnels ‘s’il est nécessaire qu’il pleuve, donc il est possible que je me mouille’
Le même principe est utilisé pour définir autres types d’opérateurs modales: Logique déontique, dont les opérateurs modales sont obligatoire, défendu,
permis, etc. Logique temporelle, dont les opérateurs sont ‘désormais’, ‘finalement’
La logique temporelle fut introduite en informatique par Amir Pnueli en 1977
INF6001 Chap 6 38
Logique: Rappel de Notation
Variables: x, y, z… Constantes: a, b, c… Opérateurs principaux:
Logique propositionnelle: (et) (parfois aussi écrit &, &&..) (ou) (parfois aussi écrit ||) (négation) (parfois aussi écrit ~ ou !) (implication), A B est défini comme A B (équivalence, iff), A B est défini comme A B B A
Logique des prédicats: P(x1, …, xn) (le tuple x1, …, xn a la propriété P) x1,…,xn (il existe x1, …, xn ) x1,…,xn (pour tous les x1, …, xn )
P.ex. x,y z =(x+y,z) ou x,y z (x+y=z) (x (P(x) Q(x)) P(a) ) Q(a) (x (P(x) Q(x)) y(P(y))) z Q(z)
INF6001 Chap 6 39
Dualité entre opérateurs logiques
Lois de dualité (De Morgan): A B = (A B) A B = (A B) x P(x) = x P(x) x P(x) = x P(x)
Ces deux dernières se justifient par les deux premières et le fait que
x P(x) = ( P(a) P(b) P(c)….)
x P(x) = (P(a) P(b) P(c)….)
Si a, b, c… sont tous les éléments du domaine en considération Faisant l’hypotèse que le domaine n’est pas vide!
INF6001 Chap 6 40
Logiques modales
Dans les logiques modales, on ajoute des opérateurs pour exprimer certaines propriétés qui ne peuvent pas être exprimées directement en logique pure
P.ex. nécessité et possibilité (logique modale usuelle)Obligation et permission (logique déontique)Les logiques modales sont caractérisées par le fait
qu’il y a dualité entre ces opérateurs: nécessaire (x) non possible non x obligatoire (x) = non permis non x
INF6001 Chap 6 41
Logique temporelle
Les modalités principales sont: dorénavant, désormais (aussi écrit G) finalement, enfin (aussi écrit F)
Dualité: p = p (s’il fera beau dorénavant, il est faux que finalement il pleuvra!)
p = p (si finalement je serai riche, il est faux que je serai toujours pauvre!)
Et donc aussi (par élimination des doubles négations) p = p p = p
INF6001 Chap 6 42
Assertions sur traces ou runs = exécutions Holzmann, SPIN model checker, Chap. 6
Le modèle de SPIN est un automate fini qui est capable d’exécuter des séquences d’événements
Une exécution (ou run, ou chaîne) est une séquence de transitions d’état correspondant à une exécution de l’automate Les transitions sont de la forme:(si, l, sj)
État initial, étiquette (opération exécutée), état final Les traces sont de la forme
{(s0, l0, s1), (s1, l1, s2), (s2, l2, s3), … }
Ces séquences ont des propriétés qui peuvent être contrôlées (checked) Vrai ou faux
= chaînes
Concept de modèle
Un modèle représente un ‘monde’, un ‘univers’ qui peut ou non avoir certaines propriétés
P.ex. les automates discutés dans le cours sont des modèles de protocoles
INF6001 Chap 6 43
INF6001 Chap 6 44
Un modèle
X=13 X=(X/2)+1 X>0
X=X/2
X≤0
s0
Nous pouvons affirmer des propriétés pour:
Des états: p.ex. à l’état s1, X=13 toujours (invariant)pas besoin de logique temporelle ici
Des chaînes, p.ex. x≤0 ou x≤0, mais pas x≤0 (!)Exercice: contrôlez ceci
s1 s2 s3
X: entier
.État d’acceptation
Une chaîne possible pour ce modèlè
(s0, X=13, s1)(s1, x=(x/2)+1, s2)(s2, x>0, S3) ….
INF6001 Chap 6 45
INF6001 Chap 6 46
Acceptation de chaînes infinies
Dans cette logique, une chaîne est acceptée ssi elle passe un nombre infini de fois par un état d’acceptation Ssi elle reste dans une boucle incluant un état d’acceptation
On n’accepte que des chaînes infinies On ne considère que les propriétés des chaînes
infinies
Concept de satisfaction, symbole╞
Un modèle, ou partie de modèle, peut satisfaire une propriété ou non Il satisfait la propriété ssi la propriété est vraie dans le modèle
P.ex. si on regarde le modèle de la vie d’un sujet A, on pourrait constater que A a été étudiant gradué: propriété satisfaite A est devenu professeur: propriété satisfaite A est devenu riche: propriété non-satisfaite A a vécu dans au moins 4 villes différentes: propriété satisfaite A a vécu dans 10 villes différentes: propriété non-satisfaite
INF6001 Chap 6 47
Exemples de satisfaction en logique
Une formule logique est satisfiable s’il y a une affectation de valeurs de vérité aux variables qui la rend vraie
p q est satisfait si au moins un de p ou q est satisfait (= est vrai)
P.ex. supposons qu’aujourd’hui il fait beau(Il fait beau) (j’ai bien mangé)
est satisfait indépendamment de comment j’ai mangé.Mais (Il fait beau) (j’ai bien mangé)est satisfait seulement si les deux sont satisfaits
INF6001 Chap 6 48
Une propriété peut aussi être satisfaite à un état
À l’état courant, chacun de vous satisfait la propriété: vous êtes étudiant gradué
Dans un état futur, vous pourriez ou non satisfaire la propriété: avoir obtenu la maîtrise
INF6001 Chap 6 49
INF6001 Chap 6 50
Les opérateurs temporels sont des abréviations
Utilisons la notation ╞p pour dire: La chaîne satisfait la propriété p
╞vrai est toujours vrai, pour tout ╞faux est toujours faux, pour tout
╞p est une abréviation pour: pour tous les éléments de , p est vrai dorénavant, désormais
╞p est une abréviation pour: Pour au moins un élément de p est vrai finalement, enfin
INF6001 Chap 6 51
Notation pour les chaînes
i est l’élément i de la chaîne
[i] est la chaîne qui commence à l’élément i
Donc récursivement: 1 [2] 1 2 [3] Etc.
…… σ i
σ[i]
Par rapport à notre exemple
(s0, X=13, s1)(s1, x=(x/2)+1, s2)(s2, x>0, S3)(s3, x=x/2,s2) …
1 = (s0, X=13, s1) [1] = 2 = (s1, x=(x/2)+1, s2) [2] = (s1, x=(x/2)+1, s2)(s2, x>0, S3) (s3, x=x/2,s2) …. 3 =(s2, x>0, S3) [3] = (s2, x>0, S3) (s3, x=x/2,s2) …
Etc.
INF6001 Chap 6 52
INF6001 Chap 6 53
Notation pour les chaînes
i ╞P veut dire que le i-ème élément de la chaîne satisfait la propriété P
i] ╞Q veut dire que la chaîne à partir du i-ème élément satisfait la propriété Q
…… σ i
σ[i]
Deux opérateurs jusqu’à: faible et fort
FAIBLE: Je serai pauvre jusqu’à ce que je serai riche: Définition:
Ou bien je suis déjà riche Ou bien je serai pauvre jusqu’à ce que je serai riche
L’événement attendu pourrait ne jamais se vérifier
FORT: Nous regarderons le spectacle jusqu’à la fin Définition:
Nous regarderons le spectacle jusqu’à la fin dans le sens précédent
Il y aura une fin
INF6001 Chap 6 54
INF6001 Chap 6 55
Définition formelle de jusqu’à faible U
i] ╞ (p U q)
Définition: i ╞ q (i ╞ p i+1] ╞ (p U q) )
σ à partir du ième élém. satisfait p U q
ou bien le i-ème élément de σ satisfait déjà q,
ou le ième élément satisfait p
et le reste de la chaîne satisfait p U q
INF6001 Chap 6 56
Définition formelle de dorénavant
╞ p
Définition: ╞ (p U faux)
1 ╞ faux (1 ╞ p 2] ╞ (p U faux))
Touj. faux Récursivement, p est vrai pour tous les i
et donc il est vrai pour
INF6001 Chap 6 57
Définition formelle de jusqu’à fort U
Le ‘jusqu’à fort’ garantit que q devient vrai
i] ╞ (p U q)
Définition: i] ╞ (p U q) j, i≤j (j ╞ q)
la chaîne satisfait p U q il y aura un σj futur qui satisfiera qi≤j: i présent, j futur
Observez: pour définir U fort nous utilisons l’U faible
INF6001 Chap 6 58
Définition formelle de finalement
╞q
Définition: ╞ (vrai U q)
1] ╞ (vrai U q) j, i≤j (j ╞ q)
[1] ╞ (vrai U q) =1 ╞ q (1 ╞ vrai 2] ╞ (vrai U q) ) =
1 ╞ q 2] ╞ (vrai U q) =
1 ╞ q (2 ╞ q 3] ╞ (vrai U q)) etc. jusqu’à ce que q sera satisfait
N’importe quelle chaîne satisfait vrai!
Importance de U, jusqu’à faible
Il est intéressant d’observer que U est l’opérateur fondamental de la logique temporelle.
Il peut être défini sans utiliser les autres opérateurs, mais les autres opérateurs peuvent être définis en termes de lui.
Comme conséquence des définitions, nous avons:
INF6001 Chap 6 59
(p U q) (p U q)
INF6001 Chap 6 60
Formules fréquemment utilisées
p q réponse, causalitép qUr p implique q jusqu’à r (précédence) p toujours finalement p (progrès vers p)
infiniment souvent pil sera toujours vrai qu’il y aura des p
dans le futur
p finalement toujours p nous allons vers une stabilité
p q corrélation p p finalement devient toujours faux p p deviendra faux au moins une fois
encore il sera toujours vrai que p sera faux dans un futur
La différence…
riche(L) Dorénavant, il y aura toujours un futur dans lequel L sera
riche La richesse reviendra toujours à L
(il pourra cependant être non-riche de temps en temps)
riche(L) Il y aura un moment à partir duquel L sera toujours riche
INF6001 Chap 6 61
INF6001 Chap 6 62
Équivalences utiles (exercice: en prouver quelques unes)
Équivalent à
(p U q) (q) U (p q)
(p U q) (q) U (p q)
(p q) p q
(p q) p q
p U (q r) (p U q) (p U r)
(p q) U r (p U r) (q U r)
p U (q r) ( p U q) (p U r)
(p q) U r (p U r) (q U r)
(p q) p p
(p q) p q
pp
pp
Lois d’implication http://www.pst.informatik.uni-muenchen.de/lehre/WS0304/tl/Vorlesung/46-1.pd
INF6001 Chap 6 63
Lois de réflexivité p p (si p dorénavant, donc p maintenant)
p p (si p maintenant, donc enfin p)
Implications entre opérateurs p pp p
Distributivité faible (p q) (p q)p v q (p v q)( p q) (p q) (p q) p q
INF6001 Chap 6 64
Opérateur ‘prochain état’ (aussi écrit X)
i] ╞ p
Définition: i+1 ╞ p
est vrai dans le prochain état Attention: ceci est le prochain état par rapport à l’état courant,
pas à un état suivant par rapport à un autre operateur comme
…… i i+1
σ[i]
INF6001 Chap 6 65
Une façon plus intuitive de définir
Par raisonnement récursif, il est possible de prouver que
╞ p ssi i (i ╞ p)Pour faire un peu de pratique, voyons comment ceci fonctionne pour un de la forme: 1
1 ╞ p =1 ╞(p U faux) =1 ╞ faux (1 ╞p ╞(p U faux) ) = (étant donné que 1 ╞ faux est faux)
1 ╞p ╞(p U faux) =1 ╞p (2 ╞ faux (2 ╞p ╞(p U faux) )) = (étant donné que 2 ╞ faux est faux)
1 ╞p (2 ╞p ╞(p U faux) ) = . . .1 ╞p 2 ╞p 3 ╞p …etc. donc tous les satisfont p
INF6001 Chap 6 66
Une façon plus intuitive de définir
Par raisonnement récursif, il est aussi possible de prouver que
╞ p ssi i (i ╞ p)Le raisonnement est semblable au précédent:
s’en convaincre comme exercice
Dualité de
p = p (il sera sec dorénavant, ssi il est faux que finalement il pleuvra!)
p = p (finalement je serai riche ssi il est faux que je serai toujours pauvre!)
INF6001 Chap 6 67
INF6001 Chap 6 68
Dualité de
Il est maintenant facile de prouver que , sont duales, comme conséquence de la dualité de ,
p = i (i ╞ p) =
¬ i ¬ (i ╞ p) = (dualité de et )
¬ ¬ p
La preuve de ╞ ¬¬p = ╞ p est semblable
INF6001 Chap 6 69
Logiques temporelles linéaires et à branchements
La logique temporelle que nous venons d’étudier est dite ‘logique temporelle linéaire’
Car elle est basée sur l’hypothèse qu’il n’y a qu’un seul futurOn étudie aussi les logiques temporelles à branchements,
basées sur l’hypothèse qu’il y a plusieurs futurs CTL, Computational Tree Logic Nous avons des opérateurs pour exprimer:
Dans tout futur possible, p sera vrai Il y a un futur dans lequel p sera vrai
Il y a aussi des logiques pour exprimer le passé: Si p a été vrai dans un passé, il devra être vrai dans un futur
Temporal logic with past
INF6001 Chap 6 70
Conclusion sur la logique temporelle
Elle est utile pour exprimer les propriétés de systèmes qui évoluent dans le temps Comme tous les systèmes réels
Les vérificateurs de modèles temporels (temporal logic model checkers) l’utilisent L’utilisation de ces concepts dépasse grandement
l’ingénierie des protocole Il y a par ex. des applics à la vérif du matériel, circuits etc.
Exercice
L’expression p q dit que si enfin p se vérifie, il y aura aussi un q sans ordre entre p et q
Donc une question pourrait être si p q implique q p ou si les deux sont équivalents
La réponse est négative, car p q = p q
Ceci est vrai dans le cas où p est dorénavant faux ou q se vérifie enfin
q p = q p Ceci est vrai dans le cas où q est dorénavant faux ou p se
vérifie enfinPour bien comprendre, remplacez p et q par des événements
concretsINF6001 Chap 6 71
Automate Büchi (v. prochain cours)
Utilisant l’outil http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/index.php voici l’automate de Büchi de p q
Celui pour q p est identique après échange de p et q
INF6001 Chap 6 72
Cependant …
(p q) (( p q) (qp))
Ceci est vrai, mais il n’a rien à faire avec la logique temporelle, car
(p q) ((p q) (qp))
Est aussi vrai : il est une tautologie
INF6001 Chap 6 73
INF6001 Chap 6 74
Autres symboles de logique et théorie des ensembles
Je mets ici quelques symboles utiles, car il ne se trouvent toujours pas dans les tableaux de symboles fournis par Word.
Cette diapo n’est pas nécessairement reliée au cours ∩∈ ∉ ∅ ⊆ ⊂ ∪ ┬ ┴├
INF6001 Chap 6 75
