## [Relative Expressivität](/de/node/61099) Definition Eine Relation, die zwei formale Sprachen oder Formalismen vergleicht, wobei die eine als mindestens so ausdrucksstark gilt wie die andere, wenn sie alle in der zweiten definierbaren Eigenschaften, Klassen von Strukturen oder Prädikate in der ersten definieren oder simulieren kann. ## Prinzip Prinzip Ausdrucksstärke wird durch Definierbarkeit oder treue Simulation gemessen: L1 ist mindestens so ausdrucksstark wie L2, wenn es eine systematische Kodierung oder Interpretation gibt, die jede in L2 definierbare Eigenschaft auf eine in L1 definierbare Eigenschaft abbildet; üblicherweise ergibt das eine Präordnung (reflexiv, transitiv) auf Sprachen. ## Demonstration Demonstration Die Aussagenlogik ist strikt weniger ausdrucksstark als die Prädikatenlogik erster Stufe, weil es erststufige Eigenschaften (z. B. „es existieren zwei verschiedene Elemente“) gibt, die in der Aussagenlogik nicht formulierbar sind; viele modale Logiken sind dagegen weniger ausdrucksstark als der Teil der Prädikatenlogik, der durch die Standardübersetzung modaler Formeln in prädikatenlogische Formeln über Rahmen entsteht. ## Fehlanwendung Fehlanwendung Expressivität fälschlich mit Entscheidbarkeit, Komplexität oder Kürze gleichsetzen; etwa zu folgern, dass eine ausdrucksstärkere Sprache zwangsläufig unentscheidbar ist, oder Ausdrucksstärke mit knappen Formeln zu verwechseln. ## Konsequenz Konsequenz Wenn eine Sprache mindestens so ausdrucksstark ist wie eine andere, lassen sich Metasätze, Definierbarkeitsergebnisse und manche semantische Unterscheidungen mittels der Kodierung übertragen; das leitet die Wahl eines Formalismus für Spezifikation und Analyse. ## Umkehrung Umkehrung Die umgekehrte Relation zeigt strikte Unausdrucksstärke: L1 ist weniger ausdrucksstark als L2, wenn es Eigenschaften gibt, die in L2 definierbar sind, die sich durch keine Kodierung in L1 abbilden lassen, was qualitative Unterschiede zwischen Sprachen offenbart. ## Abgrenzung Abgrenzung Gilt für formale Sprachen und Formalismen mit einer klaren Auffassung von Definierbarkeit oder Erfüllung; sie vergleicht nicht unmittelbar Implementierungsleistung, Beweissuchkomplexität oder pragmatische Kürze, sofern dies nicht explizit Teil des Definierbarkeitskriteriums ist. ## Semantische Spannung Semantische Spannung Im Wettbewerb mit Begriffen wie Entscheidbarkeit und Kürze: Eine ausdrucksstärkere Sprache kann Entscheidbarkeit opfern oder längere Formeln erfordern, weshalb Ausdrucksstärke gegen algorithmische und praktische Aspekte abzuwägen ist. ## Synthese Synthese Relative Ausdrucksstärke ist die durch systematische Kodierungen oder Simulationen induzierte Präordnung auf Formalismen, die angibt, wann eine Sprache die beschreibenden Mittel einer anderen treu abbildet und zugleich die Kompromisse mit Entscheidbarkeit und Komplexität berücksichtigt.