Archivo de la etiqueta: cuantificadores

Teoría de los Conjuntos I: Repaso sobre el lenguaje de la Teoría de los Conjuntos

Introducción

Se entiende por un conjunto a la agrupación en un todo de objetos bien diferenciados de nuestra intuición o nuestra mente.

Georg Cantor

Para iniciar tu aventura en la Teoría de Conjuntos es importante hacer una breve introducción al lenguaje que utiliza está misma. Profundizaremos en la definición que dio Cantor sobre un conjunto. Podremos entender que es una colección de objetos a los que podemos describir con una propiedad, más aún, está propiedad no debe ser ambigua pues es necesario poder decidir si un elemento forma parte o no del conjunto.

Un poco de lógica

Antes de navegar por la teoría de conjuntos, haremos una pequeña pero importante parada por otra de las ramas de la matemática: la lógica. Dado que en las matemáticas siempre estamos buscando la verdad de las cosas, necesitamos definir cuando un enunciado es verdadero o falso.

Definición: Una proposición es un enunciado al que podemos asignarle un único valor de verdad, ya sea verdadero o falso. A las proposiciones las denotaremos con letras: $P_1, P_2,\cdots P_n, P, Q, …, p, q, p_1, p_2, …, p_n$.

Ejemplos:

Si «$P_1= 2$ es un número par», diremos que la proposición $P_1$ es verdadera pues sabemos que $2$ en efecto es un número par.

Si «$P_2= 4$ es primo», diremos que $P_2$ es una proposición falsa.

$\square$

Una vez definido el concepto de proposición vamos a hablar acerca de conectivos lógicos y sus tablas de verdad.

Conectivos lógicos

Negación: Sea $P$ una proposición. Definimos la negación de $P$ como el enunciado: «no es cierto $P$» y lo denotamos como $\neg P$.

Dado que $P$ solo puede tomar un valor de verdad: verdadero o falso. Si $P$ es verdadero, entonces $\neg P$ es falso. Si $P$ es falso entonces $\neg P$ es verdadero. Veamos su tabla de verdad:

$P$$\neg P$
VF
FV

A continuación definiremos conectivos para dos o más proposiciones las cuales se llamaran compuestas. Si la tabla de verdad de una proposición compuesta tiene solo valores verdaderos diremos que se trata de una tautología.

Conjunción: Sean $P$ y $Q$ proposiciones. Definimos la conjunción de $P$ y $Q$ como el enunciado: «$P$ y $Q$» y lo denotamos por $P\land Q$. En este caso, $P\land Q$ es verdadero si y solo si tanto $P$ como $Q$ son verdaderos, veamos su tabla de verdad:

$P$$Q$$P\land Q$
VVV
VFF
FVF
FFF

Luego, la negación de la conjunción $\neg(P\land Q)$ es equivalente a $\neg P \vee \neg Q$ pues $\neg(P \land Q)\leftrightarrow (\neg P\vee \neg Q)$ es una tautología y lo denotamos como sigue: $\neg(P \land Q)\equiv (\neg P\vee \neg Q)$. Observemos la tabla de verdad:

$P$$Q$$\neg(P\land Q)$$\neg P \vee \neg Q $
VVFVF
VFVVV
FVVVV
FFVVV

Disyunción: Sean $P$ y $Q$ proposiciones. Definimos a la disyunción de $P$ con $Q$ como el enunciado: «$P$ o $Q$» y lo denotamos por $P\vee Q$. En este caso, $P\vee Q$ es verdadero si y solo si al menos una de las proposiciones $P$ o $Q$ es verdadera, veamos su tabla de verdad:

$P$$Q$$P\vee Q$
VVV
VFV
FFV
FFF

La negación de la disyunción $\neg(P\vee Q)$ es equivalente a $\neg P \land \neg Q$. Observemos la tabla de verdad:

$P$$Q$$\neg(P\vee Q)$$\leftrightarrow$$\neg P\land \neg Q$
VVFVF
VFFVF
FVFVF
FFVVV

Implicación: Sean $P$ y $Q$ proposiciones. Definimos a la implicación como el enunciado «$P$ implica $Q$» y lo denotamos por $P\rightarrow Q$. En este caso, «$P\rightarrow Q$» es verdadero si y solo si tanto $P$ como $Q$ son verdaderos, o bien $P$ es falso. Veamos su tabla de verdad:

$P$$Q$$P\rightarrow Q$
VVV
VFF
FVV
FFV

Podemos verificar que $\neg(P\rightarrow Q)\equiv (P\land \neg Q)$.

Bicondicional: Sean $P$ y $Q$ proposiciones. Definimos a la bicondicional de $P$ y $Q$ como el enunciado: «$P$ si y sólo si $Q$» y lo denotamos por «$P\leftrightarrow Q$». En este caso, $P \leftrightarrow Q$ es verdadero si y solo si $P$ y $Q$ tienen el mismo valor de verdad. Veamos su tabla de verdad:

$P$$Q$$P \leftrightarrow Q$
VVV
VFF
FVF
FFV

Podemos verificar que $\neg(P\leftrightarrow Q)\equiv (P\land \neg Q)\vee(Q\land \neg P)$.

Cuantificador universal y existencial

Ahora que hemos recordado los conectivos lógicos y sus tablas de verdad, podemos familiarizarnos con cuantificadores y sus negaciones. Para ello definamos primero lo siguiente:

Definición: Un predicado es un enunciado con una variable $x$ tal que al sustituirla se obtiene un proposición. La denotamos como $P(x)$.

Ejemplos:

  1. $P(x)= x+2=5$. Es claro que $x+2=5$ no es una proposición pues si no sabemos el valor de $x$ no podremos decir cual es su valor de verdad, sin embargo, que pasaría si a $x$ le damos el valor de $3$, entonces $x+2=3+2=5$ es verdadero y por lo tanto, una proposición.
  2. Si $Q(x)=x$ es par, sólo si definimos que valores toma $x$ sabremos si $Q(x)$ es verdadero o falso.

$\square$

Ahora que hemos definido que es un predicado, podemos hablar acerca de los cuantificadores: universal y existencial.

Definición: Sea $P(x)$ un predicado, definimos «$\exists x P(x)$» como el cuantificador existencial y se interpreta como «existe x tal que $P(x)$». La manera en que vamos a negar $\exists x P(x)$» es la siguiente: $\neg(\exists x P(x))\equiv \forall x(\neg(P(x))$».

Definición: Sea $P(x)$ un predicado, definimos «$\forall x P(x)$» como el cuantificador universal y se interpreta como «para cualquier x, $P(x)$». La manera en que vamos a negar $\forall x P(x)$» es la siguiente: $\neg(\forall x P(x))\equiv \exists x(\neg(P(x))$».

Ahora que tenemos las definiciones necesarias de lógica, comenzaremos a recordar la noción de pertenecer a un conjunto.

Elementos y pertenencia

Si tenemos que $A$ es un conjunto, para decir que un objeto es parte del conjunto utilizaremos la notación $x\in A$, que puede leerse como «$x$ es elemento de $A$» o «$x$ pertenece a $A$».

Por ejemplo, si $B=\set{1,2,3}$ podemos decir lo siguiente:

  • $1\in B$
  • $2\in B$
  • $3\in B$

Esto porque tanto $1,2$ y $3$ están dentro del conjunto $B$. Así mismo podemos decidir si un objeto forma parte de $B$ o no, si quisiera saber si $5\in B$ la respuesta que daremos será que no, la manera en que vamos a denotar la no pertenencia es la siguiente: $5\notin B$. En general, si un elemento no forma parte de un conjunto $A$ diremos que $x\notin A$ ($x$ no pertenece a $A$).

Contención e igualdad

Ahora que ya sabemos diferenciar cuando un elemento pertenece o no a un conjunto, podemos ver si un conjunto es subconjunto de otro. Sean $A$ y $B$ conjuntos, decimos que $A\subseteq B$ si y sólo si $\forall x(x\in A\rightarrow x\in B)$. De modo que tendremos que $A\not\subseteq B$ si y sólo si $\exists x(x\in A$ y $x\notin B)$.

Ejemplo:

Sean $A=\set{a,b,c,d}$ y $B=\set{a,b,c,d,e,f}$. Decimos que $A\subseteq B$ pues cada elemento de $A$ es elemento de $B$. Sin embargo, $B$ no es subconjunto de $A$ pues podemos exhibir un elemento que está en $B$ pero no está en $A$, el elemento que nos funciona en este ejemplo es $e$ ya que $e\in B$ y $e\notin A$. Seguro estarás notando que existe más de un elemento ($f$ también funciona) que hace que $B\not\subseteq A$, pero basta con exhibir uno solo pues de este modo se satisface la definición.

Tarea Moral

  • Demuestra que si $p$ y $q$ son proposiciones, entonces $p\rightarrow q$ es equivalente a $\neg q\rightarrow \neg p$.
  • Demuestra que $\neg(p\rightarrow q)\equiv (p\land \neg q)$ y $\neg(p\leftrightarrow q)\equiv [(p\land \neg q)\vee (q\land \neg p )]$
  • Sea $B=\set{a,b,c,\set{a,b}}. Di si las siguientes afirmaciones son verdaderas o falsas:

a) $a\in B$,

b) $\set{a,b} \in B$,

c) $\set{b,c} \in B$.

  • Si $A= \set{1,2,3}$, di quienes son los elementos de $A$ y además da todos los subconjuntos de $A$.
  • Demuestra que si $A$ es un conjunto cualquiera, entonces $A\subseteq A$.

Más adelante…

En la siguiente entrada podrás encontrar contenido referente a la definición de conjunto y los primeros axiomas de Zermelo-Fraenkel para la Teoría de los Conjuntos, ahí tendrás que tener algunos conocimientos acerca de lógica para entender la notación que usaremos en adelante. Sin embargo ya hemos sentado las bases necesarios en esta entrada.

Otros enlaces:

Los siguientes enlaces te servirán para revisar con mejor detalle el tema

Álgebra Superior I: Demostración de proposiciones con cuantificadores

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

En esta entrada revisaremos más a fondo cómo es que los cuantificadores que repasamos antes se usan dentro de las proposiciones y cómo demostrar estas. Veremos ejemplos con estos y algunos ejemplos famosos.

Los cuantificadores en las demostraciones

Ya hemos trabajado antes con los cuantificadores, aunque quizá no lo hayas notado, ya hemos trabajado con ellos. Por ejemplo, cuando hicimos la demostración de «Los Blorgs amarillos comen peces», lo que hicimos fue considerar cualquier blorg amarillo e hicimos una serie de pasos lógicos para demostrarlo. En ningún lugar dice que solo algunos Blorgs amarillos comen peces, en general dice que Los Blorgs amarillos comen peces, es decir todos los Blorgs amarillos cumplen la condición de comer peces. ¿La palabra resaltada te recuerda algo? Pues regresando a lo que antes vimos como los cuantificadores, recordarás que usabamos algunos cuantificadores para hacer énfasis en cómo eran las proposiciones. Pues, por ejemplo si consideramos el universo de discurso de los Blorgs y decimos $P(x) = \text{ x come los viernes}$, sería incorrecto:

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

Pues los únicos que comen los viernes son los Blurgs. En cambio existe al menos una especie que come esos días, así que sería correcto decir:

$$\exists x P(x), $$

ya que si $x$ es un blurg, entonces $P(x)$ es verdadero.

Así que podríamos demostrar la siguiente afirmación:

Proposición. Existen Blorgs que comen los viernes.

Demostración. Para ello, notemos que un blorg puede ser blarg, blerg y blurgs. A continuación vamos a considerar a $x$ un blorg que es blurg (podemos hacer esto, pues dentro del «conjunto» de los Blorgs, hay Blurgs). Y como sabemos, todos los Blurgs comen los Lunes y Viernes. En particular, comen los viernes, por lo que hemos demostrado la proposición.

$\square$

Diferencias entre cuantificadores

Vamos a detenernos y analizar cómo se diferenció la última demostración con lo que hemos estado haciendo antes. Analiza la demostración anterior con la siguiente:

Proposición. Los Blorgs comen un día antes de los Martes.

Demostración. Consideremos $x$ un blorg. Como es un blorg puede que sea un blarg, blerg o blurg.

Caso 1. $x$ es un blarg.

Como $x$ es blarg, entonces come los Lunes, que resulta ser un día antes de los Martes.

Caso 2. $x$ es un blerg.

Igual que en el caso anterior, si $x$ es blerg, entonces come los días antes de los Martes.

Caso 3. $x$ es un blurg.

Sabemos que los Blurgs comen los Lunes y los Viernes. Si $x$ es un blurg, entonces en particular come los lunes, y así, come los días antes de los Martes.

En cualquiera de los casos, $x$ cumple la proposición.

$\square$

Esta es una demostración que bien pudimos haber escrito como «Todos los Blorgs comen los días antes de los Martes». Sin embargo, en la práctica no es muy común ver escrito explícitamente la palabra «todos/todas», pues al hablar de «Los Blorgs», se infiere que hablamos de todos los Blorgs. Así podemos hacer notar las siguientes diferencias entre las dos demostraciones, la primera en donde usamos el cuantificador existe y en la que usamos todos.

Existen Blorgs que comen los viernes.(todos) Los Blorgs comen un día antes de los Martes.
Se puede reescribir como
$$\exists x P(x) $$
Se puede reescribir como
$$\forall x P(x) $$
Consideramos un blorg «mañoso». Es decir, dentro del «conjunto» de los Blorgs, consideramos a uno estratégicamente que nos ayudara a demostrar que al menos un blorg cumplía la condición, en este caso un blurg. Consideramos un blorg arbitrario (tuvimos que considerar distintos casos en los que el blorg fuera blarg, blerg o blurg)
Exhibimos el ejemplo de un blorg, que comía los viernes. Y con eso demostramso que la proposición se cumplía.Llegamos a la conclusión de que sin importar cómo fuera el blorg, comía un dia antes de los Martes.

Esto nos quiere decir que cuando estemos hablando del cuantificador $\exists$, no necesitamos generalizar el caso, solo necesitamos exhibir un ejemplo donde la proposición se cumpla. Mientras que cuando hablamos de $\forall$, tenemos que generalizar, es decir, tenemos que considerar todos los casos posibles para probar que una afirmación sea verdadera o no.

Tratando con la unicidad.

Vamos a ver ahora un pequeño mapa de cómo viven los Blorgs en el mundo Blorg:

Este mapa muestra cómo se dividen los Blorgs, así que cuando estuvimos haciendo la demostración de existencia de los Blorgs que comen los Viernes, elegimos alguno de estos:

Mientras que cuando hablamos de $\forall$, tuvimos que comprobar que se cumplía para cualquiera de los Blorgs, ya fueran Blergs, Blargs o Blurgs. Pero aún falta otro cuantificador, que es el $\exists !$.

Ahora lee la siguiente proposición:

Proposición. Existe una única raza de Blorgs que dentro de su dieta puede haber fresas.

Nota que ahora no estamos hablando de los Blorgs como criaturas, sino de sus especies, y solo existen tres especies de blorg: Blargs, Blergs y Blurgs. Es decir, nos piden demostrar que entre estas tres, solo existe una que come fresas.

Nuestra proposición no nos habla de los Blorgs como criaturas individuales, sino que ahora nos habla de las especies de los Blorgs. Nota que ahora la flecha señala a las especies (círculos).

Entonces para demostrar que se cumple la proposición, tendremos que primero exhibir una especie que coma fresas y después demostrar que es única.

Demostración. Solo existen tres especies de Blorgs, notemos que dentro de estas, se encuentran los Blergs que comen frutos, por lo que son los Blergs quienes pueden incluir fresas en sus dietas.

(Hasta aquí hemos probado que existe una especie que puede comer fresas)

Ahora, para demostrar que es única, veamos que las otras dos razas solo comen peces, los cuales evidentemente no pueden incluir las fresas, por tanto esta especie es única.

(Así demostramos la unicidad)

$\square$

Esta es una proposición que se puede escribir como

$$\exists ! x P(x) $$

Entonces para demostrar el cuantificador $\exists ! x P(x)$, primero debemos demostrar $\exists x P(x)$ y después que es única. Nota que demostrar la unicidad, equivale a demostrar lo siguiente:

$$\exists! x P(x) = \exists x (P(x) \land \forall y \neq x (\neg P(y))) $$

Es decir «Existe $x$ que cumple $P(x)$ y todo elemento $y$ distinto a $x$, no cumple $P(y)$»

En nuestra demostración la primera parte antes del primer paréntesis, demostramos que existe $x$ (Blergs) que cumple $P(x)$. Mientras que en la segunda parte mostramos que todo elemento $y$ distinto a $x$(Blargs y Blurgs) , no cumple $P(y)$. Para la segunda parte, vimos que si $y$ no eran los Blergs, entonces no podían comer fresas.

Nos saltamos un conector, que es el $\nexists$, para demostrar estos casos, es suficiente notar que

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

Por ejemplo, para demostrar que «No existen especies de Blorgs que coman los miércoles», solo basta demostrar que todas las especies de Blorgs no comen los miércoles.

Algunos ejemplos de demostraciones con los cuantificadores que utilizan

A continuación mostramos algunos ejemplos de proposiciones y de qué cuantificador hablan ayudados de su escritura como lógica proposicional. No es necesario que entiendas a qué se refiere cada uno, pero sus cuantificadores.

ProposiciónProposición en lógica proposicional
: Para todo $a$ número real, $a \leq |a|$ y $-a \leq |a|$Sea $P(a)$ = $a \leq |a|$ y $-a \leq |a|$:
$$\forall a \text{ número real } P(a)$$
El neutro aditivo es único en los números reales.Sea $P(x)$ = $x$ es neutro aditivo:
$$\exists ! x \text{ número real } P(x)$$
Para todo binomio con coeficientes reales (es de la forma $ax^2+b^x+c$ donde $a,b,c$ son números reales), existe solución compleja. *Sea $P(p,x)$ = $p$ tiene solución compleja $x$:
$$\forall p \text{ binomio con coeficientes reales } \exists x (P(p,x)) $$

Notas

*: Esta es una consecuencia de algo que se conoce como el «Teorema fundamental del álgebra», que se usa en un segundo curso de álgebra superior (la continuación de este curso). Solo se utiliza, más no se demuestra, la herramienta necesaria para su demostración, normalmente se puede ver en cursos de hasta el tercer año de una licenciatura en matemáticas.

Tarea moral

  1. Demuestra que existen Blorgs que no viven dentro del agua.
  2. Demuestra que todos los Blorgs comen al menos una vez a la semana.
  3. Demuestra que existe una única especie de Blorgs que habla con animales con aletas.
  4. Demuestra que no existe una especie de Blorgs que coman los miércoles.

Más adelante…

Antes de terminar de estudiar estas «formas» de demostrar, vamos a terminar viendo el último conector que intencionalmente nos saltamos, este es la «doble implicación», y hay un motivo para ello, pues comúnmente te vas a encontrar este tipo de demostraciones y verás la técnica que se empleará.

Entradas relacionadas

Á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 condicionales y cuantificadores

Introducción

En esta entrada resolveremos problemas de temas vistos en entradas anteriores. Haremos algunos ejemplos relacionados con los conectores condicionales que vimos en una entrada anterior: la implicación y la doble implicación. También veremos algunos de cuantificadores lógicos.

Problemas resueltos

Problema. Si $P$ y $R$ son verdaderas y $Q$ es falsa, di si la siguiente proposición es verdadera o falsa: $$(P \lor R) \Rightarrow \neg(Q \land R).$$

Solución. Haremos una tabla de verdad pero únicamente con los valores que nos dan, es decir, no vamos a hacer la tabla para todos los casos, sino únicamente los que nos interesan en este momento:

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

Por lo tanto la proposición es verdadera para los valores de verdad dados.

$\square$

Problema. Di si las siguientes proposiciones sobre los números enteros son verdaderas o no:

  1. $(3+1=4) \Rightarrow (0<10)$
  2. $(4=5) \Leftrightarrow (9+1=10)$
  3. $((6<7) \lor (3^2=10)) \Rightarrow (12<12^2)$
  4. $((-1<1) \land (1<-1)) \Leftrightarrow ((13-1=12-1+1)\Rightarrow (1+1<2))$

Solución.

Vamos a hacer algunas verificaciones sobre cada una de las proposiciones para encontrar su valor de verdad:

  • $(3+1=4) \Rightarrow (0<10)$

Como $3+1=4$ es verdadera y $0<10$ es verdadera también, entonces la proposición es verdadera.

  • $(4=5) \Leftrightarrow (9+1=10)$

Recordemos que la doble condicional es verdadera si ambas proposiciones tienen el mismo valor de verdad. Por un lado no es cierto que $4=5$ mientras que sí es verdad que $9+1=10$. Por lo tanto la proposición es falsa.

  • $((6<7) \lor (3^2=10)) \Rightarrow (12<12^2)$

Vamos a ver la proposición por partes. Primero veamos que $((6<7) \lor (3^2=10))$ es una disyunción verdadera pues una de las proposiciones que la componen, $6<7$, lo es. Como $12<12^2$ es verdad, entonces la implicación tiene antecedente y subsecuente verdaderos y por lo tanto es verdadera.

  • $((-1<1) \land (1<-1)) \Leftrightarrow ((13-1=12-1+1)\Rightarrow (1+1<2))$

De nuevo vamos a dividir la proposición en sus partes, $(-1<1) \land (1<-1)$ y $(13-1=12-1+1)\Rightarrow (1+1<2)$. Primero notemos que $(-1<1) \land (1<-1)$ es falsa, pues no es cierto que $1<-1$.

Ahora, veamos cómo es $(13-1=12-1+1)\Rightarrow (1+1<2)$. Nota que $12=13-1$ y $12=12-1+1$, entonces $13-1=12-1+1$. Entonces esta primera parte es verdad, mientras que $1+1=2$ pero no es cierto que $2<2$. Así que es falso que $1+1<2$. Entonces $(13-1=12-1+1)\Rightarrow (1+1<2)$ es falso.

Como $(-1<1) \land (1<-1)$, $(13-1=12-1+1)\Rightarrow (1+1<2)$ son ambas falsas, entonces $((-1<1) \land (1<-1)) \Leftrightarrow ((13-1=12-1+1)\Rightarrow (1+1<2))$ es verdadero.

Nota: En este tipo de ejercicios, ¿viste cómo se dieron las argumentaciones de las proposiciones en cada caso? El secreto aquí fue «desarmar» las proposiciones en partes más pequeñas. Esto lo hacemos pues recuerda que los conectores son binarios, esto significa que su valor de verdad depende del valor de verdad de las dos proposiciones que conectan.

Así, para ver cuál es el valor de verdad de $((6<7) \lor (3^2=10)) \Rightarrow (12<12^2)$, lo que hicimos fue deshacerlo en sus partes. Una parte $A$ fue $(6<7) \lor (3^2=10)$ y la otra parte $B$ fue $12<12^2$. Entonces bastaba con verificar cuáles eran los valores de verdad de $A$ y $B$. Para ello, volvimos a «desarmar» a $A$ en sus partes «atómicas». Es decir, desarmamos $(6<7) \lor (3^2=10)$ en $6<7$ y $3^2=10$ y estudiamos el valor de verdad de cada uno de ellos. Usualmente este tipo de pensamiento de «desarmar un problema en sus partes» te ayudará a verificar o demostrar cosas más adelante.

Problema. Sean $P(x)$, $Q(x)$ y $R(x)$ los siguientes predicados:

  • $P(x): x \leq 4$
  • $Q(x): x +1$ es par.
  • $R(x): x> 0$

Si nuestro universo de discurso son los números enteros, ¿cuáles son los valores de verdad de las siguientes proposiciones?

  1. $P(1)$
  2. $P(1) \Rightarrow Q(1)$
  3. $P(0) \Rightarrow (R(5) \Rightarrow Q(0))$
  4. $R(-1) \lor P(2)$
  5. $\neg R(-2) \lor P(-2)$

Solución.

1.$P(1)$

Es verdadera, pues $1 \leq 4$.

2. $P(1) \Rightarrow Q(1)$

Como $P(1)$ es verdadera y además $1+1=2$ es par, entonces la proposición es verdadera.

3. $P(0) \Rightarrow (R(5) \Rightarrow Q(0))$

Vamos a dividir la proposición en partes. Primero notemos que $P(0)$ es verdad. Mientras que $R(5) \Rightarrow Q(0)$ es falsa, ya que es cierto que $5>0$ pero es falso que $0+1$ sea par. Entonces la proposición es falsa.

4. $R(-1) \lor P(2)$

Como $R(-1)$ es falsa pero $P(2)$ es verdad, entonces la proposición es verdadera.

5. $\neg R(-2) \lor P(-2)$

Como $-2<0$ es verdad, entonces $\neg R(-2)$ es falso, mientras que $-2<4$ es verdad. De esta manera la proposición es verdadera.

Problema. Considera los siguientes predicados:

  • $P(x): 2x>0$
  • $Q(x):x>0$
  • $R(x): x=20$
  • $T(x):x<0$

Determina la verdad o falsedad de las siguientes proposiciones, considerando que nuestro universo de discurso son los números enteros. Si la proposición no es verdadera, da un contraejemplo o explicación de ello.

  1. $\forall x(P(x) \Rightarrow Q(x))$
  2. $\exists x (Q(x) \land T(x))$
  3. $\forall x(R(x) \Rightarrow(Q(x))$
  4. $\exists ! x(R(x))$
  5. $ \nexists x (Q(x) \land P(x))$

Solución.

  • $\forall x(P(x) \Rightarrow Q(x))$

Nota que siempre que se cumple $2x>0$ entonces $x>0$ (más adelante demostrarás esto con toda formalidad, pero de momento lo daremos por cierto). Por lo tanto la proposición es verdadera.

  • $\exists x (Q(x) \land T(x))$

Para que esto sucediera, necesitaríamos la existencia de al menos un elemento $x$ que cumpla $0<x$ y $x>0$, es decir necesitaríamos un elemento que sea positivo y negativo a la vez, pero esto no es posible. Por lo tanto la proposición es falsa.

  • $\forall x(R(x) \Rightarrow(Q(x))$

Lo que nos dice esta proposición es «Para todo número entero $x$ que cumpla $x=20$ entonces $x>0$» o dicho de otra manera: «Si un número entero es igual a 20, entonces será positivo.» Lo cuál es correcto, pues si el número es distinto a 20, la implicación será correcta (recuerda la tabla de verdad de la implicación), mientras que el único caso en donde la hipótesis se cumple es cuando $x=20$ y claramente es un número que cumple $x>0$. Entonces la proposición es verdadera.

  • $\exists ! x(R(x))$

Esto nos quiere decir que existe un único número entero que sea igual a 20, e inmediatamente podemos saber que es verdadera, pero ¿A qué nos referiremos que un número sea igual a 20? Primero tendríamos que ponernos de acuerdo de qué significa la igualdad. Aunque ahora no lo haremos, piensa el cómo nos aseguraríamos de que es el único número entero que cumple esa propiedad ¿Qué pasaría si no fuera cierto?

  • $ \nexists x (Q(x) \land P(x))$

Lo que dice la proposición es que ningún número $x$ va a cumplir a la vez $x>0$ y $2x>0$, pero esto no es cierto, pues pensemos en $x=1$. Cumple $Q(x)$ ya que $1>0$ y cumple $P(x)$ porque $2*1=2>0$. Entonces podemos decir que es falso pues dimos un contraejemplo que contradijo la proposición.

Entradas relacionadas