Introducción a la Lógica
En virtud de las entradas que ya hemos visto, debemos tener en cuenta que la Lógica (cualquier Lógica Matemática) tiene dos componentes fundamentales:
- Semántica: Una colección de configuraciones o mundos posibles que pueden ser modelados. En matemáticas formales, a estos mundos se les suele llamar estructuras o interpretaciones. El número de configuraciones es a menudo extremadamente grande, a veces infinito, y por tanto puede llegar a ser imposible describirlos y razonar sobre ellos de forma directa.
- Sintaxis: Un lenguaje para describir las propiedades de los posibles mundos, junto con un conjunto de reglas para razonar sobre ellos.
No se puede comprender la Lógica a menos que se entiendan estas dos ideas y la relación que hay entre ellas. Así que vamos a dar esta introducción con un ejemplo que nos permita entender esta relación de la forma más directa posible. Además, el ejemplo lo veremos representado en las dos lógicas más sencillas y en las que se basa el curso: la Lógica Proposicional, y la Lógica de Primer Orden, y de esa forma también nos prepararemos para ver las ventajas e inconvenientes de usar cada una de ellas.
El Mundo-Bloque
Nuestro mundo está formado por 2 cubos y 2 pirámides encima de una mesa (un mundo limitado, pero que dispone de todo lo necesario para nuestros objetivos). En este mundo los cubos se pueden apilar, y las pirámides se pueden poner encima de los cubos, pero con la restricción de que solo se permite apilar un bloque encima de otro único bloque, no apoyado sobre dos bloques a la vez, además, las pirámides solo pueden apoyarse encima de cubos, no encima de otra pirámide.
Si analizamos las posibles configuraciones que pueden tomar nuestros bloques, veremos rápidamente que se admiten 13 distintas configuraciones (o que hay 13 mundos posibles):
Uno con esta distribución:
Dos con cada una de estas distribuciones:
Y cuatro con cada una de estas distribuciones:
Lo que hemos hecho hasta ahora es describir la semántica de nuestro mundo. Las afrimaciones básicas en este mundo serían de la forma "$B_1$ es un cubo", "$P_1$ está sobre $B_2$, "$P_2$ está sobre la mesa", etc. Veamos ahora una posible sintaxis para describirlo de forma más cómoda y sin ambigüedad (pero es solo eso, una forma más cómoda, nada más):
Si consideramos que $x,y\in \{B_1,B_2,P_1,P_2\}$, entonces podemos definir los siguientes esquemas proposicionales (afirmaciones simples que podemos hacer del mundo):
- $OnTable(x)$ : el objeto $x$ está sobre la mesa directamente.
- $On(x,y)$ : el objeto $x$ está sobre el objeto $y$.
- $IsCube(x)$ : el objeto $x$ es un cubo.
- $IsPyramid(x)$ : el objeto $x$ es una pirámide.
Por ejemplo: $OnTable(B_1)$: "$B_1$ está sobre la mesa", $On(P_1,B_1)$: "$P_1$ está sobre $B_1$", $IsCube(B_1)$: "$B_1$ es un cubo", $IsPyramid(P_2)$: "$P_2$ es una pirámide". Estas proposiciones son simples porque no se pueden descomponer en proposiciones más simples, de alguna forma, es lo más básico que se puede decir de nuestro mundo.
- Algunas proposiciones son ciertas en todos los mundos posibles: $IsCube(B_1)$.
- Algunas proposiciones son falsas en todos los mundos posibles: $IsCube(P_1)$
- Algunas proposiciones son ciertas en unos mundos y falsas en otros: $On(P_1,B_1)$.
Un mundo en el que una proposición $\varphi$ es cierta se llama modelo de $\varphi$.
Para formar expresiones más ricas y complejas podemos usar conectivas lógicas que las combinan con el significado habitual (podéis encontrarlos formalizados en los apuntes del curso): $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$. Cuando estas conectivas se usan adecuadamente y se construyen expresiones correctas, se dice que estamos ante una fórmula bien formada. Algunos ejemplos son:
- $IsCube(B_1) \vee IsPyramid(B_1)$
- $(On(B_1,B_2) \rightarrow (OnTable(P_1) \vee OnTable(P_2))$
- $(OnTable(B_1) \wedge \neg OnTable(B_1))$
- $OnTable(B_1) \rightarrow (OnTable(B_2) \vee On(P_1,B_1))$
Al igual que ocurría con las proposiciones simples, estas fórmulas pueden ser ciertas en todos los mundos, falsas en todos los mundos, o ciertas en unos mundos y falsas en otros, y el concepto de modelo se extiende a ellas con la misma idea.
Describiendo un único mundo posible
Consideremos el mundo siguiente:
Las proposiciones que son verdad en este mundo son:
$$\{IsCube(B_1), IsCube(B_2), IsPyramid(P_1),IsPyramid(P_2), \\ OnTable(B_1), OnTable(B_2), OnTable(P_1), On(P_2,B_1)\}$$
Y la fórmula
$$IsCube(B_1)\wedge IsCube(B_2)\wedge IsPyramid(P_1)\wedge IsPyramid(P_2)\wedge\\ OnTable(B_1)\wedge OnTable(B_2)\wedge OnTable(P_1)\wedge On(P_2,B_1)$$
que se obtiene a partir de ellas caracteriza este mundo concreto (ningún otro mundo de los 13 posibles la verifica). Pero obsérvese que incluso $$OnTable(B_1)\wedge OnTable(B_2)\wedge OnTable(P_1)\wedge On(P_2,B_1)$$ o $$OnTable(B_1)\wedge OnTable(P_1)\wedge On(P_2,B_1)$$ también lo caracterizan.
Esto es un resultado del proceso de modelado, del conjunto de proposiciones atómicas que hemos considerado, y no es cierto en general. Por ejemplo, si en nuestra semántica eliminamos las proposiciones del tipo $OnTable(x)$, entonces hay mundos posibles, como:
que se se caracteriza por $On(P_2,B_1) \wedge \neg On(P_1,B_2) \wedge \neg On(B_1,B_2)$, pero no hay ningún conjunto de proposiciones atómicas positivas (tal y como se han dado) que lo describa.
En general, necesitaremos las proposiciones atómicas ciertas y las falsas para poder describir completamente un mundo. Pero incluso en algunas situaciones (por ejemplo, cuando estamos trabajando sobre un conjunto infinito) será imposible describir un mundo por medio de las proposiciones atómicas y sus negaciones.
Consecuencia Lógica
Si $W$ denota el conjunto de los 13 posibles mundos del ejemplo anterior, y $\varphi$ es una fórmula bien formada, entonces escribiremos:
$$\models^W \varphi$$
para denotar que $\varphi$ es cierto en cualquier mundo posible (una fórmula así se denomina Válida o Tautología).
Por ejemplo: $\models^W (OnTable(B_1) ∨ OnTable(B_2))$
Si $\Sigma$ es un conjunto de fórmulas bien formadas, escribiremos
$$\Sigma \models^W \varphi$$
para denotar que $\varphi$ es cierta en todos los mundos en los que se verifican todas las fórmulas de $\Sigma$, y diremos que $\varphi$ es consecuencia lógica de $\Sigma$.
Por ejemplo: $\{On(B_1,B_2)\} \models^W (OnTable(P_1) \vee OnTable(P_2))$
Observa (y se puede probar que siempre es cierto) que la expresión anterior es equivalente a esta otra: $$\models^W (On(B_1,B_2)\rightarrow (OnTable(P_1) \vee OnTable(P_2)))$$
Razonando sobre el mundo de bloques
Por ahora lo que tenemos es:
- Un conjunto posible de mundos.
- Un lenguaje para describir propiedades de esos mundos.
Pero, ¿qué es lo que falta?
- Un medio para razonar acerca de las propiedades de esos mundos.
Por ejemplo, considera la siguiente propiedad: O bien $B_1$ está sobre la mesa o, si no, $B_1$ está sobre $B_2$, que se escribe formalmente como: $OnTable(B_1) \vee On(B_1,B_2)$.
Para verificar la validez de esta afirmación el único método que tenemos actualmente es comprobarla en cada uno de los 13 mundos posibles. El problema es que las aplicaciones más interesantes tienen muchos más mundos posibles (incluso una cantidad infinita), por lo que este método no es una buena opción.
La alternativa es disponer de un procedimiento (si es automatizable, mejor) de inferencia de manera que si alimentamos el procedimiento con la propiedad que queremos probar, $\varphi$, y la descripción semántica de $W$, entonces la respuesta, que denotaremos como $W\vdash \varphi$, sea cierta solo en el caso en que se tenga que $\models^W \varphi$.
Clases de Lógicas
En este curso vamos a estudiar dos clases de Lógicas:
- Lógica Proposicional
- Lógica de Primer Orden
Lógica Proposicional
En la Lógica Proposicional las proposiciones básicas no tienen parámetros. La forma en que hemos escrito las propiedades del mundo de bloques en los ejemplos anteriores es básicamente en una Lógica Proposicional.
Las ventajas de la Lógica Proposicional son:
- Es simple.
- No tiene problemas de decibilidad (es decir, tenemos mecanismos para responder siempre a la pregunta de si una afirmación es cierta o falsa).
Sus desventajas son:
- Tiene una capacidad de representación limitada.
- Algunas afirmaciones simples pueden requerir representaciones muy largas y enrevesadas.
Por ejemplo, la afirmación "Hay una pila de 3 objetos" tiene 4 opciones para describirse que se pueden resumir como:
$$(On(B_1,B_2) \wedge (On(P_1,B_1) \vee On(P_2,B_1)))\vee \\ (On(B_2,B_1) \wedge (On(P_1,B_2) \vee On(P_2,B_2)))$$
y si consideramos la afirmación "Hay al menos 2 objetos sobre la mesa", algo que siempre es cierto, su representación es más compleja porque contiene 6 opciones:
$$(OnTable(B_1) \wedge OnTable(B_2)) \vee\\ (OnTable(B_1) \wedge OnTable(P_1)) \vee\\ (OnTable(B_1) \wedge OnTable(P_2)) \vee\\ (OnTable(B_2) \wedge OnTable(P_1)) \vee\\ (OnTable(B_2) \wedge OnTable(P_2)) \vee\\ (OnTable(P_1) \wedge OnTable(P_2))$$
Lógica de Primer Orden
La principal diferencia entre las Lógicas Proposicionales y las Lógicas de Primer Orden es que estas últimas admiten:
- Variables que pueden tomar valores en un dominio de elementos.
- Cuantificadores ("para todo" y "existe").
Lo que resulta en representaciones mucho más compactas y legibles. Por ejemplo, “Hay una pila de 3 objetos" se escribiría:
$$\exists x \exists y \exists z (On(y,x) \wedge On(z,y))$$
Observa que esta fórmula se puede generalizar fácilmente a pilas con cualquier número de objetos, a diferencia de la misma fórmula escrita en una Lógica Proposicional.
El otro ejemplo: "Hay al menos 2 objetos sobre la mesa", requiere un truco adicional. Una primera aproximación sería:
$$\exists x \exists y(OnTable(x) \wedge OnTable(y))$$
pero no es correcta, ya que nada garantiza que $x$ e $y$ sean objetos distintos. Para representar este ejemplo de forma satisfactoria, hemos de permitir que el lenguaje haga uso de la igualdad:
$$\exists x \exists y (OnTable(x) \wedge OnTable(y)) \wedge (x\neq y))$$
Veremos a lo largo del curso que introducir la igualdad complica la lógica sustancialmente, sobre todo desde un punto de vista computacional.
La principal ventaja de la Lógica de Primer Orden es:
- Mayor capacidad de representación.
Y sus desventajas:
- Genera problemas computacionalmente difíciles.
- La inferencia se vuelve indecidible (es decir, en general no podemos asegurar que haya un método automatizable para inferir si una afirmación es cierta o no).
Veamos algunos ejemplos de cómo se describirían afirmaciones en esta lógica, y a la vez intentaremos ver si somos capaces de extraer un conjunto de afirmaciones que caractericen los mundos posibles de bloques (a este proceso se le llama axiomatización, y a las fórmulas de este conjunto, axiomas):
- Todo es un cubo o una pirámide: $$\forall x (IsCube(x)\vee IsPyramid(x))$$
- Nada puede ser las dos cosas a la vez: $$\forall x (\neg (IsCube(x) \wedge IsPyramid(x)))$$
- Los objetos se pueden definir explícitamente: $$ \forall x ( IsCube(x) \leftrightarrow ( x=B_1 \vee x=B_2))$$ $$\forall x ( IsPyramid(x) \leftrightarrow ( x=P_1 \vee x=P_2))$$
- Los objetos son distintos entre sí: $$(B_1 \neq B_2) \wedge (P_1 \neq P_2) \wedge (B_1 \neq P_1) \wedge (B_1 \neq P_2) \wedge (B_2 \neq P_1) \wedge (B_2 \neq P_2)$$ (en realidad, solo serían necesarias dos afirmaciones, el resto se podría deducir haciendo uso de otros axiomas).
- Ningún objeto puede descansar sobre una pirámide: $$\forall x \forall y (\neg (IsPyramid(x) \wedge On(y,x)))$$
- Ningún objeto puede descansar encima de otro objeto y sobre la mesa a la vez:$$\forall x \forall y (\neg(OnTable(x) ∧ On(x,y)))$$
- Todo objeto está sobre la mesa o encima de otro objeto:$$\forall x \exists y ( OnTable(x) \vee On(x,y)))$$
- Ningún objeto descansa encima de sí mismo: $$\forall x (\neg On(x,x)))$$
- Un objeto descansa, a lo sumo, encima de un solo objeto: $$\forall x \forall y \forall z ((On(x,y) \wedge On(x,z)) \rightarrow y=z))$$
- A lo sumo un solo objeto puede descansar encima de otro: $$\forall x \forall y \forall z ((On(y,x) \wedge On(z,x)) \rightarrow y=z))$$
De una axiomatización como esta surgen algunas preguntas fundamentales:
¿Es esta representación completa?, ¿se nos pueden colar configuraciones ilegales? Incluso para este caso sencillo no es fácil responder a estas preguntas, y puede ser extremadamente complicado para casos ligeramente más complejos.
Si el motor de inferencia debe razonar correctamente, se le debe proporcionar una axiomatización completa y correcta del conjunto de mundos posibles. Esta caracterización podría ser hecha también usando la Lógica Proposicional, pero en ese caso suele contener muchos más axiomas.
Algunas notas finales
Hay muchas otras clases de Lógicas que son importantes para las Ciencias de la Computación, por ejemplo:
- Lógicas Modales.
- Lógicas Temporales.
- Lógicas Dinámicas.
- Lógicas Multivaluadas.
- Lógicas Difusas.
- Lógicas de Características.
- Lógicas de Orden Superior.
Para entender estas otras Lógicas es imprescindible comenzar por las dos que veremos en este curso, y que constituyen la base de todas las demás.