Álgebra Booleana
El Álgebra Booleana trata sobre verdadero, lo falso y la lógica.
No
Lo más sencillo que podemos hacer es "no" o "invertir":
- si algo no verdadero es falso
- si algo no falso es verdadero
Podemos escribir esto en una "tabla de verdad" (usamos V para verdadero y F para falso):
| A | no A | |
|---|---|---|
| F | V | |
| V | F |
Y
Podemos combinar dos valores con "y". Ambos deben ser verdaderos para que el resultado sea verdadero:
| A | B | A y B | |
|---|---|---|---|
| F | F | F | |
| F | V | F | |
| V | F | F | |
| V | V | V |
Ejemplo: ¡Si cortamos el césped y lavamos el coche, conseguimos helado!
| cortar césped | lavar coche | helado | |
|---|---|---|---|
| F | F | F | |
| F | V | F | |
| V | F | F | |
| V | V | V |
Solo si hacemos ambos trabajos conseguimos helado.
O
Podemos combinar dos valores con "o". El resultado es verdadero si alguno (o ambos) es verdadero:
| A | B | A o B | |
|---|---|---|---|
| F | F | F | |
| F | V | V | |
| V | F | V | |
| V | V | V |
Ejemplo: ¡Si cortamos el césped o lavamos el coche, conseguimos helado!
| cortar césped | lavar coche | helado | |
|---|---|---|---|
| F | F | F | |
| F | V | V | |
| V | F | V | |
| V | V | V |
En este caso, podemos hacer cualquiera de los trabajos (o ambos) para conseguir helado. Vamos a lavar el coche.
¡Simplicidad!
Así que solo tenemos dos posibles valores:
- verdadero
- falso
Y solo tres operaciones básicas:
- y
- o
- no
Podemos combinarlas para resolver cosas lógicas. Eso es todo.
Y, o, ...
En español usamos las palabras libremente. Decimos "Me gustan las manzanas y las peras", pero en lógica eso significa que te gustan cuando están juntas.
Recuerda que la lógica dice:
- y: deben estar ambas juntas
- o: puede ser una o ambas
Notación
¡Pero hay diferentes maneras de escribir lo mismo!
Aquí hay diferentes maneras de escribir "no A":
A = ¬A = ~A = A'
Aquí hay dos maneras principales de escribir "y" y "o":
Puedes elegir el estilo que prefieras presionando este botón:
| y: | · |
| o: | ＋ |
| (A y B) o C: | (A·B) ＋ C |
(Nota: el estilo "Punto / Más" tiene muchas similitudes con multiplicar y sumar, mientras que el estilo "Arriba / Abajo" tiene equivalentes con la intersección ∩ y unión ∪ de conjuntos.)
Xor (o Exclusivo) ⊕
Xor es lo mismo que o, excepto que es falso cuando ambas entradas son verdaderas:
| A | B | A o B | A xor B | |
|---|---|---|---|---|
| F | F | F | F | |
| F | V | V | V | |
| V | F | V | V | |
| V | V | V | F |
Podemos tener una verdadera pero no ambas.
Xor es como si tus dos mejores amigos pelearan. La vida es divertida estando con uno u otro, pero no con ambos.
Equivalencia ≡
Solo es verdadero cuando las entradas coinciden (son equivalentes):
| A | B | A ≡ B | |
|---|---|---|---|
| F | F | V | |
| F | V | F | |
| V | F | F | |
| V | V | V |
La equivalencia es lo opuesto de xor.
Implicación →
Es verdadera, excepto cuando A es verdadera y B es falso:
| A | B | A → B | |
|---|---|---|---|
| F | F | V | |
| F | V | V | |
| V | F | F | |
| V | V | V |
Ejemplo: El guardia "A" revisa tu boleto "B"
- Sin el guardia puedes entrar en cualquier momento
- Con el guardia necesitas un boleto para entrar
Así que puedes entrar excepto cuando hay un guardia y no tienes boleto.
Ahora todo junto
Aquí están todos juntos:
| y | o | xor | equiv | implica | |||
| A | B | A · B | A ＋ B | A ⊕ B | A ≡ B | A → B | |
|---|---|---|---|---|---|---|---|
| F | F | F | F | F | V | V | |
| F | V | F | V | V | F | V | |
| V | F | F | V | V | F | F | |
| V | V | V | V | F | V | V |
En realidad, hay 16 combinaciones posibles, pero estas son las más importantes.
Venn
Así es como un Diagrama de Venn se relaciona con una tabla de verdad:
Regiones del Diagrama de Venn
En la región exterior, tanto A como B son falsas
Y podemos hacer bonitos Diagramas de Venn para ilustrar y, o, etc.:
Leyes
Esto es genial: suponiendo que "y es multiplicar" y "o es sumar", encontramos que el Álgebra Booleana comparte estas Leyes del álgebra ordinaria:
Leyes Conmutativas: podemos intercambiar valores en estos casos:
A · B = B · A
A ＋ B = B ＋ A
Ejemplo: Carrera de niños menores de 15 años.
Debes ser un niño y tener menos de 15 años:
Niño y Menor de 15 es lo mismo que Menor de 15 y Niño
Leyes Asociativas: podemos cambiar o quitar paréntesis en estos casos:
A · (B · C) = (A · B) · C = A · B · C
A ＋ (B ＋ C) = (A ＋ B) ＋ C = A ＋ B ＋ C
Ejemplo: ¡Hamburguesas gratis para estudiantes, padres o maestros!
Estos casos son iguales:
estudiante o (padre o maestro)
(estudiante o padre) o maestro
estudiante o padre o maestro
Distribución de y sobre o:
A · (B ＋ C) = (A · B) ＋ (A · C)
Leyes de Identidad: obtenemos el valor original en estos casos:
A · verdadero = A
A ＋ falso = A
Doble negación: un "no" cancela otro "no" y obtenemos el valor original:
A = A
Decir "NO no comas" es lo mismo que decir "¡Come!"
Las siguientes leyes también son ciertas en el Álgebra Booleana, pero no en el álgebra ordinaria:
Distribución de o sobre y:
A ＋ (B · C) = (A ＋ B) · (A ＋ C)
Leyes de Absorción: podemos "absorber" el término entre paréntesis en estos dos casos:
A · (A ＋ B) = A
A ＋ (A · B) = A
¿Por qué? Usando las Leyes de Identidad y Distribución, veamos el primer caso:
Leyes Idempotentes: también podemos simplificar estos casos:
A · A = A
A ＋ A = A
Leyes de Complemento: simplificamos un valor con su inverso en estos casos:
A · = falso
A ＋ = verdadero
De Morgan: una regla muy útil, especialmente cuando se programa:
·
=
＋ =
Veamos cada una por separado:
·
=
"no A y no B = no (A o B)"
Ejemplo: · =
Ejemplo: "No quiero mayonesa y no quiero jamón"
Es lo mismo que "No quiero (mayonesa o jamón)"
Y la otra regla de De Morgan:
＋
=
"no A o no B = no (A y B)"
Ejemplo: ＋ =
Ejemplo: "No quiero mayonesa o no quiero jamón"
Es lo mismo que "No quiero (mayonesa y jamón)"
En otras palabras, no mayonesa y jamón juntos, pero cualquiera de los dos por separado está bien.
Ejemplo: Ensalada
Estás haciendo una ensalada. Tu amigo dice "Solo quiero ingredientes que no sean verdes o no sean pequeños". ¿Qué significa?
Decodifiquemos eso:
＋ =
que en realidad es lo mismo que "no (verde y pequeño)"
En otras palabras: probablemente no quiere aceitunas verdes ni alcaparras, chícharos, etc.
Cadena
Una serie de "y"s comparada con una serie de "o"s:
- A y B y C y D y ... deben ser todos verdaderos para que el resultado sea verdadero.
- A o B o C o D o ... deben ser todos falsos para que el resultado sea falso.
