El procedimiento de decisión o tarea algorítmica de determinar si un conjunto de premisas Γ implica semánticamente una conclusión φ en una lógica y semántica especificadas (Γ ⊨ φ), a menudo buscando pruebas o contraejemplos modelos.

Principio

La comprobación de consecuencia se reduce a demostrar que todo modelo de Γ es modelo de φ (enfoque semántico) o que φ es derivable de Γ en un sistema de prueba correcto (enfoque sintáctico); la equivalencia depende de la corrección y completitud del sistema de prueba respecto a la semántica.

Demostración

En lógica proposicional, Γ ⊨ φ se comprueba mediante satisfacibilidad: Γ ⊨ φ si y solo si Γ ∪ {¬φ} es insatisfiable, por lo que un solver SAT puede confirmar la consecuencia reportando insatisfabilidad para la fórmula combinada.

Aplicación incorrecta

Confundir derivabilidad sintáctica (Γ ⊢ φ) con consecuencia semántica cuando el sistema de prueba elegido es incompleto para la semántica prevista, o aplicar procedimientos de verificación de consecuencia fuera de su dominio de decidibilidad (suponer un procedimiento decisorio para lógicas indecidibles).

Consecuencia

La comprobación fiable de consecuencia permite teoremas automáticos, verificación de programas y respuesta a consultas; su complejidad o decidibilidad guía el diseño de herramientas (por ejemplo NP-completo en proposicional, semi-decidible o indecidible en muchos fragmentos del primer orden).

Inversión

La no-consecuencia (Γ ⊭ φ) se transforma en un testigo informativo: un contra-modelo que satisface Γ y falsifica φ, lo que refuta la consecuencia propuesta y ayuda a depurar o revisar hipótesis.

Límite

Decidible y a menudo tratable eficientemente en lógica proposicional y muchos fragmentos decidibles restringidos; indecidible o solo semi-decidible en lógica de primer orden general según el fragmento y la semántica; depende de la lógica, la firma y de si se pregunta por consecuencia en modelos finitos.

Tensión semántica

Existe tensión entre la consecuencia modelística (semántica) y la demostrabilidad proof-teórica (sintáctica): los sistemas prácticos equilibran esto mediante heurísticas sonoras, completas o incompletas y sacrificando a veces completitud por rendimiento.

Síntesis

La verificación de consecuencia es la tarea operacional de decidir si premisas implican una conclusión mediante búsqueda de modelos semánticos o búsqueda de pruebas sintácticas; su aplicabilidad y garantías dependen de la decidibilidad de la lógica y de la estrategia de verificación elegida.