El número total de ocurrencias de literales en una fórmula o conjunto de cláusulas, contando por separado cada aparición de un átomo o su negación.

Principio

Medir el tamaño sintáctico sumando las multiplicidades de los átomos y sus negaciones; las repeticiones y ocurrencias duplicadas aumentan el conteo.

Demostración

Para la CNF { (x1 ∨ ¬x2), (x1 ∨ x3 ∨ ¬x2) } el conteo de literales es 2 + 3 = 5 porque x1 aparece dos veces, ¬x2 aparece dos veces y x3 una vez, contando cada aparición.

Aplicación incorrecta

Usar el conteo de literales como si fuera el número de variables distintas o tipos distintos de literales conduce a subestimar la redundancia cuando el mismo literal aparece muchas veces.

Consecuencia

Sirve como un proxy directo para memoria y tamaño sintáctico; conteos altos de literales suelen aumentar la necesidad de almacenamiento y empeorar la complejidad de algoritmos sintácticos.

Inversión

Contar solo literales distintos (ignorar multiplicidad) produce una medida que puede ocultar repeticiones de cláusulas y subestimar la complejidad sintáctica.

Límite

Se aplica a conjuntos de cláusulas proposicionales y fórmulas en forma clausal; excluye ponderaciones, multiplicidades anotadas y representaciones no clausales como circuitos booleanos salvo que se conviertan a cláusulas.

Tensión semántica

Compite con el conteo de variables y la anchura de cláusula: una instancia con pocas variables puede aun tener un conteo alto de literales por muchas repeticiones, lo que provoca predicciones distintas sobre la dificultad.

Síntesis

El Conteo De Literales es la medida sintáctica cruda que suma cada aparición de átomos y sus negaciones en una representación clausal; captura multiplicidad y refina estimaciones de complejidad basadas en tamaño más allá del simple conteo de variables o cláusulas.