3.2: Lógica Proposicional
- Page ID
- 118456
La lógica proposicional estudia cómo la verdad o falsedad de los enunciados compuestos está determinada por la verdad o falsedad de los enunciados constitutivos. Nos da una manera de derivar de manera confiable conclusiones verdaderas a partir de verdaderas suposiciones.
Si\(P\) es una declaración que es verdadera, entonces\(P\) tiene valor de verdad 1. Si\(P\) es una declaración que es falsa,\(P\) tiene valor de verdad 0. Escribimos\(T(P)\) para el valor de verdad de\(P\).
Los valores de la verdad pueden pensarse como una función\(T: S \rightarrow\ulcorner 2\urcorner\), donde\(S\) está el conjunto de todas las afirmaciones. Al investigar los principios abstractos de la lógica proposicional, consideramos posibles asignaciones de valores de verdad a variables que representan declaraciones. Nos interesan las afirmaciones que son independientes de cualquier asignación particular de valores de verdad a las variables proposicionales. Usamos los enteros 0 y 1 para representar valores de verdad porque nos permite usar operaciones aritméticas en lógica proposicional. Otros autores prefieren\(F\) y\(T\).
Los símbolos\(\wedge, \vee, \neg\) y\(\Rightarrow\) son conectivos proposicionales. Se definen de la siguiente manera para declaraciones\(P\) y\(Q\).
| Conectivo | Nombre | Definición |
|---|---|---|
| \(\neg\) | negación | \(T(\neg P)=1-T(P)\) |
| \(\hat{\vee}\) | conjunción | \(T(P \wedge Q)=T(P) \cdot T(Q)\) |
| \(\Rightarrow\) | disyunción | \(T(P \vee Q)=T(P)+T(Q)-T(P) \cdot T(Q)\) |
| \(\Rightarrow\) | implicación | \(T(P \Rightarrow Q)=1-T(P)+T(P) \cdot T(Q)\) |
En la expresión "\(P \Rightarrow Q\)“, el enunciado\(P\) se denomina antecedente o hipótesis y\(Q\) se denomina la consecuencia o conclusión.
Los conectivos proposicionales son equivalentes formales de los conectivos del lenguaje natural.
| Conectivo | Equivalente a Lenguaje Natural |
|---|---|
| \(\neg\) | no |
| \(\wedge\) | y |
| \(\vee\) | o |
| \(\Rightarrow\) | implica |
Comprueba que las fórmulas que definen los conectivos proposicionales dan el significado que esperas. Por ejemplo, comprobar que la definición del valor de verdad para\(P \wedge Q\) significa que\(P \wedge Q\) es cierto si y sólo si ambos\(P\) y\(Q\) son verdaderos.
Los conectivos proposicionales se aproximan a las conectivas del lenguaje natural. Los conectivos proposicionales son formales y precisos, mientras que los conectivos del lenguaje natural son imprecisos y algo más expresivos; en consecuencia, la aproximación es imperfecta. Vimos un ejemplo de esto al contrastar el uso de los matemáticos del “o” conectivo con su uso en el lenguaje cotidiano. Para mayor precisión en matemáticas interpretamos los conectivos formalmente, incluso cuando se utilizan expresiones de lenguaje natural.
Podemos construir declaraciones compuestas muy complicadas mediante el uso de conectivos lógicos. Naturalmente, existen reglas para construir declaraciones correctas con conectivos.
Una declaración atómica es una declaración sin conectivos proposicionales explícitos.
Una declaración atómica suele estar representada por una letra mayúscula.
Definimos una declaración proposicional bien formada recursivamente de la siguiente manera.
Las declaraciones atómicas están bien formadas.
Si\(P\) y\(Q\) son declaraciones bien formadas, entonces las siguientes son declaraciones bien formadas:
-
\((\neg P)\)
-
\((P \wedge Q)\)
-
\((P \vee Q)\)
-
\((P \Rightarrow Q)\). En la práctica se dejan caer los paréntesis a menos que exista la posibilidad de ambigüedad. Adicionalmente, “[” y “]” pueden sustituirse por paréntesis en aras de la legibilidad. Para cualquier asignación de valores de verdad a las declaraciones atómicas en una declaración bien formada, la declaración compuesta tendrá un valor de verdad bien definido.
Una declaración compuesta es una declaración bien formada compuesta por declaraciones atómicas y conectivos proposicionales.
3.2.1. Equivalencia proposicional.
Un propósito de la lógica proposicional es dar herramientas para evaluar la verdad de una declaración compuesta sin necesariamente tener que entender el significado específico de las declaraciones atómicas. Es decir, algunas afirmaciones son demostrablemente verdaderas o falsas en virtud de su forma. En este entendimiento es central la idea de equivalencia proposicional.
Dejar\(P\) y\(Q\) ser declaraciones bien formadas construidas a partir de declaraciones atómicas. Decimos eso\(P\) y\(Q\) son proposicionalmente equivalentes siempre que\(T(P)=T(Q)\) para cualquier asignación de valores de verdad a las declaraciones atómicas constitutivas.
Si\(P\) y\(Q\) son proposicionalmente equivalentes, podemos escribir el\[P \equiv Q .\] EJEMPLO 3.1. \[[P \Rightarrow Q] \equiv[(\neg Q) \Rightarrow(\neg P)]\]Este es un ejemplo muy importante de una equivalencia proposicional. Demostraremos esto considerando todas las posibles asignaciones de valores de verdad a\(P\) y\(Q\). Vamos a poner esto en lo que popularmente se llama una tabla de la verdad. Consideramos todas las asignaciones posibles de valores de verdad a\(P\) y\(Q\), y comparamos los valores de verdad de las afirmaciones compuestas bajo consideración:
\(\begin{array}{cccc}\frac{T(P)}{0} & \frac{T(Q)}{0} & \frac{T(P \Rightarrow Q)}{1} & \frac{T((\neg Q) \Rightarrow(\neg(P)))}{1} \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1\end{array}\)
Cada fila de la tabla de verdad representa una asignación particular de valores de verdad a las declaraciones atómicas\(P\) y\(Q\). Las cuatro asignaciones posibles se agotan por las filas de la tabla de la verdad. Los valores de verdad de las declaraciones compuestas coinciden en cada fila de la tabla de verdad por lo que las declaraciones son equivalentes.
\[\begin{aligned} &{[\neg(P \wedge Q)] \equiv[(\neg P) \vee(\neg Q)]} \\ &{[\neg(P \vee Q)] \equiv[(\neg P) \wedge(\neg Q)]} \end{aligned}\]Las declaraciones (3.3) y (3.4) se conocen como leyes de Morgan. (¿Cómo se relacionan con el Ejercicio 1.2?)
Con dos posibles excepciones, una vez que estudies cuidadosamente lo que significan estas conectivas, debes entenderlas intuitivamente. Una excepción es que el lógico y matemático “o”,\(\vee\), es inclusivo. Esto lo discutimos al inicio del Capítulo 2. La otra excepción es el conectivo lógico "\(\Rightarrow\)”.
3.2.2. Implicación.
A los estudiantes a menudo les resulta confuso que la implicación\(P \Rightarrow Q\) pueda ser cierta cuando la consecuencia,\(Q\), es falsa. Esto es comprensible cuando consideramos que las implicaciones suelen emplearse en argumento en el siguiente silogismo:\[\begin{gathered} P \\ P \Rightarrow Q \end{gathered}\] por lo tanto, (es decir, si\(P\) es verdad, y\(P \Rightarrow Q\), entonces\(Q\) es verdad). Este silogismo es la regla más importante de deducción lógica (llamada Modus Ponens). La implicación lógica se utiliza tan a menudo para demostrar la verdad de la consecuencia que es fácil entender por qué uno podría pensar erróneamente que la consecuencia debe seguir de la implicación, en lugar de seguir del antecedente. Considera la siguiente declaración:
Si eres el rey de Francia, entonces yo soy el tío de un mono.
¿Es cierta esta afirmación? Presumiblemente no eres el rey de Francia, y no creo que sea tío de mono. Entonces tanto el antecedente como la consecuencia son falsos. Sin embargo la afirmación es cierta. De hecho, esta afirmación es lógicamente equivalente a la afirmación:
Si no soy tío de mono, entonces tú no eres el rey de Francia.
La definición de implicación lógica dice que una implicación en la que el antecedente es falso no da información sobre la consecuencia. De ahí que cualquier implicación lógica con el antecedente “Tú eres el rey de Francia” será cierta.
Existe una preocupación adicional con implicación lógica. En el lenguaje natural (e intuitivamente en matemáticas), la afirmación\[P \Rightarrow Q\] sugiere una relación entre las afirmaciones\(P\) y\(Q\) -es decir, que la verdad de\(P\) alguna manera obliga a la verdad de\(Q\). Como conectivo proposicional, esta relación entre\(P\) y no\(Q\) es necesaria para la implicación lógica. La verdad de\(P \Rightarrow Q\) es una función de los valores de verdad de\(P\) y\(Q\), no de sus significados. En la escritura matemática, se entiende que no sólo es lógicamente cierta la implicación, sino que\(P\) y\(Q\) están relacionados y que la verdad de\(P\) hecho obliga a la verdad de\(Q\). Por ejemplo, considere la afirmación\[\mathbb{N} \subset \mathbb{Q} \Rightarrow 3>2 .\] Esta afirmación es cierta por la definición formal de\(\Rightarrow\). De hecho, como declaración proposicional, podríamos sustituir el antecedente por cualquier otra afirmación, verdadera o falsa, y la declaración condicional sería verdadera. No obstante, tal afirmación es matemáticamente inaceptable, ya que el antecedente y la consecuencia no tienen nada que ver entre sí. No nos preocupan los valores de verdad accidentales de las declaraciones atómicas, sino las conexiones matemáticas entre estas afirmaciones, que cumplen, pero van más allá, de la definición formal de las conectivas lógicas.
3.2.3. Converse y Contrapositivo.
La mayoría de las afirmaciones matemáticas tienen la forma de una implicación. Por lo tanto, es necesario estar familiarizado con la nomenclatura convencional que rodea la implicación lógica. Supongamos que nos interesa una implicación lógica particular,\[P \Rightarrow Q \text {. }\] Hay otras dos implicaciones lógicas con las que naturalmente se asocian\(P \Rightarrow Q\). Uno es el contrapositivo,\[\neg Q \Rightarrow \neg P .\] Una implicación y sus contrapositivos son proposicionalmente equivalentes.
La declaración,
“Si esto es un insecto entonces tiene seis patas”.
es proposicionalmente equivalente a la declaración
“Si esto no tiene seis patas, no es un insecto”.
El contrapositivo de
“Una ballena es un pez”
es
“Si no es un pez entonces no es una ballena”.
Este último ejemplo ilustra que una declaración no necesita ser cierta para tener un contrapositivo (que es, por supuesto, todavía proposicionalmente equivalente a la declaración condicional original). También ilustra que las declaraciones condicionales en lenguaje natural no necesitan incluir la palabra “si” o “entonces”, ni ser escritas en una forma particular, para ser una declaración condicional. Lo contrario de una declaración condicional,\[P \Rightarrow Q\] es la declaración condicional,\[Q \Rightarrow P .\] Una declaración condicional y su converse no son proposicionalmente equivalentes. Puedes comprobarlo fácilmente\(P \Rightarrow Q\) y\(Q \Rightarrow P\) tener diferentes valores de verdad si\(T(P)=1\) y\(T(Q)=0\).
¿Qué es lo contrario a la declaración?
¿"Todos los peces viven en el agua”?
Dado que esto está escrito en lenguaje natural, no hay una respuesta única.
Un obvio contrario es
“Si algo vive en el agua, entonces es un pez”.
Si armamos una implicación y su contrario, obtenemos el conectivo bicondicional.
Dejar\(P\) y\(Q\) ser declaraciones. El bicondicional, escrito\(\Longleftrightarrow\), se define de la siguiente manera.
| Conectivo | Nombre | Definición |
|---|---|---|
| \(\Longleftrightarrow\) | bicondicional | \(T(P \Longleftrightarrow Q)=T(P \Rightarrow Q) \cdot T(Q \Rightarrow P)\) |
El conectivo bicondicional es la interpretación formal de “si y solo si”. Esta frase es tan utilizada en matemáticas que tiene su propia abreviatura: iff.
Otras palabras del lenguaje natural que pueden traducirse en conectivos proposicionales son “necesarias” y “suficientes”. El comunicado
“\(P\)Para que pueda sostenerse, es necesario que\(Q\) sostenga” equivale a\(P \Rightarrow Q\). El comunicado
“\(P\)Para que pueda sostenerse, basta con que\(Q\) sostenga”
es equivalente a\(Q \Rightarrow P\). Combinando estos dos, conseguimos que la afirmación “\(P\)Para poder sostener, es necesario y suficiente que\(Q\) sostiene” es equivalente a\(P \Longleftrightarrow Q\).