El lenguaje de la Lógica Proposicional

Resumen

En este apunte se revisa el lenguaje de la lógica proposicional como un metalenguaje utilizado para obtener expresiones válidas de la lengua base formada por dos símbolos. Se explican las reglas de sintaxis, los conceptos de variables proposicionales y conector, y también se introduce la negación conjunta, el uso de paréntesis y reordenamiento para facilitar la lectura de las expresiones. Además, se mencionan las vocalizaciones de las expresiones de la lógica proposicional. Finalmente, se sintetiza el lenguaje de la lógica proposicional como una herramienta fundamental en la matemática y la lógica, y se reflexiona sobre la posibilidad de encontrar una «lengua base de la base» a partir de la cual podría reconstruirse todo lo demás.

Objetivos de aprendizaje:

Al completar esta sección se espera que el estudiante sea capaz de:

1. Entender el concepto de metalenguaje y su aplicación en la lógica proposicional.
2. Comprender las reglas de sintaxis del lenguaje de la lógica proposicional.
3. Conocer el concepto de variable proposicional y su uso en la construcción de expresiones.
4. Entender el uso del conector y la negación conjunta en el lenguaje de la lógica proposicional.
5. Aprender a usar paréntesis y reordenamiento para facilitar la lectura de las expresiones.
6. Conocer las vocalizaciones de las expresiones de la lógica proposicional.
7. Sintetizar el lenguaje de la lógica proposicional como una herramienta fundamental en la matemática y la lógica.
8. Reflexionar sobre la posibilidad de encontrar una «lengua base de la base» a partir de la cual podría reconstruirse todo lo demás.
9. Aplicar los conceptos aprendidos en la construcción de expresiones de la lógica proposicional.
10. Utilizar el lenguaje de la lógica proposicional para comprender y resolver problemas matemáticos y lógicos.

Índice

EL LENGUAJE DE LA LÓGICA PROPOSICIONAL: ALFABETOS Y CADENAS DE SÍMBOLOS
INICIEMOS CON UN ÚNICO SÍMBOLO
AGREGUEMOS ENTONCES UN SEGUNDO SÍMBOLO
EL LENGUAJE DE LA LÓGICA PROPOSICIONAL: SINTAXIS
EJEMPLOS DE REVISIÓN DE SINTAXIS
CONVENIOS DE NOTACIÓN
METAVARIABLES Y EL CONECTOR \downarrow
EJEMPLOS DEL USO DE LA NEGACIÓN CONJUNTA
REORDENAMIENTO Y PARÉNTESIS
CONECTORES DERIVADOS
VOCALIZACIÓN DE LAS EXPRESIONES DE LA LÓGICA PROPOSICIONAL
SÍNTESIS Y REFLEXIONES SOBRE EL LENGUAJE DE LA LÓGICA PROPOSICIONAL
LA MATRIX DETRÁS DE LA MATRIX DETRÁS DE LA COMPRENSIÓN DE TODAS LAS COSAS

El lenguaje de la Lógica Proposicional: Alfabetos y cadenas de símbolos

Iniciemos con un único símbolo

Para construir El lenguaje de la Lógica Proposicional, iniciaremos nuestro estudio a partir del alfabeto más sencillo: aquél que posee un único símbolo. No importa la figura que tenga, sino el hecho de que es único. Si escribimos usando tal alfabeto, lo único que distingue una cadena de símbolos de otra es la cantidad de veces que tal símbolo es repetido. Por tanto, si tenemos la capacidad de escribir cadenas de símbolos de hasta longitud N, sólo podremos escribir N cadenas diferentes. Como puedes ver, este alfabeto es bastante limitado y no hay mucho más que se pueda decir sobre él.

Agreguemos entonces un segundo símbolo

Si agregamos un segundo símbolo a nuestro alfabeto, la escritura se vuelve más rica que en el alfabeto anterior. Ahora podemos apreciar la forma en que se ordenan los símbolos, por ejemplo si 0 y 1 son nuestros símbolos, podemos distinguir entre 01 y 10. Ambas cadenas involucran los mismos símbolos, pero en distinto orden. Si la cadena más larga que podemos escribir es de longitud N =1,2,3,\cdots, entonces podemos escribir 2^1=2 cadenas de longitud 1, 2^2=4 cadenas de longitud 2, 2^3=8 cadenas de longitud 3, y así en general 2^N cadenas distintas de longitud N.

Ejercicio: Se escriben en una hoja todas las cadenas distintas que es posible escribir con entre 1 y N símbolos. ¿Cuántas cadenas se escriben en total?

Solución:
Si S_N es la suma de todas las cadenas, de longitud 1, 2, 3, y así hasta llegar a N, entonces ya hemos visto que:

\displaystyle S_N=2^1 + 2^2 + \cdots +2^{N-1} + 2^N

Multiplicando por 2 la expresión anterior se tiene:

\displaystyle 2 S_N=2^2 + 2^3 + \cdots + 2^N + 2^{N+1}

Y por lo tanto:

\displaystyle S_N=2 S_N - S_N = 2^N-1

EN consecuencia, la cantidad total de cadenas escritas en la hoja será 2^N-1.

El lenguaje de la Lógica Proposicional: Sintaxis

Hemos visto que, con dos símbolos, podemos distinguir una cadena de otra por su longitud y por el orden en que están dispuestos. Esto es importante porque nos permite definir una sintaxis para el alfabeto que hemos construido. Una sintaxis es un conjunto de reglas que separan las cadenas de símbolos en dos categorías: Expresiones y No-Expresiones. Si \mathcal{L}_2 es el conjunto de todas las cadenas que se pueden construir con los símbolos 0 y 1, entonces la sintaxis de \mathcal{L}_2 es un subconjunto \mathcal{SL}_2\subset\mathcal{L}_2.

Podemos definir el conjunto \mathcal{SL}_2 con las siguientes reglas recursivas:

1. 00, 11 \in \mathcal{SL}_2
2. Si \alpha, \beta \in \mathcal{SL}_2, entonces 01\alpha\beta \in \mathcal{SL}_2

Con estas dos reglas podemos construir expresiones del lenguaje y verificar si una cadena dada es una expresión del lenguaje. Un lenguaje es un alfabeto con una sintaxis asociada. Al lenguaje que se ha presentado aquí le daremos el nombre de «Lengua Base de dos Símbolos», o \mathcal{B}_2.

Ejemplos de revisión de sintaxis

Para hacer de estas ideas algo más fácil de comprender, revisemos los siguientes ejemplos:

Ejemplo: Dado que 0000 y 1111 están contenidos en \mathcal{SL}_2, se tiene que 0100 00 01 0011 01 110000 y 0111111111 están en \mathcal{SL}_2; por lo tanto, son expresiones de \mathcal{B}_2. Esto se demuestra aplicando las reglas que acabamos de introducir.

Fin del ejemplo \blacksquare

Ejercicio: En el ejemplo anterior hemos visto cómo construir expresiones a partir de otras dos expresiones elementales. En si esto no es una tarea complicada; sin embargo, en el proceso inverso, que consiste en demostrar si cierta expresión es o no una expresión, puede que nos encontremos con algo un poco más desafiante.

Determine, utilizando las reglas de sintaxis, si las siguientes cadenas son o no expresiones de \mathcal{B}_2:

1. {}012100

2. 101100

3. {}0100010000

4. 0101000011

5. {}01010000010000

6. 01010010000100101000011

Solución:
Antes de ver la solución te recomiendo que lo intentes primero por tu cuenta y luego compares los resultados. Si ya lo has hecho, entonces adelante 👍

1. 012100.

   Como podemos ver, ésta incluye el símbolo 2, que no está contenido en \mathcal{L}_2; esta cadena no puede estar contenida en \mathcal{SL}_2 y por tanto no es una expresión de \mathcal{B}_2.

2. 101100.

   Aquí se aprecia que esta cadena parte por 10. De las reglas de sintaxis podemos inferir que todas las cadenas de longitud superior a 2 parten, por necesidad, por 01, por lo tanto, no puede ser expresión de \mathcal{B}_2.

3. 0100010000

   Esta cadena parte por 01, por lo que pasa el primer test. De aquí se tiene que, para que sea una expresión de \mathcal{L}_2, es necesario que lo que se marca en azul se pueda descomponer de manera única en dos expresiones.

   0100010000

   Si aun cumpliendo las leyes de sintaxis la descomposición no fuera única, entonces la sintaxis que se ha definido es ambigua y por tanto debe corregirse.
   

   Analizando la parte azul se tienen las siguientes posibles separaciones:

   00010000	00010000	00010000
   00010000	00010000	00010000
   00010000

   En esta parte debemos notar que si la parte dorada no es 0000 0 1111, entonces la parte azul correspondiente debe comenzar por 01 para que la cadena completa sea expresión, entonces es posible hacer los siguientes descartes

   0{}0010000❌	00010000✅	000{}10000❌
   00010000❌	00010000❌	00010000❌
   00010000❌

   Es por esto que la unica separación que sobrevive a este análisis es 00010000, donde la parte dorada es una expresión y la azul se separa de manera única y consistente con la sintaxis. Finalmente, la cadena 0100010000 admite una descomposición única y consistente con la sintaxis, que es 0100010000, y por lo tanto es una expresión del lenguaje \mathcal{B}_2

4. 0101000011

   Para esta cadena podemos hacer la siguiente separación, que demarco con colores:

   010100001111

   Por las reglas de sintaxis, para que una cadena de longitud superior a 2 sea una expresión, es necesario que comience por 01, y luego de esto deben seguir dos expresiones, las que he demarcado en azul y dorado. Es facil ver que esta separación es única, porque si la zona azul o la dorada cambian de longitud, cualquier cambio que éste sea, ya no serán ambas partes una expresión al mismo tiempo.

5. 01010000010000

   Revisando de derecha a izquierda podemos encontrar la siguiente separación:

   \underbrace{01\underbrace{01\overbrace{00}\overbrace{00}}_{{expresión}}\underbrace{01\overbrace{00}\overbrace{00}}_{{expresión}}}_{{expresión}}

6. 01010010000100101000011

   Un ojo agudo notará que esta cadena tiene longitud 23 y que es imposible construir una cadena de longitud impar a través de las leyes de sintaxis de \mathcal{L}_2, que construye expresiones yuxtaponiendo cadenas de longitud par. Todas las cadenas de \mathcal{SL}_2 tienen longitud par, por lo tanto, 01010010000100101000011 no es expresión de \mathcal{B}_2.

Fin del ejercicio \blacksquare

Convenios de Notación

Trabajar con ceros y unos puede ser confuso para nuestra percepción y nos puede hacer cometer errores. Para hacer el proceso más amigable para la forma en que los humanos interpretamos las cosas, podemos usar convenios de notación y algunos metasímbolos.

metavariables y el conector \downarrow

Un metasímbolo es un símbolo utilizado para representar cadenas de símbolos de un lenguaje objetivo. Por ejemplo, cuando se definió la sintaxis \mathcal{SL}_2 de \mathcal{L}_2, se utilizaron los símbolos \alpha y \beta para representar expresiones de \mathcal{B}_2. Estos símbolos reciben el nombre de metavariables de \mathcal{B}_2: metasímbolos que, al ser todos sustituidos por expresiones del lenguaje, generan a través de la sintaxis otra expresión del lenguaje, tal y como lo establece la segunda regla sobre los elementos de \mathcal{SL}_2:

Si \alpha,\beta \in \mathcal{SL}_2, entonces 01\alpha\beta \in\mathcal{SL}_2

Por esta razón, se dice que estas metavariables son metaexpresiones de \mathcal{B}_2.

Para facilitar nuestra escritura en adelante, vamos a utilizar el metasímbolo \downarrow para representar la cadena 01. Este metasímbolo es lo que decimos que es un conector y se conoce como Negación Conjunta por razones semánticas.

Con esto, podemos expresar la sintaxis \mathcal{SL}_2 de manera metalingüística a través de las siguientes reglas recursivas:

1. Todas las metavariables de \mathcal{B}_2 son metaexpresiones \mathcal{B}_2

2. Si \alpha y \beta son metavariables de \mathcal{B}_2, entonces \downarrow\alpha\beta es una metaexpresión \mathcal{B}_2

Con estas reglas podemos escribir metaexpresiones que, cuando se remplazan todas sus metavariables por expresiones y conectores en sy forma representada por ceros y unos, se obtiene una expresión de \mathcal{B}_2. Cada metaexpresión de este tipo hace referencia a una familia infinita de expresiones de \mathcal{B}_2: el conjunto de todas las expresiones de \mathcal{B}_2 que se pueden representar con esa estructura. Esto es justo lo que significa tener un lenguaje formal.

Ejemplos del uso de la negación conjunta

Ejemplo: A partir de la metaexpresión \downarrow\alpha\downarrow\beta\gamma se pueden obtener, a través de remplazos, las siguientes expresiones:

1. Remplazando \alpha := 00, \beta := 011100 y \gamma := 010011

   Se llega a la expresión:

   010001011100010011

2. Si sustituimos \alpha := 011100, \beta := 0111011100 y \gamma := 0111010011

   Se genera:

   010111000101110111000111010011

La metaexpresión \downarrow\alpha\downarrow\beta\gamma no solo es más fácil de asimilar que cualquier otra expresión que satisface su forma, sino aque además representa a todas las expresiones que se pueden obtener a partir de ésta remplazando sus metavariables por expresiones.

Fin del ejemplo \blacksquare

Cuando se remplaza una metavariables, se remplaza en todos los lugares donde ésta aparece

Ejemplo: Consideremos la metaexpresión \downarrow\downarrow\alpha\beta\downarrow\alpha\gamma

1. Si remplazamos \alpha:=11, entonces obtenemos:

   \downarrow\downarrow 11\beta\downarrow 11\gamma

2. Si ahora hacemos \beta:=011100, el resultado será:

   \downarrow\downarrow 11011100\downarrow 11\gamma

3. Y si ahora hacemos el cambio \gamma:=011111, nos quedará:

   \downarrow\downarrow 11011100\downarrow 11011111

4. Finalmente, cambiando \downarrow:=01, concluiremos con esta expresión:

   0101110111000111011111

Fin del ejemplo \blacksquare

Reordenamiento y paréntesis

Verificar que esta es una metaexpresión no resulta especialmente difícil, pero requiere una atención permanente al número de metasímbolos y el alcance del conector \downarrow. Esta dificultad crece rápidamente con el aumento de la longitud de la metaexpresión. Es por esto que es válida la pregunta de si existe alguna forma de representar estas cosas de una manera mas facil de verificar y la respuesta es que si; en efecto, podemos utilizar paréntesis y reordenamientos adecuados para la metaexpresión que se adaptan mejor a nuestra forma natural de agrupar las cosas. Para establecer este punto, revisemos la siguiente metaexpresión:

\downarrow\alpha\downarrow\downarrow\alpha\beta\alpha

Resulta que, aunque no es especialmente difícil corroborar que esto es una metaexpresión, no es algo que podamos hacer sin vernos obligados a contar símbolos sin arriesgarnos a perder la cuenta en el proceso, y el riesgo crece rápidamente a medida que la longitud de la metaexpresión aumenta. ¿Habrá alguna forma representar lo mismo de una manera más cómoda de leer? Lo cierto es que tal método existe y se configura de acuerdo con nuestra forma natural de agrupar las cosas. Para esto se introducen los paréntesis y el reordenamiento a través del siguiente convenio de notación:

\downarrow\alpha\beta:=(\alpha\downarrow\beta)

Ejemplo: Consideremos la metaexpresión \downarrow\alpha\downarrow\downarrow\beta\gamma\delta. Si aplicamos la introducción de paréntesis y el reordenamiento, entonces se transformará de la siguiente manera:

\downarrow\alpha\downarrow\downarrow\beta\gamma\delta	:=	\downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta
\downarrow\alpha\downarrow(\beta\downarrow \gamma)\delta	:=	\downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta)
\downarrow\alpha((\beta\downarrow \gamma)\downarrow\delta)	:=	(\alpha \downarrow((\beta\downarrow \gamma)\downarrow\delta)) ✅

Esta última metaexpresión es mucho más fácil de leer y de revisar que la original, porque cada bloque de paréntesis es una metaexpresión que se compone de elementos fáciles de distinguir: una negación conjunta en el centro y una metaexpresión a cada lado.

Fin del ejemplo \blacksquare

Conectores Derivados

Tanto en la lógica como en el resto de la matemática, existen ciertas combinaciones de conectores que se utilizan de manera frecuente. Es por esto que, para hacer aún más cómoda la escritura (para humanos) se introducen los conectores derivados a través de los siguientes convenios de notación:

Negación:	\neg \alpha	:=	(\alpha\downarrow\alpha)
Disyunción Inclusiva:	(\alpha \vee \beta)	:=	\neg(\alpha\downarrow\beta)
Conjunción:	(\alpha \wedge \beta)	:=	\neg(\neg\alpha\vee \neg\beta)
Implicancia:	(\alpha \rightarrow \beta)	:=	(\neg\alpha\vee \beta)
Doble Implicancia:	(\alpha \leftrightarrow \beta)	:=	((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha))
Disyunción Exclusiva:	(\alpha \veebar \beta)	:=	\neg(\alpha\leftrightarrow \beta)

Este metalenguaje que hemos construido sobre la lengua base de dos símbolos es lo que se conoce como Lenguaje de Orden Cero de la Lógica Proposicional. A través de este lenguaje es que se representan todas las expresiones de la lógica proposicional de manera precisa y libre de ambigüedades.

Vocalización de las expresiones de la lógica proposicional

Aunque no es necesario para hacer lógica, es importante tener en cuenta que nuestra comunicación no se basa solo en símbolos escritos, sino que también tenemos la tendencia natural de vocalizar las cosas en nuestro lenguaje natural. Por eso, para las expresiones del lenguaje de la lógica proposicional existen vocalizaciones que evocan ideas similares a las que tratan sus homólogos en la lógica proposicional. Estas vocalizaciones son las siguientes:

(\alpha \downarrow \beta)	Ni \alpha ni \beta
\neg \alpha	Negación de \alpha
(\alpha \vee \beta)	\alpha o \beta
(\alpha \wedge \beta)	\alpha y \beta
(\alpha \rightarrow \beta)	\alpha implica \beta
(\alpha \leftrightarrow \beta)	\alpha si y sólo si \beta
(\alpha \veebar \beta)	o bien \alpha, o bien \beta, pero no ambos

Síntesis y reflexiones sobre el lenguaje de la lógica proposicional

Con esta última parte finaliza la construcción del lenguaje de la lógica proposicional, que podemos sintetizar como un metalenguaje que permite obtener expresiones válidas en la lengua base de dos símbolos. El lenguaje de la lógica proposicional es un lenguaje formal, ya que define la estructura (o forma) de las expresiones en la lengua base, y cada una de sus expresiones determina la forma de una familia infinita de expresiones en la lengua base. Como mencionamos anteriormente, la sintaxis de un lenguaje formal es extremadamente rígida, pero a cambio es precisa y exacta: no tiene ambigüedad.

La Matrix detrás de la Matrix detrás de la comprensión de todas las cosas

Una última cosa. La lógica proposicional y la matemática se basan en gran medida en la lógica proposicional, que a su vez se construye a partir de una lengua base formada por unos y ceros. ¿Significa que a través de esto hemos llegado a la «Matrix» detrás de la lógica y la matemática? Es posible. Pero también es posible considerar una lengua base para la lengua base, a partir de la cual sería posible reconstruir todo lo demás; sin embargo, para encontrar tal lengua necesitaríamos encontrar nociones aún más fundamentales que los conceptos de orden y cantidad (los que se utilizaron para establecer la primera lengua base). Encontrar una lengua base de la base implica realizar reflexiones sobre los aspectos más fundamentales de lo que significa «entender las cosas». Si profundizas más, si logras llegar al fondo, podríamos decir que has logrado ver «la Matrix detrás de la Matrix detrás de la comprensión de todas las cosas», y es posible que este proceso de fundamentación se pueda seguir realizando al infinito, otorgando una nueva capa de profundidad de conocimiento en cada paso fundacional.

(\alpha \vee \beta)\alpha o \beta(\alpha \wedge \beta)\alpha y \beta(\alpha \rightarrow \beta)\alpha implica \beta(\alpha \leftrightarrow \beta)\alpha si y sólo si \beta(\alpha \veebar \beta)o bien \alpha, o bien \beta, pero no ambos

Síntesis y reflexiones sobre el lenguaje de la lógica proposicional

Con esta última parte finaliza la construcción del lenguaje de la lógica proposicional, que podemos sintetizar como un metalenguaje que permite obtener expresiones válidas en la lengua base de dos símbolos. El lenguaje de la lógica proposicional es un lenguaje formal, ya que define la estructura (o forma) de las expresiones en la lengua base, y cada una de sus expresiones determina la forma de una familia infinita de expresiones en la lengua base. Como mencionamos anteriormente, la sintaxis de un lenguaje formal es extremadamente rígida, pero a cambio es precisa y exacta: no tiene ambigüedad.

La Matrix detrás de la Matrix detrás de la comprensión de todas las cosas

Una última cosa. La lógica proposicional y la matemática se basan en gran medida en la lógica proposicional, que a su vez se construye a partir de una lengua base formada por unos y ceros. ¿Significa que a través de esto hemos llegado a la «Matrix» detrás de la lógica y la matemática? Es posible. Pero también es posible considerar una lengua base para la lengua base, a partir de la cual sería posible reconstruir todo lo demás; sin embargo, para encontrar tal lengua necesitaríamos encontrar nociones aún más fundamentales que los conceptos de orden y cantidad (los que se utilizaron para establecer la primera lengua base). Encontrar una lengua base de la base implica realizar reflexiones sobre los aspectos más fundamentales de lo que significa «entender las cosas». Si profundizas más, si logras llegar al fondo, podríamos decir que has logrado ver «la Matrix detrás de la Matrix detrás de la comprensión de todas las cosas», y es posible que este proceso de fundamentación se pueda seguir realizando al infinito, otorgando una nueva capa de profundidad de conocimiento en cada paso fundacional.