Algebra booleana.

..

1. Álgebra Booleana
El álgebra booleana es un sistema matemático deductivo centrado en los valores cero
y uno (falso y verdadero). Un operador binario " º " definido en éste juego de valores
acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador
booleano AND acepta dos entradas booleanas y produce una sola salida booleana.
Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se
pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el
álgebra booleana a menudo emplea los siguientes postulados:
Cerrado. El sistema booleano se considera cerrado con respecto a un operador
binario si para cada par de valores booleanos se produce un solo resultado
booleano.
Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A
para todos los posibles valores de A y B.
Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B
º C) para todos los valores booleanos A, B, y C.
Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) =
(A º B) % (A º C) para todos los valores booleanos A, B, y C.
Identidad. Un valor booleano I se dice que es un elemento de identidad con
respecto a un operador binario " º " si A º I = A.
Inverso. Un valor booleano I es un elemento inverso con respecto a un operador
booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de
A.
Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de
operadores y valores:
- Los dos posibles valores en el sistema booleano son cero y uno, a menudo
llamaremos a éstos valores respectivamente como falso y verdadero.
- El símbolo · representa la operación lógica AND. Cuando se utilicen nombres de
variables de una sola letra se eliminará el símbolo ·, por lo tanto AB representa la
operación lógica AND entre las variables A y B, a esto también le llamamos
el producto entre A y B.
- El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación
lógica OR entre A y B, también llamada la suma de A y B.
- El complemento lógico, negación ó NOT es un operador unitario, en
éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A'
denota la operación lógica NOT de A.
- Si varios operadores diferentes aparecen en una sola expresión booleana, el
resultado de la expresión depende de la procedencia de los operadores, la cual es de
mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador
lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda.
Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan
de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.
Utilizaremos además los siguientes postulados:
P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT
P2 El elemento de identidad con respecto a · es uno y con respecto a + es cero.
No existe elemento de identidad para el operador NOT
P3 Los operadores · y + son conmutativos.
P4 · y + son distributivos uno con respecto al otro, esto es, A· (B+C) = (A·B)+(A·C)
y A+ (B·C) = (A+B) ·(A+C).

2. P5 Para cada valor A existe un valor A' tal que A·A' = 0 y A+A' = 1. Éste valor es el
complemento lógico de A.
P6 · y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B)+C = A+ (B+C).
Es posible probar todos los teoremas del álgebra booleana utilizando éstos
postulados, además es buena idea familiarizarse con algunos de los teoremas más
importantes de los cuales podemos mencionar los siguientes:
Teorema 1: A + A = A
Teorema 2: A · A = A
Teorema 3: A + 0 = A
Teorema 4: A · 1 = A
Teorema 5: A · 0 = 0
Teorema 6: A + 1 = 1
Teorema 7: (A + B)' = A' · B'
Teorema 8: (A · B)' = A' + B'
Teorema 9: A + A · B = A
Teorema 10: A · (A + B) = A
Teorema 11: A + A'B = A + B
Teorema 12: A' · (A + B') = A'B'
Teorema 13: AB + AB' = A
Teorema 14: (A' + B') · (A' + B) = A'
Teorema 15: A + A' = 1
Teorema 16: A · A' = 0
Los teoremas siete y ocho son conocidos como Teoremas de DeMorgan en honor al
matemático que los descubrió.
Características:
Un álgebra de Boole es un conjunto en el que destacan las siguientes características:
1- Se han definido dos funciones binarias (que necesitan dos parámetros) que
llamaremos aditiva (que representaremos por x
+ y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo
parámetro) que representaremos por x'.
2- Se han definido dos elementos (que designaremos por 0 y 1)
Y 3- Tiene las siguientes propiedades:
Conmutativa respecto a la primera función: x + y = y + x
Conmutativa respecto a la segunda función: xy = yx
Asociativa respecto a la primera función: (x + y) + z = x + (y +z)
Asociativa respecto a la segunda función: (xy)z = x(yz)
Distributiva respecto a la primera función: (x +y)z = xz + yz
Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z)
Identidad respecto a la primera función: x + 0 = x
Identidad respecto a la segunda función: x1 = x
Complemento respecto a la primera función: x + x' = 1
Complemento respecto a la segunda función: xx' = 0
Propiedades Del Álgebra De Boole
1. Idempotente respecto a la primera función: x + x = x
Idempotente respecto a la segunda función: xx = x
Maximalidad del 1: x + 1 = 1

3. Minimalidad del 0: x0 = 0
Involución: x'' = x
Inmersión respecto a la primera función: x + (xy) = x
Inmersión respecto a la segunda función: x(x + y) = x
Ley de Morgan respecto a la primera función: (x + y)' = x'y'
Ley de Morgan respecto a la segunda función: (xy)' = x' + y'
Función Booleana
Una función booleana es una de A x A x A x....A en A, siendo A un conjunto cuyos
elementos son 0 y 1 y tiene estructura de álgebra de Boole.
Supongamos que cuatro amigos deciden ir al cine si lo quiere la mayoría. Cada uno
puede votar sí o no. Representemos el voto de cada uno por xi. La función devolverá
sí (1) cuando el número de votos afirmativos sea 3 y en caso contrario devolverá 0.
Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.
Producto mínimo (es el número posible de casos) es un producto en el que aparecen
todas las variables o sus negaciones.
El número posible de casos es 2n.
Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los
posibles casos son:
Votos Resultado
ABCD
1111 1
1110 1
1101 1
1100 0
1011 1
1010 0
1001 0
1000 0
0111 1
0110 0
0101 0
0100 0
0011 0
0010 0
0001 0
0000 0
Las funciones booleanas se pueden representar como la suma de productos mínimos
(minterms) iguales a 1.
En nuestro ejemplo la función booleana será:
f(A,B,C,D) = ABCD + ABCD' + ABC'D + AB'CD + A'BCD
Diagramas De Karnaugh
Los diagramas de Karnaugh se utilizan para simplificar las funciones booleanas.
Se construye una tabla con las variables y sus valores posibles y se agrupan los 1
adyacentes, siempre que el número de 1 sea potencia de 2.
En esta página tienes un programa para minimización de funciones booleanas
mediante mapas de Karnaugh

4. La relación que existe entre la lógica booleana y los sistemas de cómputo es fuerte, de
hecho se da una relación uno a uno entre las funciones booleanas y los circuitos
electrónicos de compuertas digitales. Para cada función booleana es posible diseñar
un circuito electrónico y viceversa, como las funciones booleanas solo requieren de los
operadores AND, OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente éstos operadores utilizando las compuertas lógicas homónimas
Un hecho interesante es que es posible implementar cualquier circuito electrónico
utilizando una sola compuerta, ésta es la compuerta NAND
Para probar que podemos construir cualquier función booleana utilizando sólo
compuertas NAND, necesitamos demostrar cómo construir un inversor (NOT), una
compuerta AND y una compuerta OR a partir de una compuerta NAND, ya que como
se dijo, es posible implementar cualquier función booleana utilizando sólo los
operadores booleanos AND, OR y NOT. Para construir un inversor simplemente
conectamos juntas las dos entradas de una compuerta NAND. Una vez que tenemos
un inversor, construir una compuerta AND es fácil, sólo invertimos la salida de una
compuerta NAND, después de todo, NOT ( NOT (A AND B)) es equivalente a A AND
B. Por supuesto, se requieren dos compuertas NAND para construir una sola
compuerta AND, nadie ha dicho que los circuitos implementados sólo utilizando
compuertas NAND sean lo óptimo, solo se ha dicho que es posible hacerlo.
Se dice que una variable tiene valor booleano cuando, en general, la variable contiene
un 0 lógico o un 1 lógico. Esto, en la mayoría de los lenguajes de programación, se
traduce en false (falso) o true (verdadero), respectivamente.
Una variable puede no ser de tipo booleano, y guardar valores que, en principio, no
son booleanos; ya que, globalmente, los compiladores trabajan con esos otros valores,
numéricos normalmente aunque también algunos permiten cambios desde, incluso,
caracteres, finalizando en valor booleano.
El 0 lógico

El valor booleano de negación suele ser representado como false, aunque también
permite y equivale al valor natural, entero y decimal (exacto) 0, así como la cadena
"false", e incluso la cadena "0".
El 1 lógico

5. En cambio, el resto de valores apuntan al valor booleano de afirmación, representado
normalmente comotrue, ya que, por definición, el valor 1 se tiene cuando no es 0.
Cualquier número distinto de cero se comporta como un 1 lógico, y lo mismo sucede
con casi cualquier cadena (menos la "false", en caso de ser ésta la correspondiente al
0 lógico).
Importancia del Algebra Booleana
A mediados del siglo XX el álgebra Booleana resultó de una gran importancia práctica,
importancia que se ha ido incrementando hasta nuestros días, en el manejo
de información digital (por eso hablamos de Lógica Digital). Gracias a ella, Shannon
(1930) pudo formular su teoría de la codificación y JohnVon Neumann pudo enunciar
el modelo de arquitectura que define la estructura interna de los ordenadores desde la
primera generación.
Todas las variables y constantes del Álgebra booleana, admiten sólo uno de dos
valores en sus entradas y salidas: Sí/No, 0/1 o Verdadero/Falso. Estos valores
bivalentes y opuestos pueden ser representados por números binarios de un dígito
(bits), por lo cual el Álgebra booleana se puede entender cómo el Álgebra
del Sistema Binario. Al igual que en álgebra tradicional, también se trabaja con letras
del alfabeto para denominar variables y formarecuaciones para obtener el resultado de
ciertas operaciones mediante una ecuación o expresión booleana. Evidentemente los
resultados de las correspondientes operaciones también serán binarios.
Todas las operaciones (representadas por símbolos determinados) pueden ser
materializadas mediante elementos físicos de diferentes tipos (mecánicos, eléctricos,
neumáticos o electrónicos) que admiten entradas binarias o lógicas y que devuelven
una respuesta (salida) también binaria o lógica. Ejemplos de dichos estados son:
Abierto/Cerrado (interruptor), Encendida/Apagada (bombilla), Cargado/Descargado
(condensador) , Nivel Lógico 0/Nivel lógico 1 (salida lógica de un circuito
semiconductor), etcétera.
Los dispositivos con los cuales se implementan las funciones lógicas son llamados
puertas (o compuertas) y, habitualmente, son dispositivos electrónicos basados
en transistores. Estos dispositivos, y otros que veremos a lo largo de esta unidad, son
los que permiten el diseño, y la ulterior implementación, de los circuitos de cualquier
ordenador moderno, así como de muchos de los elementos físicos que permiten la
existencia de lastelecomunicaciones modernas, el control de máquinas, etcétera. De
hecho, pensando en los ordenadores como una jerarquía de niveles, la base o nivel
inferior sería ocupada por la lógica digital (en el nivel más alto del ordenador
encontraríamos los actuales lenguajes de programación de alto nivel).
En esta unidad se representan las puertas lógicas elementales, algunas puertas
complejas y algunos ejemplos de circuitos digitales simples, así como algunas
cuestiones de notación. Por otra parte se plantean actividades de trabajo, muchas de
las cuales implican una respuesta escrita en vuestro cuaderno de trabajo. El deseo del
autor es que os resulte sencillo y ameno adentraros en el mundo de la lógica digital y
despertaros la curiosidad, tanto por ella, como por la matemática que subyace en ella.
Puertas lógicas
Una puerta lógica, o compuerta lógica, es un dispositivo electrónico el cual es la
expresión física de un operador booleano en la lógica deconmutación. Cada puerta

6. lógica consiste en una red de dispositivos interruptores que cumple las condiciones
booleanas para el operador particular. Son esencialmente circuitos de
conmutación integrados en un chip.
Claude Elwood Shannon experimentaba con relés o interruptores electromagnéticos
para conseguir las condiciones de cada compuerta lógica, por ejemplo, para la función
booleana Y (AND) colocaba interruptores en circuito serie, ya que con uno solo de
éstos que tuviera la condición «abierto», la salida de la compuerta Y sería = 0,
mientras que para la implementación de una compuerta O (OR), la conexión de los
interruptores tiene una configuración en circuito paralelo.
La tecnología microelectrónica actual permite la elevada integración
de transistores actuando como conmutadores en redes lógicas dentro de un
pequeño circuito integrado. El chip de la CPU es una de las máximas expresiones de
este avance tecnológico.
En nanotecnología se está desarrollando el uso de una compuerta lógica molecular,
que haga posible la miniaturización de circuitos.

Puerta SÍ o Buffer

Símbolo de la función lógica SÍ: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica SÍ, realiza la función booleana igualdad. En la práctica se suele utilizar
como amplificador de corriente o como seguidor de tensión, para adaptar impedancias
(buffer en inglés).
La ecuación característica que describe el comportamiento de la puerta SÍ es:

Su tabla de verdad es la siguiente:
Tabla de verdad puerta SI
Entrada A Salida A

7. 0 0
1 1
Puerta AND


Puerta AND con transistores

Símbolo de la función lógica Y: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica Y, más conocida por su nombre en inglés AND ( ),
realiza la función booleana de producto lógico. Su símbolo es un punto (·), aunque se
suele omitir. Así, el producto lógico de las variables A y B se indica como AB, y se lee
A y B o simplemente A por B.
La ecuación característica que describe el comportamiento de la puerta AND es:

Su tabla de verdad es la siguiente:
Tabla de verdad puerta AND
Entrada A Entrada B Salida
0 0 0
0 1 0

8. 1 0 0
1 1 1
Así, desde el punto de vista de la aritmética módulo 2, la compuerta AND implementa
el producto módulo 2.

Puerta OR


Puerta OR con transistores

Símbolo de la función lógica O: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica O, más conocida por su nombre en inglés OR ( ),
realiza la operación de suma lógica.
La ecuación característica que describe el comportamiento de la puerta OR es:

9. Su tabla de verdad es la siguiente:
Tabla de verdad puerta OR
Entrada A Entrada B Salida
0 0 0
0 1 1
1 0 1
1 1 1
Podemos definir la puerta O como aquella que proporciona a su salida un 1 lógico si al
menos una de sus entradas está a 1.

Puerta OR-exclusiva (XOR)

Símbolo de la función lógica O-exclusiva: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica OR-exclusiva, más conocida por su nombre en inglés XOR, realiza la
función booleana A'B+AB'. Su símbolo es el más (+) inscrito en un círculo. En la figura
de la derecha pueden observarse sus símbolos en electrónica.
La ecuación característica que describe el comportamiento de la puerta XOR es:
|-

10. Su tabla de verdad es la siguiente:
Tabla de verdad puerta XOR
Entrada A Entrada B Salida
0 0 0
0 1 1
1 0 1
1 1 0
Se puede definir esta puerta como aquella que da por resultado uno, cuando los
valores en las entradas son distintos. ej: 1 y 0, 0 y 1 (en una compuerta de dos
entradas). Se obtiene cuando ambas entradas tienen distinto valor.
Si la puerta tuviese tres o más entradas , la XOR tomaría la función de suma de
paridad, cuenta el número de unos a la entrada y si son un número impar, pone un 1 a
la salida, para que el número de unos pase a ser par. Esto es así porque la operación
XOR es asociativa, para tres entradas escribiríamos: a(bc) o bien (ab)c. Su
tabla de verdad sería:
XOR de tres entradas
Entrada A Entrada B Entrada C Salida
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

11. 1 1 1 1
Desde el punto de vista de la aritmética módulo 2, la puerta XOR implementa la suma
módulo 2, pero mucho más simple de ver, la salida tendrá un 1 siempre que el número
de entradas a 1 sea impar.

Puerta NO (NOT)

Símbolo de la función lógica NO: a) Contactos, b) Normalizado y c) No normalizada
La puerta lógica NO (NOT en inglés) realiza la función booleana de inversión o
negación de una variable lógica. Una variable lógica A a la cual se le aplica la
negación se pronuncia como "no A" o "A negada".


Puerta NOT con transistores
La ecuación característica que describe el comportamiento de la puerta NOT es:

Su tabla de verdad es la siguiente:

12. Tabla de verdad puerta NOT
Entrada A Salida
0 1
1 0
Se puede definir como una puerta que proporciona el estado inverso del que esté en
su entrada.
Puerta NO-Y (NAND)

Símbolo de la función lógica NO-Y: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica NO-Y, más conocida por su nombre en inglés NAND, realiza la
operación deproducto lógico negado. En la figura de la derecha pueden observarse
sus símbolos enelectrónica.


Puerta NAND con transistores

13. La ecuación característica que describe el comportamiento de la puerta NAND es:

Su tabla de verdad es la siguiente:
Tabla de verdad puerta NAND
Entrada A Entrada B Salida
0 0 1
0 1 1
1 0 1
1 1 0
Podemos definir la puerta NO-Y como aquella que proporciona a su salida un 0 lógico
únicamente cuando todas sus entradas están a 1.
Puerta NO-O (NOR)

Símbolo de la función lógica NO-O: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica NO-O, más conocida por su nombre en inglés NOR, realiza la
operación de suma lógica negada. En la figura de la derecha pueden observarse sus
símbolos en electrónica.

14. Puerta NOR con transistores

La ecuación característica que describe el comportamiento de la puerta NOR es:

Su tabla de verdad es la siguiente:
Tabla de verdad puerta NOR
Entrada A Entrada B Salida
0 0 1
0 1 0
1 0 0
1 1 0
Podemos definir la puerta NO-O como aquella que proporciona a su salida un 1 lógico
sólo cuando todas sus entradas están a 0. La puerta lógica NOR constituye un
conjunto completo de operadores.

15. Puerta equivalencia (XNOR)

Símbolo de la función lógica equivalencia: a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica equivalencia, realiza la función booleana AB+~A~B. Su símbolo es
un punto (·) inscrito en un círculo. En la figura de la derecha pueden observarse sus
símbolos en electrónica. La ecuación característica que describe el comportamiento de
la puerta XNOR es:

Su tabla de verdad es la siguiente:
Tabla de verdad puerta XNOR
Entrada A Entrada B Salida
0 0 1
0 1 0
1 0 0
1 1 1
Se puede definir esta puerta como aquella que proporciona un 1 lógico, sólo si las dos
entradas son iguales, esto es, 0 y 0 ó 1 y 1 (2 encendidos o 2 apagados). Sólo es
verdadero si ambos componentes tiene el mismo valor lógico
[editar]Conjunto de puertas lógicas completo
Un conjunto de puertas lógicas completo es aquel con el que se puede
implementar cualquier función lógica. A continuación se muestran distintos conjuntos
completos (uno por línea):
 Puertas AND, OR y NOT.
 Puertas AND y NOT.

16.  Puertas OR y NOT.
 Puertas NAND.
 Puertas NOR.
Además, un conjunto de puertas lógicas es completo si puede implementar todas las
puertas de otro conjunto completo conocido. A continuación se muestran las
equivalencias al conjunto de puertas lógicas completas con las funciones NAND y
NOR.
Conjunto completo de puertas lógicas utilizando sólo
puertas NAND. Equivalencias.
Conjunto de puertas lógicas completo :
A B




Salida
función NAND(A,B)
Salida
función NOR(A,B)
1 1 0 1 1 1

0 0
1 0 0 0 1 0

1 0
0 1 1 0 1 1

1 0
0 0 1 0 0 1

1 1
Equivalencias del conjunto completo anterior con sólo puertas NAND :




Equivalencias del conjunto completo anterior con sólo puertas NOR :



