Bisimulace: Porovnání verzí

Řádek 10: Řádek 10:
 
Když <math>B(w,x)</math>, pak musí platit následující tři podmínky:
 
Když <math>B(w,x)</math>, pak musí platit následující tři podmínky:
 
# atomická harmonie
 
# atomická harmonie
     $$\forall p (w {\Vdash_1} p \Longleftrightarrow x {\Vdash_2} p)$$
+
     :<math>\forall p (w {\Vdash_1} p \Longleftrightarrow x {\Vdash_2} p)</math>
 
# "tam"
 
# "tam"
     $$w{R_1}w' \Rightarrow \exists x'(x{R_2}x' \wedge B(w', x'))$$Relace
+
     :<math>w{R_1}w' \Rightarrow \exists x'(x{R_2}x' \wedge B(w', x'))</math>
 
# "zpět"  
 
# "zpět"  
     $$x{R_2}x' \Rightarrow \exists w'(w{R_2}w' \wedge B(w', x'))$$
+
     :<math>x{R_2}x' \Rightarrow \exists w'(w{R_2}w' \wedge B(w', x'))</math>
  
Řekneme, že $(\mathbb{M}_1,w)$ a $(\mathbb{M}_2,x)$ jsou '''bisimilární''', když existuje bisimulace B taková, že $B(w,x)$.
+
Řekneme, že <math>(\mathbb{M}_1,w)</math> a <math>(\mathbb{M}_2,x)</math> jsou '''bisimilární''', když existuje bisimulace B taková, že <math>B(w,x)</math>.
 
      
 
      
 
=== Vlastnosti bisimulace ===
 
=== Vlastnosti bisimulace ===
  
 
* je '''reflexivní''' <br />
 
* je '''reflexivní''' <br />
   Identická relace je bisimulace z $\mathbb{M}$ do $\mathbb{M}$. <br />
+
   Identická relace je bisimulace z <math>\mathbb{M}</math> do <math>\mathbb{M}</math>. <br />
   $Id=\{(x,x)|x\in W\}$, tudíž $\mathbb{M}, x \underline{\leftrightarrow} \mathbb{M}, x$
+
   <math>Id=\{(x,x)|x\in W\}</math>, tudíž <math>\mathbb{M}, x \underline{\leftrightarrow} \mathbb{M}, x</math>
 
* je '''symetrická''' <br />
 
* je '''symetrická''' <br />
   Když $B\subseteq {W_1}\times{W_2}$ je bisimulace z $\mathbb{M}_1$ do $\mathbb{M}_2$, tak $\breve{B}=\{(x,w)|B(w,x)\}$ je bisimulace z $\mathbb{M}_2$ do $\mathbb{M}_1$.
+
   Když <math>B\subseteq {W_1}\times{W_2}</math> je bisimulace z <math>\mathbb{M}_1</math> do <math>\mathbb{M}_2</math>, tak <math>\breve{B}=\{(x,w)|B(w,x)\}</math> je bisimulace z <math>\mathbb{M}_2</math> do <math>\mathbb{M}_1</math>.
 
* je '''tranzitivní''' <br />
 
* je '''tranzitivní''' <br />
   Když $B_1$ je bisimulace z $\mathbb{M}_1$ do $\mathbb{M}_2$ a $B_2$ je bisimulace z $\mathbb{M}_2$ do $\mathbb{M}_3$, pak $ B_1 \circ B_2 =\{({w_1},{w_2})|\exists{w_2}({w_1}{B_1}{w_2}\wedge {w_2}{B_2}{w_3})\}$ je bisimulace.
+
   Když <math>B_1</math> je bisimulace z <math>\mathbb{M}_1</math> do <math>\mathbb{M}_2</math> a <math>B_2</math> je bisimulace z <math>\mathbb{M}_2</math> do <math>\mathbb{M}_3</math>, pak <math>B_1 \circ B_2 =\{({w_1},{w_2})|\exists{w_2}({w_1}{B_1}{w_2}\wedge {w_2}{B_2}{w_3})\}</math> je bisimulace.
  
 
== Zdroje ==
 
== Zdroje ==

Verze z 10. 9. 2014, 13:00


Definice

Bisimulace je binární relace ekvivalence mezi dvěma sémantickými modely.

Mějme dva Kripkovské modely a . Řekneme, že je relace bisimulace mezi a , pokud:

Když , pak musí platit následující tři podmínky:

  1. atomická harmonie
   :
  1. "tam"
   :
  1. "zpět"
   :

Řekneme, že a jsou bisimilární, když existuje bisimulace B taková, že .

Vlastnosti bisimulace

  • je reflexivní
 Identická relace je bisimulace z  do . 
, tudíž
  • je symetrická
 Když  je bisimulace z  do , tak  je bisimulace z  do .
  • je tranzitivní
 Když  je bisimulace z  do  a  je bisimulace z  do , pak  je bisimulace.

Zdroje

  1. Blackburn P., de Rijke M., Venema Y. Modal Logic. Cambridge University Press. (2002).
  2. Arazim P. Relace bisimulace (bakalářská práce). (2009).