Archivo de la etiqueta: conectores lógicos

Álgebra Superior I: Demostración de condicionales y dobles condicionales

Esta entrada es parte de una serie de notas introductorias sobre técnicas de demostración. Cada una es independiente de la otra, y para su explicación, se usa el siguiente diagrama de un mundo imaginario llamado el mundo de los Blorgs. Para leer más sobre ello, haz click aquí.

Introducción

Para terminar nuestra sección de demostraciones (no significa que terminamos de demostrar, para nada, apenas es el comienzo), vamos a ver el caso en donde tengamos la doble implicación. Esto no va a ser difícil, pues hemos desarrollado suficientes estrategias para ello, y solo verás que la forma de demostrar estas proposiciones, es ver la doble implicación de otra manera.

La suficiencia y necesidad

Es común ver proposiciones matemáticas de la forma

$$\forall x (P(x) \Leftrightarrow Q(x)) $$

Como por ejemplo

Proposición. Un blorg come dos veces a la semana si y solo si tiene amigos amarillos y rojos.

Para este tipo de demostraciones, lo que haremos será demostrar dos cosas: la suficiencia y la necesidad. Recordemos que la doble implicación puede escribirse de la siguiente manera:

$$\forall x (P(x) \Leftrightarrow Q(x)) = \forall x ((P(x) \Rightarrow Q(x)) \land (Q(x) \Rightarrow P(x) )) $$

Es decir, para demostrar la condición, es necesario demostrar que si un blorg come dos veces a la semana entonces tiene amigos amarillos y rojos, y también será necesario mostrar que si un blorg tiene amigos amarillos y rojos come dos veces a la semana. Esto es, demostrar que las condiciones son equivalentes: un blorg solo tiene amigos amarillos y rojos si y solo si come dos veces por semana.

Demostración. Para esto, consideremos primero a un blorg $x$, para demostrar la doble implicación, es común dividir el problema en dos partes que podrás encontrar como «la ida» y «el regreso», esto hace referencia a que al demostrar la ida, demostraras que $P(x) \Rightarrow Q(x)$ y el regreso demuestra que $P(x) \Leftarrow Q(x)$. No dejes que te confunda la dirección de la flecha, simplemente es otra forma de demostrar que $Q(x) \Rightarrow P(x)$ (mira la dirección de la flecha).

Y comúnmente encontrarás en las demostraciones las notaciones de $\Rightarrow$ y $\Leftarrow$ haciendo referencia a si demostrarán la ida o el regreso, justo como lo haremos a continuación.

$\Rightarrow$

Primero demostraremos que si un $x$ come dos veces a la semana, entonces tiene amigos rojos y amarillos.

Como $x$ come dos veces a la semana, entonces es un blurg, pues es la única especie que come los Lunes y Viernes, mientras que los Blargs y Blergs comen solo los Lunes. Ahora, notemos que un blurg es amigo de los Blergs y los Blargs, cuyos respectivos colores son rojos y amarillos. Así hemos demostrado que si un $x$ come dos veces a la semana, entonces tiene amigos rojos y amarillos.

$\Leftarrow$

Ahora, para demostrar el regreso, supongamos que $x$ tiene amigos rojos y amarillos y lleguemos a la conclusión de que come dos veces a la semana.

Notemos a los amigos de cada especie de blorg. Los Blargs son amigos de los Blurgs y de los delfines, los cuales son azules, entonces no tienes amigos amarillos y rojos, por otro lado los Blergs son amigos de los Blurgs, que son azules, por lo que tampoco cumplen la condición. Mientras que los Blurgs son amigos de los Blergs y Blargs, que cumplen con ser rojos y amarillos. Entonces $x$ tiene que se un blurg. A continuación, notemos que los Blurgs comen los Lunes y Viernes, esto es, que comen dos veces por la semana, cumpliendo la proposición.

De esta forma hemos demostrado que un blorg come dos veces a la semana si y solo si tiene amigos amarillos y rojos.

Otro vistazo a la doble implicación

Para que te des una idea mejor sobre el poder de este tipo de proposiciones, recuerda lo siguiente: «La doble implicación es la forma de decir que dos cosas son equivalentes». Esto no es algo nuevo, pues ya hemos mencionado esto antes. La diferencia es que ahora ya tenemos aplicaciones prácticas de esto, ve el siguiente ejemplo:

Proposición. Un blorg come dos veces por semana si y solo si tiene un amigo de otra especie que puede comer fresas.

Demostración. Ahora, no solo vamos a usar la doble implicación para la demostración, sino que juntaremos proposiciones que hemos demostrado anteriormente. Primero que nada, notemos que la proposición se parece en parte a la pasada. Usaremos lo que sabemos de la proposición pasada. Como un blorg come dos veces por semana si y solo si tiene amigos amarillos y rojos. Ahora veamos cómo podemos usarla para demostrar esto.

Considera las proposiciones:

$$ P(x) = \text{ x come dos veces por semana},$$

$$ Q(x) = \text{ x tiene amigos rojos y amarillos},$$

$$ R(x) = \text{ x tiene un amigo de otra especie que puede comer fresas}.$$

Lo que nos pide demostrar la proposición es que

$$\forall x (P(x) \Leftrightarrow R(x)). $$

Pero sabemos que

$$\forall x (P(x) \Leftrightarrow Q(x)). $$

Y notemos que la siguiente regla de inferencia es válida

$$ \begin{array}{rl} & P \Leftrightarrow Q \\ & P \Leftrightarrow R \\ \hline \therefore & Q \Leftrightarrow R\end{array}.$$

Entonces podemos reducir esta proposición a demostrar «Un blorg tiene amigos amarillos y rojos si y solo si uno de sus amigos de otra especie puede comer fresas». Entonces demostremos esto.

Afirmación. Un blorg tiene amigos amarillos y rojos si y solo si uno de sus amigos de otra especie puede comer fresas.

Demostración de la afirmación.

$\Rightarrow$

Sea $y$ un blorg con amigos amarillos y rojos. Basta exhibir a algún amigo que pueda comer fresas, así que ingeniosamente decimos: sea $x$ un amigo rojo de $y$ (esto lo podemos hacer, ya que suponemos que el blorg tiene amigos amarillos y rojos). Como $x$ es rojo, entonces es un blerg. Además, sabemos por una proposición de la entrada anterior que existe una única raza de Blorgs que pueden comer fresas, y son precesiamente los Blergs. De esta manera $x$ puede comer fresas.

Por lo tanto $y$ tiene un amigo que puede comer fresas. Como además tiene amigos de dos colores, y la única especie que puede tener amigos amarillos y rojos son los Blurgs, entonces $y$ es un blurg. Así, $y$ tiene un amigo de otra especie que puede comer fresas.

$\Leftarrow$

Ahora supongamos que $y$ es un blorg y tiene un amigo $x$ de otra especie que puede comer fresas. Como la única especie vegetariana son los Blergs, entonces $x$ es un Blerg (supongamos que esto es cierto por ahora, más adelante lo demostrarás). De esta manera, $y$ es un blarg o blurg (pues recordemos que $x$ y $y$ son de diferentes especies). Veamos que si $y$ fuera un blarg, tendría únicamente amigos Blurgs y delfines, y no de Blergs, mientras que los Blurgs sí son amigos de los Blergs, por lo tanto $y$ es blurg.

Finalmente, nota que los Blurgs tienen amigos Blargs y Blergs, los cuales son amarillos y rojos.

De esta manera, hemos demostrado que un blorg tiene amigos amarillos y rojos si y solo si uno de sus amigos de otra especie puede comer fresas.

$\square$

Habiendo demostrado la afirmación, y sabiendo que $$ \begin{array}{rl} & P \Leftrightarrow Q \\ & P \Leftrightarrow R \\ \hline \therefore & Q \Leftrightarrow R\end{array}.$$ Entonces se cumple que Un blorg come dos veces por semana si y solo si tiene un amigo de otra especie que puede comer fresas.

$\square$

Tarea moral

  1. Prueba que la siguiente regla de inferencia es válida: $$ \begin{array}{rl} & P \Leftrightarrow Q \\ & P \Leftrightarrow R \\ \hline \therefore & Q \Leftrightarrow R\end{array}.$$
  2. Demuestra que un blorg es vegetariano si y solo si es un blerg.
  3. Usando la última proposición de la entrada, demuestra que Un blorg come dos veces por semana si y solo si tiene un amigo que puede comer alimentos con semillas.
  4. Demuestra que un blorg no es amigo de los Blergs si y solo si come los mismos días que los Blergs y es amigo de un animal marino.

Más adelante…

El mundo de los Blorgs nos ayudó a poner un paso dentro del pensamiento matemático. Nos acompañarán solo un poco más, pero ya no estaremos enfocados en las demostraciones. Daremos pasos hacia un camino que puede resultar un poco distinto, pero verás que se parece mucho a la lógica proposicional. Algunos dicen que no puede haber una sin otra. Y este tema es la teoría de conjuntos. Si pudiéramos poner las matemáticas como un edificio, algunos dirían que la estructura estaría hecha de lógica y conjuntos. Así que exploraremos este otro «ingrediente» de las matemáticas.

Entradas relacionadas

  • Ir a Álgebra Superior I
  • Entrada anterior del curso: Problemas de demostraciones con conectores y cuantificadores
  • Siguiente entrada del curso: Problemas de demostraciones de condicionales y dobles condicionales.

Álgebra Superior I: Negaciones de proposiciones con conectores y cuantificadores

Introducción

Ya hemos visto cómo podemos hacer uso de las proposiciones que usan conectores y algunos ejemplos de sus negaciones. Y también ya hemos visto sobre el significado de los cuantificadores así como su uso y ejemplos. Pues en esta entrada haremos uso del conector negación para entender qué significa negar una proposición con conector o cómo son las negaciones de los cuantificadores.

Conectores y su negación

Ya hemos repasado cuatro conectores binarios:

  • Conjunción
  • Disyunción
  • Implicación
  • Doble Implicación

Ahora veamos qué sucede cuando negamos cada uno de estos.

Conjunción y disyunción

Esta es una propiedad que ya visitamos con anterioridad cuando hablamos de la conjunción y disyunción, y que a la negación de estas dos se les conocen como Leyes de Demorgan y nos dicen que la negación de estas corresponden a:

  • $\neg (P \lor Q) = \neg P \land \neg Q$
  • $\neg (P \land Q) = \neg P \lor \neg Q$

Siendo que trabajemos con alguna de estas, solo es necesario recordar: La conjunción se niega con la disyunción y la disyunción se niega con la conjunción.

Implicación

Para ver cómo es que se niega este conector, recordemos su equivalencia lógica: $P \Rightarrow Q = \neg P \lor Q$. Lo siguiente que podemos hacer es aplicar las leyes de Demorgan para encontrar cómo es la negación de esta. Nota que $\neg (P \Rightarrow Q) = \neg(\neg P \lor Q) =P \land \neg Q $. Lo cuál nos quiere decir: «La negación de la implicación es que se cumpla la hipótesis y no la tesis», que es la única forma en que no se cumple la implicación.

Doble implicación

Ahora, recordemos que la doble implicación $P \Leftrightarrow Q$ es una equivalencia lógica a $(P\Rightarrow Q) \land (Q \Rightarrow P)$. De esta manera

$$ \begin{aligned} \neg(P \Leftrightarrow Q) &= \neg((P\Rightarrow Q) \land (Q \Rightarrow P))\\ &=\neg(P\Rightarrow Q) \lor \neg(Q \Rightarrow P) \\ &= (P \land \neg Q) \lor (Q \land \neg P)\end{aligned}$$

Esto es una equivalencia a decir «Las dos proposiciones deben tener valores de verdad distintos». Para que la negación de la doble implicación sea verdadera necesitamos que $P$ sea verdad y $Q$ falsa o $Q$ verdad y $P$ falsa.

Para recapitular esta parte, recuerda la siguiente tabla:

ConectorNegación
$P \lor Q$$\neg P \land \neg Q$
$P \land Q$$\neg P \lor \neg Q$
$P \Rightarrow Q$$P \land \neg Q $
$P \Leftrightarrow Q$$(P \land \neg Q) \lor (Q \land \neg P)$

Negando cuantificadores

Ahora que ya hemos visto sobre las negaciones de los conectores, es turno de que hablemos un poco de los cuantificadores. Y para esto recordemos que un cuantificador nos da información de cómo una proposición con término variable o también conocidas como predicados.

Negación de cuantificadores universales

Observa por un momento el siguiente predicado:

«Todos los números primos son impares»

Esta proposición la podemos ver de la forma $\forall x P(x)$ en el universo de discurso de los número enteros. Y la proposición nos dice que cada número primo que tomemos, será impar. ¿Esto es verdad? Pues resulta que no. Y de hecho el único número primo que no es impar es el 2. En este caso no podemos decir que sea verdad el cuantificador, esto pues existe al menos un número entero que no cumple la proposición. ¿Ves a dónde vamos con las palabras resaltadas?

Para negar el cuantificador $\forall$ usamos el cuantificador $\exists$ diciendo que existe un elemento que no cumple la propiedad:

$\neg(\forall x P(x)) = \exists x \neg P(x)$

Pensemos en el significado de la expresión. Si tenemos el esquema proposicional $\neg(\forall x P(x))$ significa que en el universo de discurso, existe una variable $a$ donde $P(a)$ es falsa, es decir $\neg P(a)$ es verdadera.

Negación de cuantificadores existenciales

Por otro lado, pensemos en el siguiente ejemplo:

«Existe un número entero mayor a 1 y menor a 2»

Para poder decir si es verdad o no, deberíamos ponernos de acuerdo en qué es un número entero o qué significa que sea menor o mayor que otro. Pero nuestra intuición nos dice que esto no es cierto (y estamos en lo correcto al pensar así). Ahora ¿Cómo se te ocurre que podríamos negar la expresión $\exists x P(x)$, donde nuestro universo de discurso son los números enteros y $P(x) : 1<x<2$? Pues necesitaríamos que no exista algún elemento que cumpla la condición, entonces podemos decir:

$\neg (\exists x P(x)) = \nexists x P(x)$

Pero podemos ir un poco más allá, y notar que lo que nos dice esta negación es que cualquier elemento que tomemos de nuestro universo de discurso, no cumplirá con la proposición. Es decir, «Para todo x en el universo de discurso, no se cumplirá el predicado». Dicho de otra forma:

$= \neg (\exists x P(x)) = \forall x \neg (P(x))$

Y por transitividad, ahora sabemos que $\nexists x P(x) = \forall x \neg (P(x))$. Y en nuestro ejemplo significa que «cada número entero no cumplirá que sea menor a 2 y mayor a 1».

Tarea moral

  1. ¿Cuál es la negación de las siguientes proposiciones?
    • $P\lor (Q \Rightarrow S)$
    • $(P \Leftrightarrow (Q\land \neg S))$
    • $P \land (Q\lor R)$
    • $P \Rightarrow(Q \Rightarrow P)$
  2. ¿Cuál es la negación de los siguientes predicados?
    • $\forall x (P(x)\RightarrowQ(x))$
    • $\exists y (\forall x(P(x)\land Q(y)))$

Más adelante…

Llegando a este punto, ya tenemos el conocimiento necesario para hablar de una sustancia muy importante en la matemática: las demostraciones. Esto es, ¿Cómo podemos estar seguros de cuándo algo se cumple y cuándo no? ¿Qué significa que un enunciado se derive de otros enunciados? Y más importante: en lo que a partir de ahora estudiarás en las matemáticas, vamos a introducir algunas técnicas de demostración que te ayudarán a entender de qué estamos hablando en matemáticas cuando haya que verificar algo. Y para esto usaremos algo conocido como reglas de inferencia.

Entradas relacionadas

Álgebra Superior I: Problemas de proposiciones y conectores

Introducción

En esta entrada, presentaremos únicamente problemas resueltos de proposiciones y conectores. Con ayuda de ellos podrás poner en práctica lo visto con anterioridad y entender mejor las propiedades de los conceptos vistos.

Problemas resueltos

Problema 1. ¿Cuáles de los siguientes enunciados son proposiciones?

  • ¿Qué día es hoy?
  • Toda función derivable es continua.
  • ¿El día de hoy lloverá?
  • ¿Cuántos números primos existen?
  • ¡Que gusto verte!
  • Todo espacio vectorial tiene dimensión finita.
  • El libro habla sobre historia universal.

Solución. Veamos cada oración con cuidado.

¿Qué día es hoy?

No es proposición. Esta oración es una pregunta, por lo cuál no puede tener asignado algún valor de verdad, pues no denota información que puede ser cierta o falsa (ojo: al responder la pregunta con por ejemplo «Hoy es lunes» esta respuesta tiene valor de verdad, pues podríamos decir que es lunes o no, pero en sí, la pregunta no tiene un valor de verdad por lo que no es proposición).

Toda función derivable es continua.

es proposición. Independientemente de que sepas qué es una función derivable o qué es una función continua, sabes que esta solo tiene dos opciones: o es cierta o no lo es. Esto es lo que le da el atributo de ser proposición (además es proposición matemática), pues se le puede asignar un valor de verdad.

¿El día de hoy lloverá?

No es proposición. Nuevamente como el primer ejemplo, la pregunta no carga consigo algún valor de verdad, puesto que la pregunta no está afirmando o negando algo, sino está preguntando algo sin decir que será de una u otra manera. Otro caso sería si la oración fuera «El día de hoy lloverá» (¿Notas que ya no tiene signos de interrogación?) que sí es una proposición.

¿Cuántos números primos existen?

No es una proposición. Esto debido a que es una pregunta que no afirma o niega algún hecho.

¡Que gusto verte!

No es una proposición. Esta es una expresión, y no se le puede asignar un valor de verdad. Este tipo de oraciones que denotan expresiones no son proposiciones.

Todo espacio vectorial tiene dimensión finita.

es una proposición. Esta es una proposición matemática la cual puede ser verdadera o falsa, pues afirma que todo espacio vectorial (no es necesario que sepas que es un espacio vectorial) cumple la propiedad de tener dimensión finita (tampoco es necesario que sepas que significa esto). Entonces podemos decir «Es cierto que todo espacio vectorial tiene dimensión finita» o «Es falso que todo espacio vectorial tiene dimensión finita».

El libro habla sobre historia universal.

es una proposición. Observa que para decidir si es verdad o no deberíamos saber de qué libro estamos hablando, pero independientemente de eso, se puede decir que la oración es verdadera o falsa, es decir, se le puede asignar un valor de verdad.

$\square$

Problema 2. ¿Son equivalentes $\neg Q$ y $(\neg P \land Q) \lor \neg Q)$?

Solución. No lo son, para ello, nota que no coinciden en su tabla de verdad. Estamos indicando en verde las columnas de las expresiones que nos interesan.

$P$$Q$$\neg P$ $\neg Q$$\neg P \land Q$$(\neg P \land Q) \lor \neg Q)$
$0$$0$ $1$$1$ $0$  $1$ 
$0$$1$$1$  $0$  $1$ $1$ 
$1$$0$  $0$ $1$  $0$ $1$
$1$$1$  $0$ $0$  $0$   $0$

Esto quiere decir que si $P$ es falso y $Q$ es verdadero,  $\neg Q$ es falso mientras que $(\neg P \land Q) \lor \neg Q)$ es verdadero, por lo que las expresiones no son equivalentes.

$\square$

Problema 3. ¿Cuál de las siguientes expresiones es equivalente a $\neg (P \lor (Q \land R))$?

  • $ P \lor (\neg Q \lor \neg R)$
  • $\neg P \land (\neg Q \lor \neg R)$
  • $\neg P \land (\neg Q \land \neg R)$

Para la que es equivalente, justifica por qué lo es. Para las que no son equivalentes, encuentra valores de verdad de $P$, $Q$ y $R$ que haga que las expresiones sean diferentes.

Solución. Una técnica que podríamos usar son las tablas de verdad, sin embargo sería una tabla grande, pues en principio hay 8 combinaciones para los valores de verdad de $P,Q$ y $R$. Por esta razón, mejor haremos uso de las propiedades de los conectores que ya hemos demostrado.

Primero veamos de qué forma podríamos cambiar la forma en que pensamos a $\neg (P \lor (Q \land R))$. ¿Notas que hay una negación al principio de la proposición? Algo natural sería tratar de «distribuirla», pero recuerda que cuando «distribuimos» la negación, aplicamos las leyes de De Morgan. Entonces,

$$\neg (P \lor (Q \land R)) = \neg P \land \neg(Q \land R) $$

Ahora vamos a fijarnos en $\neg P \land \neg(Q \land R)$. Y vamos a notar que podemos aplicar nuevamente las leyes de De Morgan, ahora para distribuir la negación del segundo paréntesis. Dicho de otra manera,

$$\neg P \land \neg (Q \land R) = \neg P \land (\neg Q \lor \neg R)$$

Nota que para esto, la negación se distribuyó entre $Q$ y $R$. Así, hemos mostrado que

\begin{align*}
\neg (P \lor (Q \land R)) &= \neg P \land \neg(Q \land R), \text{ y que}\\
\neg P \land \neg (Q \land R) &= \neg P \land (\neg Q \lor \neg R).
\end{align*}

Ahora, recordando la propiedad transitiva de la equivalencia, tenemos que

$$\neg (P \lor (Q \land R)) = \neg P \land (\neg Q \lor \neg R)$$

Así, encontramos que la la expresión del inicio es equivalente a la segunda opción. Si quisieras, podrías hacer la tabla de verdad para verificar esto.

Veamos ahora que las otras dos proposiciones no son equivalentes. Para ello, basta encontrar valores de verdad de $P$ y $Q$ para los cuales las expresiones no tengan el mismo valor de verdad.

Primero verificaremos que $ P \lor (\neg Q \lor \neg R)$ no es equivalente a $\neg (P \lor (Q \land R))$. Para ello, nota que $ P \lor (\neg Q \lor \neg R) = P \lor \neg (Q \land R)$ Y esta última es equivalente a $\neg (\neg P \land (Q \land R))$. Ahora nota que si $P$ es verdadero, entonces $\neg (\neg P \land (Q \land R))$ es verdadero, mientras que $\neg (P \lor (Q \land R))$ es falso. Si aún no te queda claro, observa el siguiente renglón de la tabla de verdad:

$P$$Q$$R$$Q \land R$$P \lor (Q \land R)$$\neg (P \lor (Q \land R))$$\neg P$$\neg P \land (Q \land R)$$\neg(\neg P \land (Q \land R))$
$1$$0$$0$$0$$1$$0$$0$$0$$1$

En el párrafo anterior estamos mostrando un caso en donde $P$ es verdadero (observa que en nuestra justificación del párrafo anterior no importa qué valores tienen $Q$ y $R$, pero en este caso observamos la combinación en donde ambos son falsos, eso no afecta el resultado) y las celdas coloreadas (que son aquellas que deseamos comparar) no coinciden. Es decir no pueden ser equivalentes porque existe al menos un caso en donde no coinciden en su tabla de verdad.

De manera similar, para probar que $\neg P \land (\neg Q \land \neg R)$ no es equivalente a $\neg (P \lor (Q \land R))$ daremos un caso en donde no se da la igualdad en las tablas de verdad. Nota que $\neg P \land (\neg Q \land \neg R) = \neg P \land \neg ( Q \lor R)$ y a su vez, $\neg P \land \neg ( Q \lor R) = \neg (P \lor (Q \lor R))$. Ahora veamos el caso particular en la siguienta tabla de verdad:

$P$$Q$$R$$Q \land R$$P \lor (Q \land R)$$\neg (P \lor (Q \land R))$$Q \lor R$$ P \lor (Q \lor R)$$ \neg (P \lor (Q \lor R))$
$0$$1$$0$$0$$0$$1$$1$$1$$0$

Esto termina el problema.

$\square$

¿Cómo le hicimos en la segunda parte para «sacar de la manga» los valores de verdad de $P$, $Q$ y $R$ que nos ayudarían a verificar que las proposiciones no eran equivalentes? La intuición fue la siguiente:

Quisiéramos un caso en que no coincidieran los valores, uno que fuera verdadero y otro falso. Veamos cómo se comporta $\neg (P \lor (Q \land R))$. Para que esta no sea equivalente a la segunda proposición, deberíamos pensar que una es verdadera y la otra falsa. Le asignaremos un valor de verdad a la primera proposición, digamos que es verdadera (entonces la segunda proposición sería falsa), y como hay una negación delante entonces $P \lor (Q \land R)$ debería ser falsa. Pon atención que tenemos un $\lor$ adentro de la expresión, el cuál es falso si las dos proposiciones que conectan son falsas, así que piensa en qué necesitan para ser falsas, y date cuenta que requieren las siguientes dos condiciones:

  • $P$ falsa
  • $Q$ o $R$ falsa

A fuerza, $P$ debe ser falsa, así que no le movemos más.

Por otro lado, vamos a ver cómo se comporta $ \neg (P \lor (Q \lor R))$. Recuerda que pensamos en un caso en que no coincidan las proposiciones, y si quedamos en que la primera proposición era verdadera, entonces esta es falsa, lo cual haría a $P \lor (Q \lor R)$ verdadera. Además también dijimos que $P$ es falsa, entonces para que toda la proposición sea verdadera, tendremos que hacer que $Q \lor R$ sea verdadera. Alguna de estas dos es falsa (también era una condición que establecimos para la veracidad de la primera proposición), digamos que $R$ es la falsa, entonces $Q$ es verdadera. De esta manera obtuvimos el ejemplo que hacía las proposiciones diferir en alguna combinación de valores de verdad.

Tarea moral

  1. Completa la tabla de verdad para verificar que $\neg (\neg P \land (Q \land R))$ no es equivalente a $\neg (P \lor (Q \land R))$. Observa cómo en todas los renglones en donde $P$ es verdadero, $\neg (\neg P \land (Q \land R))$ es distinto a $\neg (P \lor (Q \land R))$.
  2. Completa la tabla de verdad de$ \neg (P \lor (Q \lor R))$ junto a $\neg (P \lor (Q \land R))$. ¿Existen otros casos en donde sus valores de verdad sean distintos?

Entradas relacionadas

Álgebra Superior I: Propiedades de la negación, conjunción y disyunción

Introducción

En la entrada pasada vimos que con conectores podemos construir nuevas proposiciones a partir de otras. Y nombramos a tres de ellas: la negación, la conjunción y la disyunción.

Ahora, discutiremos sobre algunas consecuencias que tiene juntar unas con otras y diremos en términos formales qué significa que una proposición sea «igual» a otra.

Equivalencia de proposiciones

Volvamos a retomar un ejemplo que ya habíamos revisado anteriormente.

$P$$\neg P$$\neg(\neg P)$
$0$$1$ $0$
$1$$0$$1$ 

Habíamos dicho que al coincidir las columnas de $\neg ( \neg P)$ con $P$ entonces $\neg(\neg P) = P$. Esto leeremos como «$\neg(\neg P)$ es equivalente a $P$». La equivalencia de proposiciones nos dice que sus valores de verdad siempre coinciden. En este ejemplo, en cualquier caso en que $\neg(\neg P)$ sea verdad, sucede que $P$ es verdad. De igual forma, cada vez que suceda que $\neg(\neg P)$ sea falso, $P$ también lo será.

Podemos dar un ejemplo más concreto. Pensemos en que nuestra proposición $P$ es: «El 2 es un número impar». En este caso $\neg(\neg P)$ corresponde a: «No es cierto que 2 no es un número impar». Si la proposición $P$ es verdadera, entonces la equivalencia nos diría que $\neg(\neg P)$ también lo es. Es decir, si es verdadero que 2 es un número impar, entonces también es verdadero que «No es cierto que 2 no es un número impar». Aunque nosotros sepamos que 2 es un número par (y por ende la proposición $P$ es falsa), una persona que no tuviera el conocimiento de este hecho pero que sepa lógica, podría saber que si $P$ es verdadero $\neg(\neg P)$ también es verdadero. O si $\neg(\neg P)$ es verdadero, $P$ también es verdadero.

Ahora, nota que acabamos de hacer una definición, pues nombramos a dos proposiciones que tienen la misma tabla de verdad como equivalentes. Como lo mencionamos en la entrada de los tipos de enunciados, les estamos poniendo un nombre a un objeto matemático que cumple ciertas propiedades.

Definición. Dos proposiciones $P$ y $Q$ son equivalentes si sus tablas de verdad coinciden y lo escribiremos como $P=Q$.

Esta «igualdad» en las proposiciones nos será muy útil, pues en la matemática nos ayudará a ver algunos resultados de otra manera. Por ejemplo, retomemos $\neg(\neg P) = P$. Como sabemos que es falso que 2 es impar, en consecuencia también sabemos que es falso que «No sea cierto que 2 no es impar» y esto lo sabemos sin tener que verificar algo más, pues el hecho de que sean equivalentes, basta saber que una sea verdad para que la otra sea verdad, o que una sea falsa para que la otra también lo sea. Esta equivalencia también nos ayudará a demostrar otros resultados en el futuro.

Nota además que si $P$ y $Q$ son equivalentes, y $Q$ y $R$ son equivalentes (es decir $P=Q$, $Q=R$) entonces $P$ y $R$ también son equivalentes. Puedes convencerte de esto como sigue. Del hecho de que $P$ y $Q$ lo sean, sale que $P$ y $Q$ tienen la misma tabla de verdad. Del hecho de que $Q$ y $R$ lo sean, sale que $Q$ y $R$ tienen la misma tabla de verdad. Pero entonces $P$ y $R$ tienen la misma tabla de verdad (la de $Q$). A esto se le conoce como la propiedad transitiva. No es importante que recuerdes este nombre, sin embargo después volveremos a estudiar esta propiedad con más calma. Y para recordar mejor esto, piensa en que funciona similar a la igualdad entre números, por ejemplo $2+2=4$ y $4=2^2$, entonces $2+2=2^2$.

Algunas propiedades de la conjunción y la disyunción

Hemos hablado un poco sobre la negación, pero ahora cambiemos el foco a la conjunción y la disyunción. Para empezar, recordemos que la conjunción $P\land Q$ solo es verdadera cuando tanto $P$ como $Q$ son verdaderas, y en la entrada anterior verificamos que $Q \land P$ es equivalente a $P \land Q$.

También nos va a interesar el caso en donde combinamos más de dos proposiciones. Sin embargo, hay que tener cuidado. Por definición, la conjunción es un conector que combina únicamente dos proposición. Así, para unir a más de dos proposiciones mediante la conjunción, tendremos que agruparlas.

Piensa el agrupamiento como piensas la suma: si quieres sumar $2+3+4$, lo más habitual es sumar primero $2+3$ que resulta en cinco, y después sumárselo a $4$, de manera que podemos escribir la suma como $2+3+4=(2+3)+4$. Algo similar va a pasar con las proposiciones, pues podemos pensar a $P \land Q \land R$ como $(P \land Q) \land R$. Ahora piensa de nuevo en la suma $2+3+4$. El resultado de esta suma es $9$ y nosotros decidimos agrupar $2+3$ y después sumar el resultado con $4$. Pero esto es lo mismo que haber agrupado primero $3+4$ y después sumarlo a $2$. Esto no es coincidencia, pues la suma tiene una propiedad que se llama asociatividad que nos dice que $(2+3)+4=2+(3+4)$. ¿Pasará lo mismo con la conjunción? Veamos que sí.

Lo que queremos ver si $P \land (Q \land R)=(P \land Q) \land R$ es decir, queremos ver si $P \land (Q \land R)$ es equivalente a $(P \land Q) \land R$. La equivalencia está dada en términos de tablas de verdad, así que tenemos que hacer las tablas para ambas proposiciones. La presentamos a continuación.

$P$$Q$$R$$Q \land R$$P \land ( Q\land R)$$P \land Q$$(P \land Q) \land R$
$0$$0$$0$$0$$0$$0$$0$
$0$$0$$1$$0$$0$$0$$0$
$0$$1$$0$$0$$0$$0$$0$
$0$$1$$1$$1$$0$$0$$0$
$1$$0$$0$$0$$0$$0$$0$
$1$$0$$1$$0$$0$$0$$0$
$1$$1$$0$$0$$0$$1$$0$
$1$$1$$1$$1$$1$$1$$1$

Como puedes notar, las columnas $P \land (Q \land R)$ y $(P \land Q) \land R$ coinciden, es decir, coinciden en sus tablas de verdad, por lo tanto son equivalentes.

Con este ejemplo, vimos cómo la conjunción tiene la propiedad asociativa, es decir, cuando combinamos tres o más proposiciones mediante la conjunción, no importa «dónde pongamos los paréntesis». Lo mismo pasará con la disyunción que de igual manera es asociativa.

Combinando la conjunción con la disyunción

También podemos juntar los conectores de conjunción y disyunción. Porejemplo, piensa que tenemos tres proposiciones $P, Q, R$ donde,

$P = \text{Toda persona es mortal}$

$Q = \text{2 es un número impar}$

$R = \text{2 es un número par}$

¿Qué significaría la proposición $P \lor (Q \land R)$? Si lo escribieramos en palabras, sería «Toda persona es mortal o 2 es un número par e impar a la vez». Sabemos que toda persona es mortal, y también sabemos que 2 no puede ser impar y par a la vez (por ahora parece que sabemos que 2 es un número par, en otros cursos profundizarás más en lo que significa ser par). Entonces nuestra proposición está formada por dos componentes, la proposición $P$ y la proposición $Q \land R$. Como un número no puede ser par e impar a la vez, entonces la segunda proposición es falsa. Pero la primera proposición $P$ es verdadera, entonces la proposición $P \lor (Q \land R)$ es verdadera, porque para la disyunción solo basta que alguna de las dos sea verdadera.

Vayamos un poco más lejos. ¿Será que esta es la única forma de escribir la proposición? Resulta que no. Esta proposición tiene una propiedad que se llama la propiedad distributiva para los conectores de conjunción y disyunción, la cual nos dice que $$P \lor (Q \land R) = (P \lor Q) \land (P \lor R).$$

Si te resulta un poco confuso esto, puedes pensarlo por ahora como la distribución de una multiplicación con la suma, es decir la operación $2 \times (1+3) = (2 \times 1) + (2 \times 3)$, en donde nuestra disyunción $\lor$ junta a $P$ con $Q$ y a $P$ con $R$ y la conjunción $\land$ los distribuye.

Para convencernos de que se satisface la propiedad distributiva, veamos las tablas de verdad de cada una de las expresiones que están involucradas.

$P$$Q$$R$$Q \land R$$P \lor ( Q\land R)$$P \lor Q$$P \lor R$$(P \lor Q) \land (P \lor R)$
$0$$0$$0$$0$$0$$0$$0$$0$
$0$$0$$1$$0$$0$$0$$1$$0$
$0$$1$$0$$0$$0$$1$$0$$0$
$0$$1$$1$$1$$1$$1$$1$$1$
$1$$0$$0$$0$$1$$1$$1$$1$
$1$$0$$1$$0$$1$$1$$1$$1$
$1$$1$$0$$0$$1$$1$$1$$1$
$1$$1$$1$$1$$1$$1$$1$$1$

Nota que las columnas coloreadas corresponden a las proposiciones y son iguales, entonces $P \lor (Q \land R) = (P \lor Q) \land (P \lor R)$. Lo mismo sucede si cambiamos el orden de los conectores, es decir $P \land (Q \lor R) = (P \land Q) \lor (P \land R)$, así podemos distribuir los conectores conjuntivos y disyuntivos como más nos convenga.

Agregando la negación a la mezcla

Por último, vamos a incluir a la negación en nuestra mezcla de conjunciones y disyunciones. ¿Qué pasará cuando tenemos proposiciones del estilo $\neg (P \land Q)$ y $\neg (P \lor Q)$? Sería lógico pensar en un inicio que igual la negación se va a distribuir, pero eso no es cierto. Para esto, piensa en el siguiente ejemplo:

$$P = \text{32 es un número perfecto} $$

$$ Q = 2^7-1 \text{ es un número primo} $$

Aquí hablamos de dos cosas que quizá aún no sepas: números perfectos y números primos, no te preocupes por lo que signifiquen, en otros cursos los verás con más detalle, aunque te puedo decir que solo una de estas dos afirmaciones es correcta (¿Puedes adivinar cuál es?), entonces la conjunción es falsa, por lo que la negación de la conjunción es verdadera.

Lo que acabamos de decir es que $P \land Q$ es falsa y por consecuente $\neg (P \land Q)$ es verdadera. Si sucediera que la negación fuera distributiva, entonces $\neg (P \land Q)$ sería equivalente a $\neg P \land \neg Q$. Pero esto no es cierto, porque $\neg P$ es verdadero, y $\neg Q$ es falso, y entonces $\neg P \land \neg Q$ es falso. Acabamos de llegar a una contradicción en nuestro pensar matemático es decir, primero dijimos que $\neg (P \land Q)$ es verdadera y después observamos que si la negación se distribuyera, sería falso, pero recuerda que una proposición es verdadera o falsa, no puede ser verdadera y falsa al mismo tiempo, entonces alguna de las dos suposiciones que hicimos es incorrecta. Si quieres pensarlo de otra forma, $\neg P \land \neg Q$ y $\neg (P \land Q)$ no son equivalentes pues sus tablas de verdad difieren en el renglón en el que $P$ es verdadero y $Q$ es falso.

Nuestro error fue haber distribuido la negación sin cuidado. Resulta que la negación no cumple esa propiedad, pero «casi» es distributiva. Veamos sus reglas.

$$ \neg (P \land Q) = \neg P \lor \neg Q $$

$$ \neg (P \lor Q) = \neg P \land \neg Q $$

En el ejemplo concreto de arriba, esto quiere decir que es lo mismo decir «No es cierto que (32 sea un número perfecto y $2^7-1$ sea un número primo)» a decir «No es cierto que 32 es un número perfecto, o no es cierto que $2^7-1$ es un número primo». Para que lo entiendas más claro, revisa la tabla de verdad:

$P$$Q$$P \land Q$$\neg (P \land Q)$$\neg P$$\neg Q$$\neg P \lor \neg Q$
$0$$0$$0$$1$$1$$1$$1$
$0$$1$$0$$1$$1$$0$$1$
$1$$0$$0$$1$$0$$1$$1$
$1$$1$$1$$0$$0$$0$$0$

Observa que las columnas correspondientes a las expresiones que queremos coinciden, lo que quiere decir que son equivalentes. Lo mismo puedes verificar para comprobar que $ \neg (P \lor Q) = \neg P \land \neg Q $. A estas propiedades se les conoce como las leyes de De Morgan (más adelante volverás a oír ese nombre).

Tarea Moral

  1. Demuestra que $\neg ( \neg (\neg P))$ es equivalente a $\neg P$.
  2. En la entrada vimos que podemos asociar la conjunción como queramos. Ahora verifica que lo mismo pasa con la disyunción, es decir $P \lor (Q \lor R) = (P \lor Q) \lor R$.
  3. Verifica con la tabla de verdad que $P \land (Q \lor R) = (P \land Q) \lor (P \land R)$.
  4. Verifica con la tabla de verdad que $ \neg (P \lor Q) = \neg P \land \neg Q $.

Más adelante…

Recapitulando, en esta entrada hablamos sobre las propiedades que tienen tres conectores. Vimos lo siguiente:

  • Hablamos de la equivalencia de proposiciones que ocurre cuando dos proposiciones coinciden en su tabla de verdad.
  • Observamos tres propiedades de los conectores: la asociatividad, la distributividad y las leyes de DeMorgan.

Todo esto nos da herramienta suficiente para ya empezar a hablar de lógica proposicional, pero esto apenas empieza. Recuerda que tenemos más conectores. Aún nos faltan revisar dos muy importantes: la implicación y la doble implicación. Estos dos las vamos a ver con más calma en la siguiente entrada.

Entradas relacionadas