Definition
Die Gesamtanzahl der Literalvorkommen in einer Formel oder Klauselmenge, wobei jedes Auftreten eines Atoms oder seiner Negation einzeln gezählt wird.
Prinzip
Prinzip
Die Größe einer Formel durch Summierung der Vielfachheiten von Atomen und deren Negationen messen; Duplikate und wiederholte Vorkommen erhöhen die Zählung.
Demonstration
Demonstration
Für die CNF { (x1 ∨ ¬x2), (x1 ∨ x3 ∨ ¬x2) } ist die Literalanzahl 2 + 3 = 5, da x1 zweimal, ¬x2 zweimal und x3 einmal vorkommt und jedes Vorkommen gezählt wird.
Fehlanwendung
Fehlanwendung
Die Literalanzahl irrtümlich als Anzahl distinkter Variablen oder Literaltypen zu verwenden führt dazu, Redundanz zu unterschätzen, wenn dasselbe Literal mehrfach auftritt.
Konsequenz
Konsequenz
Dient als direkter Proxy für Speicherbedarf und syntaktische Größe; höhere Literalanzahlen erhöhen typischerweise den Speicherbedarf und können die Laufzeit syntaktischer Algorithmen verschlechtern.
Umkehrung
Umkehrung
Wenn nur verschiedene Literale gezählt werden (ohne Vielfachheit), entsteht eine Maßzahl, die Klauselwiederholungen verschleiert und die syntaktische Komplexität unterschätzt.
Abgrenzung
Abgrenzung
Gilt für propositionale Klauselmengen und klausale Formeln; schließt Gewichte, annotierte Vielfachheiten und nicht-klausale Darstellungen wie boolesche Schaltkreise aus, sofern diese nicht in Klauseln umgewandelt sind.
Semantische Spannung
Semantische Spannung
Steht im Wettbewerb mit Variablenanzahl und Klauselbreite: Eine Instanz mit wenigen Variablen kann dennoch eine hohe Literalanzahl haben, was zu unterschiedlichen Vorhersagen zur Schwierigkeit führt.
Synthese
Synthese
Die Anzahl Der Literale ist die rohe syntaktische Größe, gewonnen durch Addition aller Vorkommen von Atomen und deren Negationen in einer klausalen Darstellung; sie erfasst Vielfachheit und verfeinert größenbasierte Komplexitätsschätzungen jenseits einfacher Variablen- oder Klauselzählungen.