[MaLo] Blatt 9 A5 b)

[AGo]

Hallo miteinander,

hat sich schon jemand mit dieser Aufgabe befasst?
Mir ist nich ganz klar wie man das "formal" beweisen sollte, da der Zusammenhang ja quasi "intuitiv" besteht. Meine Idee ist die ML formel in eine FO Formel umzuformen, aber bin mir nich sicher ob das so Sinn der Aktion ist?

[Friedrich]

Nein, das ist nicht Ziel der Aufgabe.
Du solltest zeigen, dass jeder transitive Graph tatsächlich Modell jeder beliebigen Formel der gegebenen Gestalt ist und andersherum, dass ein nicht transitive Graph mindest ein Formel "verletzt"

[skip]

Was sind eigentlich "transitive" Graphen?

[Friedrich]

Darstellung als gerichteter Graph

Jede beliebige Relation R auf einer Menge M kann als gerichteter Graph aufgefasst werden (Beispiel siehe oben). Die Knoten des Graphen sind dabei die Elemente von M. Vom Knoten a zum Knoten b wird genau dann eine gerichtete Kante (ein Pfeil a \longrightarrow b) gezogen, wenn a R b gilt.

Die Transitivität von R lässt sich im Graphen nun so charakterisieren: Wann immer zwei Pfeile aufeinanderfolgen (a \longrightarrow b \longrightarrow c), gibt es auch einen Pfeil, der Anfangs- und Endknoten direkt verbindet (a \longrightarrow c).

siehe http://de.wikipedia.org/wiki/Transitivi ... Mathematik)

[fw]

oder, um es einfacher zu erklären: ein transitiver graph ist ein graph dessen kantenrelation transitiv ist..

ich denke was eine transitive relation ist wird jeder wissen, oder nicht?