**IAIC 2024-25** Introducción a la Lógica De la Lógica Proposicional y la Lógica de Primer Orden !!!side:1 Para una visión más completa de la lógica, se puede visitar el material del curso [Lógica Informática](http://www.cs.us.es/cursos/liti/) que se imparte en diversos grados de la E.T.S. Ingeniería Informática de la Universidad de Sevilla, así como las referencias bibliográficas que se pueden encontrar en ellos. Estas notas son un resumen (una poda algo torpe y comprimida) del contenido de esos cursos. En este tema daremos una introdcción breve (brevísima) de **Lógica Proposicional** junto con una aproximación superficial a la **Lógica de Predicados** (o **de Primer Orden**). No podemos esperar, pues, una formalización exhaustiva, sino únicamente una aproximación intuitiva a cuáles son sus fundamentos, los problemas que buscan resolver, y algunos de los algoritmos más habituales para automatizar sus soluciones. Si ya has estudiado un curso de lógica formal lo más probable es que estas notas no te sirvan de mucho y que encuentres muchas carencias (e incluso alguna *mentira piadosa* a modo de *atajo*), pero no olvides que su objetivo es servir de primera aproximación a toda una rama fundamental de las Matemáticas y la Computación para alumnos que no han tenido contacto previo con la Lógica Formal $^1$. !!!note Antes de comenzar, queremos que el alumno observe la similitud (intencional) que se presenta entre muchos de los conceptos que vamos a ver a continuación y los que veremos en el tema siguiente, CSPs (Problemas de Satisfacción de Restricciones), que hacen que mucho de lo que veamos se pueda leer como un caso particular de los CSPs, pero aquí haciendo uso de variables booleanas (que toman los valores `true/false`) y allí de valores genéricos. En consecuencia, los métodos que veremos para resolver CSPs generales se pueden aplicar a este caso, aunque ahora nos centraremos en métodos específicos que sacan provecho del carácter booleano de las variables que intervienen. # Lógica Antes de intentar definir formalmente la Lógica Proposicional y la Lógica de Primer Orden, vamos a presentar el contexto en el que nos moveremos e intentar responder qué es la **Lógica** en general. !!!def: Lógica La **Lógica** es la rama del conocimiento que se encarga de estudiar las formas en que se pueden inferir verdades de una forma válida. La **Lógica Matemática** añade el formalismo necesario por medio de un lenguaje adecuado y de los métodos precisos para dar las condiciones de validez universal. En este sentido, se pueden dar diversos formalismos para afrontar el problema de la inferencia válida. La **Lógica Proposicional** fue, posiblemente, el primer intento serio al que se dio forma, por allá en tiempos de la famosa Grecia Clásica. Pese a su indudable utilidad, debido a las limitaciones que presentaba (y de las que hablaremos más adelante) los matemáticos la ampliaron para dotarla de mayor capacidad expresiva, lo que se formalizaría en la **Lógica de Primer Orden** (y en la multitud de variantes y extensiones que aparecieron posteriormente). Todos los sistemas lógicos intentan, de una u otra forma, resolver el problema de cómo *asegurar cuándo, dada una base de conocimientos que se suponen ciertos, podemos confirmar que una afirmación es necesariamente cierta*... de forma coloquial, cuándo podemos decir que una afirmación concreta se deduce de los hechos observados (o supuestos). Normalmente, los sistemas lógicos se enfrentan a este problema definiendo: 1. De qué forma se pueden representar los hechos y afirmaciones; es decir, proporcionando un lenguaje formal de representación. 2. Qué entendemos por *afirmación cierta*. 3. Qué reglas podemos utilizar para garantizar la corrección de las deducciones que obtenemos. !!!side:2 Podríamos decir que la Lógica fue el primer intento formal de automatizar actos considerados inteligentes de manera general. Si consideramos que extraer conclusiones (inferir) a partir de hechos observados, se considera un rasgo inteligente, el papel de la Lógica se convierte en fundamental para los objetivos de la IA $^2$. # Lógica Proposicional Comencemos, pues, por la variante más simple (y más conocida) detallando cómo se definen concretamente cada uno de estos puntos. ## Sintaxis y Semántica !!!def: Lógica Proposicional En el caso de la **Lógica Proposicional** (**LP**), las expresiones que podemos escribir con su lenguaje pueden tener dos posibles valoraciones o evaluaciones: **verdad** o **mentira** (que, habitualmente, notaremos respectivamente por $V|F$, $T|F$, o $1|0$), y permiten usar los siguientes símbolos para poder expresar las afirmaciones del mundo: 1. Un conjunto infinito (pero numerable) de símbolos, que llamaremos **variables proposicionales**: $p$, $q$, $r$, $s$, ..., $p_1$, $p_2$,... 2. Una serie de conectivas que permiten combinar esos símbolos de forma adecuada: $\neg$, $\vee$, $\wedge$, $\rightarrow$ y $\leftrightarrow$, que se corresponden, respectivamente, con la **negación** (*no*...), **disyunción** (...*o*...), **conjunción** (...*y*...), **implicación** (*si ... entonces...*), y **doble implicación** (...*si y sólo si*...). 3. Un par de **símbolos auxiliares**, $($ y $)$, para facilitar la escritura de las expresiones.  Intuitivamente, las variables proposicionales representan afirmaciones atómicas (que pueden ser verdad o mentira, y que no se pueden descomponer en afirmaciones más pequeñas), y las conectivas son operadores que permiten construir expresiones más complejas (o, al menos, más largas) a partir de expresiones más simples. Pero, al igual que en cualquier otro lenguaje, no vamos a admitir como correcta cualquier combinación de los símbolos anteriores, y llamaremos **fórmulas** solamente a aquellas expresiones que sí sean correctas en el sistema. !!!ejemplo Por ejemplo: $(p \rightarrow q) \vee (\neg q \wedge r)$ es una fórmula correcta, mientras que $p \neg \wedge q$ no lo es. Se puede dar una definición formal de qué es una fórmula (es decir, una expresión que está correctamente escrita) y qué no lo es, pero con la idea intuitiva es suficiente para este curso acelerado. Basta tener en cuenta que una expresión es una fórmula si se puede construir usando corectamente las conectivas anteriores junto con las variables proposicionales. De igual forma, podemos definir formalmente cuándo una fórmula es una **subfórmula** de otra, pero no presentaremos la definición formal y haremos uso del concepto de subfórmula de manera intuitiva. El significado de las conectivas es el esperado en el lenguaje natural, aunque para determinar sin lugar a dudas su significado es habitual dar las **Tablas de Verdad** de las conectivas en función de la veracidad de las variables (o subfórmulas) que intervienen (observa que, realmente, las conectivas son funciones que transforman valores booleanos en valores booleanos): | $p$ | $q$ | $\neg\ p$ | $\neg\ q$ | $p\land q$ | $p\lor q$ | $p\rightarrow q$ | $p\leftrightarrow q$ | | ---- | ---- | --------- | --------- | ---------- | --------- | ---------------- | -------------------- | | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | | $1$ | $0$ | $0$ | $1$ | $0$ | $1$ | $0$ | $0$ | | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | $0$ | | $0$ | $0$ | $1$ | $1$ | $0$ | $0$ | $1$ | $1$ | Las variables proposicionales no tienen un valor fijo de verdad, sino que, como su nombre indica, son variables que pueden tomar cualquiera de los dos valores posibles. Cuando tenemos una fórmula y prefijamos los valores de las variables que intervienen en ella, decimos que tenemos una **valoración** o **asignación**. A partir de los valores prefijados de las variables, y aplicando de forma iterada las reglas de la tabla anterior sobre la construcción de una fórmula, se puede obtener el valor de verdad de cualquier fórmula compuesta. Así pues, cualquier fórmula también puede verse como una *función* de las variables proposicionales que intervienen. Cuando representamos la tabla de los posibles valores que puede tomar la fórmula en función de todos los posibles valores de sus variables proposicionales, decimos que hemos construido su **Tabla de Verdad**. !!!ejemplo Por ejemplo, si la valoración $v$ asigna $v(p)=v(q)=1,\ v(r)=v(s)=0$, entonces el valor de $F=\neg(\neg(p\lor q)\lor (\neg r\lor s))$ es $v(F)=1$, ya que:  !!!note A pesar de que la Lógica Proposicional presenta claras limitaciones expresivas y no puede reflejar fielmente muchas de las afirmaciones que podemos hacer en sistemas un poco más ricos, suele ser más que suficiente para muchísimos problemas de la vida real, por lo que sigue siendo útil en campos como el de la Inteligencia Artificial. Además, muchos de los métodos que se utilizan en lógicas más potentes (como la **Lógica de Primer Orden**, la **Lógica Modal**, la **Lógica Difusa**, etc.) son extensiones de los métodos existentes para la Lógica Proposicional, por lo que su estudio en profundidad está más que justificado y es de máxima utilidad. ### Representación en Lógica Proposicional El objetivo de los elementos anteriores es representar formalmente cierta información de un contexo con el fin de poder verificar los razonamientos que se hagan. Veamos algunos ejemplos: !!!ejemplo Supongamos que queremos formalizar la siguiente información (de Platón): _Si los verdaderos amigos tienen todo en común, entonces tú no puedes ser más rico que tu compañero si dices que sois verdaderos amigos._ El primer paso es decidir cuáles son las afirmaciones atómicas, que podremos representar por medio de variables proposicionales. Recordemos que una afirmación atómica es una unidad que no se puede descomponer y que puede tener asignado un valor booleano. Así, unidades como _amigos_ es atómico, pero no tiene un valor de verdad posible, mientras que _tú no puedes ser más rico que tu compañero si dices que sois verdaderos amigos_ sí puede tener un valor de verdad pero no es atómico. Aunque la elección puede estar sometida a cierta subjetividad, hay situaciones en las que queda claro cómo asignar unidades informativas con las variables proposicionales. Por ejemplo: $p$: _Los verdaderos amigos tienen todo en común_ $q$: _Puedes ser más rico que tu compañero_ $r$: _Dices que tú y tu compañero sois verdaderos amigos_ Serían asignaciones racionales que son atómicas y valorables, y con las que la afirmación de Platón quedaría reflejada por la fórmula compuesta: $$p→(r→¬q)$$ Podemos intentar formalizar razonamientos completos, formados por varias afirmaciones (que se convertirán en fórmulas) y una conclusión. !!!ejemplo Por ejemplo, supongamos el siguiente razonamiento: _Si continúa la investigación, surgirán nuevas evidencias. Si surgen nuevas evidencias, entonces varios dirigentes se verán implicados. Si varios dirigentes están implicados, los periódicos dejarán de hablar del caso. Si la continuación de la investigación implica que los periódicos dejen de hablar del caso, entonces, el surgimiento de nuevas evidencias implica que la investigación continúa. La investigación no continúa. Por tanto, no surgirán nuevas evidencias._ Siguiendo una elección similar a la del ejemplo anterior, podríamos llegar a la conclusión de tomar como variables proposicionales: $p$: Continúa la investigación $q$: Surgen nuevas evidencias $r$: Varios dirigentes se verán implicados $s$: Los periódicos dejarán de hablar del caso. De donde podríamos sacar las hipótesis siguientes: $$\{p→q, q→r, r→s, (p→s)→(q→p), ¬p\}$$ y la conclusión: $¬q$. En estos casoa, la diferenciación entre hipótesis y conclusión, atómico o compuesto, se deja clara gracias al uso en lenguaje natural de expresiones como _Por tanto..._, _entonces_, etc. pero la riqueza del lenguaje natural humano hace que tengamos multitud de formas de reordenar la información, de forma que no se sigue siempre un patrón fijo, ni en las conclusiones, ni en las expresiones que se traducirán en fórmulas por medio de las conectivas lógicas. Esta será una de las dificultades que tenemos para automatizar la representación en problemas de IA. !!!warn Puedes encontrar muchos ejemplos de formalización en LP en [este enlace](https://www.cs.us.es/cursos/liti-2023/FormalizacionLP.md.html). ## Deducción Una vez que hemos explicitado el lenguaje que usamos para formalizar las afirmaciones, y fijado lo que entendemos por su significado (de verdad o falsedad), es el momento de formalizar qué entendemos por **inferir correctamente**: !!!side:3 Es decir, si existe una valoración, $v$, tal que $v(F)=1$. !!!def:Satisfactibilidad Algunas definiciones necesarias para el tratamiento de la inferencia son: * Dada una valoración, $v$, diremos que una fórmula, $F$, es **válida** en $v$ si $v(F)=1$, y lo notaremos $v\models F$. Cuando $v(F)=0$ lo notaremos $v\not\models F$. * Decimos que $F$ es una **Tautología** si siempre es válida, sea cual sea la valoración considerada. Como no depende de valoraciones, se puede escribir $\models F$ (sin hacer mención a las valoraciones). * Decimos que es **Insatisfactible** (o una **Contradicción**) cuando nunca es válida, y decimos que es **Satisfactible** si es válida al menos una vez $^3$. !!!ejemplo Por ejemplo: 1. La fórmula $p\vee \neg p$ es una tautología: sea cual sea el valor de $p$, la fórmula es cierta. 2. La fórmula $p\rightarrow q$ es satisfactible porque existen valoraciones que la hacen válida (por ejemplo, $v(p)=0$, $v(q)=1$ hace que $v(p\rightarrow q)=1$), pero no es tautología porque no lo hacen todas (por ejemplo, $v(p)=1$, $v(q)=0$ hace que $v(p\rightarrow q)=0$). Los mismos conceptos se pueden aplicar a conjuntos de fórmulas, y no solo a fórmulas aisladas: un conjunto de fórmulas es satisfactible si existe una valoración que hace **válidas a todas las fórmulas del conjunto simultáneamente**. !!!def Además, **tenemos un método automático para saber si una fórmula es satisfactible**, **tautología** o **insatisfactible**: basta hacer la tabla de verdad de la fórmula y verificar si en el resultado hay alguna fila con $1$, si todas son $1$, o si todas son $0$ (respectivamente). !!!side:4 Solo crear las filas de la tabla requiere una cantidad exponencial de pasos. El problema evidente es que es un proceso muy laborioso hacer la tabla de verdad de la fórmula cuando el número de variables que intervienen es alto (algo que suele ocurrir en los problemas del mundo real que son interesantes), ya que si tenemos $n$ variables en la fórmula, necesitaremos una tabla de verdad con $2^n$ casos distintos $^4$. Aunque no profundizaremos mucho en este análisis sobre la complejidad, es obligatorio decir aquí que el problema de saber si una fórmula es satisfactible (que se llama **SAT**) cae dentro de los que se denominan problemas **NP**, esencialmente, aquellos problemas para los que se conoce solución, pero es tan mala desde el punto de vista de los recursos que necesitamos para resolverlos (en tiempo o en espacio) que son **intratables** desde un punto de vista práctico cuando el tamaño del problema (el tamaño de la fórmula, en este caso) es grande. Pero este, aparentemente, sencillo problema no solo es NP, sino que además es **NP-completo**, lo que significa que está entre los más complejos de los más complejos. !!!note: Sobre NP No estamos diciendo que no tengan solución más sencilla sino que, ahora mismo, no se conoce una solución sencilla, solo soluciones malas, y es un problema abierto saber si realmente es así o no. Es el famoso problema sobre si **P=NP** o no. Aunque la impresión general es que no existen esas soluciones buenas para este tipo de problemas, todavía nadie ha sido capaz de probarlo (es decir, la suposición general es que **P $\neq$ NP**). Por ello, las soluciones que veremos más adelante relacionadas con SAT conseguirán facilitar la solución en algunos casos, pero nunca serán suficientemente buenas en todos los casos como para considerarlas óptimas. Ahora ya podemos decir qué entendemos por consecuencia lógica que, como veremos, y la intuición dice, está íntimamente relacionado con la idea de implicación: !!!def:Consecuencia Lógica *Diremos que una fórmula, $F$, es **consecuencia lógica** de un conjunto finito de fórmulas, $U=\{F_1,\dots,F_n\}$, y lo notaremos por $U\models F$, si se verifica que la fórmula $F_1\wedge \dots \wedge F_n \rightarrow F$ es una tautología.* !!!note: Reducción al absurdo Como hemos dicho, la idea fundamental es la intuición de que la consecuencia lógica se relaciona, obviamente, con la implicación. Pero además, se puede probar (aunque no lo haremos) que *la definición anterior es equivalente a decir que el conjunto $\{F_1,\dots,F_n,\neg F\}$ es insatisfactible (una contradicción)*, que viene a reflejar el método habitual de probar que algo es consecuencia lógica por medio de la **reducción al absurdo** (si suponemos lo contrario a lo que queremos probar, llegamos a una contradicción). Al reducir la consecuencia lógica a comprobar una tautología o una satisfactibilidad, los métodos que tengamos para estos problemas podrán ser aplicados directamente para poder resolver el problema de la inferencia. Por tanto, **ya tenemos un método para resolver el problema de la inferencia: tablas de verdad**, pero es un método demasiado primitivo e ineficiente para dar respuesta a muchos problemas interesantes, así que en lo que sigue nos centraremos en buscar algún otro método más elegante y, sobre todo, que proporcione un mayor control para adaptarnos a las características particulares de la fórmula. ## Fórmulas Equivalentes Aunque una fórmula es una expresión rígida, es evidente que hay formas equivalentes de escribir las fórmulas (por ejemplo, las fórmulas $p\wedge q$ y $q \wedge p$ las interpretamos como la _misma_ fórmula), pero hay que expresar formalmente qué entendemos por ser **equivalentes**: !!!def:Fórmulas equivalentes Dos fórmulas, $F_1$ y $F_2$ se dicen **equivalentes** si tienen la misma tabla de verdad o, lo que es lo mismo, la fórmula $F_1 \leftrightarrow F_2$ es una tautología. Hay muchas reglas que nos permiten cambiar la expresión de una fórmula pero obteniendo una expresión equivalente, entre ellas: 1. $F_1 \wedge F_2\equiv F_2\wedge F_1$ 1. $F_1 \vee F_2\equiv F_2\vee F_1$ 2. $F_1 \rightarrow F_2\equiv \neg F_1\vee F_1$ 2. $F_1 \leftrightarrow F_2\equiv (F_2\rightarrow F_1) \wedge (F_2\rightarrow F_1)$ 2. $\neg(F_1 \wedge F_2) \equiv \neg F_1\vee \neg F_2$ 2. ... Las equivalencias nos permiten trabajar con versiones de las _mismas_ fórmulas que pueden ser más adecuadas para manipularlas con algoritmos específicos, como veremos a continuación. ### Formas Clausales Los métodos que vamos a ver aquí se podrán aplicar a fórmulas que estén escritas de una cierta forma equivalente, denominada **Forma Clausal**. Para ello, necesitamos previamente el concepto de **literal**, que simplemente será una variable proposicional o la negación de una variable proposicional (por ejemplo, $p$, $\neg p$, ...). En general, si tenemos que $L$ es un literal, notaremos por $L^c$ al literal contrario (es decir, si $L=p$, entonces $L^c=\neg p$, pero si $L=\neg p$, entonces $L^c= p$). !!!def:Forma Clausal Una fórmula se dice que está en **forma clausal** (también llamada **Forma Normal Conjuntiva**) si es conjunción de disyunciones de literales, es decir: $$F = (L_{11}\vee \dots \vee L_{1n_1}) \wedge (L_{21}\vee \dots \vee L_{2n_2}) \wedge \dots \wedge (L_{m1}\vee \dots \vee L_{mn_m})$$ donde los $L_{ij}$ son literales. !!!ejemplo Por ejemplo: $(p \lor q \lor \neg r) \land (\neg p \lor \neg q) \land (q\lor r)$, está en escrita en Forma Clausal. Lo interesante es que se puede probar que cualquier fórmula se puede convertir en otra equivalente expresada en forma clausal, por lo que los métodos que veremos a continuación se pueden aplicar a cualquier fórmula, siempre y cuando se transforme previamente a este formato. En realidad, debido a que la fórmula se ha expresado como una conjunción de disyunciones, podemos considerar que estamos trabajando con un conjunto de $m$ disyunciones, a cada disyunción se le llama **cláusula**. Por ello, podemos hablar de la forma clausal de una fórmula o de un conjunto de fórmulas, que pasaría a ser: $$F = \left\{\{L_{11},\dots, L_{1n_1}\},\ \{L_{21},\dots,L_{2n_2}\},\dots,\{L_{m1},\dots,L_{mn_m}\}\right\} $$ Aunque no lo vamos a usar, también se puede escribir cualquier fórmula en **Forma Normal Disyuntiva**, es decir como una disyunción de conjunciones. !!!def:Leyes de Transformación Las leyes habituales que permiten transformar una fórmula cualquiera en una equivalente en **Forma Normal Conjuntiva** o **Forma Normal Disyuntiva** son (los pasos 1 a 3 son comunes para ambas formas): 1. Eliminar los bicondicionales usando la equivalencia:$$A\leftrightarrow B \equiv (A\rightarrow B)\wedge (B\rightarrow A)$$ 2. Eliminar los condicionales usando la equivalencia: $$A\rightarrow B \equiv \neg A \vee B$$ 3. Interiorizar las negaciones usando las equivalencias: $$\neg (A\wedge B) \equiv \neg A \vee \neg B$$ $$\neg (A\vee B) \equiv \neg A \wedge \neg B$$ $$\neg \neg A \equiv A$$ 4. Interiorizar las disyunciones usando la equivalencia (para obtener FNC): $$A\vee(B\wedge C) \equiv (A\vee B)\wedge (A\vee C)$$ 5. Interiorizar las conjunciones usando la equivalencia (para obtener FND): $$A\wedge(B\vee C) \equiv (A\wedge B)\vee (A\wedge C)$$ ## DPLL !!!side:5 En cierta forma, este algoritmo es como el método habitual para resolver un sudoku, si tenemos ya algunos números seguros, su conocimiento se propaga a través del sudoku y nos permite asegurar más posiciones, y si llegamos a un callejón sin salida lo más normal es hacer suposiciones acerca de alguna de las casillas, valorando cómo evoluciona el puzzle para cada uno de sus posibles valores. Además, veremos en capítulos posteriores que es, esencialmente, uno de los métodos que se pueden seguir para la resolución general de Problemas de Satisfacción de Restricciones. **DPLL** es un algoritmo para decidir la satisfactibilidad de una fórmula (o conjunto de fórmulas) a partir de su forma clausal. Fue propuesto en 1960 por Davis y Putnam, y posteriormente refinado en 1962 por Davis, Logemann y Loveland (de ahí el nombre completo del algoritmo, DPLL). Este algoritmo es la base de la mayoría de los algortimos actuales que resuelven el problema SAT y que se usan en entornos profesionales $^5$. !!!def: DPLL El **algoritmo DPLL** consta de dos partes bien diferenciadas que se van alternando en caso de necesidad. Supongamos que el conjunto de cláusulas actual es $S$: 1. **Propagación de unidades**, simplifica el conjunto de cláusulas sobre el que se trabaja. Si existe alguna cláusula unitaria, se elige una de ellas, $\{L\}\in S$, y se aplican consecutivamente las dos reglas siguientes (y se repite mientras queden cláusulas unitarias): 1. **Subsunción unitaria**. Se eliminan todas las cláusulas que contengan el literal $L$ (incluida la propia cláusula $\{L\}$). 2. **Resolución unidad**. Se elimina el literal complementario, $L^c$ de todas las cláusulas en las que aparezca (el resto de la cláusula permanece). 3. El resto de cláusulas, en las que no aparecen ni $L$ ni $L^c$, se dejan igual. 2. **División**, si no hay unidades que propagar en el conjunto actual, $S$, se elige un literal $L$ que aparezca en una de las cláusulas que permanecen y se consideran por separado los conjuntos de cláusulas: $S\cup \{L\}$ y $S\cup \{L^c\}$. A continuación aplicamos recursivamente el procedimiento a ambos conjuntos (que ya tienen las cláusulas unitarias que acabamos de introducir y, por tanto, en ambas ramas se podrá aplicar la propagación de unidades). **Importante**. Si hay unidades, es obligatorio hacer el paso 1. En caso contrario, se aplica el paso 2. El algoritmo va ramificando el proceso y **cada rama puede dar lugar a una solución distinta** al problema de la satisfactibilidad: 1. Si en una rama aparece una contradicción (una cláusula unitaria y su cláusula unitaria complementaria de forma simultánea), esa rama no proporciona una solución, pero podría haber otra rama que sí lo hiciera. 2. Si en una rama no aparece una contradicción, esa rama proporciona una valoración que hace satisfactible la forma clausal original. 3. Si todas las ramas son contradictorias, la forma clausal original es una contradicción. 4. Además, si consideramos **todas las posibles ramas** que genera el algoritmo, **obtenemos todos los posibles modelos** de la fórmula. 5. Pero si solo deseamos saber si es satisfactible (y un modelo que la satisfaga), basta parar en la primera rama que proporcione una solución. !!!ejemplo Veamos un ejemplo de cómo aplicar este algoritmo: ![](img\dpll2.jpg width="50%") En el ejemplo anterior, la rama derecha proporciona un modelo ($p=0,\ q=0,\ r=1$), por lo que la fórmula es satisfactible; mientras que las ramas izquierdas llegan a contradicción (ya que requieren que sean simultáneamente ciertas $r$ y $\neg r$) y no pueden proporcionar modelos. Como al menos una rama proporciona modelos, la fórmula original es satisfactible. Si ninguna rama proporcionara modelos (es decir, si en todas las ramas llegáramos a una contradicción), entonces la fórmula sería insatisfactible. Como la fórmula tiene $3$ variables, podría llegar a tener $2^3=8$ modelos distintos, pero solo tiene $1$, por lo que no es tautología (porque las otras 7 valoraciones no son modelos). ### DPLL e Inferencia Como hemos visto que el problema de la inferencia se puede reducir a una verificación de satisfactibilidad, podremos usar DPLL para resolver el problema de inferencia: !!!note:Aplicación a la Consecuencia Lógica En resumen, si queremos resolver el problema de saber si una cierta fórmula es consecuencia lógica (la podemos deducir/inferir) de un conjunto de fórmulas (hipótesis), formalmente, $\{F_1,\dots,F_n\}\models F$, los pasos a seguir serían: 1. Convertimos el problema en **verificar si $\{F_1,\dots,F_n,\neg F\}$ es satisfactible o no**, es decir, si somos capaces de encontrar un modelo que verifique todas esas fórmulas simultáneamente o no. 2. **Pasamos cada una de esas fórmulas a forma clausal** (FNC) aplicando las reglas habituales para ello (ley distributiva, asociativa, de Morgan, etc). Podemos hacerlo por separado para cada fórmula y después simplemente consideramos el conjunto de todas las cláusulas obtenidas por todas las fórmulas: $\{C_1,\dots,C_m\}$. 3. **Aplicamos DPLL** al conjunto de cláusulas obtenido. 4. **Si encontramos un modelo** (una da las ramas de **DPLL** proporciona una solución), **entonces la consecuencia lógica NO es cierta**, $F$ no se deduce de $\{F_1,\dots,F_n\}$ (no significa que $F$ no sea cierta, sino que no es consecuencia de las demás). 5. **Si no encontramos un modelo** (todas las ramas de **DPLL** llegan a una contradicción), **entonces la consecuencia lógica SÍ es cierta**, es decir, que $F$ sí se deduce de las demás. ## Sobre la automatización Aunque en general los algoritmos que existen para obtener nuevos resultados matemáticos no son automatizables (es decir, no se pueden programar en una máquina), el caso de la lógica proposicional, con todas sus limitaciones, sí que se puede automatizar. Ya vimos que el método más directo, y el más incómodo, para ello es el de la construcción de la tabla de verdad (de tamaño exponencial). Pero hemos visto otro algoritmo, DPLL, que es fácilmente implementable (apenas usando algunas estructuras de listas o similares) y que puede resultar más recomendable en caso de querer disponer de una implementación práctica. A pesar de todo, no debemos olvidar que el problema que está detrás es **SAT**, y que es un problema **NP**-completo, por tanto, no debemos poner nuestras esperanzas en conseguir algoritmos que rebajen el problema de la inferencia (ni siquiera en la Lógica Proposicional) y que lo conviertan en un problema tratable para todos los casos: nos conformamos con obtener métodos que sean suficientemente buenos como para poder atacar problemas con un gran número de variables en muchos casos. # Lógica de Primer Orden Pese a las virtudes que ofrece un sistema de representación y razonamiento formal como la Lógica Proposicional (LP), esta puede no ser apropiada para expresar ciertos tipos de conocimiento. !!!ejemplo Por ejemplo, una afirmación tan sencilla como: *Algunas máquinas son inteligentes* solo dispone de una posible representación en LP, como variable proposicional, ya que es una afirmación atómica, perdiendo el grano fino que permita extraer, y reutilizar, un mayor conocimiento de su estructura. Si representamos esta sentencia por una variable proposicional, el sistema no será capaz de relacionar su contenido con una afirmación similar pero que da una información bien distinta: *Las máquinas son inteligentes* Este tipo de carencias, y muchas otras que surgen cuando intentamos modelar una información más rica, es la que nos lleva a la conclusión de que LP no es suficientemente expresiva para modelar cierto tipo de afirmaciones y razonamientos. Parte del problema que muestra LP es que no tiene capacidad para diferenciar propiedades en familias de elementos de un dominio: o bien habla de objetos particulares que tienen una descripción propia (un nombre que los identifica), o habla de propiedades del dominio completo como una unidad. No tiene capacidad de **ajuste fino**. La **Lógica de Primer Orden** (**LPO**) viene a solucionar este tipo de problemas: - Permite hacer **cuantificación** sobre los objetos de un dominio, por ejemplo, puede expresar variantes como: *Todas las máquinas son inteligentes*, *Algunas máquinas son inteligentes*, dejando las unidades informativas comunes reconocibles. - Permite representar **propiedades** de los objetos particulares del dominio por medio de predicados y funciones: *la máquina X es inteligente*. - Permite trabajar con subconjuntos de objetos que pueden venir caracterizados por propiedades que se describen por medio de propiedades y funciones: *las máquinas que son inteligentes*. !!!ejemplo Con el fin de aterrizar las ideas que vamos a introducir aquí, trabajaremos a lo largo de esta entrada con la formalización de la siguiente base de conocimientos acerca del mundo romano: - Marco era pompeyano. - Todos los pompeyanos eran romanos. - Cada romano, o era leal a César, o le odiaba. - Todo el mundo es leal a alguien. - La gente sólo intenta asesinar a aquellos a quienes no es leal. - Marco intentó asesinar a César. - Todo pompeyano es leal a su padre. ## Sintaxis y Semántica Siguiendo un esquema similar a cuando presentamos LP, comenzaremos especificando formalmente cómo se escribe correctamente en Primer Orden, y cómo se interpreta lo que escribimos. !!!def: Lógica de Primer Orden (o Lógica de Predicados) Formalmente, un **Lenguaje de Primer Orden** está compuesto por los siguientes elementos: 1. Un conjunto, finito o numerable, de símbolos de **constantes** para designar objetos particulares: $C=\{c_1,c_2,\dots\}=\{a,b,c,\dots\}$ (no tenemos porqué tener designadores para todos los objetos del mundo modelado, quizás solo de algunos de ellos). 2. Un conjunto, finito o numerable, de símbolos para designar **funciones**: $F=\{f_1,f_2,\dots\}=\{f,g,h,\dots\}$ (cada función tiene una aridad propia, que indica el número de argumentos que recibe como entrada). 3. Un conjunto, finito o numerable, de símbolos para designar **predicados** (**propiedades**): $P=\{P_1,P_2,\dots\}=\{P,Q,R,\dots\}$ (cada predicado tiene una aridad propia, que indica el número de objetos que relaciona). !!!ejemplo En el ejemplo anterior: - Objetos (individuos) como César y Marco necesitarían de símbolos específicos para poder referirnos a ellos y expresar las afirmaciones en las que intervienen. Así pues, en nuestro lenguaje tomaremos $C=\{{\bf Marco}, {\bf Cesar}\}$. - Encontramos una función que asocia objetos a objetos, en este caso, asociada al concepto _padre_, que denotaremos por $f$, por lo que $F=\{f\}$, y para un objeto del mundo, por ejemplo, $Marco$, $f(Marco)$ representa a su padre. - Disponemos de varios predicados que necesitamos formalizar: $P(a)$ para decir que $a$ _es pompeyano_, $R(a)$ para expresar que $a$ _es romano_, $L(a,b)$ para indicar que $a$ _es leal a_ $b$, $O(a,b)$ para indicar que $a$ _odia a_ $b$, $IA(a,b)$ para indicar que $a$ _intentó asesinar a_ $b$. Observa que hablamos de *símbolos*, porque estamos definiendo un lenguaje, pero lo hacemos desde un punto de vista completamente formal, sin preocuparnos por el significado de lo que podamos escribir en él. Eso lo veremos más adelante en lo que podríamos denominar la **semántica** del lenguaje, que depende del uso que se le dé. !!!def:Lógica de Primer Orden (continuación) Además de estos elementos, un LPO necesita también otros símbolos que le permitan componer fórmulas y expresiones más complejas, y que son, esencialmente, una extensión de los mismos símbolos que usábamos para la LP: 4. $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$: **conectivas lógicas** usuales y con el mismo uso que se le dio en LP. 5. $=$: un predicado especial para la **igualdad**. No es obligatorio, pero si lo añadimos, tendrá el uso de la igualdad habitual en la que $a=b$ si y sólo si $a$ y $b$ son el mismo objeto. 6. $V=\{x_1, x_2, \dots\}=\{x,y,z,\dots\}$: un conjunto numerable de **variables** con las que podemos representar objetos del mundo que estamos describiendo. 7. $\exists$, $\forall$: **cuantificadores existencial y universal**, habituales en la formalización matemática estándar que, en combinación con el uso de variables, permiten extender las propiedades particulares que podemos referenciar en objetos del mundo a propiedades de conjuntos de objetos. 8. $($ $,$ $)$: símbolos de **puntuación** auxiliares para facilitar la escritura y lectura de las expresiones que escribamos. !!!ejemplo Usando el LPO anotado en la definición anterior, una formalización de las sentencias anteriores sería: - $P({\bf Marco})$ - $\forall x\, ( P(x)\rightarrow R(x))$ - $\forall x\, (R(x)\rightarrow (L(x,{\bf Cesar})\vee O(x,{\bf Cesar})))$ - $\forall x\,\exists y\, L(x,y)$ - $\forall x\,\forall y\, (IA(x,y)\rightarrow \neg L(x,y))$ - $IA({\bf Marco},{\bf Cesar})$ - $\forall x\, (P(x)\rightarrow L(x, f(x)))$ !!!warn Puedes encontrar muchos ejemplos de formalización en LPO en [este enlace](https://www.cs.us.es/cursos/liti-2023/FormalizacionLPO.md.html). Con este aparato podemos definir formalmente cómo se escriben las expresiones correctas en este lenguaje, pero no vamos a entrar en tanto detalle (lo puedes encontrar en los apuntes oficiales de la asignatura de Lógica Informática), ya que su uso habitual en disciplinas de estudio conocidas (como matemáticas y física) nos proporciona suficientes ejemplos como para que podamos diferenciar las expresiones válidas de las no válidas sin posibilidad de error y sin necesidad de una farragosa definición formal. Lo único importante, porque lo usaremos más adelante, es diferenciar entre los tipos de expresiones que podemos construir: !!!side:7 Que jugarían el papel de las fórmulas atómicas, que no se pueden dividir en fórmulas más pequeñas. !!!def: Términos y Fórmulas Aquellas expresiones que se identifican con posibles objetos se denominan **términos**, y están formadas a partir de constantes (para hablar de objetos específicos), variables (para hablar de objetos genéricos), y funciones aplicadas a otros términos más pequeños. Aquellas expresiones que se identifican con afirmaciones sobre los objetos se denominan **fórmulas**, y están formadas a partir de predicados sobre términos $^7$, y construcciones lógicas de estos predicados (conjunciones, implicaciones, cuantificaciones, etc.). !!!ejemplo En el ejemplo anterior, son términos: ${\bf Marco}$, $f({\bf Marco})$, $f(f({\bf Cesar}))$, $f(x)$, etc. La formalización de las sentencias anteriores son ejemplos de fórmulas. Una fórmula atómica sería, por ejemplo, $IA({\bf Marco},{\bf Cesar})$, o $L(x,{\bf Cesar})$. Observa que los LPO hablan de objetos, propiedades y funciones. Lo interesante es cuando estas expresiones se usan para hablar de mundos formados por objetos, con propiedades y funciones que tienen una interpretación con algún significado para nosotros. !!!side:8 Un mundo se puede ajustar a muchos lenguajes, y un mismo lenguaje se puede ajustar a muchos mundos posibles cambiando la interpretación. A estos mundos que se pueden adaptar a un lenguaje particular, $L$, se les denomina comúnmente **$L$-estructuras** $^8$. !!!def:Semántica LPO Informalmente, una **$L$-estructura**, $M$, es un conjunto en el que cada símbolo del lenguaje $L$ se puede interpretar como un elemento, propiedad o función real en ese conjunto. De hecho, a la identificación concreta que dice cómo se interpreta cada símbolo de $L$ se le llama **interpretación**. Es esta interpretación la que da sentido a los elementos del lenguaje que, hasta este momento, no eran más que símbolos sin contenido, sin más utilidad que la de poder escribir expresiones correctamente. !!!ejemplo Una interpretación *natural* del ejemplo anterior sería considerar el mundo antiguo formado por romanos y pompeyanos como conjunto de *objetos*, y el significado natural de cada uno de los predicados, constantes y funciones. Pero no es la única interpretación posible. Podríamos considerar, en un alarde de imaginación y libertad, que el conjunto de objetos sobre el que se trabaja son los números naturales, donde ${\bf Marco}$ representa al número $0$, ${\bf Cesar}$ representa al número $1$, el padre de un individuo es el siguiente (es decir, por ejemplo, $f({\bf César})$ representa al número $2$), ser romano es ser par, ser pompeyano es ser múltiplo de 4, etc... Los términos y fórmulas escritas en el lenguaje no cambian, pero su interpretación (significado) en este nuevo mundo son completamente distintas, y habrá fórmulas que se verificarán con esta nueva interpretación que quizás en la interpretación natural no se verifiquen (o al revés). Si queremos usar LPO para razonar acerca de lo que ocurre en el mundo, debemos ser capaces de describir el mundo sin que haya posibilidad de que las fórmulas sean verdaderas en estructuras que no tienen nada que ver con el mundo que estamos modelando. Esta tarea no es nada trivial, y a veces, por mucho que queramos especificar concretamente las propiedades que caracterizan el mundo de interés, podemos encontrar **mundos extraños** que verifican las mismas propiedades pero no son nuestro objeto de interés. ## Consecuencia Lógica Con el fin de modelar el conocimiento de dominios de forma lógica también para este tipo de lenguajes más potentes debemos precisar con igual claridad cuándo una fórmula es verdadera en una cierta estructura: !!!def:Satisfactibilidad Diremos que una fórmula, $\varphi$, de $L$ es **satisfactible** si hay una $L$-estructura, $M$, donde se verifica la fórmula (con el significado estándar de los símbolos lógicos y la interpretación en esa estructura de los símbolos de constantes, predicados y funciones), y en este caso se dice que la estructura es **modelo** de la fórmula, y escribimos: $M\models \varphi$. Esta idea se puede extender a un conjunto de fórmulas, $\Sigma$, que será **satisfactible** en una estructura si lo son todas sus fórmulas bajo la misma estructura: $M\models \Sigma$. !!!ejemplo Por ejemplo, en el mundo de los romanos con la interpretación natural se tiene que la fórmula $\forall x (P(x)\rightarrow R(x))$ se satisface (con la interpretación de los números naturales que hemos dado, también, pero es fácil pensar en estructuras donde no se verifica). !!!def:Consecuencia Lógica Y podemos definir el concepto fundamental que persigue la lógica acerca de cuándo podemos **concluir** una fórmula, $\varphi$, de un conjunto de fórmulas, $\Sigma$: $\Sigma\models \varphi$, y es que será así cuando, en todo mundo posible en el que $\Sigma$ se verifique, necesariamente $\varphi$ se verifica. Es decir: Si $M$ es una $L$-estructura tal que $M\models \Sigma$, entonces $M\models \varphi$. Observa que, si $\Sigma=\{\varphi_1,\dots,\varphi_n\}$ es un conjunto finito de fórmulas, entonces esta definición es equivalente a decir que $$M\models \varphi_1\wedge \dots\wedge \varphi_n \rightarrow \varphi$$ se tiene para cualquier $L$-estructura $M$. !!!ejemplo Por ejemplo, tomando como $\Sigma$ el conjunto de sentencias formalizadas anteriormente, podríamos preguntarnos si de ellas se deduce (si es consecuencia lógica) si *Marco era leal a César* ($L({\bf Marco},{\bf Cesar})$), o no. Al igual que se hace con la Lógica Proposicional, sería interesante ver de qué forma podemos dar métodos (y si son automatizables, mejor) para comprobar si una fórmula es consecuencia lógica de un conjunto de fórmulas, métodos que no sean el de comprobar directamente la definición, que precisa de verificar la condición anterior sobre todos los mundos posibles, o estructuras. !!!note Para entender cómo se diferencia ahora este objetivo en Primer Orden del equivalente en Proposicional es importante observar que, en Proposicional, si tenemos un conjunto finito de fórmulas que hacen uso de un conjunto finito de variables proposicionales, entonces el número de mundos posibles es finito, ya que consiste simplemente en todas las posibles combinaciones de valores de verdad de las variables proposicionales que aparecen, por lo que bastaría comprobar en cada uno de ellos si se tiene la condición anterior o no (es, esencialmente, lo que se hace con una tabla de verdad). Sin embargo, en Primer Orden no podemos afirmar lo mismo, los mundos son mucho más ricos y complejos, y aunque estemos trabajando con un conjunto finito de fórmulas que hacen uso de un conjunto finito de símbolos, no podemos asegurar que haya únicamente un número finito de mundos posibles, por lo que este método de comprobación exhaustiva ya no es válido y hay que buscar métodos alternativos. ## De Proposicional a Primer Orden Debido a que LPO se puede considerar como una extensión de LP, mucho del trabajo realizado en LPO es ver hasta qué punto se pueden extrapolar y adaptar los métodos que funcionan en LP. Una opción que sí nos trasladaría a una situación similar sería si pudiéramos asegurar que los mundos posibles son finitos y además tenemos un símbolo de constante para nombrar cada uno de sus objetos, porque en este caso LPO se podría ver como una forma más abreviada de escribir fórmulas proposicionales (tendríamos todas las afirmaciones de lo que se puede decir acerca de los objetos del mundo describiéndolas una a una sobre cada objeto... un conjunto resultante de fórmulas muy grande, posiblemente infinito, pero muy simple). Es obvio que esto no es cierto y, de hecho, en general no podemos afirmar que todos los mundos posibles (estructuras) vayan a ser finitos. Sin embargo, podemos usar esta idea para tratar de trabajar con una **versión casi-proposicional** de nuestro lenguaje. Si tenemos en cuenta que tenemos un conjunto de símbolos de constantes, y que los objetos del mundo solo se pueden referenciar en el lenguaje por medio de los términos, que son aquellas expresiones formadas por las combinaciones correctas de estos símbolos con los símbolos de función, entonces de forma efectiva solo podremos referenciar concretamente aquellos objetos del mundo que se puedan nombrar por medio de los términos que no hacen uso de las variables $x,y,z...$ (que no representa objetos concretos), es decir, los **términos cerrados**. !!!ejemplo Por ejemplo, $f({\bf Cesar})$ es un término cerrado, pero $f(x)$, no. Téngase presente que el conjunto de términos cerrados puede ser infinito: basta que haya un símbolo de función y un símbolo de constante para que las combinaciones expresivas en estos términos explote con $c$, $f(c)$, $f(f(c))$, etc.. Así pues, si consideramos el conjunto de las posibles fórmulas de $\Sigma$ pero instanciando sus variables libres (si las tiene) con los objetos que pueden conseguirse por medio de términos cerrados (lo más probable es que hubiera que añadir algunos símbolos nuevos de constantes y funciones para las fórmulas existenciales que hubiera en $\Sigma$, siguiendo lo que se llama un proceso de **skolemnización**), tendríamos un conjunto de fórmulas (mucho más grande) pero escrito en un lenguaje equivalente a uno proposicional y que diría exactamente lo mismo que dicen las fórmulas de $\Sigma$. En cierta forma, es el proceso de descomprimir la información que da $\Sigma$ usando las variables libres de un LPO reescribiendo las fórmulas en un lenguaje que habla solo de objetos concretos. Este proceso tan simple conceptualmente es el que está detrás de la famosa (y temida por los alumnos) **extensión de Herbrand**. !!!ejemplo Por ejemplo, a partir de la fórmula $\forall x\, (P(x)\rightarrow R(x))$ del conjunto $\Sigma$ anterior obtendríamos las siguientes versiones sin variables (que hacen uso de términos cerrados únicamente): $$P({\bf Marco})\rightarrow R({\bf Marco}),\ P({\bf Cesar})\rightarrow R({\bf Cesar})\\ P(f({\bf Marco}))\rightarrow R(f({\bf Marco})),\ P(f({\bf Cesar}))\rightarrow R(f({\bf Cesar}))\\ \cdots$$ que, esencialmente, son como fórmulas proposicionales que hacen uso de la *nuevas* variables proposicionales $P({\bf Marco})$, $R({\bf Marco})$, $P({\bf Cesar})$, $R({\bf Cesar})$, $P(f({\bf Marco}))$, ... El conjunto de estas nuevas versiones con términos cerrados de las fórmulas de $\Sigma$ proporciona una especie de versión proposicional de la información que hay en $\Sigma$, y podríamos intentar aplicarles los métodos de razonamiento propios de los lenguajes LP, como DPLL (observa que estas nuevas fórmulas ya no tienen variables ni cuantificadores, que son la principal diferencia sintáctica entre LP y LPO). !!!side:9 En otros temas de este curso encontraremos otras técnicas que pueden ayudarnos a transferir métodos de deducción de LP a LPO. No es la única técnica posible, ni siquiera la más sencilla y cómoda, pero sí la más inmediata que permite aplicar técnicas desarrolladas originalmente para LP al caso de los LPO. Estas técnicas, que se comportan de forma decidible en el caso de LP, se encuentran ante una explosión (a menudo infinita) en esta extensión, lo que hace que el caso LPO sea, en general, indecidible $^9$.