Bisimulace: Porovnání verzí

Řádek 1: Řádek 1:
 
=== Definice ===
 
  
 
Bisimulace je binární [[Ekvivalence|relace ekvivalence]] mezi dvěma sémantickými modely. <br />
 
Bisimulace je binární [[Ekvivalence|relace ekvivalence]] mezi dvěma sémantickými modely. <br />
Řádek 17: Řádek 15:
 
Ř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 />
Řádek 30: Řádek 28:
 
== Zdroje ==
 
== Zdroje ==
  
# Blackburn P., de Rijke M., Venema Y. 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 P. 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]]

Verze z 14. 9. 2014, 19:29

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).