Ein Maß für den Umfang der Eigenschaften, Unterscheidungen oder Strukturen, die eine gegebene logische Sprache oder ein Formalismus auf einer Klasse von Strukturen definieren oder erfassen kann; Vergleiche erfolgen oft dadurch, ob Formeln einer Sprache in einer anderen übersetzbar sind, wobei Wahrheit in allen betrachteten Strukturen erhalten bleibt.

Prinzip

Die Ausdrucksstärke wird bestimmt durch verfügbare syntaktische Mittel (Quantoren, Quantifikation über Mengen/Funktionen, Fixpunktoperatoren, modale Operatoren) und deren Wechselwirkung mit der Modellklasse und eingebetteten Relationen; mehr Konstrukte erhöhen typischerweise das Definierbare, können aber andere Eigenschaften beeinflussen.

Demonstration

Die Prädikatenlogik erster Stufe kann Konnektivität in Graphen nicht ausdrücken, während monadische Zweite‑Stufe‑Logik (MSO) oder FO mit transitiver Hülle dies können; damit haben MSO oder FO+TC größere Ausdrucksstärke für diese Eigenschaft auf Graphen.

Fehlanwendung

Aus größerer Ausdrucksstärke direkt praktische Eignung abzuleiten: mächtigere Sprachen können unentscheidbar oder algorithmisch unpraktisch sein, sodass die Sprachwahl einen Kompromiss zwischen Ausdrucksstärke, Entscheidbarkeit und Knappheit verlangt.

Konsequenz

Verständnis der Ausdrucksstärke leitet die Wahl von Logiken für Spezifikation und Verifikation, klärt welche Eigenschaften erfasst werden können und liegt Ergebnissen zugrunde, die logische Fragmente mit Komplexitätsklassen verbinden (deskriptive Komplexität).

Umkehrung

Ausdrucksschwäche: eine Sprache ist zu schwach, um beabsichtigte Eigenschaften zu definieren, was zur Folge hat, die Sprache zu erweitern oder Inexpressibilität hinzunehmen und alternative Spezifikationsmethoden zu nutzen.

Abgrenzung

Hängt vom Anwendungsbereich (Graphen, Ordnungen, Arithmetik), davon ab, ob feste Signaturen oder eingebaute Relationen erlaubt sind, und von der Semantik (endliche vs. unendliche Strukturen); Vergleiche müssen die Strukturklasse und die Übersetzungsmethode spezifizieren.

Semantische Spannung

Spannung zwischen Ausdrucksstärke und algorithmischer Handhabbarkeit oder konzeptueller Klarheit: zusätzliche Ausdrucksmittel können Spezifikationen verkürzen, aber die Analyse erschweren; zwei Sprachen können unvergleichbar sein und unterschiedliche Intuitionen abbilden.

Synthese

Ausdrucksstärke diagnostiziert, was eine Sprache über Strukturen aussagen kann, indem sie syntaktische Mittel mit semantischer Definierbarkeit verbindet: sie ist ein praktischer und theoretischer Maßstab zur Wahl und zum Vergleich von Formalismen, stets ausbalanciert mit Entscheidbarkeit, Knappheit und den intendierten Modellen.