8.2: Lógica predicado

Lógica predicado

La lógica proposicional puede representar muchas cosas, pero resulta ser demasiado limitante para ser prácticamente útil. Y eso tiene que ver con la naturaleza atómica de las proposiciones. Cada proposición es su propio pedazo opaco de veracidad o falsedad, sin forma de dividirla en partes constituyentes. Supongamos que quería afirmar que cada estado del sindicato tenía un gobernador. Para afirmar esto en la lógica proposicional, tendría que crear una nueva propuesta para cada estado:

Que G1 sea la proposición de que Alabama tenga un gobernador.

Que G2 sea la proposición de que Alaska tiene un gobernador.

Que G3 sea la proposición de que Arizona tiene gobernador.

...

y luego, finalmente, podría afirmar:

G1\(\wedge\) G2\(\wedge\) G3\(\wedge \cdots \wedge\) G50.

Eso es mucho trabajo solo para crear un montón de proposiciones individuales que son esencialmente las mismas. Lo que necesitamos es algún tipo de plantilla de proposición, con la que podamos “acuñar” nuevas proposiciones de una forma similar enchufando nuevos valores.

Esto es exactamente lo que es un predicado, que forma la base de la lógica de predicado, o “lógica de predicado de primer orden”, para ser más exactos. ¹ Un predicado es una fórmula que produce una proposición para cada valor de sus entradas. Por ejemplo, puedo definir un predicado llamado “hasGoveror" de la siguiente manera:

Que hasGovernor (\(x\)) sea la proposición de que\(x\) es un estado que tiene un gobernador.

Entonces puedo afirmar:

HasGoveror (Virginia)

para afirmar que Virginia tiene gobernador. Este mecanismo alivia la necesidad de definir cincuenta proposiciones casi idénticas. En cambio, definimos un predicado.

Si eres programador, puedes pensar en un predicado como una función que devuelve un booleano. Tanto si eres programador como si no, puedes pensar en un predicado como una función (en el sentido del capítulo) mapeando objetos a proposiciones:\[HasGovernor : \Omega \rightarrow P,\] dónde\(P\) está el conjunto de todas las proposiciones. Obsérvese que el dominio de esta función es\(\Omega\), todo el dominio del discurso. Esto significa que se puede dar cualquier entrada en absoluto al predicado. Por ejemplo, podemos afirmar:

\(\neg\)HasGoveror (mayonesa)

lo cual es perfectamente cierto. ²

Tal vez recuerdes la palabra “predicado” de tu clase de gramática de secundaria. Cada oración, recuerda, tiene un sujeto y un predicado. En “Billy salta”, “Billy” es el sujeto, y “salta” el predicado. En “El chico solitario comió espaguetis con gusto”, tenemos como tema a “el chico solitario” y “comía espaguetis con gusto” como predicado. Básicamente, un predicado es cualquier cosa que pueda describir o afirmar algo sobre un tema, que es exactamente lo que estamos haciendo aquí. Imagínese afirmar “Jumps (Billy)” y “AtespaghettiWithGusto (chico solitario)”.

Un predicado puede tener más de una entrada. Supongamos que definimos el predicado IsFanOf de la siguiente manera:

Que isFanof (\(x,y\)) sea la proposición que\(x\) cava la música de la banda de rock\(y\).

Entonces puedo afirmar:

IsFanof (Stephen, Led Zeppelin)

IsFanof (Rachel, Los Beatles)

IsFanof (Stephen, Los Beatles)

\(\neg\)IsFanof (Stephen, Los Rolling Stones)

Incluso podríamos definir TraveledTobyModeinYear con un montón de entradas:

Que TraveledTobyModeinYear (\(p,d,m,y\)) sea la proposición de que la persona\(p\) viajó a destino\(d\) por modo\(m\) en año\(y\).

Las siguientes afirmaciones son entonces verdaderas:

ViajadoTobyModeinYear (Stephen, Richmond, coche, 2007)

TraveledTobyModeinYear (Rachel, Austria, avión, 2010)

\(\neg\)ViajadoTobyModeinYear (Johnny, Marte, nave espacial, 1776)

Definir múltiples entradas nos da más precisión en la definición de relaciones. Imagínese crear el predicado “AteWithAttitude" y luego afirmar:

AteWithAttitude (chico solitario, espaguetis, gusto)

\(\neg\)AteWithAttitude (Johnny, brócoli, gusto)

AteWithAttitude (Johnny, brócoli, trepidación)

Predicados y relaciones

El lector astuto pudo haber notado que el predicado de IsFanOf, arriba, parece muy similar a una relación IsFanOf definida entre sets\(P\) (el conjunto de personas) y\(R\) (el conjunto de bandas de rock), donde IsFanof\(\subseteq P \times R\). En ambos casos, tenemos pares de personas/bandas para las que es cierto, y parejas para las que es falso.

Efectivamente estos conceptos son idénticos. De hecho, una relación puede definirse como el conjunto de pares ordenados (o tuplas) para los cuales un predicado es verdadero. Decir “IsFanof (Rachel, The Beatles)” e “\(\neg\)IsFanof (Stephen, The Rolling Stones)” es realmente otra forma de decir “Rachel IsFanOf The Beatles” y “Stephen —IsFanof— The Rolling Stones”.

Cuantificadores

Una característica poderosa de la lógica del predicado es la capacidad de hacer declaraciones grandiosas sobre muchas cosas a la vez. Supongamos que sí quisiéramos afirmar que cada estado tenía un gobernador. ¿Cómo lo podemos hacer?

Añadiremos a nuestro repertorio la noción de cuantificadores. Hay dos tipos de cuantificadores en la lógica de predicados, el primero de los cuales se llama el cuantificador universal. Está escrito “\(\forall\)" y se pronuncia “para todos”. He aquí un ejemplo:\[\forall x\ HasGovernor(x).\] Esto afirma que por cada x, HasGob es cierto. En realidad, esto no está del todo bien, pues aunque Michigan y California tienen gobernadores, la mayonesa no. Para ser precisos, deberíamos decir:\[\forall x\in S\ HasGovernor(x),\] ¿dónde\(S\) está el conjunto de los cincuenta estados de Estados Unidos?

Podemos usar un cuantificador para cualquier expresión compleja, no solo un simple predicado. Por ejemplo, si\(H\) es el conjunto de todos los humanos, entonces:\[\forall h\in H\ Male(h) \oplus Female(h)\] afirma que todo ser humano es masculino o femenino, pero no ambos. Otra forma (más común) de escribir esto es prescindir de conjuntos y definir otro predicado Humano. Entonces podemos decir:\[\forall h\ Human(h) \Rightarrow Male(h) \oplus Female(h).\] Piensa esto detenidamente. Ahora estamos afirmando que esta expresión es cierta para todos los objetos, ya sean Brad Pitt, Lady Gaga, o un plato de avena. Para ver que es cierto para los tres, seamos\(h\) primero iguales a Brad Pitt. Sustituimos a Brad Pitt\(h\) y obtenemos:\[\begin{aligned} Human(\text{Brad Pitt}) & \Rightarrow Male(\text{Brad Pitt}) \oplus Female(\text{Brad Pitt}) \\ \text{true} & \Rightarrow \text{true} \oplus \text{false} \\ \text{true} & \Rightarrow \text{true} \\ \text{true} & \ \checkmark\end{aligned}\] Recuerda que “implica” (\(\Rightarrow\)) es cierto siempre y cuando la premisa (lado izquierdo) sea falsa y/o la conclusión (lado derecho) sea verdadera. En este caso, ambos son ciertos, así que tenemos un verdadero resultado final. Algo similar le sucede a Lady Gaga:\[\begin{aligned} Human(\text{Lady Gaga}) & \Rightarrow Male(\text{Lady Gaga}) \oplus Female(\text{Lady Gaga}) \\ \text{true} & \Rightarrow \text{false} \oplus \text{true} \\ \text{true} & \Rightarrow \text{true} \\ \text{true} & \ \checkmark\end{aligned}\] Entonces estos dos casos ambos resultan en verdad. Pero quizás sorprendentemente, también nos hacemos realidad para la avena:\[\begin{aligned} Human(\text{bowl of oatmeal}) & \Rightarrow Male(\text{bowl of oatmeal}) \oplus Female(\text{bowl of oatmeal}) \\ \text{false} & \Rightarrow \text{false} \oplus \text{false} \\ \text{false} & \Rightarrow \text{false} \\ \text{true} & \ \checkmark\end{aligned}\] Whoa, ¿cómo surgió la verdad de eso? Simplemente porque la premisa era falsa, y así todas las apuestas estaban apagadas. Efectivamente dijimos “si un tazón de avena es humano, entonces será macho o hembra. Pero no lo es, así que no importa”. Dicho de otra manera, el tazón de avena no resultó ser un contraejemplo, y así estamos seguros afirmando que esta expresión es cierta “para todos h”:\(\forall\) h.

El otro tipo de cuantificador se llama el cuantificador existencial. Como su nombre indica, afirma la existencia de algo. Lo escribimos “\(\exists\)" y lo pronunciamos “existe”. Por ejemplo,\[\exists x\ HasGovernor(x)\] asevera que hay al menos un estado que tiene gobernador. Esto no nos dice para cuántos estados es cierto esto, y de hecho a pesar de su nombre, los cuantificadores realmente no son muy buenos para “cuantificar” las cosas para nosotros, al menos numéricamente. A partir de 2008, la afirmación\[\exists x\ President(x) \wedge African-American(x)\] es cierta, y siempre lo será, sin importar cuántos presidentes estadounidenses afroamericanos más tengamos. Tenga en cuenta que en expresiones compuestas como esta, una variable (like\(x\)) siempre representa una sola entidad donde quiera que aparezca. Desde hace cientos de años han existido afroamericanos, y han existido presidentes, por lo que la expresión anterior sería ridículamente obvia si solo significara “ha habido presidentes, y ha habido afroamericanos”. Pero la misma variable\(x\) que se utiliza como insumos a ambos predicados es lo que sella el trato y lo hace representar la afirmación mucho más fuerte “hay al menos un individuo que es personalmente tanto afroamericano como Presidente de los Estados Estados al mismo tiempo”.

Es una práctica común negar cuantificadores, tanto universales como existenciales. A partir de 2012, la siguiente afirmación sigue siendo cierta:\[\neg \exists p\ President(p) \wedge Female(p).\] Esto transmite que no existe una presidenta femenina. Como otro ejemplo, si un día Missouri reconstruye su estructura de gobierno y la reemplaza por una mobocracia, tal vez digamos:\[\neg \forall x\ HasGovernor(x).\]

Intercambiar cuantificadores

Algunos temas iluminadores se pueden ver cuando examinamos la relación que los dos tipos de cuantificadores tienen entre sí. Considera primero éste:\[\begin{aligned} \forall x \ P(x) \Leftrightarrow \neg \exists x\ \neg P(x), (\PageIndex{1})\end{aligned}\] donde P es cualquier predicado (o para el caso, cualquier expresión que involucre muchos predicados). Eso es sensato. Afirma: “si\(P\) es verdad de todas las cosas, entonces no existe nada para lo que no sea cierto”. Otras tres equivalencias salen a la luz:\[\begin{aligned} \neg \forall x \ P(x) & \Leftrightarrow \exists x\ \neg P(x) (\PageIndex{2}) \\ \forall x \ \neg P(x) & \Leftrightarrow \neg \exists x\ P(x) (\PageIndex{3}) \\ \neg \forall x \ \neg P(x) & \Leftrightarrow \exists x\ P(x) (\PageIndex{4}) \end{aligned}\]

En palabras, identity\ pageIndex {2} dice “si no es cierto para todo, entonces debe ser falso para algo”. Identity\ PageIndex {3} dice “si es falso para todo, entonces no hay nada para lo que sea cierto”. Y la identidad\ PageIndex {4} dice “si no es falso para todo, entonces debe ser cierto para algo”. Todos estos son eminentemente lógicos, creo que estarás de acuerdo. También implican que casi siempre hay múltiples formas correctas de afirmar algo. En nuestra visión apocalíptica de Missouri, por ejemplo, dijimos “\(\neg \forall x\)hasGovernor”\((x)\), pero también podríamos haber dicho “\(\exists x\ \neg\)hasGovernor”\((x)\), lo que equivale a lo mismo.

Asuntos de orden

Cuando te enfrentas a un intimidante pantano de\(\forall\)\(\exists\)'s y\(\vee\)\(\Rightarrow\)'s y's y Dios sabe qué más, es fácil perderse en la salsa. Pero hay que tener mucho cuidado para diseccionar la expresión para averiguar qué significa. Considera ésta:\[\begin{aligned} \forall x \in \mathbb{R} \exists y \in \mathbb{R} \ x+1=y.\end{aligned}\] Esta afirmación es cierta. Dice que por cada número real (llámalo\(x\)), es cierto que puedes encontrar algún otro número (llamarlo\(y\)) que sea uno mayor que él. Si generas algunos ejemplos es fácil ver que esto es cierto. Supongamos que tenemos el número real\(x=5\). ¿Hay algún otro número\(y\) que sea igual a\(x+1\)? Por supuesto, el número 6. ¿Y si\(x=-32.4\)? ¿Hay algún número\(y\) que satisfaga esta ecuación? Por supuesto,\(y=-31.4\). Obviamente no importa qué número\(x\) elijamos, podemos encontrar el número deseado\(y\) con solo agregar uno. De ahí que esta afirmación sea cierta para todos\(x\), tal y como dice.

¿Qué pasa, sin embargo, si cambiamos inocentemente el orden de los cuantificadores? Intentemos afirmar esto:\[\begin{aligned} \exists y \in \mathbb{R} \forall x \in \mathbb{R} \ x+1=y.\end{aligned}\] ¿Esto también es cierto? Mire con cuidado. Dice “existe algún número mágico\(y\) que tiene la siguiente propiedad increíble: no importa qué valor\(x\) elijas, ¡este\(y\) es uno mayor que\(x\)!” Obviamente esto no es cierto. No existe tal número\(y\). Si elijo\(y=13\), eso funciona muy bien mientras yo elija\(x=12\), pero para cualquier otra opción de\(x\), está muerto en el agua.

La lección aprendida aquí es que el orden de los cuantificadores importa. Tienes que tomar cada par cuantificador/variable por turno, y pensar para ti mismo, “bien, esta afirmación está afirmando que una vez que elijo la primera variable, el resto de la expresión es verdad para esa elección”.

El valor de la precisión

Esta fluidez con la sintaxis básica y el significado de la lógica predicada fue nuestro único objetivo en este capítulo. Existen todo tipo de reglas lógicas que se pueden aplicar a las declaraciones lógicas de predicado con el fin de deducir otras declaraciones, y aprenderás sobre ellas cuando estudies la inteligencia artificial más adelante. La mayoría de ellos son versiones formalizadas del sentido común. “Si sabes que A es verdad, y sabes que A\(\Rightarrow\) B es verdad, entonces puedes concluir que B es verdad”. O “si sabes que X\(\wedge\) Y es falso, y entonces descubres que Y es verdad, entonces puedes concluir que X es falso”. Etc. El poder de producir nueva verdad a partir de la verdad existente es el sello distintivo de los sistemas de IA, y por qué esto realmente importa.

Si puedes imaginar un programa haciendo este tipo de razonamiento automatizado, quedará claro por qué se vuelve importante la precisión de algo así como la lógica del predicado —en lugar del descuido del inglés—. El inglés es un lenguaje hermoso y poético, pero su ambigüedad es notoria. Por ejemplo, de vuelta en el capítulo usamos la frase “algún empleado pertenece a cada departamento” al describir las relaciones. Ahora considera esa frase en inglés. ¿Qué significa realmente “algún empleado pertenece a cada departamento”? ¿Significa que hay algún empleado especial que pasa a tener membresía en todos los departamentos de la empresa? O significa que ningún departamento está vacío: todos los departamentos tienen al menos una persona en ellos, ¿por gritar en voz alta? El inglés podría significar cualquiera de los dos. En la lógica del predicado, o bien estamos afirmando:\[\exists x\ Employee(x) \wedge \forall y\ BelongsTo(x,y)\] o\[\forall y\ \exists x\ Employee(x) \wedge BelongsTo(x,y)\] Estas son dos cosas muy distintas. Un ser humano se daría cuenta de que es el segundo al que se refiere el hablante, partiendo de toda una gama de experiencias y pistas de sentido común y contexto. Pero un 'bot no tiene disponible ninguno de estos, por lo que exige que el lenguaje exprese de manera clara e inequívoca exactamente lo que se quiere decir.

El inglés está plagado de estas ambigüedades, especialmente involucrando pronombres. “Después de que John golpeó a George se escapó”. ¿Qué pasó? ¿John huyó tras golpear a George, temiendo que George tomara represalias? ¿O George se escapó tras ser golpeado, temiendo abusos adicionales? No está claro a qué se refiere “él”, así que no podemos decir solo desde la oración.

Aquí hay una divertida con la que terminaré. Considera la frase “Él la hizo agacharse”. ¿Qué se pretende aquí? ¿Estiró la mano y empujó con fuerza su cabeza hacia abajo fuera del camino de un proyectil gritando? ¿O preparó un suculento platillo de aves asadas para celebrar su cumpleaños? Oh, si la computadora sólo pudiera saber.

---

1. O bien, si quieres sonar realmente nerd, puedes llamarlo cálculo predicado de primer orden, que es sinónimo.
2. Por cierto, cuando digo se puede dar cualquier insumo en absoluto a un predicado, me refiero a cualquier elemento individual del dominio del discurso. No quiero decir que un conjunto de elementos pueda ser una entrada. Esta limitación es la razón por la que se le llama lógica de predicado de “primer orden”. Si permites que los conjuntos sean entradas a predicados, se llama “lógica de predicados de segundo orden” y puede ser bastante desordenada