Le nombre total d'occurrences de littéraux dans une formule ou un ensemble de clauses, en comptant séparément chaque apparition d'un atome ou de sa négation.

Principe

Mesurer la taille syntaxique en sommant les multiplicitées des atomes et de leurs négations ; les doublons et les occurrences répétées augmentent le compte.

Démonstration

Pour la CNF { (x1 ∨ ¬x2), (x1 ∨ x3 ∨ ¬x2) } le nombre de littéraux est 2 + 3 = 5 car x1 apparaît deux fois, ¬x2 apparaît deux fois et x3 une fois, chaque apparition étant comptée.

Mauvaise application

Employer le nombre de littéraux comme s'il s'agissait du nombre de variables distinctes ou de types littéraux distincts conduit à sous-estimer la redondance lorsque la même occurrence littérale se répète.

Conséquence

Constitue un indicateur direct de la mémoire et de la taille syntaxique ; un nombre élevé de littéraux augmente généralement les besoins de stockage et peut aggraver le temps d'exécution des algorithmes syntaxiques.

Inversion

Ne compter que les littéraux distincts (ignorer la multiplicité) donne une mesure qui peut masquer la répétition des clauses et sous-estimer la complexité syntaxique.

Limite

S'applique aux ensembles de clauses propositionnelles et aux formules sous forme clausale ; exclut les poids, les multiplicitées annotées et les représentations non clausales comme les circuits booléens, sauf conversion en clauses.

Tension sémantique

En tension avec le nombre de variables et la largeur des clauses : une instance avec peu de variables peut néanmoins avoir un nombre élevé de littéraux à cause de nombreuses répétitions, menant à des prédictions de complexité différentes.

Synthèse

Le Nombre De Littéraux est la taille syntaxique brute obtenue en sommant chaque occurrence d'atomes et de leurs négations dans une représentation clausale ; il saisit la multiplicité et affine les estimations de complexité basées sur la taille au-delà des simples comptes de variables ou de clauses.