Archivo de la etiqueta: tablas

Álgebra Moderna I: Operación binaria asociativa y conmutativa

Por Cecilia del Carmen Villatoro Ramos

3 respuestas

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En la entrada anterior definimos el concepto de operación binaria, en esta entrada veremos dos tipos más específicos de operaciones binarias: las operaciones binarias asociativas y las operaciones conmutativas. Éstas nos interesan ya que hacen que las operaciones sean más sencillas de manejar.

Nuevas definiciones

Definición. Una operación binaria $*$ en un conjunto $\mathcal{S}$ es asociativa si, para todos $a, b, c \in \mathcal{S}$

$(a*b)*c = a*(b*c)$.

Definición. Una operación binaria $*$ en un conjunto $\mathcal{S}$ es conmutativa si, para todos $a,b \in \mathcal{S}$

$a*b=b*a$.

Ejemplos de operaciones binarias asociativas y conmutativas

Repasemos los ejemplos vistos en la entrada anterior. Ahora los analizaremos con mayor profundidad.

  • Consideremos $\mathcal{S} := \mathbb{R}$ con la operación $a*b=ab-2$. Entonces $*$ no es asociativa.

Demostración. Sean $a,b,c \in \mathbb{R}$.

Si sustituimos los valores de acuerdo a la forma en que está definida $*$, por un lado obtenemos

$\begin{align}(a * b)*c = (ab-2)c -2 = (ab)c -2c-2\end{align}$

y por otro,

$\begin{align}a*(b*c) = a*(bc -2) = a(bc-2)-2 = a(bc)-2a-2. \end{align}$

Observamos que $(1)$ y $(2)$ en general son distintos. Por lo tanto $*$ no es asociativa.

Ejemplo. Si hacemos la operación con $1, 2, 3$ obtenemos:

$(1*2)*3 = 0 * 3 = -2$

$1*(2*3)= 1 *4 = +2$

Así, claramente no es asociativa.

$\blacksquare$

Sin embargo, sí es conmutativa.

Demostración. Por la conmutatividad de la multiplicación de reales,

$a*b = ab-2 = ba-2 = b*a \qquad \forall a,b \in \mathbb{R}$.

$\blacksquare$

  • Consideremos ahora el conjunto $\mathcal{S} := \mathbb{R}^+$ (los reales positivos), con la operación $a*b=\frac{a}{b}$. Entonces $*$ no es asociativa.

Demostración. Sean $a,b,c \in \mathbb{R}^+$.

Si sustituimos de acuerdo a la definición de nuestra operación binaria, obtenemos

$(a*b)*c = \frac{a}{b}*c =\frac{\frac{a}{b}}{c} = \frac{a}{bc}$

por otro lado,

$a*(b*c)= a* \frac{b}{c} = \frac{a}{\frac{b}{c}} = \frac{ac}{b}$.

En general, $(a*b)*c \neq a*(b*c)$, por lo que esta operación binaria no es asociativa.

$\blacksquare$

Ejemplo. Tomemos $3,4$ y $5$:

$(3*4)*5 = \frac{3}{4} * 5 = \frac{\frac{3}{4}}{5} = \frac{3}{20}$.

$3*(4*5) = 3* \frac{4}{5} = \frac{3}{\frac{4}{5}} = \frac{15}{4}$.

Claramente, $$\frac{3}{20} \neq \frac{15}{4}.$$

$\blacksquare$

Esta operación tampoco es conmutativa.

Demostración. Sean $a,b \in \mathbb{R}^+$.

Sustituyendo nuestra definición, en general tenemos que,

$a*b = \frac{a}{b} \neq \frac{b}{a} = b*a$.

Por lo tanto, nuestra operación binaria no es conmutativa.

$\blacksquare$

Ejemplo. Un ejemplo sencillo y claro,

$1*2 = \frac{1}{2} \neq 2 = 2*1$.

$\blacksquare$

  • En $\mathcal{S} := \mathbb{Z}^+$, $a*b = \text{máx} \{a,b\}$ es asociativa y conmutativa.
  • En $\mathcal{S} := \mathbb{Z}^+$, $a*b = a$ es asociativa y no conmutativa.
  • En $\mathcal{S} := \mathcal{M}_{2\times 2}(\mathbb{Z})$, $A*B = A + B$ es asociativa y conmutativa.
  • En $\mathcal{S}:= \{f \; | \; f: \mathbb{R} \to \mathbb{R} \}$, $f*g := f\circ g$ es asociativa pero no conmutativa.
  • En $\mathcal{S}:= S_3$, $f*g = f\circ g$. Es asociativa pero no conmutativa.

Ejemplo con tablas

En esta sección analizaremos algunas operaciones binarias definidas con tablas. El hecho de que una función sea conmutativa se ve reflejado en la tabla. Cuando la operación es conmutativa, si nos fijamos en la línea diagonal que divide a la tabla (la diagonal principal), podemos observar que la tabla es simétrica con respecto a la diagonal.

Demostrar la asociatividad a partir de la tabla es un poco más complicado. Se tendrían que escoger todas las distintas combinaciones de tres elementos del conjunto, lo que lo haría muy largo, incluso para conjuntos pequeños. Por eso conviene definir la operación de otra manera. En los siguientes ejemplos encontrarás la función definida de ambas maneras, con la tabla y con una regla de correspondencia.

  • En $\mathcal{S} = \{2,4,6\}$, la operación $a*b = \text{máx}\{a,b\}$ se vería como
$*$$2$$4$$6$
$2$$2$$4$$6$
$4$$4$$4$$6$
$6$$6$$6$$6$

La tabla es simétrica con respecto a la diagonal principal, por lo tanto esta operación sí es conmutativa. Queda como ejercicio demostrar que es asociativa.

  • En $\mathcal{S} = \{2,4,6\}$, la operación $a*b = a$ se vería como
$*$$2$$4$$6$
$2$$2$$2$$2$
$4$$4$$4$$4$
$6$$6$$6$$6$

De la misma manera, si nos fijamos en la diagonal principal, observamos que esta operación no es conmutativa. Pero, será tu trabajo demostrar que sí es asociativa.

  • En $\mathcal{S} = \{1, -1\}$, la operación $a*b = ab$ se vería como
$*$$1$$-1$
$1$$1$$-1$
$-1$$-1$$1$

A diferencia de los anteriores dos ejemplos, esta operación sí es conmutativa y también asociativa.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra o da contraejemplos de las propiedades (conmutatividad y asociatividad) que quedaron pendientes en los ejemplos.
  2. Con ayuda de las tablas, verifica las propiedades de conmutatividad y asociatividad que quedaron pendientes en los ejemplos correspondientes.
  3. Para el conjunto $\mathcal{S}:= \{\bigstar, \blacktriangledown, \blacklozenge, \clubsuit \}$, define
    • una operacion binaria conmutativa (pero no asociativa),
    • una operación asociativa (pero no conmutativa),
    • una operación asociativa y conmutativa,
    • una operación que no sea ni asociativa ni conmutativa.
  4. De los ejemplos que hiciste en la tarea moral anterior, determina si son conmutativas, asociativas o ambas.
  5. Del ejercicio 5 de la tarea moral anterior, determina si las operaciones binarias son conmutativas, asociativas, ambas o ninguna de las dos.

Más adelante…

Ahora sí, ya estás listo para que comencemos con los grupos. En la siguiente entrada comenzaremos a definirlos y a dar algunos ejemplos. Verás que las operaciones binarias tienen un papel importante a la hora de definir esta estructura algebraica.

Entradas relacionadas

Álgebra Superior I: Conectores: negaciones, conjunciones y disyunciones

Por Leonardo Ignacio Martínez Sandoval

7 respuestas

Introducción

En la entrada de introducción a este curso ya acordamos que una proposición matemática (o simplemente proposición) es un enunciado que puede ser verdadero o falso (pero no ambos), y que habla de objetos matemáticos. También hablamos de variables proposicionales como $P,Q,R$, que nos permiten hablar de proposiciones indeterminadas. Y mencionamos brevemente lo que será una tabla de verdad.

Ahora hablaremos de algunas reglas que nos permiten comenzar con una o más proposiciones y combinarlas para obtener otras proposiciones. Hablaremos de la negación, de la conjunción y de la disyunción. De manera informal, la primera antepone un «no es cierto que» a cualquier proposición, y le cambia su veracidad. La segunda y tercera combinan dos proposiciones en una sola. De manera informal, ponen «y» y «o» entre las oraciones, respectivamente.

A estas reglas se les conoce como conectores o conectivos. Discutiremos cada uno de ellos de manera intuitiva y después definiremos qué quieren decir de manera formal.

Conectores lógicos

De tu experiencia previa, ya sabes que hay formas en las que podemos combinar, por ejemplo, a números enteros para obtener nuevos números. Si tomamos el número $2$ y el número $3$ y les aplicamos la operación «suma», entonces debemos entreponer un signo $+$ entre ellos para obtener la expresión $2+3$. Esta expresión es de nuevo un número entero: el $5$. Así como hacemos operaciones entre números, también podemos hacer operaciones entre proposiciones.

Un conector lógico (o simplemente conector) es una regla que permite tomar una o más proposiciones, «operarlas» y de ahí construir una nueva proposición «resultado». Como lo que más nos importa de las proposiciones es si son verdaderas o falsas, entonces lo más importante de cada conector que demos es decir cómo se determina la veracidad de la proposición que obtuvimos como resultado. En estas entradas hablaremos a detalle de los siguientes conectores:

  • Negaciones: Usan el símbolo $\neg$. Toman una proposición $P$ y la convierten en la proposición $\neg P$ cuyo valor de verdad es opuesto al de $P$.
  • Conjunciones: Usan el símbolo $\land$. Toman dos proposiciones $P$ y $Q$ y las convierten en la proposición $P\land Q$, que para ser verdadera necesita que tanto $P$ como $Q$ sean verdaderas.
  • Disyunciones: Usan el símbolo $\lor$. Toman dos proposiciones $P$ y $Q$ y las convierten en la proposición $P\lor Q$, que para ser verdadera necesita que alguna de $P$ o $Q$ lo sean (o ambas).
  • Implicaciones: Usan el símbolo $\Rightarrow$. Toman dos proposiciones $P$ y $Q$ y las convierten en la proposición $P\Rightarrow Q$, que para ser verdadera se necesita o bien que $P$ sea falsa (y $Q$ puede ser lo que sea), o bien que tanto $P$ como $Q$ sean verdaderas.
  • Dobles implicaciones: Usan el símbolo $\Leftrightarrow$. Toman dos proposiciones $P$ y $Q$ y las convierten en la proposición $P \Leftrightarrow Q$, que para ser verdadera necesita que $P\Rightarrow Q$ sea verdadera y que $Q\Rightarrow P$ sea verdadera.

Ahora profundizaremos en las primeras tres y las últimas dos las dejaremos para más adelante.

Negaciones

Lo que hacen las negaciones a nivel de texto es anteponer un «no es cierto que» a una proposición. Por ejemplo si comenzamos con la proposición $$A=\text{«El cielo es azul.»}$$ entonces su negación es $$\neg A=\text{«No es cierto que el cielo es azul.»}$$ Observa que si pensamos a $A$ como una proposición verdadera, entonces la proposición $\neg A$ es falsa.

Hay que tener cuidado. El efecto que hacen las negaciones simplemente es anteponer «no es cierto que» a una proposición. Puede ser tentador intentar poner un «no» en alguna parte de la oración de manera arbitraria, pero esto puede llevar a problemas. Por ejemplo, la negación de la oración $$B=\text{«El número $2$ es par y múltiplo de $3$.»}$$ es simplemente $$\text{«No es cierto que el número $2$ es par y múltiplo de $3$.»}$$ Si hacemos la negación con poco cuidado, podríamos llegar a $$\text{«El número $2$ no es par ni múltiplo de $3$.»}$$ que no funciona, pues no tiene el valor opuesto de verdad: la oración original es falsa, y esta también.

Más adelante hablaremos con cuidado del conector «y» que usamos en el ejemplo anterior. Veremos cómo se pueden negar de manera correcta a las proposiciones que lo usan.

Tabla de verdad de negaciones

De manera formal, dada una proposición $P$ definimos a la negación de $P$, que denotamos por $\neg P$ como una proposición que tiene valor opuesto de verdad al de $P$. Pensando entonces a $P$ como una variable proposicional, se tiene que $\neg P$ es una fórmula proposicional con la siguiente tabla de verdad:

$P$$\neg P$
$0$ $1$
$1$$0$ 

Ya que al aplicar una negación obtenemos una nueva proposición, entonces ahora podemos volverle a aplicar negación a la nueva proposición obtenida. Así, si comenzamos con $$P=\text{«El cielo es azul.»}$$ y lo negamos, obtenemos $$\neg P = \text{«No es cierto que el cielo es azul.»}$$ y luego podemos negar de nuevo para obtener $$\neg(\neg P) = \text{«No es cierto que no es cierto que el cielo es azul.»}$$

Como la negación cambia el valor de verdadero a falso y viceversa, entonces $P$ y $\neg(\neg P)$ tienen el mismo valor de verdad. Esto lo podemos verificar en la siguiente tabla de verdad, llenando primero la segunda columna y luego la tercera a partir de la segunda.

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

Observa que las columnas de $P$ y de $\neg(\neg P)$ tienen exactamente los mismos valores. Esto ocurrirá con frecuencia. Cuando dos fórmulas proposicionales tengan exactamente el mismo valor de verdad para todas las asignaciones de verdad de sus variables proposicionales, diremos que son equivalentes y lo denotaremos escribiendo $\equiv$ entre ambas. Discutiremos esto con más detalle en la siguiente entrada. Así, por lo visto arriba podemos escribir $P\equiv \neg(\neg P)$.

Conjunciones

Lo que hacen las conjunciones a nivel de texto es anteponer un «y» entre dos proposiciones. Por ejemplo si comenzamos con las proposiciones $$P=\text{«El número $20$ es impar.»}$$ y $$Q=\text{«El número $9$ es un número cuadrado.»}$$ entonces la conjunción de ambas es $$P\land Q=\text{«El número $20$ es impar y el número $9$ es cuadrado.»}$$ Para que esta nueva proposición sea verdadera, debe suceder que cada una de las proposiciones que la conforman deben serlo. En este caso en específico, esto no ocurre. La proposición $Q$ es verdadera, pero la proposición $P$ es falsa. De este modo, la conjunción es falsa.

Veamos algunos ejemplos más. Tomemos las siguientes proposiciones:

$$A=\text{«Los gatos son felinos.»}$$

$$B=\text{«Todos los blorg son rojos.»}$$

$$C=\text{«El número $3$ es mayor que el número $1$.»}$$

$$D=\text{«Un cuadrado tiene ángulos de $60^\circ$.»}$$

$$E=\text{«La luna es azul.»}$$

Para determinar la veracidad de cada una de estas, tendríamos que ponernos de acuerdo en la definición de varios términos como «felinos», «blorg», «es mayor que», «cuadrado», «luna», etc. Pero por practicidad, daremos por hecho que $A$, $B$ y $C$ son proposiciones verdaderas y que $D$ y $E$ son falsas.

La conjunción de $A$ con $B$ es $$A\land B = \text{«Los gatos son felinos y todos los blorg son rojos.»}$$ Como cada una de las proposiciones que conforman la conjunción es verdadera, entonces la conjunción lo es.

La conjunción de $B$ con $E$ es $$B\land E = \text{«Todos los blorg son rojos y la luna es azul».}$$ Por muy cierto que sea que todos los blorg sean rojos, la conjunción no es verdadera pues $E$ es falsa.

Una vez que formamos una conjunción, esta es ahora una nueva proposición. Por lo tanto, se vuelve candidata a aplicarle negaciones y conjunciones. De esta forma, tiene sentido pensar en la proposición $\neg(A\land B)$, en donde los paréntesis implican que primero se hace esa operación. A nivel textual también usaremos los paréntesis para no confundirnos, de modo que escribiremos: \begin{align*}\neg(A\land B) &= \text{«No es cierto que (los gatos son felinos y todas}\\ &\text{los blorg son rojos).»}\end{align*}

También tiene sentido pensar en la proposición $(\neg C) \land E$. O bien en la proposición $A\land( (\neg C) \land E)$. Puedes practicar pasar estas proposiciones a oraciones con paréntesis.

Tabla de verdad de conjunciones

Para formalizar la discusión anterior, definimos a la conjunción de dos proposiciones $P$ y $Q$ como la proposición $P\land Q$ que es verdadera únicamente cuando tanto $P$ como $Q$ son verdaderas. Así, como fórmula lógica, $P\land Q$ queda definida mediante la siguiente tabla de verdad:

$P$$Q$$P\land Q$
$0$$0$$0$ 
$0$$1$$0$ 
$1$$0$$0$ 
$1$$1$$1$ 

¿Importará el orden en el que hacemos la conjunción? Esta es una pregunta muy natural. Para responderla, podemos hacer la tabla de verdad considerando tanto a las columnas $P\land Q$ como $Q\land P$ y llenándolas por separado.

$P$$Q$$P\land Q$$Q \land P$
$0$$0$ $0$$0$ 
$0$$1$$0$ $0$ 
$1$$0$$0$ $0$
$1$$1$$1$ $1$ 

Observa que las columnas correspondientes a $P\land Q$ y $Q\land P$ son iguales, de modo que podemos concluir que ambas fórmulas lógicas son equivalentes. Recuerda que escribirmos $P\land Q\equiv Q\land P$. Hay otras preguntas muy naturales: ¿qué pasa si hacemos la conjunción de más de dos proposiciones? ¿son equivalentes iguales $(P\land Q) \land R$ y $R\land(Q \land P)$? ¿qué pasa si combinamos a la negación con la conjunción? Esto lo veremos más adelante.

Disyunciones

Lo que hacen las disyunciones a nivel de texto es anteponer un «o» entre dos proposiciones. Por ejemplo si comenzamos con las proposiciones $$P=\text{«El número $10$ es impar.»}$$ y $$Q=\text{«El número $7$ es un número primo.»}$$ entonces la conjunción de ambas es $$P\lor Q=\text{«El número $10$ es impar o el número $7$ es primo.»}$$ Para que esta nueva proposición sea verdadera, es suficiente con que una de las proposiciones que la conforman lo sea. En este caso en específico, esto sí ocurre. La proposición $Q$ es verdadera, de modo que aunque la proposición $P$ sea falsa, la disyunción resulta ser verdadera.

Retomemos las proposiciones de la sección anterior para ver más ejemplos.

$$A=\text{«Los gatos son felinos.»}$$

$$B=\text{«Todos los blorg son rojos.»}$$

$$C=\text{«El número $3$ es mayor que el número $1$.»}$$

$$D=\text{«Un cuadrado tiene ángulos de $60^\circ$.»}$$

$$E=\text{«La luna es azul.»}$$

Recuerda que estamos dando por hecho que $A$, $B$ y $C$ son proposiciones verdaderas y que $D$ y $E$ son falsas.

La disyunción de $A$ con $B$ es $$A\lor B = \text{«Los gatos son felinos o todos los blorg son rojos.»}$$ Como $A$ es verdadera, esto basta para decir que $A\lor B$ es verdadera. Como $B$ también es verdadera, también esto bastaba para decir que $A\lor B$ es verdadera. No hay ningún problema con que tanto $A$ como $B$ sean verdaderas.

La conjunción de $D$ con $E$ es $$D\lor E = \text{«Un cuadrado tiene ángulos de $60^\circ$ o la luna es azul».}$$ Aquí tanto $D$ como $E$ son falsas, de modo que la disyunción también lo es.

Las disyunciones también crean proposiciones nuevas, a las que se les pueden aplicar negaciones, conjunciones y disyunciones. El uso del paréntesis se vuelve crucial. Observa que usando las proposiciones ejemplo de arriba, tenemos que

  • $(D\land C) \lor A $ es verdadera
  • $D\land (C \lor A)$ es falsa

Tabla de verdad de disyunciones

Para formalizar la discusión anterior, definimos a la disyunción de dos proposiciones $P$ y $Q$ como la proposición $P\lor Q$ que es verdadera cuando por lo menos una de las proosiciones $P$ y $Q$ lo es. Así, pensada como fórmula lógica, la tabla de verdad sería la siguiente:

$P$$Q$$P\lor Q$
$0$$0$$0$ 
$0$$1$$1$ 
$1$$0$$1$ 
$1$$1$$1$ 

¿Importará el orden en el que hacemos la conjunción? Esta es una pregunta muy natural, y ya puedes responderla por tu cuenta. Intenta hacer esto haciendo una tabla de vedad que incluya tanto a las columnas $P\lor Q$ como $Q\lor P$.

En la sección anterior vimos la importancia de poner paréntesis en las expresiones. Esta importancia también podemos verificarla mediante la siguiente tabla de verdad, en donde consideramos tres variables proposicionales $P$, $Q$ y $R$ y estudiamos qué sucede con las fórmulas proposicionales $(P\land Q) \lor R$ y con $P \land (Q \lor R)$. Como hay $2$ posibilidades para cada una de $P$, $Q$, $R$, debemos tener $2\cdot 2 \cdot 2 = 8$ filas.

Llenamos primero las primeras dos columnas usando lo que sabemos de $P\land Q$ y $Q\lor R$.

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

Y ahora sí podemos llenar las últimas dos porque ya sabemos cómo es el valor de verdad de cada una de las fórmulas que las conforman.

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

Observa que las columnas correspondientes a $(P\land Q) \lor R$ y $P \land (Q \lor R)$ no son iguales, pues difieren en algunos renglones, por ejemplo, en el segundo renglón. De este modo, podemos concluir que hay ocasiones en las que lás fórmulas lógicas $(P\land Q) \lor R$ y $P \land (Q \lor R)$ difieren. Decimos entonces que no son equivalentes. En conclusión, el orden de las operaciones suele ser importante.

Más adelante…

En esta entrada hablamos de la negación, la conjunción y la disyunción. Vimos cómo justificar algunas de sus propiedades mediante tablas de verdad, como $A\land B\equiv B\land A$. En la siguiente entrada usaremos esta técnica y otras más para probar otras propiedades interesantes de estos conectores.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Escribe en texto y usando paréntesis la proposición $(A\land B) \lor (\neg D)$, usando $A$, $B$ y $D$ como las proposiciones ejemplo que dimos.
  2. Mediante una tabla de verdad, justifica la equivalencia $P\lor Q \equiv Q \lor P$.
  3. Mediante una tabla de verdad, justifica la equivalencia $(P\lor Q) \lor R \equiv P \lor (Q \lor R)$.
  4. Haz una tabla de verdad para verificar que las fórmulas proposicionales $\neg(P \land Q)$ y $(\neg P) \land (\neg Q)$ no son equivalentes. Es decir, debes de hacer todos los casos y ver que las columnas difieren en uno o más renglones.
  5. Haz una tabla de verdad para verificar que las fórmulas proposicionales $(P\land Q) \land (R \land S)$ y $(((P\land Q) \land R) \land S)$ son equivalentes. Va a ser una tabla grande, de $16$ renglones.

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»