## [Signaturgröße](/de/node/60886) Definition Die Anzahl der unterschiedlichen nicht-logischen Symbole in der Signatur einer Sprache, üblicherweise die Funktionssymbole, Prädikatsymbole und Konstantensymbole zählend (je nach Konvention wird ein Symbol zusammen mit seiner Arität als eigene Einheit betrachtet). ## Prinzip Prinzip Die Signaturgröße misst den Wortschatz, der zum Bilden von Formeln verfügbar ist; sie begrenzt die Vielfalt atomarer Formeln und beeinflusst damit Ausdrucksstärke, die Kombinatorik von Strukturen und die Komplexität von Entscheidungsproblemen. ## Demonstration Demonstration Eine Signatur Σ = {c (Konstante), f (unäre Funktion), g (binäre Funktion), P (unäres Prädikat), R (binäres Prädikat)} hat nach der Zählkonvention 5 Symbole; unter einer Konvention, die Symbol-Aritäts-Paare zählt, bleibt sie 5, sofern die Aritäten mit den Symbolen festgehalten werden. ## Fehlanwendung Fehlanwendung Logische Junktoren (¬, ∧, →) oder Metavariablen als Signatursymbole zu zählen oder nicht zu klären, ob unterschiedliche Aritäten desselben Namens verschieden gezählt werden, führt zu inkonsistenten Vergleichen der Signaturgröße zwischen Sprachen oder Ergebnissen. ## Konsequenz Konsequenz Die Kontrolle der Signaturgröße ist in der endlichen Modelltheorie und in Komplexitätsanalysen wichtig: Begrenzte Signaturen vereinfachen Zählargumente und machen manche Entscheidungsverfahren praktikabler, während unbeschränkte oder unendliche Signaturen die Ausdrucksstärke und technische Komplexität erhöhen. ## Umkehrung Umkehrung Die duale Sicht ist eine unendliche oder sehr große Signatur, in der neue Symbole frei eingeführt werden; eine solche Erweiterung erhöht die Ausdrucksstärke trivial, kann jedoch gewisse Klassifikationsergebnisse entwerten oder zusätzlichen administrativen Aufwand bei Konstruktionen erfordern. ## Abgrenzung Abgrenzung Die Signaturgröße bezieht sich nur auf die Anzahl nicht-logischer Symbole in der gewählten formalen Sprache und schließt logische Junktoren, Interpunktion, Variablen und externen Kodierungsaufwand aus; die genaue Behandlung von Arität und Symboläquivalenz muss angegeben werden, um Mehrdeutigkeiten zu vermeiden. ## Semantische Spannung Semantische Spannung Die Signaturgröße steht im Spannungsfeld zu Maßen wie der Dichte des Vokabulars, etwa Verteilung der Aritäten und Wiederverwendung von Symbolen: Zwei Signaturen gleicher Größe können stark variieren, wenn die eine viele hoch-arity Symbole und die andere viele Konstanten hat, was zu unterschiedlichen Modellierungsmöglichkeiten führt. ## Synthese Synthese Die Signaturgröße ist die Anzahl der unterschiedlichen nicht-logischen Symbole in einer Sprache (mit einer festgelegten Konvention zur Arität); sie ist ein einfaches Maß für Wortschatzreichtum, das Ausdrucksstärke, Kombinatorik und Komplexität in logischen Untersuchungen mitbestimmt.