8.1: Lógica proposicional

El más simple —pero menos poderoso— de los dos sistemas lógicos que estudiaremos se llama lógica proposicional. Tiene este nombre porque el bloque de construcción central es la proposición. Una proposición es simplemente una afirmación que tiene un “valor de verdad”, lo que significa que es verdadera o falsa. La declaración “todas las plantas son seres vivos” podría ser una proposición, al igual que “Barack Obama fue el primer presidente afroamericano” y “Kim Kardashian interpretará el papel principal en el próximo Batman Reborn”. Por el contrario, preguntas como “¿estás bien?” no pueden ser proposiciones, ni pueden comandos como “¡date prisa y contesta ya!” o frases como “Schnauzer recién nacido de Lynn”, porque no son afirmaciones que puedan ser verdaderas o falsas. (Lingüísticamente hablando, las proposiciones tienen que estar en el estado de ánimo indicativo.)

Normalmente usamos mayúsculas (¿qué más?) para denotar proposiciones, como:

Que A sea la proposición de que UMW está en Virginia.

Que B sea la proposición de que la Reina de Inglaterra es varonil.

Que C sea la proposición de que los perros son carnívoros.

No hay que olvidar que una proposición no tiene que ser cierta para ser una proposición válida (B sigue siendo una proposición, por ejemplo). Simplemente importa que esté etiquetado y que tenga el potencial de ser verdadero o falso.

Las proposiciones se consideran atómicas. Esto quiere decir que son indivisibles: para el propio sistema lógico, o para un programa de computadora, son simplemente un pedazo opaco de verdad (o falsedad) llamado “A” o lo que sea. Cuando los humanos leemos la descripción de A, nos damos cuenta de que tiene que ver con la ubicación de una institución particular de educación superior, y con el estado de la unión en el que podría residir (o no). Todo esto es invisible para un agente artificialmente inteligente, sin embargo, que trata a “A” como nada más que una etiqueta suplente para una declaración que no tiene más estructura discernible.

Entonces las cosas son bastante aburridas hasta ahora. Podemos definir y etiquetar proposiciones, pero ninguna de ellas tiene ninguna conexión con las demás. Cambiamos eso introduciendo operadores lógicos (también llamados conectivos lógicos) con los que podemos construir construcciones compuestas a partir de múltiples proposiciones. Los seis conectivos que aprenderemos son:

\(\wedge\)— “y”	\(\neg\)— “no”
\(\vee\)— “o”	\(\Rightarrow\)— “implica” (o “si... entonces...”)
\(\oplus\)— “xor” (exclusivo “o”)	\(\Leftrightarrow\)— “equiv” (equivalente)

Así como los operadores algebraicos ordinarios (+, -, etc.) se pueden usar para unir números y producir otro número, y así como los operadores set se pueden usar para unir conjuntos y producir otro conjunto, los operadores lógicos se pueden usar para unir proposiciones y producir otra proposición. La expresión “34 + 59" produce el número 93. La expresión “{X, Y}\(\cup\) {Y, Z}” produce el conjunto {X, Y, Z}. Y la expresión “A\(\wedge\) B” produce el valor falso, ya que aunque UMW se encuentra en Virginia, la Reina es femenina.

Repasemos por los seis operadores, algunos de los cuales son intuitivos y otros no:

\(\wedge\)(“y”)

La proposición X\(\wedge\) Y es cierta cuando tanto X como Y son verdaderas proposiciones. “A\(\wedge\) C” representa la proposición “UMW está en Virginia y los perros son carnívoros”, lo que tiene un valor de verdad de verdad ya que ambos componentes son verdaderos. Esta operación a veces se llama conjunción. Observe que el signo “\(\wedge\)" se parece un poco al signo “\(\cap\)" para la intersección establecida. Esto no es un accidente. Un elemento se encuentra en la intersección de dos conjuntos si es miembro del primer y del segundo conjunto. De ahí que los matemáticos hayan elegido símbolos que refuercen esta conexión.

\(\vee\)(“o”)

La proposición X\(\vee\) Y es verdadera cuando X o Y (o ambas) son verdaderas proposiciones. “B\(\vee\) C” representa la proposición “La Reina de Inglaterra es macho o los perros son carnívoros”, lo que tiene un valor de verdad de verdad ya que el segundo componente es cierto. Esta operación a veces se denomina disyunción. El\(\vee\) se parece algo al signo “\(\cup\)" para la unión de conjunto, ya que un elemento está en la unión de dos conjuntos si es un elemento del primer conjunto o del segundo conjunto (o ambos). A este operador a veces se le llama “inclusivo o” ya que es cierto si ambas proposiciones son verdaderas.

\(\oplus\)(“xor”)

El\(\oplus\) operador es igual a\(\vee\) excepción de que es exclusivo: la proposición X\(\oplus\) Y es verdadera cuando X o Y (pero no ambas) son verdaderas proposiciones. “B\(\vee\) C” y “B\(\oplus\) C” son ambos ciertos, pero “A\(\oplus\) C” es falso, ya que UMW está en Virginia y los perros son carnívoros.

\(\neg\)(“no”)

Este operador es diferente de los demás en que es unario, lo que significa que solo opera sobre una proposición en lugar de dos. Todo lo que hace es voltear el valor de verdadero a falso (o viceversa). La proposición “A” es cierta, pero la proposición “\(\neg\)A” es falsa. “\(\neg\)B”, en cambio, es cierto. Esta operación a veces se llama negación.

\(\Rightarrow\)(“implica”)

Bien, ahora para el más duro. Vamos a pasar un tiempo significativo pensando detenidamente en este, porque es a la vez importante (de alguna manera, el más importante de los operadores) y también potencialmente desconcertante. He estudiado estas cosas durante años, y todavía a veces me quedo atascado al tratar de averiguarlo\(\Rightarrow\).

Si decimos “X\(\Rightarrow\) Y”, estamos afirmando que “si X es verdad, entonces Y es verdad”. Obsérvese cuidadosamente que no estamos alegando que X en sí sea cierto. Simplemente estamos afirmando que si es cierto, entonces Y necesariamente también debe ser verdad. Llamamos a la primera parte de una\(\Rightarrow\) proposición la premisa, y a la segunda parte la conclusión. Aquí, X es la premisa e Y la conclusión.

Hasta el momento, parece fácil. Se vuelve más difícil cuando te das cuenta de que X\(\Rightarrow\) Y es cierto siempre que X es falso o Y es cierto (o ambos). Por ejemplo, A\(\Rightarrow\) C es una verdadera proposición, lo creas o no. En inglés, dice “UMW estar en Virginia implica que los perros son carnívoros”. También es cierta la proposición B\(\Rightarrow\) A: “La Reina de Inglaterra siendo varón implica que UMW está en Virginia”. ¿Qué sentido podemos tener de estas afirmaciones sin sentido?

La clave para entenderlo, al menos para mí, es doble. Primero, recuerda que para una computadora (o un sistema lógico), las proposiciones no tienen sentido: son simplemente bloques de construcción atómicos, cada uno de los cuales es verdadero o falso. Entonces, el hecho de que para un humano, el contenido de las proposiciones no tenga nada que ver entre sí —Reinas inglesas y perros— es irrelevante para una computadora: simplemente piensa indiferentemente en términos de “X” e “Y”, y no tiene idea a qué entidades del mundo real se refiere cualquiera de esto. Segundo, pensar en términos de descartar contraejemplos. Cuando afirmo X\(\Rightarrow\) Y, lo que estoy diciendo es “es imposible que X sea cierto e Y falso, porque la veracidad de X implicaría la veracidad de Y”. Así como cuando afirmo X\(\vee\) Y estoy prometiendo que X o Y es cierto (o ambos), cuando afirmo X\(\Rightarrow\) Y estoy prometiendo que o X es verdadero o Y es falso (o ambos).

De esta manera, empieza a tener sentido cuando alguien dice: “El hecho de que Iowa esté en el hemisferio sur implica que la capa de Batman es roja”. Esa afirmación es como una promesa: “si resulta que Iowa está en el hemisferio sur, entonces garantizo que la capa de Batman es roja”. Pero como Iowa no está en el hemisferio sur, todas las apuestas están apagadas. La conclusión estuvo condicionada a la premisa.

La razón por la que este operador es tan importante es que en la inteligencia artificial, el nombre del juego está concluyendo nuevos hechos a partir de hechos conocidos existentes, por lo que se incrementa el conocimiento. Cada vez que un 'bot aprende que X\(\Rightarrow\) Y es verdad, y luego también aprende que la premisa (X) es verdadera, puede concluir que la conclusión (Y) es cierta, aunque nunca se le dijera explícitamente que Y era verdad. Esta regla de lógica se llama modus ponens, y es el caballo de batalla de las bases de conocimiento automatizadas.

\(\Leftrightarrow\)(“equiv”)

Por último, la proposición X\(\Leftrightarrow\) Y es verdadera siempre que X e Y tengan el mismo valor: ambas son verdaderas, o ambas falsas. Esto puede verse como “implica en ambos sentidos”, ya que X\(\Leftrightarrow\) Y significa “si X es verdadero, entonces Y es verdadero; y si Y es verdadero, entonces X es cierto”. Este operador también es el inverso de\(\oplus\), ya que X\(\oplus\) Y es verdadero solo si X e Y son diferentes, y X\(\Leftrightarrow\) Y es cierto solo si son iguales.

Estos operadores, cada uno de los cuales produce otra proposición (llamada propuesta compuesta) a partir de la (s) proposición (s) sobre la (s) que operan, se pueden combinar para formar expresiones complejas. Por ejemplo:

• \(\neg\)B es la proposición de que la Reina de Inglaterra no es varonil. (Esto es cierto.)

• A\(\wedge\)\(\neg\) B es la proposición de que UMW está en Virginia y la Reina de Inglaterra no es masculina. (Esto también es cierto.)

• C\(\oplus\) (A\(\wedge\)\(\neg\) B) es la proposición de que o los perros son carnívoros o UMW está en Virginia y la Reina de Inglaterra no es macho. (Esto es falso, porque ambas mitades del xor son verdaderas.)

• (C\(\oplus\) (A\(\wedge \neg\) B))\(\Rightarrow\)\(\neg\) A es la proposición de que si cualquiera de los perros son carnívoros o UMW reside en Virginia y la Reina de Inglaterra no es macho, entonces UMW no debe residir en Virginia. (Esto es cierto, ya que los perros son carnívoros y UMW reside en Virginia y la Reina de Inglaterra no es macho, por lo que el lado izquierdo del\(\Rightarrow\) es falso, lo que significa que toda la expresión es verdadera independientemente del valor de verdad del lado derecho (que también es falso, ya que UMW no reside en Virginia.)

• Etc.

Tablas de la verdad

Varias veces en este libro, hemos dibujado la distinción entre la intensión —el significado interior, conceptual— y la extensión — la lista exhaustiva de ejemplos. Un conjunto puede tener tanto una intención como “los números primos menores que diez” y una extensión como {2,3,5,7}. Una relación puede tener una intención como “IsDaughterOf" y una extensión como “{(Lisa, Homero), (Lisa, Marge), (Maggie, Homero), (Maggie, Marge)}.” Entonces, también, con las conectivas lógicas. Cuando decimos que el “\(\wedge\)" operador significa “ambas proposiciones deben ser verdaderas”, estamos especificando el significado conceptual del operador “y”. Otra forma de describirlo, sin embargo, sería simplemente enumerar su valor para todas las entradas posibles.

Una lista tan exhaustiva se llama tabla de verdad. Especificamos cada combinación posible de entradas, y enumeramos la salida para cada una de ellas. Aquí está la tabla de la verdad para\(\wedge\) “:

X	Y	X\(\wedge\) Y
0	0	0
0	1	0
1	0	0
1	1	1

 

Usamos “1" para representar true y “0" para false, solo para hacer la mesa más compacta. El operador “\(\wedge\)" trabaja sobre dos proposiciones, cualquiera de las cuales puede tener un valor de verdad o 0 o 1. Por lo tanto, por el Teorema Fundamental del Conteo, hay cuatro combinaciones diferentes de entradas, y así nuestra tabla de verdad tiene cuatro filas. La columna más a la derecha muestra la salida para cada uno de estos conjuntos de entradas. Indica que X\(\wedge\) Y es 1 sólo cuando ambas entradas son 1, y 0 en caso contrario. Incluso si no entendiéramos el concepto simple de que “\(\wedge\)" se supone que representa el concepto de “y”, podríamos simplemente buscar el valor de X\(\wedge\) Y si conociéramos los valores de verdad de X e Y.

A veces mostramos más de una salida en una tabla de verdad. Por ejemplo, esta tabla de verdad muestra los valores para los otros cinco operadores:

X	Y	X\(\vee\) Y	X\(\oplus\) Y	\(\neg\)X	X\(\Rightarrow\) Y	X\(\Leftrightarrow\) Y
0	0	0	0	1	1	1
0	1	1	1	1	1	0
1	0	1	1	0	0	0
1	1	1	0	0	1	1

Tómese un momento y observe cuidadosamente las entradas en esa tabla, y asegúrese de estar de acuerdo en que esto representa correctamente las salidas para los cinco operadores. (Tenga en cuenta que\(\neg\) ““, al ser un operador unario, sólo tiene X como entrada, lo que significa que el valor de Y es efectivamente ignorado para esa columna.)

Ahora a veces tenemos una expresión más compleja (como la (C\(\oplus\) (A\(\wedge \neg\) B))\(\Rightarrow\)\(\neg\) Un ejemplo de arriba) y queremos conocer el valor de verdad de toda la expresión. ¿Bajo qué circunstancias —es decir, para qué valores de verdad de A, B y C— es cierta esa expresión? Podemos usar tablas de verdad para calcular esta pieza por pieza.

Trabajemos a través de ese ejemplo en su totalidad. Primero, configuramos las entradas para nuestra tabla de verdad:

A	B	C
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

En este caso, hay tres entradas a la expresión (A, B y C) y así tenemos\(2^3\), u ocho, filas en la tabla de verdad.

Ahora trabajamos nuestro camino a través de la expresión de adentro hacia afuera, anotando los valores de las partes intermedias de la expresión. Necesitamos saber el valor de\(\neg\) B para resolver algunas otras cosas, así que comencemos con esa:

A	B	C	\(\neg\)B
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	0

Ahora podemos calcular A\(\wedge \neg\) B, un componente de la expresión:

A	B	C	\(\neg\)B	A\(\wedge \neg\) B
0	0	0	1	0
0	0	1	1	0
0	1	0	0	0
0	1	1	0	0
1	0	0	1	1
1	0	1	1	1
1	1	0	0	0
1	1	1	0	0

Esto produce un 1 solo para filas donde A es verdadero y B es falso. Saber esto nos permite calcular el valor de (C\(\oplus\) (A\(\wedge \neg\) B)):

A	B	C	\(\neg\)B	A\(\wedge \neg\) B	(C\(\oplus\) (A\(\wedge \neg\) B))
0	0	0	1	0	0
0	0	1	1	0	1
0	1	0	0	0	0
0	1	1	0	0	1
1	0	0	1	1	1
1	0	1	1	1	0
1	1	0	0	0	0
1	1	1	0	0	1

que es cierto sólo cuando el valor de C es diferente al valor de (A\(\wedge \neg\) B). Ya casi estamos ahí. Todo lo que necesitamos es\(\neg\) A:

A	B	C	\(\neg\)B	A\(\wedge \neg\) B	(C\(\oplus\) (A\(\wedge \neg\) B))	\(\neg\)A
0	0	0	1	0	0	1
0	0	1	1	0	1	1
0	1	0	0	0	0	1
0	1	1	0	0	1	1
1	0	0	1	1	1	0
1	0	1	1	1	0	0
1	1	0	0	0	0	0
1	1	1	0	0	1	0

y finalmente podemos obtener nuestra respuesta:

A	B	C	\(\neg\)B	A\(\wedge \neg\) B	(C\(\oplus\) (A\(\wedge \neg\) B))	\(\neg\)A	(C\(\oplus\) (A\(\wedge \neg\) B))\(\Rightarrow\)\(\neg\) A
0	0	0	1	0	0	1	1
0	0	1	1	0	1	1	1
0	1	0	0	0	0	1	1
0	1	1	0	0	1	1	1
1	0	0	1	1	1	0	0
1	0	1	1	1	0	0	1
1	1	0	0	0	0	0	1
1	1	1	0	0	1	0	0

Ese último paso es el más difícil. Observamos la tercera columna de salida (C\(\oplus\) (A\(\wedge \neg\) B) y la cuarta (\(\neg\)A) y marcamos hacia abajo un 1 por cada fila en la que la tercera es 0 o la cuarta es 1. (Revisa la tabla de verdad para el operador “\(\Rightarrow\)" si tienes dudas al respecto). El resultado final es que nuestra expresión compleja es verdadera para todos los valores posibles de A, B y C, excepto cuando tienen los valores 1, 0 y 0, o bien 1, 1 y 1, respectivamente. En nuestro ejemplo original, sabemos que UMW está en Virginia, la Reina no es macho, y los perros son carnívoros, por lo que nuestros valores de entrada son 1, 0, y 1 para A, B y C. Por lo tanto, para esas entradas, esta expresión es verdadera.

Tautologías

Trabajemos a través de este proceso para un ejemplo diferente. Supongamos que quiero saber bajo qué circunstancias la expresión\(\neg\) Z\(\wedge\) (X\(\Leftrightarrow\) Y)\(\wedge\) (X\(\oplus\) Z)\(\Rightarrow\) (X\(\wedge\)\(\neg\) Z) evalúa como verdadera. Cuando seguimos el procedimiento anterior, arroja la siguiente tabla de verdad:

X	Y	Z	\(\neg\)Z	X\(\Leftrightarrow\) Y	\(\neg\)Z\(\wedge\) (X\(\Leftrightarrow\) Y)	X\(\oplus\) Z	A ^1	(X\(\wedge\neg\) Z)	B
0	0	0	1	1	1	0	0	0	1
0	0	1	0	1	0	1	0	0	1
0	1	0	1	0	0	0	0	0	1
0	1	1	0	0	0	1	0	0	1
1	0	0	1	0	0	1	0	1	1
1	0	1	0	0	0	0	0	0	1
1	1	0	1	1	1	1	1	1	1
1	1	1	0	1	0	0	0	0	1

(Si estás buscando algo de práctica, comenzar a través de este ejemplo por tu cuenta y luego comparar tus respuestas con la tabla de verdad anterior no es mala idea en absoluto).

Notarás que la columna de “respuesta” tiene todos los 1's, lo que significa que la expresión siempre es verdadera, sin importar cuáles sean los valores de las proposiciones individuales. Tal expresión se llama tautología: siempre es verdad. La palabra “tautología” tiene una connotación negativa en el uso regular del inglés: se refiere a una afirmación tan obvia que no te dice nada, como “todos los triángulos tienen tres lados”, o “la sobredosis fatal fue mortal”. Pero en lógica, las tautologías son bastante útiles, ya que representan identidades confiables.

La tautología anterior fue un ejemplo ideado, y no útil en la práctica. Aquí hay algunos otros importantes, aunque:

X	\(\neg\)X	X\(\vee\neg\) X
0	1	1
1	0	1

A veces llamada la ley del medio excluido, esta identidad establece que ya sea una proposición o su negativo siempre será cierto. (No hay una tercera opción.)

X	Y	X\(\vee\) Y	\(\neg\)(X\(\vee\) Y)	\(\neg\)X	\(\neg\)Y	\(\neg\)X\(\wedge\neg\) Y	\(\neg\)(X\(\vee\) Y)\(\Leftrightarrow\) (\(\neg\)X\(\wedge\neg\) Y)
0	0	0	1	1	1	1	1
0	1	1	0	1	0	0	1
1	0	1	0	0	1	0	1
1	1	1	0	0	0	0	1

Esta es una de las Leyes de De Morgan, que hemos visto anteriormente en lo que respecta a los sets (p.). Aquí está el otro:

X	Y	X\(\wedge\) Y	\(\neg\)(X\(\wedge\) Y)	\(\neg\)X	\(\neg\)Y	\(\neg\)X\(\vee\neg\) Y	\(\neg\)(X\(\wedge\) Y)\(\Leftrightarrow\) (\(\neg\)X\(\vee\neg\) Y)
0	0	0	1	1	1	1	1
0	1	0	1	1	0	1	1
1	0	0	1	0	1	1	1
1	1	1	0	0	0	0	1

El primero puede expresarse como “la negación de la disyunción es igual a la conjunción de las negaciones”, y el segundo como “la negación de la conjunción es igual a la disyunción de las negaciones”. Si eso ayuda en absoluto.

Una última identidad es esta:

X	Y	Z	Y\(\vee\) Z	X\(\wedge\) (Y\(\vee\) Z)	X\(\wedge\) Y	X\(\wedge\) Z	(X\(\wedge\) Y)\(\vee\) (X\(\wedge\) Z)	A ^2
0	0	0	0	0	0	0	0	1
0	0	1	1	0	0	0	0	1
0	1	0	1	0	0	0	0	1
0	1	1	1	0	0	0	0	1
1	0	0	0	0	0	0	0	1
1	0	1	1	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	1	1	1	1	1	1	1

Esto no es otro que la ley distributiva, que también vimos para conjunto unión e intersección (p.) y que también debes recordar del álgebra introductoria:\(x\cdot(y+z)=x\cdot y+x\cdot z\).

Es interesante, en realidad, cuando se compara la ley distributiva del álgebra a la ley distributiva para la lógica:\[\begin{aligned} x\cdot(y+z) &= x\cdot y+x\cdot z \\ X\wedge(Y\vee Z) & \Leftrightarrow(X\wedge Y)\vee(X\wedge Z)\end{aligned}\] El operador “\(\wedge\)" es análogo a “\(\cdot\)" (tiempos), mientras que “\(\vee\)" corresponde a “+” (más). De hecho, si vuelves a mirar las tablas de verdad para estos dos operadores, verás un parecido extraño:

X	Y	X\(\wedge\) Y	X\(\vee\) Y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	(1)

Excepto por el (1) que puse entre paréntesis, esta tabla de verdad es exactamente lo que obtendrías si multiplicaras matemáticamente (\(\wedge\)) y agregaras (\(\vee\)) las entradas! En algún nivel, lógicamente “y-ing” se está multiplicando, mientras que “o-ing” es sumando. Fascinante.

---

1. Aquí, “A” significa ¬Z( XY) (XZ) y “B” es “¬Z( XY) (XY) ⇒ (X¬Z)”, que eran demasiado largas para caber en el encabezado de la tabla
2. Aquí, “A” es XZ (YZ) ⇔ (XY) ⇔ (XY) ⇔ (XZ).