[MaLo] Blatt 9

[jim]

Mal ein Beispiel für die A3b)

Das geht nicht, ich habe zwei Kripkestrukturen
K:= 4 Knoten x, a, y, z mit gerichteten Kanten Exa, Eyz
K' := 3 Knoten x', a', y' mit gerichteter Kante Ex'a.

K, x |= Formel
K', x' !|= Formel
und K, x ~ K', x'

oder?

Ich glaub du brauchst bei K noch eine Kante Ezz damit K,x |= Formel gilt, oder? :-/

[nathan99]

Mhm... warum denn? Ich finds so eigentlich bisimilar, und einmal finde ich, ist die Formel wahr, einmal falsch.

[fw]

Mhm... warum denn? Ich finds so eigentlich bisimilar, und einmal finde ich, ist die Formel wahr, einmal falsch.

du hast auch recht, dein gegenbeispiel funktioniert schon so wie du es gegeben hast imho (weil eben die für den knoten y' in K' weder gilt das eine kante von x rein kommt noch das eine raus geht)

[Alexander Urban]

EDIT: Urgs, Fehler gefunden.

[nathan99]

Bei der A5a

i) P -> <>P

heisst doch, dass ich von einem Knoten in dem P gilt, eine Kante zu einem Knoten haben muss in dem wieder P gilt...
Das sind also alle Graphen, in denen dass für alle Knoten gilt.
Jetzt wurde mir aber eben "gesagt", damit wären alle Graphen gemeint, die eine Schlaufe haben... weil "irgendwie alle möglichen P's gleichzeitig" gemeint sind.

Wieso das?

[Lupus]

Keine Ahnung - hört sich aber falsch an. Bei mir sind das alle Graphen, bei denen ich von jedem Knoten, der P erfüllt, einen unendlich langen P-Weg laufen kann. (Also einen Weg, auf dem nach jedem Schritt P gilt)

[fw]

weil "irgendwie alle möglichen P's gleichzeitig" gemeint sind. Wieso das?

Weil das in der Aufgabenstellung so definiert ist.. Jede Formel der Menge, an jedem Knoten für jedes P \subseteq V.. Schau nochmal nach was da steht!

[nathan99]

Das hab ich doch gesagt: Jeder P-Knoten hat einen P-Nachfolger. Dass der wieder einen P-Nachfolger hat, ist obligatorisch.
Dass man dadurch einen unendlichen P-Weg hat, ist auch klar.



Aber mir gegenüber behauptet jemand steif und fest (und gewöhnlich hat der Schweinepriester recht! ), damit wären alle Graphen gemeint, in denen jeder Knoten eine Schlaufe zu sich selber hat.

weil "irgendwie alle möglichen P's gleichzeitig" gemeint sind. Wieso das?

Weil das in der Aufgabenstellung so definiert ist.. Jede Formel der Menge, an jedem Knoten für jedes P \subseteq V.. Schau nochmal nach was da steht!

Naja du meinst den zweiten "Punkt", oder?

[fw]

Aber mir gegenüber behauptet jemand steif und fest (und gewöhnlich hat der Schweinepriester recht! 8) :wink: ), damit wären alle Graphen gemeint, in denen jeder Knoten eine Schlaufe zu sich selber hat

er hat auch diesmal recht.. warum das so ist wurde weiter oben doch schon erklärt

[nathan99]

Weiter oben?
Mhm... ich kann hier in diesem Thread und in den anderen nur "ist so" finden .
Du meinst das im zweiten Punkt der Aufgabenstellung. Aber warum schliesst das meine "Interpretation" der Graphenklasse aus?

Vermutlich hast du jetzt das Gefühl ich stelle mich dumm an - aber so verstehe ich nunmal die Aufgabe...

i) P -> <>P
ist doch erstmal in ALLEN Graphen erfüllt, in denen man von jedem P-Knoten einen P-Knoten erreichen kann.
Und warum axiomatisiert das nicht genau diese Menge von Graphen?
Weil der zweite Punkt der Aufgabenstellung einige Graphen ausschliesst?
Warum tut der das? Das verstehe ich nicht.

Wenn ich den Graphen:

X_p <-> Y_p
betrachte, dann erfüllt der diese Modalformel.
Axiomatisiert wird der nicht, weil es ein P \subseteq V gibt, wodurch (V,E, P) !|= füralle Formeln.
Joa, das P ist doch "fest" für diesen Graphen, oder?
Ok, die Aufgabe meint offenbar an irgendeiner Stelle, dass ich bei einem Graphen die "P"s beliebig verteilen darf, richtig? Dann könnte ich das so basteln, dass der Graph nicht axiomatisiert wird. Bei den Graphen, bei denen jeder eine Schlaufe hat, geht das net.
RICHTIG?

[fw]

i) P -> <>P
ist doch erstmal in ALLEN Graphen erfüllt, in denen man von jedem P-Knoten einen P-Knoten erreichen kann.
Und warum axiomatisiert das nicht genau diese Menge von Graphen?
Weil der zweite Punkt der Aufgabenstellung einige Graphen ausschliesst?
Warum tut der das? Das verstehe ich nicht.

Die Aussage soll für alle möglichen P gelten!

Angenommen du hast eine Kante von Knoten v nach Knoten w, aber keine Kante von Knoten v nach Knoten v selbst.. Dann wähle ich einfach P={v}, dann gilt zwar der linke Teil der Implikation an Knoten v, der Rechte aber nicht (<>P gilt nicht weil P nicht an w gilt), somit ist die Implikation falsch und die Formel nicht erfüllt, also gehört der von dir genannte Graph nicht zur von der Formelmenge axiomatisierten Klasse von Graphen..

Schau dir die Definition nochmal ganz genau an..

Für alle Knoten
Für alle Formeln des Axiomensystems
Für alle möglichen P!

[kb]

Ich glaube er hatte es verstanden, so hab ich jedenfalls das "RICHTIG?" interpretiert.

heisst doch, dass ich von einem Knoten in dem P gilt, eine Kante zu einem Knoten haben muss in dem wieder P gilt...
Das sind also alle Graphen, in denen dass für alle Knoten gilt.

joah, so hast du quasi nur die Formel "vorgelesen", aber keine "Klasse" von Graphen genannt.

[MartinR]

Die Sache ist halt, dass die P-Belegung nicht im Graph eingebaut ist. Stell's dir wieder als ein Spiel vor, in dem du jemanden überzeugen willst, dass das die-und-die Art Graphen axiomatisiert und der dir das durch seine P-Belegung kaputt machen will.
bei deinem Beispiel gibst du ihm also
X <-> Y und er sagt, dass nur X P hat. Bäm, kaputt. Deswegen geht des nur mit Schlaufen.
Keine Ahnung, ob das noch jemandem was bringt jetzt