Monadische Prädikatenlogik zweiter Stufe

Die monadische Prädikatenlogik zweiter Stufe, nach dem englischen monadic second order logic auch kurz MSO genannt, ist ein Begriff aus dem Bereich der mathematischen Logik. Es handelt sich um dasjenige Fragment der Prädikatenlogik zweiter Stufe, das nur die einstelligen Prädikate betrachtet.

Definition

Zu einer Signatur $\sigma$ betrachte die Sprache $L_{II}^{\sigma }$ der Prädikatenlogik zweiter Stufe. Die Formeln der MSO sind genau diejenigen $L_{II}^{\sigma }$-Formeln, bei denen alle vorkommenden Relationsvariablen einstellig sind. Damit ist die Syntax der MSO beschrieben. Die Semantik ist die Einschränkung der Semantik der Prädikatenlogik zweiter Ordnung.

Beachte, dass durchaus mehrstellige Relationen in der MSO vorkommen können, nur müssen diese dann Bestandteil der Signatur sein. Über diese kann nicht quantifiziert werden.

Da einstellige Relationen in jeder Interpretation Teilmengen der Grundmenge sind, kann man in der MSO also Aussagen über alle Teilmengen der zugehörigen $\sigma$-Strukturen aufstellen und über diese beliebig quantifizieren. Man kann nicht über Funktionssymbole oder mehrstellige Relationssymbole quantifizieren.

Beispiele

Prädikatenlogik erster Stufe

Jeder Ausdruck der Prädikatenlogik erster Stufe ist ein MSO-Ausdruck, denn ein solcher enthält überhaupt keine Relationsvariablen, insbesondere also keine mehrstelligen.

Induktionsaxiom

Die Peano-Arithmetik kann bekanntlich mit der Signatur $\sigma =\{0,s\}$ beschrieben werden, wobei 0 eine Konstante und $s$ ein Funktionssymbol ist. Die Konstante wird als Nullelement und s als Nachfolger-Funktion interpretiert. Das sogenannte Induktionsaxiom

$\forall X((X0\land \forall x(Xx\rightarrow Xsx))\rightarrow \forall x\,Xx)$

ist offenbar ein MSO-Satz.

Zusammenhang von Graphen

Ist $\sigma =\{E\}$ für ein zweistelliges Relationssymbol $E$, so ist jede $\sigma$-Struktur ein Graph $G$, wobei das $G$ das Universum, das heißt die Grundmenge, der Struktur ist und die Interpretation $E^{G}$ von $E$ die Kantenrelation auf $G$ ist. Dann ist

$\forall X((\exists x\,Xx\land \exists x\,\neg Xx)\rightarrow \exists x\exists y\,(Xx\land \neg Xy\land Exy))$

ein syntaktisch korrekter MSO-Ausdruck, denn die einzige vorkommende Relationsvariable $X$ ist einstellig. Das zweistellige Relationssymbol $E$ gehört zur Signatur und ist daher keine Relationsvariable. Die Semantik dieses Ausdrucks lautet: Für jede Teilmenge ($\forall X$) gilt: wenn die Teilmenge nicht leer ist ($\exists x\,Xx$) und auch ihr Komplement nicht leer ist ($\exists x\,\neg Xx$), dann gibt es zwischen ihr und ihrem Komplement eine Kante ($\exists x\exists y(Xx\land \neg Xy\land Exy))$). Das ist offenbar äquivalent zum Zusammenhang des Graphen und wir halten fest, dass man in der MSO den Zusammenhang von Graphen beschreiben kann. In der Prädikatenlogik erster Stufe ist das nicht möglich, siehe Lokalität (Logik), so dass sich MSO durch dieses Beispiel als echt ausdrucksstärker erweist.

Gerade Anzahl von Elementen

Für $\sigma =\emptyset$ gibt es keinen MSO-Satz, der auf einer als endlich vorausgesetzten Menge ausdrückt, dass diese geradzahlig ist. In der Prädikatenlogik zweiter Stufe ist das aber möglich, indem man zum Beispiel ausdrückt, dass es eine Teilmenge $X$ gibt und eine bijektive Funktion von $X$ auf ihr Komplement:

$\exists X\,\exists Y\,(''Y{\text{ ist Funktion}}''\,\land \,''X{\text{ ist Definitionsbereich von }}Y''\,\land \,''\neg X{\text{ ist Wertebereich von }}Y''\,\land \,''Y{\text{ ist bijektiv}}''\}$,

wobei klar ist, dass die in Apostrophen eingeschlossenen Teilsätze sogar in der Prädikatenlogik erster Stufe formulierbar sind. Da hier die zweistellige Relationsvariable $Y$ verwendet wird, handelt es sich nicht um einen MSO-Satz. Dieses Beispiel zeigt, dass die Prädikatenlogik zweiter Stufe echt ausdrucksstärker als MSO ist.

MSO auf Wörtern

Modelle von Wörtern

Die monadische Prädikatenlogik zweiter Stufe eignet sich zur Formulierung von Aussagen über Wörtern über einem endlichen Alphabet $\Sigma$. Dazu verwenden wir als Signatur $\sigma =\{<,P_{a},P_{b},\ldots \}$, wobei $a,b,\ldots$ die Zeichen des Alphabets sind und wir formulieren, dass < eine lineare Ordnung auf dem Universum ist und die $P_{a},P_{b}\ldots$ eine Partition des Universums bilden.

$\forall x\,\neg (x<x)\,\land \,\forall x\forall y\forall z\,(((x<y)\land (y<z))\rightarrow (x<z))\,\land \,\forall x\forall y\,((x=y)\lor (x<y)\lor (y<x))$

drückt die lineare Ordnung aus, und

$\forall x\,((P_{a}x\lor P_{b}x\lor P_{c}x)\land \neg (P_{a}x\land P_{b}x)\land \neg (P_{a}x\land P_{c}x)\land \neg (P_{b}x\land P_{c}x))$

drückt die Partitionseigenschaft aus.

Ein endliches Universum können wir dann als isomorph zu $\{1,2,\ldots ,n\}$ annehmen, wobei < als die natürliche Ordnung interpretiert wird und $P_{a}i$ als an $i$-ter Stelle steht ein a, entsprechend für $P_{b}i$ und so weiter.

Ist etwa $\Sigma =\{a,b,c\}$, so definiert das Wort $s=aabcbca$ eine $\{<,P_{a},P_{b},P_{c}\}$-Struktur $M_{s}$ auf dem Universum $\{1,2,3,4,5,6,7\}$ mit den Interpretationen $\{1,2,7\}$ für $P_{a}$, $\{3,5\}$ für $P_{b}$, $\{2,4\}$ für $P_{c}$ und der natürlichen Ordnung für <. Die Wörter aus $\Sigma ^{*}$, das heißt die endlichen Zeichenketten über dem Alphabet $\Sigma$, sind in diesem Sinne genau die $L_{II}^{\sigma }$-Modelle.

MSO-Definierbarkeit

Man kann nun mittels MSO-Ausdrücken Teilmengen solcher Zeichenketten beschreiben. Ist $\Phi$ ein MSO-Satz, das heißt eine MSO-Formel ohne freie Variablen, so ist

$L(\Phi ):=\{s\in \Sigma ^{*}|\,M_{s}\vDash \Phi \}$

die Menge (Sprache) aller Wörter, die Modell für $\Phi$ sind, das heißt die $\Phi$ erfüllen. Eine Sprache dieser Form heißt MSO-definierbar.

So können wir zum Beispiel die Sprache aller Zeichenketten über $\Sigma =\{a,b,c\}$, die eine gerade Anzahl $a$'s enthält, wie folgt beschreiben:

$\Phi =\exists X\exists Y\,{\big (}\forall x((P_{a}x\leftrightarrow (Xx\lor Yx))\land \neg (Xx\land Yx))$

$\land \exists x(Xx\land \forall y\,(y<x\rightarrow \neg P_{a}x))$

$\land \exists x(Yx\land \forall y\,(x<y\rightarrow \neg P_{a}x))$

$\land \forall x\forall y\,((Xx\land Xy\land x<y)\rightarrow \exists z(Yz\land x<z\land z<y))$

$\land \forall x\forall y\,((Yx\land Yy\land x<y)\rightarrow \exists z(Xz\land x<z\land z<y)){\big )}$

In Worten bedeutet das

Die $a$'s verteilen sich auf zwei Mengen $X$ und $Y$, die disjunkt sind,

und das erste $a$ liegt in $X$

und das letzte $a$ liegt in $Y$

und zwischen zwei verschiedenen Elementen aus $X$ liegt eines aus $Y$

und zwischen zwei verschiedenen Elementen aus $Y$ liegt eines aus $X$.

Damit ist dann klar, dass $L(\Phi )$ genau die die Menge der Zeichenketten ist, die eine gerade Anzahl von $a$'s enthält, das heißt diese Sprache ist MSO-definierbar.

Satz von Büchi

Der Satz von Büchi, benannt nach Julius Richard Büchi, gibt Auskunft darüber, welche Sprachen MSO-definierbar sind:

• Eine Sprache ist genau dann MSO-definierbar, wenn sie regulär ist.

Dieser aus dem Jahre 1960 stammende Satz stellt somit eine sehr frühe Verbindung zwischen mathematischer Logik und theoretischer Informatik her, er gilt als erstes Resultat der deskriptiven Komplexitätstheorie. Der Satz wurde unabhängig auch von Boris Trakhtenbrot gefunden.

Eine Analyse des Beweises zeigt, dass man sogar mit MSO-Ausdrücken der Art

$\exists X_{1}\ldots \exists X_{n}\varphi$

auskommt, wobei $\varphi$ ein Ausdruck der Prädikatenlogik erster Stufe in einer um $X_{1},\ldots ,X_{n}$ erweiterten Signatur ist. Die Menge dieser Ausdrücke nennt man $M\Sigma _{1}^{1}$. Für Sprachen sind daher Regularität, MSO-Definierbarkeit und $M\Sigma _{1}^{1}$-Definierbarkeit äquivalent.