Bisimulace: Porovnání verzí

 
Řádek 1: Řádek 1:
 
+
'''Bisimulace''' je binární [[Ekvivalence|relace ekvivalence]] mezi dvěma sémantickými modely. <br /><br />
Bisimulace je binární [[Ekvivalence|relace ekvivalence]] mezi dvěma sémantickými modely. <br />
+
Mějme dva [[Kripkovská sémantika|Kripkovské modely]] <math>\mathbb{M}_1 = (W_1, R_1, V_1)</math> a <math>\mathbb{M}_2=(W_2, R_2, V_2)</math>.<br />
 
+
Řekneme, že <math>B\subseteq {W_1} \times {W_2}</math> je relace bisimulace mezi <math>\mathbb{M}_1</math> a <math>\mathbb{M}_2</math>, pokud: <br /><br />
Mějme dva [[Kripkovská sémantika|Kripkovské modely]] <math>\mathbb{M}_1 = (W_1, R_1, V_1)</math> a <math>\mathbb{M}_2=(W_2, R_2, V_2)</math>.
 
Řekneme, že <math>B\subseteq {W_1} \times {W_2}</math> je relace bisimulace mezi <math>\mathbb{M}_1</math> a <math>\mathbb{M}_2</math>, pokud: <br />
 
 
 
 
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
Řádek 14: Řádek 11:
  
 
Řekneme, že <math>(\mathbb{M}_1,w)</math> a <math>(\mathbb{M}_2,x)</math> jsou '''bisimilární''', když existuje bisimulace <math>B</math> taková, že <math>B(w,x)</math>.
 
Řekneme, že <math>(\mathbb{M}_1,w)</math> a <math>(\mathbb{M}_2,x)</math> jsou '''bisimilární''', když existuje bisimulace <math>B</math> taková, že <math>B(w,x)</math>.
   
 
 
== Vlastnosti bisimulace ==
 
== Vlastnosti bisimulace ==
 
 
* je '''reflexivní''' <br />
 
* je '''reflexivní''' <br />
 
   Identická relace je bisimulace z <math>\mathbb{M}</math> do <math>\mathbb{M}</math>. <br />
 
   Identická relace je bisimulace z <math>\mathbb{M}</math> do <math>\mathbb{M}</math>. <br />
Řádek 27: Řádek 22:
  
 
== Zdroje ==
 
== Zdroje ==
 
 
# BLACKBURN Patrick, de RIJKE Maarten, VENEMA Yde. Modal Logic. Cambridge University Press. (2002).
 
# BLACKBURN Patrick, de RIJKE Maarten, VENEMA Yde. Modal Logic. Cambridge University Press. (2002).
 
# [https://is.cuni.cz/webapps/zzp/detail/74476/ ARAZIM Pavel. Relace bisimulace (bakalářská práce). (2009).]
 
# [https://is.cuni.cz/webapps/zzp/detail/74476/ ARAZIM Pavel. Relace bisimulace (bakalářská práce). (2009).]
  
 
[[Kategorie: Modální logiky]]
 
[[Kategorie: Modální logiky]]

Aktuální verze z 16. 9. 2014, 04:09

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:

  • atomická harmonie
   
  • "tam"
   
  • "zpět"
   

Řekneme, že a jsou bisimilární, když existuje bisimulace 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 Patrick, de RIJKE Maarten, VENEMA Yde. Modal Logic. Cambridge University Press. (2002).
  2. ARAZIM Pavel. Relace bisimulace (bakalářská práce). (2009).