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 usa sin calificación, con diferentes significados según el contexto, en su mayoría refiriéndose 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 son verdaderas.
La propiedad inversa a la completitud 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.
Formas de completitud
Completitud expresiva
Un lenguaje formal es expresivamente completo si puede expresar el tema al que está destinado.
Integridad funcional
Un conjunto de conectivos lógicos asociados con un sistema formal es funcionalmente completo si puede expresar todas las funciones proposicionales .
Completitud semántica
La completitud 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 en todos los casos). interpretación del lenguaje del sistema que sea consistente con las reglas del sistema). Es decir,
Por ejemplo, el teorema de completitud de Gödel establece completitud semántica para la lógica de primer orden .
Completitud fuerte
Un sistema formal S es muy completo o completo en el sentido estricto si para cada conjunto de premisas Γ, cualquier fórmula que se siga semánticamente de Γ es derivable de Γ. Es decir:
Integridad de la refutación
Un sistema formal S es refutación completo si es capaz de derivar falso de cada conjunto insatisfactorio de fórmulas. Es decir,
Todo sistema fuertemente completo es también refutación-completa. Intuitivamente, una completa integridad significa que, dado un conjunto de fórmulas, es posible calcular todas las consecuencias semánticas de , mientras que refutación-completitud significa que, dado un conjunto de fórmulas y una formula , es posible comprobar si es una consecuencia semántica de .
Ejemplos de sistemas de refutación completa incluyen: resolución SLD en cláusulas Horn , superposición en lógica de primer orden de cláusulas ecuacionales, resolución de Robinson en conjuntos de cláusulas . [3] Este último no es muy completo: p. Ej. se mantiene incluso en el subconjunto proposicional de la lógica de primer orden, pero no se puede derivar de por resolución. Sin emabargo, puede ser derivado.
Completitud sintáctica
Un sistema formal S es sintácticamente completa o por deducción completa o máximamente completa si para cada frase (fórmula cerrado) φ del idioma del sistema, ya sea φ o ¬φ es un teorema de S . Esto también se denomina completitud de negación y es más fuerte que completitud semántica. En otro sentido, un sistema formal es sintácticamente completo si y solo si no se le puede agregar una oración indemostrable sin introducir una inconsistencia. La lógica de proposiciones Verdad-funcional y lógica de predicados de primer orden son semánticamente completa, pero no sintácticamente completa (por ejemplo, la declaración de la lógica de proposiciones que consta de una sola variable proposicional A no es un teorema, y tampoco lo es su negación). El teorema de incompletitud de Gödel muestra que cualquier sistema recursivo que sea lo suficientemente poderoso, como la aritmética de Peano , no puede ser consistente y sintácticamente completo.
Completitud estructural
En las lógicas superintuicionista y modal , una lógica es estructuralmente completa si toda regla admisible es derivable.
Referencias
- ^ Hunter, Geoffrey, Metalogic: Una introducción a la metateoría de la lógica estándar de primer orden, University of California Pres, 1971
- ^ David A. Duffy (1991). Principios de la demostración automatizada de teoremas . Wiley.Aquí: secta. 2.2.3.1, p. 33
- ^ Stuart J. Russell, Peter Norvig (1995). Inteligencia artificial: un enfoque moderno . Prentice Hall.Aquí: secta. 9.7, p. 286