Die Gesamtanzahl der Symbole oder Tokens in einer Formel nach einer gewählten Tokenisierungs-Konvention; ein grundlegendes syntaktisches Maß, das logische Junktoren, Quantoren, Prädikat- und Funktionssymbole, Variablen, Klammern und manchmal Interpunktion zählt.

Prinzip

Formellänge dient als grobes Maß syntaktischer Komplexität und Ressourcenbedarf; sie liefert eine einfache obere Schranke für Parsing- und Kodierungskosten und wird häufig in Beweisen verwendet, die größenbasierte Induktion oder kombinatorische Zählargumente benötigen.

Demonstration

Bei einer Tokenisierung, die jedes Symbol und jede Klammer als ein Token behandelt, hat die Formel (∀x P(x) → ∃y Q(y,x)) Tokens für '(', '∀', 'x', 'P', '(', 'x', ')', '→', '∃', 'y', 'Q', '(', 'y', ',', 'x', ')', ')' und damit ist die Formellänge die Anzahl dieser Tokens.

Fehlanwendung

Formellänge direkt als Proxy für semantische Komplexität oder Berechnungskosten zu verwenden, ohne Kodierungskonventionen, Symbolaritäten oder geteilte Teilformeln zu kontrollieren, ist eine Fehlanwendung, die Vergleiche zwischen Sprachen oder Kodierungen irreführen kann.

Konsequenz

Konsistent gemessen ermöglicht Formellänge kombinatorische Argumente, Komplexitätsschätzungen und Kompaktheitsgrenzen; Längenbegrenzung ist wesentlich bei Kodierungsproblemen, Konstruktionen endlicher Modelle und Heuristiken im automatisierten Schließen.

Umkehrung

Die umgekehrte Sicht betont semantische Knappheit: Formeln minimaler Länge, die dennoch komplexe Eigenschaften ausdrücken, zeigen, dass geringe syntaktische Größe nicht geringe semantische oder rechnerische Komplexität bedeutet.

Abgrenzung

Hängt von der gewählten Tokenisierung ab und davon, ob gemeinsame Abkürzungen, definierte Symbole oder Makro-Expansionen berücksichtigt werden; schließt semantische Maße aus und ist nicht invariant unter unterschiedlichen syntaktischen Codierungen oder Umbenennungen von Symbolen.

Semantische Spannung

Formellänge steht im Spannungsfeld zu Maßen wie Kolmogorov-Komplexität, Alternationstiefe und Quantorenrang: Eine Formel kann kurz, aber semantisch komplex oder lang, aber semantisch trivial sein, was die Auswahl einer geeigneten Komplexitätsmetrik erschwert.

Synthese

Formellänge ist die Anzahl syntaktischer Tokens nach einer gegebenen Konvention; sie ist ein praktisches, sprachabhängiges Maß der Formgröße, nützlich für Kodierung, kombinatorische Schranken und Ressourcenschätzungen, das zusammen mit anderen Maßen betrachtet werden muss.