Algebra Booleana

Indice
1.
Introducción
2. Reseña
Histórica
3. Álgebra
Booleana
4. Álgebra Booleana y circuitos
electrónicos
5. Circuitos
Combinacionales
6. Relación entre la lógica
combinacional y secuencial con la
programación
7. Los Teoremas Básicos Del
Algebra Booleana
8. Bibliografía

1.
Introducción

Las álgebras booleanas, estudiadas por primera
vez en detalle por George Boole , constituyen un área de
las matemáticas que ha pasado a ocupar un lugar
prominente con el advenimiento de la computadora
digital. Son usadas ampliamente en el diseño
de circuitos de
distribución y computadoras,
y sus aplicaciones van en aumento en muchas otras áreas.
En el nivel de lógica
digital de una computadora,
lo que comúnmente se llama hardware, y que está
formado por los componentes electrónicos de la
máquina, se trabaja con diferencias de tensión, las
cuales generan funciones que son
calculadas por los circuitos que
forman el nivel. Éstas funciones, en la
etapa de diseña del hardware, son interpretadas
como funciones de boole.
En el presente trabajo se intenta dar una definición de lo
que es un álgebra de
boole; se tratan las funciones booleanas,
haciendo una correlación con las fórmulas
proposicionales. Asimismo, se plantean dos formas
canónicas de las funciones booleanas, que son
útiles para varios propósitos, tales como el de
determinar si dos expresiones representan o no la misma función.
Pero para otros propósitos son a menudo engorrosas, por
tener más operaciones que
las necesarias. Particularmente, cuando estamos construyendo los
circuitos electrónicos con que implementar funciones
booleanas, el problema de determinar una expresión
mínima para una función es
a menudo crucial. No resultan de la misma eficiencia en
dinero y
tiempo,
principalmente, dos funciones las cuales calculan lo mismo pero
donde una tiene menos variables y lo
hace en menor tiempo. Como
solución a este problema, se plantea un método de
simplificación, que hace uso de unos diagramas
especiales llamados mapas o diagramas de
Karnaugh, y el cual tiene la limitación de poder trabajar
adecuadamente sólo con pocas variables.
Se realizan estas presentaciones con el fin de demostrar la
afinidad existente entre el álgebra de
boole y la lógica
proposicional, y con el objeto de cimentar el procedimiento de
simplificación presentado en la lógica de
proposiciones.

2. Reseña
Histórica

A mediados del siglo XIX, George Boole (1815-1864), en
sus libros: "The
Mathematical Analysis of Logic" (1847) y "An Investigation of te
Laws of Thought" (1854), desarrolló la idea de que las
proposiciones lógicas podían ser tratadas mediante
herramientas
matemáticas. Las proposiciones
lógicas (asertos, frases o predicados de la lógica
clásica) son aquellas que únicamente pueden tomar
valores
Verdadero/Falso, o preguntas cuyas únicas respuestas
posibles sean Sí/No. Según Boole, estas
proposiciones pueden ser representadas mediante símbolos y
la teoría
que permite trabajar con estos símbolos, sus entradas
(variables) y sus salidas (respuestas) es la Lógica
Simbólica desarrollada por él. Dicha lógica
simbólica cuenta con operaciones
lógicas que siguen el comportamiento
de reglas algebraicas. Por ello, al conjunto de reglas de la
Lógica Simbólica se le denomina ÁLGEBRA DE
BOOLE.

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 John Von 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 formar ecuaciones
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 las
telecomunicaciones 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.

3. Á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).
• 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
   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 si o no.
Representemos el voto de cada uno por xi. La
función devolverá sí (1) cuando el numero 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. Álgebra Booleana y
circuitos electrónicos

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.
La otra compuerta que necesitamos sintetizar es la compuerta
lógica OR, ésto es sencillo si utilizamos los
teoremas de DeMorgan, que en síntesis
se logra en tres pasos, primero se reemplazan todos los
"·" por "+" después se invierte cada
literal y por último se niega la totalidad de la
expresión:

A OR B
A AND B…………………..Primer paso para aplicar el teorema
de DeMorgan
A' AND B'…………………Segundo paso para aplicar el
teorema de DeMorgan
(A' AND B')'………………Tercer paso para aplicar el teorema
de DeMorgan
(A' AND B')' = A' NAND B'…..Definición de OR utilizando
NAND

Si se tiene la necesidad de construir diferentes
compuertas de la manera descrita, bien hay dos buenas razones, la
primera es que las compuertas NAND son las más
económicas y en segundo lugar es preferible construir
circuitos complejos utilizando los mismos bloques básicos.
Observe que es posible construir cualquier circuito lógico
utilizando sólo compuertas de tipo NOR (NOR = NOT(A OR
B)). La correspondencia entre la lógica NAND y la NOR es
ortogonal entre la correspondencia de sus formas
canónicas. Mientras que la lógica NOR es
útil en muchos circuitos, la mayoría de los
diseñadores utilizan lógica NAND.

5. Circuitos
Combinacionales

Un circuito combinacional es un sistema que contiene
operaciones booleanas básicas (AND, OR, NOT), algunas
entradas y un juego de salidas, como cada salida corresponde a
una función lógica individual, un circuito
combinacional a menudo implementa varias funciones booleanas
diferentes, es muy importante recordar éste echo, cada
salida representa una función booleana
diferente.

Un ejemplo común de un circuito combinacional es
el decodificador de siete segmentos, se trata de un circuito que
acepta cuatro entradas y determina cuál de los siete
segmentos se deben iluminar para representar la respectiva
entrada, de acuerdo con lo dicho en el párrafo
anterior, se deben implementar siete funciones de salida
diferentes, una para cada segmento. Las cuatro entradas para cada
una de éstas funciones booleanas son los cuatro bits de un
número binario en el rango de 0 a 9. Sea D el bit de alto
orden de éste número y A el bit de bajo orden, cada
función lógica debe producir un uno (para el
segmento encendido) para una entrada dada si tal segmento en
particular debe ser iluminado, por ejemplo, el segmento e
debe iluminarse para los valores 0000, 0010, 0110 y
1000.

En la siguiente tabla se puede ver qué segmentos
deben iluminarse de acuerdo al valor de entrada, tenga en cuenta
que sólo se están representando valores en el rango
de 0 a 9, los decodificadores para las pantallas de siete
segmentos comerciales tienen capacidad para desplegar valores
adicionales que corresponden a las letras A a la F para
representaciones hexadecimales, sin embargo la mecánica para iluminar los respectivos
segmentos es similar a la aquí representada para los
valores numéricos.

Los circuitos combinacionales son la base de muchos
componentes en un sistema de cómputo básico, se
puede construir circuitos para sumar, restar, comparar,
multiplicar, dividir y muchas otras aplicaciones
más.

Circuitos Secuenciales
Un problema con la lógica secuencial es su falta de
"memoria". En
teoría, todas las funciones de salida en un circuito
combinacional dependen del estado actual
de los valores de entrada, cualquier cambio en los
valores de entrada se refleja (después de un intervalo de
tiempo llamado retardo de propagación) en las salidas.
Desafortunadamente las computadoras
requieren de la habilidad para "recordar" el resultado de
cálculos pasados. Éste es el dominio de la
lógica secuencial. Una celda de memoria es un
circuito electrónico que recuerda un valor de entrada
después que dicho valor ha desaparecido. La unidad de
memoria más básica es el flip-flop Set/Reset.
Aunque recordar un bit sencillo es importante, la mayoría
de los sistemas de
cómputo requieren recordar un grupo de bits,
ésto se logra combinando varios flip-flop en paralelo, una
conexión de éste tipo recibe el nombre de registro. A
partir de aquí es posible implementar diferentes circuitos
como registros de
corrimiento y contadores, éstos últimos
también los conocemos como circuitos de reloj. Con los
elementos mencionados es posible construir un microprocesador
completo.

6. Relación entre la
lógica combinacional y secuencial con la
programación

En ésta lección hemos dado una repasada
muy básica a los elementos que forman la base de los
modernos sistemas de cómputo, en la sección
dedicada al diseño electrónico estudiaremos a
profundidad los conceptos aquí presentados, pero para
aquellos que están más interesados en el aspecto
programático podemos decir que con los elementos vistos en
ésta lección es posible implementar máquinas
de estado, sin
embargo la moraleja de ésta lección es muy
importante: cualquier algoritmo que
podamos implementar en software, lo podemos a su
vez implementar directamente en hardware. Ésto sugiere que
la lógica booleana es la base computacional en los
modernos sistemas de cómputo actuales. Cualquier programa que
Usted escriba, independientemente del lenguaje que
utilice, sea éste de alto ó bajo nivel, se puede
especificar como una secuencia de ecuaciones
booleanas.

Un hecho igualmente interesante es el punto de vista
opuesto, es posible implementar cualquier función de
hardware directamente en software, en la actualidad
ésta es la función principal del lenguaje
ensamblador y otros con capacidad de trabajar directamente en
hardware, como el C y el C++. Las consecuencias de éste
fenómeno apenas se están explotando, se infiere la
existencia de un futuro muy prometedor para el profesional de la
programación, especialmente aquellos
dedicados a los sistemas incrustados (embedded systems), los
microcontroladores y los profesionales dedicados a
la Programación
Orientada a Objetos. Para tener éxito
en éstos campos de la investigación es fundamental comprender las
funciones booleanas y la manera de implementarlas en software.
Aún y cuando Usted no desee trabajar en hardware, es
importante conocer las funciones booleanas ya que muchos
lenguajes de alto nivel procesan expresiones booleanas, como es
el caso de los enunciados if-then ó los bucles
while.

7. Los Teoremas Básicos
Del Algebra Booleana

Los Teoremas Básicos del álgebra Booleana
son:

TEOREMA 1
Ley Distributiva
A (B+C) = AB+AC

TEOREMA 2

A+A = A

AA = A

TEOREMA 3

Redundancia

A+AB = A

A (A+B) = A

TEOREMA 4

0+A = A

Equivalente a una compuerta
OR con una de sus terminales
conectada a tierra

1A = A

Equivalente a una compuerta AND con una de sus
terminales conectada a 1

1+A = 1

0A = 0

8.
Bibliografía

• Matemática discreta Kolmant
• http://es.software.yahoo.com/fot/ftxt/karmap.html
• http://www.terra.es/personal/jftjft/
  algebra/boole/algboole.htm
• http://www.terra.es/personal/jftjft/algebra/
  boole/introduccion.htm
• http://es.dir.yahoo.com/ciencia_y_tecnologia/
  matematicas/algebra/algebra_de_boole/
• http://es.dir.yahoo.com/ciencia_y_tecnologia/
  matematicas/algebra/algebra_de_boole
• http://www.conocimientosweb.net/portal/directorio
• http://www.zabalnet.com/intro/cursos/03_algebra.htm
• http://www.inf.ufsc.br/ine5365/algboole.html
• http://www.ncc.up.pt/~zp/aulas/9899/me/trabalhos/
  alunos/circuitos_logicos/algboole.html
• http://buscador.hispavista.es/logica–algebra-de-boole

Autor:

Arroyo Cabrera César Edad: 19
años   

Collantes Arana Alan
A.                             

Montero Maco Oscar Enrique  edad 18
años

Ramos Layza Renzo Roberto
Sari Bustos Dany Richard
Tarrillo tarrillo José Isrrael.
Area Matematicas
Trujillo-Perú
2003