Definition
Die Anzahl der unterschiedlichen Variablen, die in einer Formel oder Theorie auftreten, wobei 'unterschiedlich' sich auf syntaktisch verschiedene Variablensymbole bezieht; verwendet als einfaches Maß syntaktischer Komplexität und Ressourcenbedarf.
Prinzip
Prinzip
Die Variablenanzahl gibt an, wie viele getrennte Platzhalter in einem Ausdruck verfügbar oder erforderlich sind; sie wirkt mit Quantorenstruktur, Sichtbarkeit und Umbenennung zusammen und kann ein entscheidender Parameter in Logikfragmenten sein (z. B. Ein- oder Zwei-Variablenfragment).
Demonstration
Demonstration
Die Formel ∀x ∃y (P(x) ∧ Q(y,z)) enthält die verschiedenen Variablen x, y, z, daher ist ihre Variablenanzahl 3; das Umbenennen von y in y' erhält die Anzahl, obwohl die Namen unterschiedlich sind.
Fehlanwendung
Fehlanwendung
Die Vorkommensanzahl von Variablen (insgesamt) statt der unterschiedlichen Variablensymbole zu zählen oder die Variablenanzahl mit der Anzahl gebundener versus freier Variablen ohne Klarstellung gleichzusetzen, ist eine Fehlanwendung, die irreführende Komplexitätsschätzungen liefert.
Konsequenz
Konsequenz
Die Begrenzung der Anzahl unterschiedlicher Variablen in einer Sprache oder einem Fragment kann starke Entscheidbarkeits- oder Komplexitätsergebnisse liefern: Viele logische Fragmente werden entscheidbar oder einfacher zu analysieren, wenn die Variablenanzahl begrenzt ist, und algorithmische Verfahren nutzen solche Schranken oft aus.
Umkehrung
Umkehrung
Die umgekehrte Situation betrachtet eine unbeschränkte oder unendliche Versorgung von Variablensymbolen; zwar flexibel zum Darstellen vieler unterschiedlicher Platzhalter, können unbeschränkte Variablen die Komplexität verschleiern und einheitliche algorithmische Schranken erschweren.
Abgrenzung
Abgrenzung
Variablenanzahl bezieht sich auf syntaktisch deklarierte Variablensymbole, die in Formeln oder einer Theorie vorkommen, und misst nicht direkt, wie Variablen verwendet werden (gebunden vs. frei), sofern der Kontext diese Unterscheidung nicht vorschreibt; sie schließt Metavariablen und nur auf Metaniveau eingeführte Parameter aus.
Semantische Spannung
Semantische Spannung
Die Variablenanzahl steht im Spannungsverhältnis zu Maßen wie dem Quantorenrang und der Formellänge: Eine kleine Variablenanzahl kann dennoch hohe Quantoralternanz oder lange Formeln durch Wiederverwendung von Variablen ermöglichen, was die Frage aufwirft, welches Maß Komplexität am besten erfasst.
Synthese
Synthese
Die Variablenanzahl ist die Zahl syntaktisch unterschiedlicher Variablensymbole, die in einer Formel oder Theorie erscheinen; als einfacher, handhabbarer Parameter beschränkt sie Scoping und Ausdruckskraft und wird häufig zur Klassifikation und Analyse logischer Fragmente verwendet.