Die Anzahl der Wechsel zwischen existenziellen und universellen Quantoren in der längsten alternierenden Folge einer Formel; anders gesagt die Anzahl der Umschaltungen ∃→∀ oder ∀→∃ entlang eines maximalen Pfades durch Quantorvorkommen.

Prinzip

Die Alternationstiefe ordnet die quantifizierte Struktur einer Formel, indem sie misst, wie oft der Quantorentyp wechselt; sie wird zur Klassifikation logischer Komplexität und zur Zuordnung von Formeln zu Schichten beschreibender oder berechenbarkeitstheoretischer Hierarchien verwendet.

Demonstration

In der Prenexformel ∃x ∀y ∃z P(x,y,z) hat das Quantorenmuster ∃→∀→∃ zwei Alternationen (∃ nach ∀ und ∀ nach ∃), also ist die Alternationstiefe 2; eine Formel ∀∀∃∃ hat genau eine Alternation.

Fehlanwendung

Die Alternationstiefe mit der Quantorverschachtelungstiefe gleichzusetzen oder benachbarte Quantoren gleichen Typs fälschlich als Alternation zu zählen (z. B. ∃∃ als Wechsel zu werten) ist eine Fehlanwendung, die die tatsächliche Alternationsstruktur überschätzt.

Konsequenz

Korrekt bestimmte Alternationstiefe sagt Ausdrucksstärke voraus und korreliert oft mit erhöhter Entscheidungs- oder Berechnungskomplexität: Mehr Alternationen können eine Spezifikation in eine höhere Schicht einer Hierarchie heben und die anwendbaren Beweis- oder Algorithmusmethoden verändern.

Umkehrung

Das Umgekehrte ist ein Quantorenpräfix ohne Alternationen (alle Quantoren des gleichen Typs), das keine Wechsel aufweist und den rein existenziellen oder rein universellen Fragmenten entspricht, deren Verhalten und Komplexität sich deutlich von alternierenden Präfixen unterscheiden.

Abgrenzung

Gilt für Quantorenfolgen (üblicherweise in Prenexform betrachtet) und für alternierende Sequenzen entlang syntaktischer Pfade; schließt das Hineinrechnen separater, nicht interagierender Quantorenblöcke in verschiedenen Teilformeln aus und hängt von der Konvention zur Bildung der Prenexform ab.

Semantische Spannung

Die Alternationstiefe steht im Spannungsverhältnis zu verwandten Maßen wie dem Quantorenrang (Verschachtelungstiefe), der Formellänge und der Anzahl der Quantorenblöcke; zwei Formeln mit gleicher Alternationstiefe können in Rang oder Länge stark variieren, was die Wahl des geeigneten Komplexitätsmaßes erschwert.

Synthese

Alternationstiefe ist die Anzahl der Umschaltungen zwischen ∃ und ∀ entlang des längsten quantifizierten Pfades einer Formel; sie fasst zusammen, wie Quantoren ihre Polarität wechseln und dient als präziser syntaktischer Indikator für Ausdrucks- und Rechenkomplexität.