Modallogik/Gerichteter Graph/Einführung/Textabschnitt

Für die Modelltheorie der Modallogik benötigen wir gerichtete Graphen. Dies ist mathematisch betrachtet einfach eine zweistellige Relation auf einer Menge.

Definition

Ein gerichteter Graph ist eine Menge ${}M$ versehen mit einer fixierten Relation ${}R\subseteq M\times M$.

Die Menge der Punkte ${}x\in M$ nennt man auch die Knoten des Graphen und man sagt, dass ein Pfeil von ${}x$ nach ${}y$ geht, wenn ${}(x,y)\in R$ ist. In dieser Weise werden gerichtete Graphen veranschaulicht. Ein Pfeil von einem Knoten zu sich selbst heißt Schleife.

Im Kontext von Ordnungsrelationen und Äquivalenzrelationen haben wir schon die Eigenschaften reflexiv, symmetrisch, transitiv kennengelernt. Einen symmetrischen gerichteten Graphen nennt man auch einen ungerichteten Graphen. In diesem Fall nennt man einen verbindenden Pfeil eine Kante. Wir besprechen einige weitere Begrifflichkeiten und Eigenschaften.

Definition

Es sei ${}(M,R)$ ein gerichteter Graph. Zu einer Teilmenge ${}T\subseteq M$ nennt man

${}\operatorname {Vorg} {\left(T\right)}={\left\{x\in M\mid {\text{ es gibt }}y\in T{\text{ mit }}xRy\right\}}\,$

die Vorgängermenge zu ${}T$.

Definition

Es sei ${}(M,R)$ ein gerichteter Graph. Zu einer Teilmenge ${}T\subseteq M$ nennt man

${}\operatorname {Nachf} {\left(T\right)}={\left\{z\in M\mid {\text{ es gibt }}y\in T{\text{ mit }}yRz\right\}}\,$

die Nachfolgermenge zu ${}T$.

Ein Knoten ohne Nachfolger, also ohne abgehenden Pfeil (also auch keine Schleife), heißt Sackgasse.

Definition

Eine Relation auf einer Menge ${}M$ heißt euklidisch, wenn zu ${}x,y,z\in M$ mit ${}xRy$ und ${}xRz$ stets ${}yRz$ gilt.