3.7.2 Consistencia y compleción de un sistema deductivo

3.7.2. Consistencia y compleción de un sistema deductivo

Un sistema deductivo está formado por un conjunto de reglas de inferencia y una estrategia de control con la que ejecutar procesos deductivos. De él podemos esperar que toda conclusión que obtenga sea «correcta» , y, a ser posible, que el sistema sea capaz de obtener cualquiera de las conclusiones «correctas» . Formalicemos esta idea:

Ya conocemos la notación para expresar la relación de implicación (Apartado 3.4.1): C significa que el conjunto de sentencias implica la sentencia C. Introducimos ahora otra notación: _SDC significa: «a partir de las sentencias , el sistema deductivo SD obtiene la sentencia C» . Al decir «obtiene» se sobreentiene que el proceso deductivo termina en un tiempo finito demostrando la sentencia.

Un sistema deductivo es consistente si siempre que ₀ _SIC se cumple que ₀C (es decir, todas las conclusiones que obteniene el sistema son correctas).
Un sistema deductivo es completo si siempre que ₀C resulta que ₀ _SIC (es decir, el sistema puede obtener todas las conclusiones correctas).

Como la implicación entre sentencias es una relación transitiva, la consistencia de un sistema está garantizada siempre que las reglas de inferencia sean correctas. No ocurre lo mismo con la compleción. En efecto, si las premisas implican C entonces el proceso que genera el sistema debe ser tal que en alguno de sus estados esté incluida C, y esto depende de dos cosas: de que el conjunto de reglas de inferencia elegido sea completo (por ejemplo, si sólo tiene la regla de modus ponens el sistema no puede inferir una conclusión que proceda de un razonamiento del tipo modus tollens) y de que la estrategia de control permita esa compleción.

DIT-ETSIT-UPM

Portada