El procedimiento de convertir fórmulas o términos en una forma representativa canónica que sea única salvo equivalencia lógica, para comparación, indexación y pruebas de igualdad.

Principio

Definir una función de normalización determinista y la relación de equivalencia elegida; aplicar reescrituras ordenadas, renombrado de variables ligadas, eliminación de ambigüedades sintácticas y un orden estándar de operandos para producir un representante único por clase de equivalencia.

Demostración

Convertir fórmulas proposicionales a una CNF canónica mediante distribución, eliminación de tautologías, ordenamiento lexicográfico de literales y cláusulas y renombrado consistente de variables, de modo que fórmulas lógicamente equivalentes produzcan la misma representación textual para indexación.

Aplicación incorrecta

Asumir que la canonicalización es gratuita o siempre posible; aplicar una ‘normalización’ heurística que no sea determinista o que dependa de nombres de símbolos arbitrarios y por tanto no garantice unicidad entre fórmulas equivalentes.

Consecuencia

Las formas canónicas permiten comprobaciones sintácticas de igualdad eficientes para la equivalencia semántica, soportan caché, indexación y eliminación de duplicados en sistemas de razonamiento automático.

Inversión

Usar varias formas normales igualmente válidas o dejar las fórmulas en formas simplificadas no reguladas produce representaciones no deterministas que dificultan las pruebas directas de equivalencia.

Límite

Depende de la lógica y de la equivalencia elegida (equivalencia semántica, congruencia estructural, alfa-equivalencia); algunas lógicas no admiten una canonicalización completa computable o la hacen prohibitivamente costosa.

Tensión semántica

La canonicalización está en tensión con la simplificación y la minimización: prioriza la unicidad y reproducibilidad de la representación, a costa posiblemente del tamaño sintáctico mínimo o de la legibilidad humana.

Síntesis

La canonicalización es el mapeo determinista de fórmulas equivalentes a un único representante elegido mediante reescrituras ordenadas y convenciones estándar para reducir consultas de equivalencia a la igualdad sintáctica.