## [Anzahl der Literale](/de/node/60890) 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.