Lógica de proposiciones

Introducción

Daremos una breve descripción de los principios fundamentales que están detrás del razonamiento matemático. Si quieres revisar, de manera más profunda, la lógica de proposiciones se recomienda (Mendelson, 2015) y (Enderton, 2021).

La principal diferencia entre las matemáticas de bachillerato y las de la facultad es que en la facultad debemos justificar las afirmaciones que hacemos. Para lograrlo hay que empezar desde el principio, una forma de definir conceptos matemáticos que nos permitan razonar de manera adecuada. Por ejemplo, debemos hacer una definición formal de qué es la suma en los naturales; además, nuestra definición debe ser suficientemente buena como para poder mostrar que satisface las propiedades conocidas: es conmutativa, asociativa, etc.

Después de que se han definido los conceptos que se estudiarán, se debe manipular a los objetos para obtener los resultados que ya conocemos, o algún resultado nuevo. La manipulación de objetos debe hacerse de manera correcta y ordenada. Las reglas que garantizan esto se reúnen en una teoría llamada lógica matemática.

Proposiciones

Una forma intuitiva de entender qué es una proposición es una expresión (matemática) que puede ser juzgada de verdadera o falsa. Aunque esto no es una definición formal, nos permite distinguir qué expresiones sí son proposiciones. Por ejemplo, \(1+1=1\) sí es una proposición, pero \(x\) no lo es. Algo que resalta con el ejemplo de proposición es que su verdad o falsedad depende del lugar donde se mire. En los números enteros la proposición \(1+1=1\) es falsa, mientras que las proposiciones definirán una estructura en la cual \(1+1=1\) es verdadera. Luego, hay proposiciones más complejas; por ejemplo, hoy es lunes y está lloviendo, no es cierto que hoy haya tomado café, etc. Así, tenemos que empezar con un conjunto de proposiciones “básicas” y construir el resto usando conectivos.

Definición

Sea \(\mathbb{P}\) un conjunto. Las fórmulas proposiciones de tipo \(\mathbb{P}\) están dadas por lo siguiente:

1. si \(P\in\mathbb{P}\), entonces \(P\) es una fórmula,
2. si \(\alpha\) y \(\beta\) son fórmulas, entonces
   • \(\alpha\land\beta\),
   • \(\alpha\lor\beta\), \(\neg\alpha\), \(\alpha\to\beta\) y \(\alpha\leftrightarrow\beta\) son fórmulas,
3. si \(\gamma\) es una proposición, entonces se obtuvo mediante aplicar una cantidad finita de veces los puntos 1 y 2.

El conjunto \(\mathbb{P}\) es el conjunto de letras proposicionales. El conjunto de fórmulas proposicionales será denotado \(\mathsf{Prop}\).

El uso que daremos a las fórmulas será, principalmente, como método de demostración. Sin embargo, no toda proposición dará un método de demostración válido. Así, necesitamos evaluar que fórmulas sí sirven para este fin. En otras palabras necesitamos decir cuando una proposición es verdadera.

Definición

Dada una asignación \(\text{v}\colon\mathbb{P}\to\{0,1\}\) se define una evaluación (de verdad) para el conjunto de fórmulas como una función \(\text{ev}\colon\mathsf{Prop}\to\{0,1\}\) tal que:

1. \(\text{ev}(\alpha\land\beta)=\text{ev}(\alpha)\cdot\text{ev}(\beta)\),
2. \(\text{ev}(\alpha\lor\beta)=\text{ev}(\alpha)+\text{ev}(\beta)-\text{ev}(\alpha)\cdot\text{ev}(\beta)\),
3. \(\text{ev}(\neg\alpha)=1-\text{ev}(\alpha)\),
4. \(\text{ev}(\alpha\to\beta)=\text{ev}(\neg\alpha\vee\beta)\),
5. \(\text{ev}(\alpha\leftrightarrow\beta)=\text{ev}(\alpha\to\beta)\cdot\text{ev}(\beta\to\alpha)\).

Con la definición anterior se hace explícito que el valor de verdad de una fórmula depende del contexto. Esto es, para alguna asignación \(\text{v}\) es posible que \(\alpha\) sea verdadera, i.e., \(\text{ev}(\alpha)=1\) y que para alguna otra \(\text{v'}\) se tenga que \(\alpha\) es falsa, \(\text{ev}'(\alpha)=0\).

Hay muchas formas equivalentes de definir el valor de verdad de las fórmulas, es decir, dada \(\text{v}\colon\mathbb{P}\to\{0,1\}\), podríamos definir \(\text{ev}\) dando expresiones diferentes que den el mismo resultado en cada caso. Por ejemplo,

Proposición

Sea \(\text{v}\colon\mathbb{P}\to\{0,1\}\) una valuación. Una forma equivalente de definir \(\text{ev}\colon\mathsf{Prop}\to\{0,1\}\) es:

1. \(\text{ev}(\alpha\land\beta)=\text{mín}\{\text{ev}(\alpha),\text{ev}(\beta),\}\),
2. \(\text{ev}(\neg\alpha)=1\) si y sólo si \(\text{ev}(\alpha)=0\),
3. \(\text{ev}(\alpha\lor\beta)=\text{máx}\{\text{ev}(\alpha),\text{ev}(\beta),\}\),

Los puntos 4 y 5 quedan igual.

Como toda fórmula \(\alpha\) está formada a partir de proposiciones \(P,Q,R,\ldots\in\mathsf{P}\) y una aplicación finita de conectivos, entonces sólo puede tener una cantidad finita de letras proposicionales. Así, su valor de verdad sólo debería depender del valor de esa cantidad finita de letras proposicionales que se usan para formar \(\alpha\).

Proposición

Sean \(P_1,\ldots,P_n\) las letras proposicionales que ocurren en \(\alpha\). Si \(\text{ev},\text{ev}'\colon\mathsf{Prop}\to\{0,1\}\) satisfacen \(\text{ev}(P_i)=\text{ev'}(P_i)\) para toda \(i=1,\ldots,n\), entonces \(\text{ev}(\alpha)=\text{ev}'(\alpha)\).

Demostración

La demostración es por inducción sobre la formación de \(\alpha\). La base de inducción es cuando \(\alpha=P\). En este caso tenemos, por hipótesis,

\[\text{ev}(\alpha)=\text{ev}(P)=\text{ev}'(P)=\text{ev}'(\alpha).\]

Luego, supongamos que \(\alpha\) y \(\beta\) satisfacen el enunciado de la proposición y veamos que las fórmulas más complejas, como fueron definidas en la definición de fórmula, también lo satisfacen.

Como las letras proposicionales que ocurren en \(\neg\alpha\) son las mismas que las que ocurren en \(\alpha\), entonces

\[\text{ev}(\neg\alpha)=1-\text{ev}(\alpha)=1-\text{ev}'(\alpha)=\text{ev}'(\neg\alpha).\]

Para la conjunción \(\alpha\land\beta\) notemos que si \(\text{ev}\) y \(\text{ev}'\) coinciden en las letras proposicionales que aparecen en \(\alpha\land\beta\), entonces coinciden en las letras proposicionales que ocurren en \(\alpha\) y en las que ocurren en \(\beta\). Así, podemos aplicar la hipótesis de inducción para concluir \(\text{ev}(\alpha)=\text{ev}'(\alpha)\) y \(\text{ev}(\beta)=\text{ev}'(\beta)\). Con esto es fácil ver, por la definición de evaluación en una conjunción, que

\[\text{ev}(\alpha\land\beta)=\text{mín}\{\text{ev}(\alpha),\text{ev}(\beta)\}=\text{mín}\{\text{ev}'(\alpha),\text{ev}'(\beta)\}=\text{ev}'(\alpha\land\beta).\]

El resto de los conectivos se hace de manera análoga

Gracias a esta proposición es posible calcular el valor de verdad de \(\alpha\) en todos los posibles contextos con una tabla finita, que usualmente se llama tabla de verdad. Para hacer la tabla de verdad de una fórmula se debe desde las letras proposicionales, pasando por las subfórmulas, hasta llegar a la fórmula que nos interesa. Por ejemplo, para hacer la tabla de \((P\lor Q)\to(P\land Q)\) hacemos lo siguiente:

\[\begin{array}{c|c|c|c|c} P & Q & P\lor Q & P\land Q & (P\lor Q)\to(P\land Q)\\ \hline 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 \end{array}\]

Las tablas de verdad son un algoritmo que nos permite encontrar fácilmente todos los posibles valores de una proposición. Ahora que podemos hacer eso de manera simple, podemos dar nombre a fórmulas especiales y a relaciones entre ellas.

Definición

Sea \(\alpha\) una fórmula. Diremos que \(\alpha\) es una tautología si para cualquier \(\text{ev}\colon\mathsf{Prop}\to\{0,1\}\) se cumple \(\text{ev}(\alpha)=1\). Si para cualquier \(\text{ev}\colon\mathsf{Prop}\to\{0,1\}\) se satisface \(\text{ev}(\alpha)=0\), entonces \(\alpha\) es una contradicción. Finalmente, diremos que \(\alpha\) es contingente si no es ni tautología ni contradicción.

Además de estas nociones, podemos notar que en la definición de evaluación se cumple que \(\text{ev}(\alpha\land\beta)\leq\text{ev}(\alpha)\). También, por definición, \(\text{ev}(\alpha\to\beta)=\text{ev}(\neg\alpha\lor\beta)\). Estas relaciones tienen los siguientes nombres:

Definición

Sean \(\alpha,\beta\in\mathsf{Prop}\). Decimos que \(\beta\) es consecuencia lógica de \(\alpha\), en símbolos \(\alpha\models\beta\), si para cualquier evaluación \(\text{ev}\colon\mathsf{Prop}\to\{0,1\}\) se satisface \(\text{ev}(\alpha)\leq\text{ev}(\beta)\). Además, \(\alpha\) es lógicamente equivalente a \(\beta\), denotado \(\alpha\equiv\beta\), si \(\text{ev}(\alpha)=\text{ev}(\beta)\).

Una forma equivalente de decir que \(\beta\) es consecuencia lógica de \(\alpha\) es que si \(\text{ev}(\alpha)=1\) entonces \(\text{ev}(\beta)=1\). Además, en la definición de consecuencia lógica es posible tomar un conjunto de fórmulas \(\Gamma\subseteq\mathsf{Prop}\) y decir que \(\beta\) es consecuencia lógica de \(\Gamma\) si para cualquier evaluación se satisface: si \(\text{ev}(\alpha)=1\), para toda \(\alpha\in\Gamma\), entonces \(\text{ev}(\beta)=1\). La notación es \(\Gamma\models\beta\).

Las fórmulas que nos interesan como métodos de demostración son las tautologías, ya que sin importar el contexto son válidas, es decir, son un razonamiento correcto. Además, una demostración en matemáticas es una argumentación que justifica la validez de algo a partir de ciertas hipótesis. Ahora podemos formalizar cuando un argumento es válido.

Un argumento es una sucesión de fórmulas \(\alpha_1,\ldots,\alpha_n,\beta\), donde \(\alpha_1,\ldots,\alpha_n\) son las hipótesis del argumento y \(\beta\) es la conclusión. Con la notación anterior, un argumento es válido si \(\{\alpha_1,\ldots,\alpha_n\}\models\beta\).

Puedes encontrar una lista de tautologías aquí. Se usó el asistente de pruebas L∃∀N para verificar que las fórmulas son, en efecto, tautologías.