[MaLo] Übung 9

[JanTenner]

Hallo, hab mal ne allgemeine Frage zur Modallogik: Wenn in einem Transitionssystem von einem Zustand X aus keine a-Kante rausgeht, ist dann die Formel [a]P für dieses X erfüllt? (P sei ein anderer, mit der _einstelligen_ Relation markierter Zustand). Ich meine, dass das in der KGÜ so gesagt wurde. Könnte mir jemand erklären, warum das so ist? Schlie´ßlich geht ja von X nichts weg, wie kann man dann also trotzdem mit allen nichtvorhandenen a-Transitionen in P landen?

Hm, hat das damit zu tun, dass die leere Menge immer ne Teilmenge von P ist?!

Danke!

[MartinL]

Im Script steht ja wie du [a]P in Prädikatenlogik übersetzt. Vielleicht wirds damit klarer.

Sei also die Formel, die an einem Knoten x gelten muss, damit obige Modallogikformel dort gilt.
Dann ist
Für den Fall, dass es keine ausgehende a-Kante gibt ist das natürlich immer erfüllt.

Ein anderer weg dies einzusehen ist direkt über die Definition der Box.

Dazu sagt das Script:


Also: Die Menge der Knoten zu denen eine a-Kante geht, soll eine Teilmenge der Knoten sein, an denen die Bed. wahr ist in unserem Transitionssystem. Und die leere Menge ist halt Teilmenge von jeder Menge.

Gruß,

Martin

[fw]

wie kann man dann also trotzdem mit allen nichtvorhandenen a-Transitionen in P landen?

Mit allen vorhandenen meinst du. "Für alle a-Transitionen landet man in P", ist doch trivialerweise erfüllt, wenn es garkeine a Transitionen gibt. Die einzige Möglichkeit diese Aussage zu falsifizieren ist doch, dass es eine a Transition gibt mit der man nicht in P landet.

Vergleich das mal mit Implikationen.. "Für alle A, die B erfüllen, gilt C" ist eine Tautologie, wenn es garkeine A gibt, die B erfüllen (selbst dann, wenn C unerfüllbar ist!).

[JanTenner]

Ok, danke.

Mal ne Frage zur 1b: Fehlt da bei den E-Relationen nicht ein Index, z.B. a? In Transitionssystemen sind die Kanten doch beschriftet, oder soll man davon ausgehen, dass da eine beliebige Beschreiftung stehen kann?!

[tobias]

Die Beschriftung ist in diesem Fall irrelevant. Es soll einfach nur ausgesagt werden, dass es irgendeine Kante gibt. Exy heißt also es gibt (irgend)eine Kante zwischen x und y.

[PsY]

ich hab bei der 3) 8 bisimilare paare, kann das jemand bestätigen?

MfG

PsY

[Tim]

ja at psy

[PsY]

noch ne frage zu FO-Formel, dürfen wir etwas benutzen wie , also sinngemäß "es existiert genau ein" ?

[Tim]

ich würde "nein" sagen, aber diesen Quantor brauchst du auch nicht.

[PsY]

-> falscher Dampfer...

[Tim]

denke erstens, dass du auf dem falschen dampfer bist, da man sowas mit den für uns definierten regeln der FO nicht ausdrücken kann, meiner meinung nach
und zweitens, dass solche äußerungen knapp an "lösung verraten" dran sind

[PsY]

gut, war vlt. bisl zuviel des guten, habs dann ma editiert n tip hättest nicht zufällig?

[Tim]

PN ist abgeschickt

[JanTenner]

Hab mal ne Frage zu Aufgabe 3a, wegen der Formeln, die man abgeben soll:
In der KGÜ-Aufgabe hatten wir ja nur einen Graphen gegeben, folglich war das Uiversium von K gleich dem Universum von K', und wir konnten Formeln der Art <a>1 angeben. Nur wie macht man das hier? in 3a wäre das ja für K ok, aber in K' gibts ja den Zustand 3 garnicht, sonder der sollte da 3' heißen. Gilt dann trotzdem, dass, wenn ich mich aufs Universum von K beschränke, so dass die ML-Formel für K erfüllt ist, dass dann automatisch die Formel für K' unerfüllbar ist (da es da ja nur x'-Zustände gibt).

Danke!

[Tim]

sag wir mal du hast ne a-kante in K die in K' nicht vorhanden ist, dann kannst du sie durch <a>1 trennen, wenn du allerdings in K' ne a-kante hast die in K nicht vorhanden ist, kannst dies mit "nicht"<a> verdeutlichen

also genau so als hättest du nur ein Transitionssystem