En lógica matemática y metalógica , un sistema formal se llama completo con respecto a una propiedad particular si cada fórmula que tiene la propiedad puede derivarse usando ese sistema, es decir, es uno de sus teoremas ; de lo contrario se dice que el sistema está incompleto . El término "completo" también se utiliza sin reservas, con diferentes significados según el contexto, refiriéndose principalmente a la propiedad de validez semántica . Intuitivamente, un sistema se llama completo en este sentido particular, si puede derivar todas las fórmulas que sean verdaderas.
La propiedad inversa a la integridad se llama solidez : un sistema es sólido con respecto a una propiedad (principalmente validez semántica) si cada uno de sus teoremas tiene esa propiedad.
Un lenguaje formal es expresivamente completo si puede expresar el tema al que está destinado.
Un conjunto de conectivos lógicos asociados con un sistema formal es funcionalmente completo si puede expresar todas las funciones proposicionales .
La integridad semántica es lo opuesto a la solidez de los sistemas formales. Un sistema formal es completo con respecto a la tautología o "semánticamente completo" cuando todas sus tautologías son teoremas , mientras que un sistema formal es "sólido" cuando todos los teoremas son tautologías (es decir, son fórmulas semánticamente válidas: fórmulas que son verdaderas bajo todas las condiciones). interpretación del lenguaje del sistema que sea consistente con las reglas del sistema). Es decir, un sistema formal es semánticamente completo si:
Por ejemplo, el teorema de completitud de Gödel establece completitud semántica para la lógica de primer orden .
Un sistema formal S es fuertemente completo o completo en sentido fuerte si para cada conjunto de premisas Γ, cualquier fórmula que semánticamente se siga de Γ es derivable de Γ. Eso es:
Un sistema formal S tiene refutación completa si es capaz de derivar falso de cada conjunto insatisfactorio de fórmulas. Eso es:
Todo sistema fuertemente completo es también una refutación completa. Intuitivamente, la completitud fuerte significa que, dado un conjunto de fórmulas , es posible calcular cada consecuencia semántica de , mientras que la completitud de refutación significa que, dado un conjunto de fórmulas y una fórmula , es posible verificar si es una consecuencia semántica de .
Ejemplos de sistemas de refutación completa incluyen: resolución SLD sobre cláusulas de Horn , superposición sobre lógica clausal ecuacional de primer orden, resolución de Robinson sobre conjuntos de cláusulas. [3] Este último no es muy completo: por ejemplo, se cumple incluso en el subconjunto proposicional de la lógica de primer orden, pero no se puede derivar mediante resolución. Sin embargo, se puede derivar.
Un sistema formal S es sintácticamente completo o deductivamente completo o máximamente completo si para cada oración (fórmula cerrada) φ del lenguaje del sistema φ o ¬φ es un teorema de S. Esto también se llama integridad de negación y es más fuerte que la integridad semántica. En otro sentido, un sistema formal es sintácticamente completo si y sólo si no se le puede agregar ninguna oración indemostrable sin introducir una inconsistencia . La lógica proposicional funcional de verdad y la lógica de predicados de primer orden son semánticamente completas, pero no sintácticamente completas (por ejemplo, el enunciado de lógica proposicional que consta de una única variable proposicional A no es un teorema, ni tampoco lo es su negación). El teorema de incompletitud de Gödel muestra que cualquier sistema computable que sea suficientemente potente, como la aritmética de Peano , no puede ser al mismo tiempo consistente y sintácticamente completo.
En lógicas superintuicionistas y modales , una lógica es estructuralmente completa si cada regla admisible es derivable.
Una teoría es un modelo completo si y sólo si cada incorporación de sus modelos es una incorporación elemental .
