Teorema de Consistencia

La consistencia o consistencia lógica es la propiedad que tienen los sistemas formales cuando no es posible deducir una contradicción dentro del sistema. Es decir, dado un lenguaje formal y un aparato deductivo (axiomas y reglas de inferencia), no es posible deducir una fórmula y su negación. La existencia de un modelo implica que una teoría lógica es consistente.

Generalizando, la consistencia es una propiedad que pueden tener los conjuntos de fórmulas. Intuitivamente un conjunto de fórmulas es consistente cuando no es posible deducir una contradicción del mismo.

Para evaluar si el conjunto es consistente según la definición semántica, podemos construir una tabla de verdad:

P	q	(q→¬p)	R
v	v	f	v
v	v	f	f
v	f	v	v
v	f	v	f
f	v	v	v
f	v	v	f
f	f	v	v
f	f	v	f

Como se ve, en ninguna de las interpretaciones (ninguna de las filas de la tabla) se da que todas las fórmulas son verdaderas. Luego, de acuerdo con la definición semántica, el conjunto es inconsistente.

Demostración de consistencia

Una demostración de consistencia, o prueba de consistencia, es una demostración formal de que un sistema formal es consistente. Un sistema formal es consistente si no contiene una contradicción, o, en forma más precisa, no existe una proposición tal que se puede demostrar o deducir simultáneamente la proposición y su negación.

Referido a un argumento la consistencia es la necesidad de que todas las premisas tengan que ser necesariamente y a la vez, como producto, todas verdaderas, para que el argumento, si es consistente, pueda ser válido o no válido. Referido al discurso la consistencia tiene que ver con que las implicaciones lógicas del mismo no sean autocontradictorias.

Técnicas de Pruebas

Las técnicas de prueba son el método que se aplica para evaluar un sistema o un componente con el fin de averiguar si satisface los requisitos establecidos. Las pruebas de un sistema ayudan a identificar las lagunas, los errores o cualquier tipo de requisito que difiera de los requisitos reales. Las técnicas de prueba son las mejores prácticas utilizadas por el equipo de pruebas para evaluar el software desarrollado con respecto a los requisitos dados. Estas técnicas garantizan la calidad general del producto o software, incluyendo el rendimiento, la seguridad, la experiencia del cliente, etc.

En un libro escrito por Kaner Bach Pettichordon sobre Técnicas de Prueba se describe que las pruebas son un sistema de cinco aspectos para cualquier prueba que el usuario quiera hacer. Son

• Probadores - Usuarios que realizan las pruebas

• Cobertura - Qué componentes se cubren

• Posibles problemas - ¿El motivo de las pruebas es encontrar errores?

• Actividades - La forma de probar o cómo probar

• Evaluación - Compara los resultados para saber si la prueba tiene éxito o no

Todos los tipos de pruebas implican las cinco dimensiones anteriores. Las técnicas de prueba permiten al usuario centrarse en una o varias dimensiones para conseguir el resultado.

Lógica del Predicado

La capacidad expresiva del lenguaje de enunciados es bastante limitada: no cualquier frase declarativa simple se puede formalizar convenientemente. Este hecho tiene como consecuencia que un gran número de razonamientos que se pueden expresar utilizando el lenguaje natural no se puedan validar utilizando las herramientas de la lógica de enunciados.

Ejemplo de las limitaciones de la lógica de enunciados A continuación presentamos un ejemplo bastante revelador de las carencias de la lógica de enunciados y de su lenguaje. Imaginemos el razonamiento (correcto) siguiente: “Los estudiantes son personas. Juan es un estudiante. Así pues, Juan es una persona.”

 • La formalización (correcta) sería la siguiente: si asignamos P a “los estudiantes son personas”, Q a “Juan es un estudiante” y R a “Juan es una persona”, entonces tenemos que: 

    P, Q ∴ R, no permite validar el razonamiento.

 • Otra formalización (que también se puede considerar correcta) es: si asignamos P a “ser estudiante”, Q a “ser persona”, R a “Juan es un estudiante” y S a “Juan es una persona”, entonces observamos que:

   P → Q, R ∴ S, tampoco permite validar el razonamiento.

La lógica de predicados es una ampliación de la lógica de enunciados que cuenta con un lenguaje formal más rico (más expresivo) y con un conjunto de reglas que permiten validar razonamientos expresados utilizando este lenguaje. La lógica de enunciados se debe entender, a partir de este momento, como un subconjunto de la lógica de predicados.

Predicados, variables y constantes

Un predicado es una aplicación definida en un dominio que adquiere valores en el conjunto de enunciados. Formalmente se expresa de la manera siguiente:

    P(x): D → enunciados.

    Informalmente, un predicado es un enunciado parametrizado (con variables)

Representaremos un predicado utilizando una letra mayúscula del alfabeto latino, con los parámetros, preferentemente representados por letras minúsculas del mismo alfabeto a partir de x, entre paréntesis y separados por comas.

Por ejemplo, el predicado P(x) podría ser la formalización de “x es un estudiante”. Se da a entender que el predicado P(x) no es un enunciado. P(x) se puede convertir en un enunciado sustituyendo la variable x (el parámetro) por algún elemento de su dominio. Si el dominio de x es el conjunto de las personas, entonces

    P(Juan) sí es un enunciado (y se corresponde con “Juan es un estudiante”).

Un predicado puede tener cualquier número (n ≥ 0) de variables. 

Según este número, los predicados se clasifican de la manera siguiente: 

1) Los predicados con n = 0 variables son los enunciados. 

2) Los predicados con n = 1 variables se denominan propiedades o predicados unarios. 

3) Los predicados con n = 2 variables se denominan relaciones o predicados binarios. 

4) A partir de n = 3 no existen nombres específicos. Un predicado con tres variables se puede denominar relación ternaria; uno con cuatro, relación cuaternaria, etc.

Teorema de completitud de Gödel

El teorema de completitud de Gödel es un importante teorema de la lógica matemática, que fue demostrado por primera vez por Kurt Gödel en 1929 y que en su forma más conocida establece lo siguiente:

-En una lógica de primer orden, toda fórmula que es válida en un sentido lógico es demostrable.

La palabra "demostrable" significa que existe una deducción formal de la fórmula. La deducción consiste en una lista finita de pasos en los que cada paso o bien invoca a un axioma o es obtenido a partir de pasos previos mediante una básica regla de inferencia. A partir de dicha deducción, es posible verificar si cada uno de los pasos es correcto mediante un algoritmo (por ejemplo, mediante una computadora o a mano).

Una fórmula es lógicamente válida si es verdadera en todo modelo para el lenguaje utilizado en la fórmula. Para expresar de manera formal el teorema de completitud de Gödel, se debe definir el significado de la palabra modelo en este contexto. Esta es una definición básica en la teoría de modelos.

El teorema de Gödel establece una correspondencia entre la verdad semántica y la probabilidad sintáctica en la lógica de primer orden. Crea un vínculo entre la teoría de modelos que se ocupa de lo que es cierto en diferentes modelos, y la teoría de la demostración que estudia lo que se puede probar formalmente en sistemas formales particulares. Gödel utilizó el teorema de completitud para probar el teorema de compacidad, demostrando la naturaleza finitaria del operador de consecuencia lógica. Estos resultados ayudaron a establecer la lógica de primer orden como el tipo de lógica dominante en las matemáticas actuales.

Declaración del teorema

Una fórmula de primer orden se llama lógicamente válida si es verdadera en cada estructura para el lenguaje de la fórmula (es decir, para cualquier asignación de valores a las variables de la fórmula). Para declarar formalmente, y luego demostrar, el teorema de la integridad, es necesario también definir un sistema deductivo. Un sistema deductivo se llama completo si toda fórmula lógicamente válida es la conclusión de alguna deducción formal, y el teorema de la completitud para un sistema deductivo particular es el teorema de que está completo en este sentido. Así, en cierto sentido, hay un teorema de completitud diferente para cada sistema deductivo. Algo importante junto con la integridad es la solidez, el hecho de que sólo las fórmulas lógicamente válidas son demostrables en el sistema deductivo.

Si algún sistema deductivo específico de lógica de primer orden es sólido y completo, entonces es "perfecto" (una fórmula es demostrable si y sólo si es una consecuencia semántica de los axiomas), equivalente a cualquier otro sistema deductivo con el mismo Calidad (cualquier prueba en un sistema se puede convertir en el otro).

La formulación original de Gödel

El teorema de la integridad dice que si una fórmula es lógicamente válida entonces hay una deducción finita (una prueba formal) de la fórmula.

El teorema de Gödel de completitud dice que un sistema deductivo de cálculo de predicados de primer orden es "completo" en el sentido de que no se requieren reglas de inferencia adicionales para probar todas las fórmulas lógicamente válidas. Junto con la integridad hay que tener en cuenta la solidez, el hecho de que sólo las fórmulas lógicamente válidas son demostrables en el sistema deductivo. Junto con la solidez (cuya verificación es fácil), este teorema implica que una fórmula es lógicamente válida si y sólo si es la conclusión de una deducción formal.

Teorema de la existencia del modelo

La versión más simple de este teorema que es suficiente en la práctica para la mayoría de las necesidades:

dice:

Cada teoría consistente y contable de primer orden tiene un modelo finito o contable.

Una versión más general se puede expresar como:

Toda teoría coherente de primer orden con un lenguaje bien ordenado tiene un modelo.

Aquí, una teoría consistente se define como aquella en la que, para ninguna fórmula 'F', tanto 'F' como '¬F' pueden ser probados. La definición sintáctica; La definición semántica sería tautológica en este contexto.

Este teorema de Henkin es la versión más directa obtenida del teorema de la completitud en su prueba más simple.

Teorema de incompletitud de Gödel

Los teoremas de incompletitud de Gödel son dos célebres teoremas de lógica matemática demostrados por Kurt Gödel en 1931. Ambos están relacionados con la existencia de proposiciones indecidibles en ciertas teorías aritméticas.

-El primer teorema de incompletitud: 

afirma que, bajo ciertas condiciones, ninguna teoría matemática formal capaz de describir los números naturales y la aritmética con suficiente expresividad, es a la vez consistente y completa. Es decir, si los axiomas de dicha teoría no se contradicen entre sí, entonces existen enunciados que no se pueden probar ni refutar a partir de ellos. En particular, la conclusión del teorema se aplica siempre que la teoría aritmética en cuestión sea recursiva, esto es, una teoría en la que el proceso de deducción se pueda llevar a cabo mediante un algoritmo.

La prueba del teorema es totalmente explícita y en ella se construye una fórmula, denotada habitualmente G en honor a Gödel, para la que dada una demostración de la misma, se puede construir una refutación, y viceversa. Sin embargo, la interpretación natural de dicha sentencia en términos de números naturales es verdadera.1​

Demostración Primer teorema de incompletitud de Gödel

Cualquier teoría aritmética recursiva que sea consistente es incompleta.

La demostración de este teorema pasa por construir una cierta fórmula, la «sentencia de Gödel» G, que no puede ser probada ni refutada en la teoría aritmética recursiva T: ni G ni ¬G (la negación de G) son teoremas de T. Se dice entonces que G y ¬G son indecidibles o independientes en T.

-Segundo teorema de incompletitud de Gödel

-El segundo teorema de incompletitud es un caso particular del primero: afirma que una de las sentencias indecidibles de dicha teoría es aquella que «afirma» la consistencia de la misma. Es decir, que si el sistema de axiomas en cuestión es consistente, no es posible demostrarlo mediante dichos axiomas.

Los teoremas de incompletitud de Gödel son uno de los grandes avances de la lógica matemática, y supusieron —según la mayoría de la comunidad matemática— una respuesta negativa al segundo problema de Hilbert.1​ Los teoremas implican que los sistemas axiomáticos de primer orden tienen severas limitaciones para fundamentar las matemáticas, y supusieron un duro golpe para el llamado programa de Hilbert para la fundamentación de las matemáticas. Por otra parte, durante algún tiempo ni Hilbert ni otros de sus colaboradores fueron conscientes de la importancia del trabajo de Gödel para su programa.

El segundo teorema de incompletitud muestra otro ejemplo explícito de una fórmula que ninguna teoría aritmética puede demostrar, además de G. De nuevo, usando la numeración de Gödel, puede encontrarse una fórmula, denotada Consis T, cuyo significado es «no puede encontrarse una contradicción en T», o en otras palabras, «T es consistente».

Demostración Segundo teorema de incompletitud de Gödel

En toda teoría aritmética recursiva consistente T, la fórmula Consistente T no es un teorema.

La demostración del segundo teorema requiere traducir el primero a una fórmula. El primer teorema afirma, entre otras cosas, que si T es consistente, entonces G no es demostrable. La fórmula que afirma la consistencia de T es Consis T, mientras que la fórmula que afirma la indemostrabilidad de G es la propia G. La fórmula que traduce el primer teorema (una parte de él) es Consis T ⇒ G, donde «⇒» significa implicación. Gödel demostró que esta fórmula es un teorema,6​ y que por lo tanto Consis T no es un teorema: si lo fuera, de las reglas básicas de T como teoría formal se deduciría que G es demostrable, en contradicción con el enunciado del primer teorema de incompletitud.

Metateorema de validación

En lógica, la validez es una propiedad que tienen los argumentos cuando las premisas implican la conclusión. Si la conclusión es una consecuencia lógica de las premisas, se dice que el argumento es deductivamente válido. Algunos consideran estas dos nociones idénticas y usan ambos términos indistintamente. Otros, sin embargo, consideran que puede haber argumentos que no sean deductivamente válidos, como las inducciones. En cualquier caso, de las inducciones a veces se dice que son buenas o malas, en vez de válidas o inválidas.

Ejemplos de argumentos deductivamente válidos son los siguientes:

1. Todos los planetas giran alrededor del Sol.

2. Marte es un planeta.

3. Por lo tanto, Marte gira alrededor del Sol.

Para que un argumento sea deductivamente válido, no es necesario que las premisas o la conclusión sean verdaderas. Sólo se requiere que la conclusión sea una consecuencia lógica de las premisas. La lógica formal exige únicamente una relación condicional entre las premisas y la conclusión. Esto es: que si las premisas son verdaderas, entonces la conclusión también lo es (esta es la caracterización semántica de la noción de consecuencia lógica); o alternativamente: que la conclusión sea deducible de las premisas conforme a las reglas de un sistema lógico (esta es la caracterización sintáctica de la noción de consecuencia lógica). Si un argumento, además de ser válido, tiene premisas verdaderas, entonces se dice que es sólido.

Las expresiones de las que depende la validez de los argumentos se llaman constantes lógica. Demostración de la validez de un argumento

Un argumento concreto es válido cuando tiene la forma de un esquema de argumento válido. Por ejemplo, considérese el siguiente argumento:

1. Es varón o es mujer

2. No es varón

3. Por lo tanto, es mujer

Este argumento es válido porque tiene la forma de un silogismo disyuntivo, el cual es un esquema de argumento válido:

1. p o q

2. No p

3. Por lo tanto, q

Para determinar la validez de un argumento concreto, entonces, alcanza con determinar la validez su esquema de argumento, y esto se puede lograr por medios semánticos o por medios sintácticos.

Método semántico

En el método semántico, se dice que un esquema de argumento es válido cuando es imposible que las premisas sean verdaderas y la conclusión falsa. Para determinar si esto es el caso, se supone la verdad de las premisas, y aplicando las definiciones de verdad, se intenta deducir la verdad de la conclusión. O también, se supone que las premisas son verdaderas y la conclusión falsa, y aplicando las definiciones de verdad, se intenta deducir una contradicción (reducción al absurdo).

En la lógica proposicional, un método alternativo es transformar un argumento en su correspondiente fórmula, y construir una tabla de verdad. Si la fórmula resulta ser una verdad lógica, entonces el argumento es válido. Esto se debe a que vale el teorema de la deducción y su converso, pero también a que la lógica proposicional es decidible, y por lo tanto siempre admite de un procedimiento algorítmico para determinar si una fórmula cualquiera es una verdad lógica o no.

Método sintáctico

En el método sintáctico, se dice que un esquema de argumento es válido cuando existe una deducción de la conclusión a partir de las premisas del argumento y los axiomas del sistema, utilizando sólo las reglas de inferencia permitidas.

En un sistema de deducción natural, es como el conjunto de axiomas es vacío, un esquema de argumento será válido cuando exista una deducción de la conclusión a partir de las premisas, utilizando sólo las reglas de inferencia permitidas.

Metateorema de solidez y completitud

La solidez es la propiedad que tienen los argumentos cuando son válidos y sus premisas son todas verdaderas.​ Si un argumento es deductivamente válido, entonces si es sólido, su conclusión será necesariamente verdadera.

Por ejemplo, considérese el siguiente argumento:

1.       Todos los seres vivos pueden morir.

2.       Todos los griegos son seres vivos.

3.       todos los griegos pueden morir.

Este argumento es sólido, porque por un lado es válido, y por otro lado las premisas son todas verdaderas. Pero considérese el siguiente argumento:

1.       Todos los griegos pueden morir.

2.       Todas las plantas son griegos

3.       Luego, todas las plantas pueden morir.

Este argumento no es sólido, porque aunque válido, una de las premisas es falsa. Por último, considérese el siguiente argumento:

1.       Todos los hombres pueden morir.

2.       Todos los patos son animales.

3.       Luego, todos los animales pueden morir.

Este argumento tampoco es sólido, porque aunque las premisas son todas verdaderas, el argumento no es válido. En nada cambia que la conclusión sea también verdadera.

Completitud

En metalógica, la completitud o completitud semántica es la propiedad metateórica que tienen los sistemas formales cuando todas las fórmulas lógicamente válidas (todas las verdades lógicas) del sistema son además teoremas del sistema.​ Es decir, cuando el conjunto de las verdades lógicas del sistema es un subconjunto del conjunto de teoremas.

Por otra parte, la completitud sintáctica es la propiedad que tienen los sistemas formales cuando, para toda fórmula del lenguaje del sistema, o bien es un teorema o bien su negación lo es. Esto es, existe una prueba para cada fórmula o para su negación.

La lógica proposicional y la lógica del primer orden son ambas semánticamente completas, pero no sintácticamente completas. Por ejemplo, en la lógica proposicional, la fórmula p no es un teorema, y tampoco lo es su negación, de modo que eso basta para mostrar que no es sintácticamente completa. No obstante, como ninguna de esas dos fórmulas es una verdad lógica, no afectan a la completitud semántica del sistema.

El teorema de completitud de la lógica de primer orden:

Según el teorema de completitud de Gödel, «para toda fórmula A de la lógica cuantificacional de primer orden, si A es lógicamente verdadera, entonces A es deducible». Se llama teorema de completitud, porque todas las verdades lógicas expresables mediante el sistema son demostrables dentro del mismo sistema. Es un sistema completo. Gödel, además de formular un teorema tan elegante, demostró que era verdadero.

Formalmente, el teorema de Gödel es así: ╞ A → ├ A. El símbolo «╞» delante de una fórmula, significa que esta es una verdad lógica; el signo «├» delante de una fórmula, significa que esta es deducible y si está entre dos fórmulas, por ejemplo A ├ B, se lee «B se deduce de A». Pues bien, para demostrar su teorema Gödel supone

 (1) ╞ A

    Si (1) es verdadera, entonces ¬A, «no A», es insatisfacible, esto es, falsa para cualquier interpretación.

 (2) ¬ ╞ ¬A

    Y si ¬A es insatisfacible, es inconsistente, esto es, se puede deducir de ella una fórmula y su contraria:

 (3) ¬A ├ B ^ ¬A ├ ¬B

    Puesto que ¬A es inconsistente, ¬¬A («no, no A»), su negación, es consistente:

 (4) (¬A ├ B ^ ¬A ├ ¬B) → ├ ¬¬ A

    Por Modus Ponens entre (3) y (4), se obtiene

 (5) ├ ¬¬A

    Y aplicando la doble negación sobre (5), se obtiene:

 (6) ├ A

    Y puesto que a partir de ╞ A hemos llegado a ├ A, queda demostrado el teorema de Gödel

 (7) ╞ A → ├ A