El conteo total de símbolos o tokens en una fórmula según una convención de tokenización elegida; una medida sintáctica básica que contabiliza conectivos lógicos, cuantificadores, símbolos de predicado y función, variables, paréntesis y a veces signos de puntuación.

Principio

La longitud de fórmula funciona como una medida burda de la complejidad sintáctica y del uso de recursos; proporciona una cota superior sencilla para los costes de análisis y codificación y se usa a menudo en demostraciones que se basan en inducción por tamaño o en conteos combinatorios.

Demostración

Bajo una tokenización que trata cada símbolo y paréntesis como un token, la fórmula (∀x P(x) → ∃y Q(y,x)) tiene tokens para '(', '∀', 'x', 'P', '(', 'x', ')', '→', '∃', 'y', 'Q', '(', 'y', ',', 'x', ')', ')' por lo que su longitud de fórmula es ese número de tokens.

Aplicación incorrecta

Utilizar la longitud de fórmula como un proxy directo de la complejidad semántica o del coste computacional sin controlar las convenciones de codificación, las aridades de los símbolos o las subexpresiones compartidas es un uso indebido que puede falsear comparaciones entre lenguajes o codificaciones.

Consecuencia

Medida consistentemente, la longitud de fórmula permite argumentos combinatorios, estimaciones de complejidad y cotas de compacidad; controlar la longitud es esencial en problemas de codificación, construcciones de modelos finitos y heurísticas de razonamiento automático.

Inversión

La vista inversa enfatiza la brevedad semántica: fórmulas de longitud mínima que sin embargo expresan propiedades complejas muestran que el tamaño sintáctico pequeño no implica baja complejidad semántica o computacional.

Límite

Depende de la tokenización elegida y de si se cuentan abreviaturas compartidas, símbolos definidos o expansiones de macros; excluye medidas semánticas y no es invariante bajo diferentes codificaciones sintácticas ni bajo renombramientos de símbolos.

Tensión semántica

La longitud de fórmula compite con medidas como la complejidad de Kolmogorov, la profundidad de alternancia y el rango de cuantificadores: una fórmula puede ser corta pero semánticamente compleja o larga pero semánticamente trivial, lo que crea tensión al elegir una métrica de complejidad.

Síntesis

La longitud de fórmula es el recuento de tokens sintácticos según una convención dada; es una medida práctica dependiente del lenguaje para tamaño de fórmula, útil en codificación, cotas combinatorias y estimación de recursos algorítmicos, que debe interpretarse junto con otras medidas.