Apuntes sobre lógica¶

---

Entenderemos por lógica al estudio de las reglas que rigen el razonamiento válido a partir de sentencias que, a su vez, constituyen una base de conocimiento. Existen diferentes aproximaciones a la lógica, pero aquí la trataremos desde el punto de vista de la lógica matemática. Esto nos llevará al planteamiento de un sistema formal con el que concretaremos una serie de reglas para su representación y tratamiento. Todo sistema formal descansa sobre un conjunto de axiomas (sentencias primeras para las que se asume su veracidad sin necesidad de demostración), unas reglas de inferencia y un lenguaje formal que determina sin ambigüedades la representación y manipulación de las expresiones resultantes.

Lógica proposicional o de orden 0¶

La lógica proposicional, lógica de orden 0 o cálculo proposicional es un sistema formal compuesto por variables proposicionales y conectores lógicos a partir de los cuales se pueden generar sentencias lógicas o proposiciones lógicas.

Sentencias, literales y conectores¶

Las sentencias son declaraciones sobre algún hecho del mundo. Podemos tener sentecias muy simples como: Está lloviendo o algo más complejas como: Está lloviendo y no tengo paraguas. Para expresar las sentencias en lógica debemos utilizar algún lenguaje de representación. Por ejemplo:

$$P \equiv \text{"Está lloviendo"}$$ $$P \land Q \equiv \text{"Está lloviendo y no tengo paraguas"}$$

Como vemos, las sentencias pueden ser hechos simples o podrían ser la combinación de dos, o más, hechos. A cada hecho lo llamaremos literal (o sentencia atómica) y lo representaremos con una letra.

Podemos unir literales en una sentencia mediante conectores $y$ y $o$, que llamaremos conjunción $(\land)$ y disyunción $(\lor)$ respectivamente. También podemos agruparlos usando paréntesis. Por ejemplo:

$$(P \lor Q) \land S$$

Los literales y las combinaciones de literales puedes ser negados mediante el operador negación $(\lnot)$:

$$\lnot(P \lor \lnot Q)$$

Las sentencias también pueden ser conclusiones sobre la existencia de uno o varios hechos. El operador implicación $(\rightarrow)$ afirma uno, o varios, hechos consecuentes a partir de uno, o varios, hechos antecedentes. Por ejemplo, si está lloviendo entonces las calles están mojadas:

$$P \rightarrow Q$$

Es importante destacar que la implicación lógica no conlleva ninguna relación de causalidad física. La implicación lógica es un conector que tan solo determina que si se da $P$ entonces debe darse $Q$.

Modelo¶

Además del lenguaje de representación con el que escribimos las sentencias, éstas también poseen una semántica. Entendemos comúnmente por semántica a la asignacion de significado a las palabras o frases. Aquí, semántica se utiliza de una manera más precisa para definir o conocer la verdad o falsedad de una sentencia. Por ejemplo, la sentencia $P \equiv \text{"Está lloviendo"}$ puede ser verdadera o falsa. Es decir, cada literal representa un hecho que no implica de por sí que sea cierto siempre. El hecho se puede dar o no. Por tanto, $P$ puede ser cierto si, efectivamente, está lloviendo o falso si no lo está. No debemos confundir la asignación de verdad o falsedad a un hecho con el operador negación. Para que nos resulte más sencillo, podemos imaginarnos a los literales como variables booleanas.

Podremos asignar verdadero o falso a cada literal en función de que ese hecho se esté realmente dando o no. Por tanto, vemos que el número de modelos distintos que podríamos tener es de dos elevado al número de literales de nuestra base de conocimiento, $2^\textit{#literales}$.

La semántica también define las reglas para asignar los valores de verdad o falsedad a las sentencias. La siguiente tabla, llamada tabla de verdad muestra los valores para cada uno de los conectores:

$$\begin{aligned} &\begin{array}{cc|ccccc} \hline P & Q & \lnot P & P \lor Q & P \land Q & P \rightarrow Q & P \leftrightarrow Q \\ \hline \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{verdadero} \\ \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{falso} \\ \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{falso} \\ \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} \\ \hline \end{array} \end{aligned}$$

Los operadores implicación y bicondicional merecen una reflexión sobre sus resultados en la tabla de verdad. ¿Cómo se interpreta que $P \rightarrow Q$ sea verdadero cuando $P$ es falso y $Q$ verdadero? Esto nos viene a decir que, que se dé el hecho $Q$ no implica que deba darse el hecho $P$. Que las calles estén mojadas no implica que haya llovido obligatoriamente, puede ser que haya pasado antes un camión cuba limpiando las calles. Sin embargo, que $P$ sea cierto, es decir, que haya llovido, indefectiblemente habrá mojado las calles. Pero eso no ha ocurrido, $Q$ es falso. Por tanto, la implicación $P \rightarrow Q$ es falsa. O, dicho de otra forma, si $P$ es verdadero y $Q$ es falso, la implicación $P \rightarrow Q$ no es cierta. Cuando tanto $P$ como $Q$ son falsas la implicación es verdadera ya que si las calles están secas es seguro que no habrá llovido y no se viola la integridad de la implicación.

Base de conocimiento¶

Llamamos base de conocimiento (BC) al conjunto de sentencias.

Inferencia¶

La inferencia es el proceso por el cual determinamos si una nueva sentencia $\alpha$ es verdadera a partir de los hechos de una BC:

$$BC \models \alpha$$

Ejemplo¶

Supongamos que tenemos las siguientes reglas/sentencias en nuestra BC:

$$\begin{aligned} &\begin{array}{cc} \hline \textit{R1:} & P \rightarrow Q \lor S \\ \textit{R2:} & P \\ \hline \end{array} \end{aligned}$$

La siguiente tabla de verdad muestra los estados de verdad o falsedad de las reglas. Cada fila muestra una de las posibles ocho combinaciones de los valores de los literales.

$$\begin{aligned} &\begin{array}{ccc|cc|c} P & Q & S & P \rightarrow Q \lor S & P & BC\\ \hline \textit{falso} & \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{falso} \\ \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{falso} \\ \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{falso} \\ \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{falso} \\ \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{falso} \\ \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} \\ \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} \\ \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} \\ \hline \end{array} \end{aligned}$$ Tabla 1

Nuestra BC puede verse como la conjunción de todas sus reglas, de esta forma:

$$\textit{BC} \equiv \textit{R1} \land \textit{R2}$$

Decimos que una sentencia es satisfecha cuando es verdadera para, al menos, un modelo. En el caso anterior vemos que las dos reglas son satisfechas con varios de los modelos. De la misma forma, decimos que una BC es satisfecha cuando todas sus sentencias son satisfechas simultáneamente por algún modelo. De nuevo, en el caso anterior vemos que esto ocurre con varios modelos.

Veamos ahora si es posible hacer alguna inferencia a partir de las reglas. Por ejemplo, ¿es posible inferir $S$? La respuesta es que no podemos asegurarlo. Si ahora introducimos la regla:

$$\textit{R3: } \lnot Q \\ $$

La cosa cambia. Tener $P$ en la regla $R2$ significa que el consecuente de la regla $R1$ se da. Es decir, tenemos $Q \lor S$. Como la regla $R3$ nos dice que $\lnot Q$ entonces tenemos $S$. Hemos inferido $S$.

Veamos la nueva tabla de verdad.

$$\begin{aligned} &\begin{array}{ccc|ccc|c} P & Q & S & P \rightarrow Q \lor S & P & \lnot Q & BC\\ \hline \textit{falso} & \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{falso} \\ \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{falso} \\ \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{falso} \\ \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{falso} \\ \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{falso} \\ \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} \\ \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{falso} \\ \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{falso} \\ \hline \end{array} \end{aligned}$$ Tabla 2

La tabla 2 nos permite ilustrar otra forma de realizar la inferencia, mediante los modelos. Nos fijamos en los modelos que satisfacen la BC. Si la sentencia que queremos inferir, en este caso $S$, tiene solo valores verdaderos siempre que la BC tenga también valores verdaderos podremos asegurar que la BC infiere a dicha sentencia. En la tabla 1 vemos cómo la BC tiene valores verdaderos (3) mientras que $S$ tiene, en esos casos, valores verdaderos y falsos, por lo que la BC no puede inferir $S$.

Tautologías¶

Las tautologías son fórmulas o conjuntos de sentencias que son verdaderas para cualquier modelo posible. Por ejemplo:

$$\begin{aligned} &\begin{array}{ccc|c|c} P & Q & S & P \land Q \land S & (P \land Q \land S) \rightarrow S\\ \hline \textit{falso} & \textit{falso} & \textit{falso} & \textit{falso} & \textit{verdadero} \\ \textit{falso} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{verdadero} \\ \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{verdadero} \\ \textit{falso} & \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{verdadero} \\ \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{falso} & \textit{verdadero} \\ \textit{verdadero} & \textit{falso} & \textit{verdadero} & \textit{falso} & \textit{verdadero} \\ \textit{verdadero} & \textit{verdadero} & \textit{falso} & \textit{falso} & \textit{verdadero} \\ \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} & \textit{verdadero} \\ \hline \end{array} \end{aligned}$$ Tabla 3

Equivalencias lógicas¶

Forma normal para la conjunción	$p \land V \equiv p$	$p \land F \equiv F$
Forma normal para la disyunción	$p \lor V \equiv V$	$p \lor F \equiv p$
Complementarios	$p \land \neg p \equiv F$	$p \lor \neg p \equiv V$
Supresión de la implicación	$p \rightarrow q \equiv \neg p \lor q$
Contraposición	$p \rightarrow q \equiv \neg q \rightarrow \neg p$
Supresión de la doble implicación	$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$
Absorción	$p \land (p \lor q) \equiv p$	$p \land (p \lor q) \equiv p$
Distributiva	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$
Doble negación	$\neg \neg p \equiv p$
De Morgan	$\neg p \lor \neg q \equiv \neg(p \land q)$	$\neg p \land \neg q \equiv \neg(p \lor q)$

Lógica de predicados o de primer orden¶

A diferencia de la lógica proposicional, la lógica de primer orden amplía la estructura interna de las sentencias incluyendo objetos, variables, propiedades/relaciones y cuantificadores.

        $\textit{Todos los hombres son mortales.}\\ \textit{Sócrates es un hombre.}\\ \textit{Luego Sócrates es mortal.}$

Veamos cómo la lógica de predicados puede expresar este razonamiento. Tomamos el objeto $s$ como Sócrates, la propiedad $H(x)$ como la de ser hombre y la propiedad $M(x)$ como la de ser mortal. Ahora podemo expresar:

$$\begin{aligned} \forall x [H(x) \rightarrow M(x)] \\H(s) \\M(s) \end{aligned}$$

Términos y predicados¶

Son constantes y variables. Las constantes designan objetos concretos de mundo. Las variables referencian a cualquier objeto del Universo. Representaremos ambas por letras minúsculas.

Ejemplos:

$$\begin{aligned} p \equiv \text{pera} \\m \equiv \text{manzana} \\n \equiv \text{naranja} \\x \equiv \text{cualquier cosa} \end{aligned}$$

En cuanto a los predicados, estos se consideran propiedades que los términos y objetos pueden tener.

Ejemplos:

$$\begin{aligned} F(x) \equiv \text{x es una fruta} \\H(y) \equiv \text{y es un hombre} \end{aligned}$$

Es posible para los predicados tener dos o más "parámetros". En este caso, los predicados se definen como relaciones.

Ejemplos:

$$\begin{aligned} P(x, y) \equiv \text{x e y son primos} \\ C(x, y) \equiv \text{x es de color y} \end{aligned}$$

Cuantificadores¶

El cuantificador universal $\forall$ determina que todos los elementos de un dominio satifacen alguna condición.

Ejemplos:

$$\begin{aligned} \text{Perro}(x): \text{x es un perro} \\ \text{Mamífero}(y): \text{y es un mamífero} \\ \forall x[\text{Perro}(x) \rightarrow \text{Mamífero}(x)] \text{: Todos los objetos que son perros son también mamíferos} \end{aligned}$$ $$\begin{aligned} \text{Hermanos}(x,y): \text{x e y son hermanos} \\ \text{Familiar}(z,w): \text{z y w son familiares} \\ \forall(x,y)[\text{Hermanos}(x,y) \rightarrow \text{Familiar}(y,x)] \end{aligned}$$

El cuantificador existencial $\exists$ indica que existe al menos un objeto de un dominio que satiface alguna condición.

Ejemplos:

$$\begin{aligned} \text{Perro}(x): \text{x es un perro} \\ \text{Negro}(y): \text{y es negro} \\ \exists x[\text{Perro}(x) \land \text{Negro}(x)] \text{: Algunos perros son negros} \end{aligned}$$

Ojo, la frase anterior también podría leerse como: "Algunos objetos negros del domino son perros".

Inferencia en la lógica de predicados¶

No podemos utilizar directamente las mismas reglas de derivación que usamos en la lógica proposicional cuando tenemos expresiones con variables cuantificadas existencial o universalmente, pero sí podemos convertirlas antes en proposiciones.

Especificación universal (EU)¶

Podemos prescindir del cuantificador durante la derivación

Especificación existencial (EE)¶

Podemos prescindir del cuantificador durante la derivación

Generalización universal (GU)¶

Podemos restituir el cuantificador universal a un enunciado condicional.

$$P(a) \rightarrow Q(a) \\ \forall x[P(x) \rightarrow Q(x)]$$

Generalización existencial (GE)¶

Podemos restituir el cuantificador universal a un enunciado conjuntivo.

$$P(a) \land Q(a) \\ \exists x[P(x) \land Q(x)]$$

Ejemplo 1:¶

Todos los felinos son mamíferos.
Todos los tigres son felinos.
Luego, todos los tigres son mamíferos.

$$\begin{aligned} &\begin{array}{l l} (1) & \forall x [F(x) \rightarrow M(x)] \\ (2) & \forall x [T(x) \rightarrow F(x)] \\ \hline \models & \forall x [T(x) \rightarrow M(x)] \\ \end{array} \end{aligned}$$

Suprimimos los cuantificadores mediante la especificación universal (EU)

$$\begin{aligned} &\begin{array}{l l l } (3) & F(a) \rightarrow M(a) & \text{EU(1)}\\ (4) & T(a) \rightarrow F(a) & \text{EU(2)}\\ \end{array} \end{aligned}$$

Derivamos 3 y 4

$$\begin{aligned} &\begin{array}{l l l } (5) & T(a) \rightarrow M(a) & \text{SH(4,3)}\\ \end{array} \end{aligned}$$

Al ser un enunciado condicional, podemos reasignarle el cuantificador universal

$$\begin{aligned} &\begin{array}{l l l } (6) & \forall x [T(x) \rightarrow M(x)] & \text{GU(5)}\\ \end{array} \end{aligned}$$

Ejemplo 2:¶

Todos los tiranos son crueles.
Algunos civiles son tiranos.
Luego, algunos civiles son crueles.

$$\begin{aligned} &\begin{array}{l l} (1) & \forall x [T(x) \rightarrow Cr(x)] \\ (2) & \exists x [Ci(x) \land T(x)] \\ \hline \models & \exists x [Ci(x) \land Cr(x)] \\ \end{array} \end{aligned}$$

Suprimimos los cuantificadores

$$\begin{aligned} &\begin{array}{l l l } (3) & T(a) \rightarrow Cr(a) & \text{EU(1)}\\ (4) & Ci(a) \land T(a) & \text{EE(2)}\\ \end{array} \end{aligned}$$

Aplicamos las leyes de derivación

$$\begin{aligned} &\begin{array}{l l l } (5) & T(a) & \text{Simp.(4)}\\ (6) & Cr(a) & \text{MP(3,5)}\\ (7) & Ci(a) & \text{Simp.(4)}\\ (8) & Cr(a) \land Ci(a) & \text{Conj.(6,7)}\\ \end{array} \end{aligned}$$

Mediante la generalización existencial, restituimos la variable

$$\begin{aligned} &\begin{array}{l l l } (9) & \exists x[Cr(x) \land Ci(x)] & \text{GE(8)}\\ \end{array} \end{aligned}$$

Ejemplo 3:¶

Todos los lógicos son reflexivos y estudiosos.
Algunos lógicos son filósofos.
Luego, algunas personas reflexivas son filósofos.

$$\begin{aligned} &\begin{array}{l l} (1) & \forall x [L(x) \rightarrow (R(x) \land E(x))] \\ (2) & \exists x [L(x) \land F(x)] \\ \hline \models & \exists x [R(x) \land F(x)] \\ \end{array} \end{aligned}$$

Derivaciones:

$$\begin{aligned} &\begin{array}{l l l } (3) & L(a) \rightarrow (R(a) \land E(a)) & \text{EU(1)}\\ (4) & L(a) \land F(a) & \text{EE(2)}\\ (5) & L(a) & \text{Simp.(4)}\\ (6) & R(a) \land E(a) & \text{MP.(3,5)}\\ (7) & R(a) & \text{Simp.(6)}\\ (8) & F(a) & \text{Simp.(4)}\\ (9) & F(a) \land R(a) & \text{Conj.(7,8)}\\ (10) & \exists x [F(x) \land R(x)] & \text{GE.(9)}\\ \end{array} \end{aligned}$$

Referencias¶

Inteligencia artificial. Un enfoque moderno. 2ª edición. Stuart Russell y Peter Norving