Eine minimale Basis von Ausdrucksfähigkeit, die ein logisches Fragment oder eine Logik besitzen muss, um eine bestimmte Klasse von Phänomenen oder Eigenschaften erfassen zu können; die kleinstmögliche Menge syntaktischer Konstrukte und semantischer Zusicherungen, die für die Angemessenheit gegenüber einer Zielvorgabe erforderlich ist.

Prinzip

Untergrenzen werden durch die minimalen Abschlusseigenschaften und Operatoren bestimmt, die notwendig sind, um wesentliche Unterscheidungen ausdrücken zu können (z. B. die Fähigkeit, atomare Fakten zu formulieren, boolesche Kombinatorik zu verwenden oder existenziell zu quantifizieren), und sind sensitiv gegenüber der Modellklasse und den zu erfassenden Eigenschaften.

Demonstration

Will man, dass eine Logik Erreichbarkeit in beliebigen gerichteten Graphen charakterisiert, so muss die Logik mindestens einen Mechanismus für transitive Hülle oder einen äquivalenten Fixpunktoperator bieten; ohne einen solchen Operator kann kein Fragment der ersten Ordnung als erforderliche Untergrenze dienen — diese notwendige Fähigkeit ist die Expressivitätsuntergrenze für Erreichbarkeit.

Fehlanwendung

Die Untergrenze als numerische Schwelle oder als Garant für Effizienz zu behandeln; eine Untergrenze besagt nur minimale expressive Eignung, nicht Kürze, Entscheidbarkeit oder geringe rechnerische Kosten.

Konsequenz

Die Bestimmung einer Untergrenze klärt Designentscheidungen: Jede Kandidatenlogik, die die Untergrenze verfehlt, kann die Zielphänomene nicht darstellen und muss erweitert werden, während das Erfüllen der Untergrenze die weitere Abwägung zwischen Ausdruckskraft, Kürze und Komplexität erlaubt.

Umkehrung

Das Entfernen von Konstrukten unterhalb der Untergrenze (z. B. das Verbot boolescher Kombinationen oder existenzieller Quantifikation) führt zu einer Logik, die die Zielklasse nicht ausdrücken kann; umgekehrt erhöht das Anreichen einer Logik über die Untergrenze ihre Fähigkeiten, kann aber Komplexitätskosten verursachen.

Abgrenzung

Eine Untergrenze ist relativ zu einer gewählten Zielbeschreibung und Modellklasse; sie impliziert keine Universalität für alle Aufgaben und schließt Überlegungen zur algorithmischen Effizienz oder zur Praktikabilität der Inferenz in der Logik, die die Untergrenze erfüllt, aus.

Semantische Spannung

Es besteht Spannung zwischen dem Festlegen einer niedrigen Untergrenze (was Einfachheit und Handhabbarkeit erhält) und dem Anheben der Untergrenze (was reichere Ausdrucksfähigkeit garantiert, aber Komplexität riskieren kann); Untergrenzen interagieren mit Obergrenzen, da eine Untergrenze nahe der Obergrenze wenig Raum für Zwischenlogiken lässt.

Synthese

Eine Expressivitätsuntergrenze legt die minimalen syntaktischen und semantischen Merkmale fest, die eine Logik besitzen muss, um eine Eigenschaftsklasse sinnvoll zu erfassen: Sie ist ein Gestaltungsprinzip, das die Eignung für eine Aufgabe sichert und leitet, ob die Logik minimal bleiben oder bewusst gestärkt werden soll unter Abwägung der resultierenden Kompromisse.