Lógica Computacional
Nota 01. Introducción¹¹Esta nota se basa en los libros: Ben-Ari M., Mathematical Logic for Computer Science y Elliott M., Introduction to Mathematical Logic.

Noé Salomón Hernández S

1 Los orígenes de la lógica matemática

La lógica formaliza métodos válidos de razonamiento. Al estudiar estos métodos, la lógica se interesa en la forma, en lugar del contenido. Los griegos comenzaron con el estudio de esta disciplina al nombrar y clasificar reglas lógicas. El conjunto más conocido de tales reglas son los silogismos, por ejemplo:

1.

Todos los hombres son mortales. Sócrates es un hombre. Por lo tanto, Sócrates es mortal.
2.

Todos los gatos comen pescado. Silvy es un gato. Por lo tanto, Silvy come pescado.

Ambos tienen la misma forma: Todo $A$ es $B$ . $S$ es $A$ . Por lo tanto, $S$ es un $B$ . La verdad o falsedad de las premisas y de la conclusión no tienen importancia para lo lógicos. Ellos sólo quieren conocer si las premisas implican la conclusión. Formalizar y catalogar sistemáticamente métodos válidos de razonamiento es una de las principales tareas de los lógicos. Cada proposición categórica puede ser reducida a una de las cuatro formas lógicas:

Nombre	Símbolo	Frase
Universal Afirmativo	$A$	Todo $S$ es $P$
Universal Negativo	$E$	Todo $S$ es no $P$
Existencial Afirmativo	$I$	Algún $S$ es $P$
Existencial Negativo	$O$	Algún $S$ es no $P$

Definición 1.1

Un silogismo categórico es un argumento que contiene únicamente proposiciones categóricas $A$ , $E$ , $I$ y $O$ , con dos premisas y una conclusión. Además, se identifican tres términos en el argumento (el mayor, el menor y el medio), cada uno figurando una vez en dos proposiciones categóricas.

Así, existen 256 posibles formas de construir silogismos categóricos, pues hay 64 combinaciones para las proposiciones categóricas usando $A$ , $E$ , $I$ y $O$ y para cada una de ellas se tienen 4 posibles figuras que determinan el orden de los términos. De las 256 sólo 24 son formas válidas.

La investigación en lógica tuvo un auge en el siglo XIX cuando los matemáticos intentaron clarificar los fundamentos de las matemáticas. Sistemas lógicos —axiomas y reglas de inferencia– fueron desarrollados y se estudiaba si tenían el comportamiento semántico esperado, como sigue:

Consistencia.: Un sistema lógico es consistente si es imposible demostrar una fórmula y su negación.
Independencia.: Los axiomas del sistema lógico son independientes si ningún axioma puede ser demostrado a partir de los demás.
Correctud.: Todos los teoremas que pueden ser demostrados en el sistema lógico son verdaderos.
Completud.: Todos los enunciados verdaderos pueden ser demostrados en el sistema lógico.

Al terminarse el siglo XIX, el mundo de las matemáticas fue sacudido por el descubrimiento de las paradojas, es decir, argumentos que conducen a una contradicción. Por ejemplo:

La paradoja de Russell (1902). Por un conjunto nos referimos a cualquier colección de objetos. Los conjuntos mismos pueden ser miembros de otros conjuntos. Puede haber conjuntos que pertenecen a ellos mismos —por ejemplo, el conjunto de todos los conjuntos. Ahora, consideremos el conjunto $A$ de todos aquellos conjuntos $X$ tales que $X$ no es un miembro de sí mismo. Por definición, $A$ es un miembro de $A$ si y solo si $A$ no es un miembro de $A$ . Así, si $A$ es un miembro de $A$ , entonces $A$ no es un miembro de $A$ ; y si $A$ no es un miembro de $A$ , entonces $A$ es un miembro de $A$ . En cualquier caso llegamos a una contradicción.

Durante la primera mitad del siglo XX, la lógica se consolidó como un tema de las matemáticas modernas. El sistema para investigar los fundamentos de las matemáticas se llamó programa de Hilbert. Su meta central era demostrar que las matemáticas, comenzando con la aritmética, podían ser axiomatizadas en un sistema que era tanto consistente como completo. En 1931, Kurt Gödel demostró que esta meta no podía lograrse: cualquier sistema axiomatizado consistente para la aritmética es incompleto ya que contiene enunciados verdaderos que no pueden ser demostrados dentro del sistema.

En la segunda mitad del siglo XX, la lógica matemática se aplicó en las ciencias de la computación.

Definición 1.2

Un argumento lógico es una colección finita de afirmaciones dividida en premisas y conclusión. El argumento lógico puede ser correcto o incorrecto. Un argumento es correcto o válido si suponiendo que sus premisas son ciertas, entonces la conclusión también lo es. En el análisis del argumento lógico no importa el contenido sino la forma de las afirmaciones en cuestión.

Componentes de un sistema lógico

Cualquier sistema lógico consta de:

Sintaxis.: Establece un lenguaje formal mediante el cual se construyen fórmulas aceptadas por el sistema lógico.
Semántica.: Define un mecanismo que proporciona de significado al lenguaje formal dado por la sintaxis.
Teoría de prueba.: Ofrece un mecanismo sintáctico cuyo propósito es obtener expresiones semánticamente válidas de un lenguaje. Es decir, se encarga de decidir la correctud de un argumento lógico por medios sintácticos.

2 Lógica proposicional

Nuestra primer tarea es formalizar el concepto de verdad de un enunciado. A cada enunciado se le asigna uno de dos valores, llamados verdadero y falso, o $\top$ y $\bot$ . Las fórmulas de la lógica proposicional se construyen a partir de proposiciones atómicas, que son enunciados que no tienen estructura interna. Tales fórmulas se pueden combinar usando operadores Booleanos, a los cuales se les dota de un significado formal en la lógica. Por ejemplo, la conjunción se define como el operador que asigna el valor verdadero si y sólo si se aplica a dos fórmulas cuyos valores son verdaderos.

Las reglas de la sintaxis definen la estructura de las fórmulas en la lógica proposicional. La semántica —el significado de las fórmulas— se define por interpretaciones, las que asignan uno de los valores de verdad $\top$ o $\bot$ a cada proposición atómica. Para cada forma de construir una fórmula, una regla semántica especifica su valor de verdad basado en los valores de sus componentes.

Una prueba o demostración es una deducción de una fórmula a partir de un conjunto de fórmulas llamadas axiomas usando reglas de inferencia. El conjunto de fórmulas demostrables es el mismo que el conjunto de fórmulas que son siempre verdaderas.

La lógica proposicional es central en el diseño de hardware porque el hardware está diseñado con componentes que tienen dos niveles de voltaje. Los circuitos son descritos por compuertas lógicas.

3 Lógica de primer orden

La lógica proposicional no es lo suficientemente expresiva para formalizar las teorías matemáticas como la aritmética. Se estudiará un sistema lógico conocido como lógica de primer orden que puede manipular y darle sentido a las variables, relaciones y funciones. Entre las aplicaciones de la lógica de primer orden están los demostradores automáticos de teoremas y la programación lógica. La investigación en los demostradores automáticos de teoremas condujo a un método nuevo y eficiente de demostración de fórmulas de la lógica de primer orden llamado resolución. El uso de demostradores de teoremas para realizar cómputos es llamado programación lógica. La programación lógica es atractiva porque es declarativa.

4 Verificación de programas

Algunos sistemas críticos en transporte, medicina y finanzas son controlados por software por lo que es vital su correcto funcionamiento. Como un programa informático es una descripción formal de un cálculo, puede ser verificado en la misma forma que un teorema matemático puede ser verificado usando lógica. Primero, es necesario expresar una especificación de correctud como un enunciado formal en lógica. La lógica temporal es ampliamente usada para este propósito porque puede expresar el comportamiento dinámico de un programa. Luego, es necesario formalizar la semántica de un programa y, finalmente, es necesario un sistema formal para deducir que un programa satisface una especificación de correctud. Un sistema axiomático para la lógica temporal puede ser usado para demostrar la correctud de programas concurrentes.

Para programas secuenciales, la verificación se realiza usando un sistema axiomático llamado lógica de Hoare por su inventor C. A. R. Hoare. La lógica de Hoare supone que conocemos la verdad de enunciados del dominio del programa.

En lugar de demostrar deductivamente la correctud de un programa relativo a la especificación, un verificador de modelos corrobora la verdad de una especificación en cada estado posible al que se puede llegar durante el cómputo de un programa.

La siguiente lista menciona varias aplicaciones de la lógica computacional, algunas de las cuales ya se han mencionado arriba.

Diseño y verificación de circuitos,
demostradores automáticos de problemas,
programación lógica,
verificación de modelos,
inteligencia artificial,
bases de datos,
representación del conocimiento,
asistentes de prueba,
diseño de lenguajes de programación, y
lenguajes de descripción de hardware, entre otros.

En resumen, la lógica matemática formaliza el razonamiento. Aunque los sistemas lógicos son muy diferentes, estudiamos cada lógica en una manera similar. Comenzamos con su sintaxis (lo que constituye una fórmula en la lógica) y su semántica (cómo se asignan valores de verdad a una fórmula). Luego, describimos el método para decidir la validez de una fórmula.

5 Ejemplo del uso de la lógica en la vida cotidiana²²Tomado de Nievergelt, Yves (2015). Logic, mathematics, and computer science: modern foundations with practical applications. New York,: Springer.

¿Es Plutón un planeta?

Una definición de planeta establece que estos cuerpos celestes son más grandes que las lunas. Esta definición puede declararse en términos de una hipótesis (H): un cuerpo celeste $P$ es un planeta; una conclusión (C): el cuerpo celeste $P$ es más grande que cualquier luna; y una implicación “si H, entonces C”:

Si un cuerpo celeste $P$ es un planeta (si H), entonces el cuerpo celeste $P$ es más grande que cualquier luna (entonces C).

Con la implicación lógica (“si H, entonces C”) se tienen otras dos formas útiles:

La recíproca “si C, entonces H”, que en este caso es falsa porque el sol es más grande que cualquier luna (C es verdadera), pero el sol no es un planeta (H es falsa).
La contrapositiva “si no C, entonces no H”:

Si un cuerpo celeste $P$ no es más grande que cualquier luna (si no C), entonces $P$ no es un planeta (entonces no H)

En 1978 se realizaron mediciones que determinaron que Plutón es más pequeño que la Luna; por consiguiente, Plutón no se debería considerar como un planeta.

La definición misma “si H, entonces C” puede examinarse en la práctica. Por ejemplo, algunos textos clasifican a Mercurio como planeta, pero también clasifican a Ganímedes como una luna de Júpiter, siendo Mercurio más pequeño que Ganímedes. Así, el enunciado “si Mercurio es un planeta, entonces Mercurio es más grande que cualquier luna” es falso. Por lo tanto, la definición anterior “si H, entonces C” es falsa y Plutón puede considerarse como planeta. La lógica ha puesto en claro que el problema no tiene que ver con la condición de Plutón, pero sí con la definición de planetas (aquí pueden consultar la definición de planeta de acuerdo a la NASA).

6 Acertijos

1.

En cierta ocasión le preguntaron a una joven que cuántos años tenía. Ella respondió así: antier tenía 22 años, pero el año próximo cumpliré 25. Esto es lógicamente posible. ¿Cómo se explicaría esta situación?
2.

En una isla viven dos tipos de hombres: los caballeros, que siempre dicen la verdad, y los bribones, que siempre mienten. Julia fue a visitar la isla y encontró a dos hombres. Le preguntó a uno de ellos si los dos eran caballeros. Con la respuesta que le dio este hombre no pudo deducir qué eran. Entonces le preguntó al otro hombre si el primero al que le había preguntado era caballero. Con la respuesta que obtuvo ya dedujo qué eran. ¿Cuál fue su conclusión?
- Que los dos eran mentirosos.
- Que el primero era mentiroso y el segundo caballero.
- Que los dos eran caballeros.
- Que el primero era caballero y el segundo mentiroso.
3.

Das una vuelta a la pista a 20 Km/hr. ¿A qué velocidad debes dar la segunda vuelta para que la velocidad promedio de las 2 vueltas sea el doble: 40 Km/hr? (Fuente: SabiasQue.info).

Lógica Computacional Nota 01. Introducción11Esta nota se basa en los libros: Ben-Ari M., Mathematical Logic for Computer Science y Elliott M., Introduction to Mathematical Logic.