ALGEBRA DE BOOLER

PRESENTADO POR:

EDWIN ANDES ORTIZ

JAVIER ARAGÓN BOHORQUEZ

HÉCTOR JULIAN PIMENTEL MARÍN

PRESENTADO A:

ING. DEIVIS SUAREZ

UNIVERSIDAD COOPERATIVA DE COLOMBIA

BOGOTÁ D.C

2009

TABLA DE CONTENIDO

1) INTRODUCCIÓN

2) ¿QUÉ SON LAS EXPRESIONES BOOLEANAS?

3) INTRODUCCIÓN AL ALGEBRA BOOLEANA

3.1) PROPIEDADES

· PROPIEDAD CONMUTATIVA

· PROPIEDAD DE IDENTIDAD

· PROPIEDAD DISTRIBUTIVA

· ELEMENTO DENOMINADO

3.2) TEOREMAS

· TEOREMA 1

· TEOREMA 2

· TEOREMA 3

· TEOREMA 4

· TEOREMA 5

· TEOREMA 6

· TEOREMA 7

4) FORMAS CANÓNICAS

· MINI TÉRMINOS

· MAXI TÉRMINOS

5) FUNCIONES BOOLEANAS

6) EJERCICIO PROPUESTO

7) CONCLUSIÓN

8) BIBLIOGRAFÍA

9) DIRECCIÓN DE BLOG

INTRODUCCIÓN

El objetivo de este ensayo es recopilar las bases y conceptos del algebra Booleana, pretendiendo con esto que los interesados abstraigan la información necesaria del tema para poder desenvolverse en el área en la cual se requiera total o parcialmente conocimientos del tema.

El desarrollo del tema a sido tratado de manera que se entienda de forma general ya que es aplicada con base a los conceptos universales; debido que para el desarrollo del tema se usa una única terminología.

¿QUÉ SON LAS EXPRESIONES BOOLEANAS?

Una expresión booleana es aquella que al evaluarla da como resultado un valor de falso o verdadero, es un valor lógico. Por ejemplo:

3 > 2

Si se evalúa la expresión anterior evidentemente nos va a generar un valor lógico verdadero ya que el numero 3 es mayor al numero 2.

Tenemos otro ejemplo:

A > B

Esta expresión lógica da un valor verdadero si el contenido del campo A es mayor al contenido del campo B. Si el contenido del campo A es menor o igual al contenido del campo B, esta expresión booleana da como resultado un valor lógico falso.

Veamos la siguiente expresión booleana:

A > B Y X = Z

Esta expresión booleana se compone de dos partes. La primera A > B y la segunda X = Z. cuando se entra a evaluar la expresión se realiza de la siguiente forma. Primero la expresión A > B y determina su valor lógico, luego evalúa la expresión X = Z y determina su valor lógico.

Supongamos que los valores almacenados en los campos A, B, X y Z son 1, 3, 5, 2 respectivamente. De acuerdo a estos valores la expresión A > B da como resultado un valor lógico falso y la expresión X = Z da como resultado un valor lógico falso. Una vez evaluada las dos expresiones determinamos que la expresión en total es falsa.

INTRODUCCIÓN AL ALGEBRA DE BOOLE

Para los matemáticos, el álgebra de Boole se encuentra entre los estudios de estructuras ordenadas particulares llamadas <> (*). Los elementos de un conjunto que forman un retículo distributivo complementario, que contienen un elemento nulo y un elemento universal, constituyen un elemento nulo y un elemento universal, constituyen un algebra de Boole. Pero gracias al teorema de Stone sobre la representación de las algebras de Boole, es fácil exponer rápidamente el tema sirviéndose de un sistema de conjuntos, es decir, de la familia de las partes de un conjunto fundamental.

(*) Un retículo es un conjunto parcialmente ordenado en el cual todo par de elementos posee un límite superior y un límite inferior.

Ø PROPIEDADES:

Toda clase de conjuntos del algebra de Boole son elementos que se pueden tomar dos valores perfectamente diferenciables que designamos por 0 y 1, relacionados por dos operaciones binarias básicas multiplicación y suma. Generalmente la operación de producto puede simbolizarse mediante la unión de dos variables sin símbolo alguno entre ellas.

ü Propiedad conmutativa: a y b son elementos del algebra de Boole y ambas son operaciones conmutativas se verifica que:

a + b = b + a a . b = b . a

ü Propiedad de Identidad: dentro del algebra de Boole existen dos elementos neutros el 0 y el 1, que cumplen la propiedad de identidad a cada una de dichas operaciones:

0 + a = a 1 . a = a

ü Propiedad distributiva: cada operación es distributiva respecto a la otra por tanto:

a . (b + c) = (a . b) + (a . c) a + (b . c) = (a + b) . (a + c)

ü Elemento denominado: para cada elemento del algebra de Boole existe un elemento denominado A tal que:

a + a = 1 a . a = 0

Este postulado define una nueva operación fundamental que es la inversión o complementación de una variable. La variable A se encuentra siempre en un estado distinto al de negación de A.

a a

0 1

1 0

Físicamente son varios los conjutos que poseen dos operaciones binarias que cumplen todas las propiedades desarrolladas.

Ejemplo de estos conjuntos son el algebra de las prepociciones o juicios formales y el algebra de la conmutación, formada por elementos que pueden tomar dos estados perfectamente diferenciables.

Los primeros circuitos de conmutación o lógicos utilizados han sido los contactos que pueden ser empleados para memorizar más fácilmente las leyes del algebra de Booler donde se destacan dos operaciones básicas:

1) La suma: se asimila a la operación en paralelo de contactos.

2) El producto: se asimila a la conexión operación en cerie de contactos.

El inverso de un contacto es otro cuyo estado es siempre el opuesto del primero; es decir cuando el primero está abierto su opuesto debe estár cerrado y viceversa.

El elemento 0 (cero), es un contacto que está siempre abierto, mientras que el elemento 1 (uno), indica que esta cerrado. Además se considera una función de transmisicon entre los dos terminales de un circuito de contactos que toma el valor 1 (uno) cuando existe un camino para la circulación de corriente entre ellos (físicamente llamado corto circuito) y el valor 0 (cero) sino existe dicho camino (circuito abierdo).

a b

a = a

a + b b + a

a b = b a

a . b b . a

0

a = a

0 + a

Teorema 1: dualidad.

El concepto de dualidad permite formalizar este hecho: a toda relación o ley lógica le corresponderá su dual, formada mediante el intercambio de los operadores unión (suma lógica) con los de intersección (producto lógico), y de los 1 con los 0.

Además hay que cambiar cada variable por su negada. Esto causa confusión al aplicarlo en los teoremas básicos, pero es totalmente necesario para la correcta aplicación del principio de dualidad. Véase que esto no modifica la tabla adjunta.

	Adición	Producto
Teorema 2: Para cada elemento A del algebra de Boole se verifica que:
Teorema 3: Para cada elemento del algebra de Boole se verifica que:
Teorema 4: Para cada elemento del algebra de Boole A y B se verifica como (ley de absorción):	a + (a . b) = a
Teorema 5: Las operaciones más (+) y producto (.) serán asociativas:	a + (b + c) = (a + b) + c = a + b + c	a . (b . c) = (a . b) . c = a .b .c
Teorema 6: Para todo elemento del algebra de Boole se verifica que:	1 . a = a a . (b + c) = (a . b) + (a . c)	a + (b . c) = (a + b) . (a + c)
Teorema 7: Para todo algebra de Boole se verifican las leyes de Morgan:	a + b + c + … + n = a . b . c … .n	ṽ . ỹ . ᾱ … . ῆ = a + v + y … + n

FORMAS CANÓNICAS

Se conoce como canónico una función lógica a todos los productos de una suma en las cuales aparecen variables en forma directa o inversa. Las variables con operadores lógicos se expresan como formas canonícas utilizando los conceptos de mini términos y maxi términos; todas las funciones se pueden expresar en términos canónicos. Las funciones Booleanas expresadas en disyunción lógica (OR) de los mini términos se conoce como suma de productos y su dual de Morgan es el producto de sumas la cual es una función expresada como un conjunción lógica (AND) de maxi términos.

Mini términos:

Para una función booleana de n variables x₁,...x_n, un producto booleano en el que cada una de las n variables aparece una sola vez (negada o sin negar) es llamado mini término. Es decir, un mini término es una expresión lógica de n variables consistente únicamente en el operador conjunción lógica (AND) y el operador complemento o negación (NOT).

Por ejemplo, abc, ab'c y abc' son ejemplos de mini términos para una función booleana con las tres variables a, b y c.

Maxi términos

Un maxi término es una expresión lógica de n variables que consiste únicamente en la disyunción lógica y el operador complemento o negación. Los maxi términos son una expresión dual de los mini términos. En vez de usar operaciones AND utilizamos operaciones OR y procedemos de forma similar.

Por ejemplo, los siguientes términos canónicos son maxi términos:

a + b' + c

a' + b + c

Las tres funciones elementales suma, producto e inversión lógica pueden ser relacionadas mediante la función OR y AND, aplicadas al teorema de Morgan tendremos que:

La inversión se representa en general mediante un sircuito, por lo tanto la función OR y AND se deducen de las funciones OR y AND añadiéndolas a un circuito; de hay que:

a

F = a . b

b

a

F = a . b

b

a F = a + b

b

a F = a + b

b

FUNCIONES BOOLEANAS

Se denomina función lógica o booleana a aquella función matemática cuyas variables son binarias y están unidas mediante los operadores del álgebra de Boole suma lógica (+), producto lógico (·) o negación(').

Existen distintas formas de representar una función lógica, entre las que podemos destacar las siguientes:

· Algebraica

· Por tabla de verdad

· Numérica

· Gráfica

El uso de una u otra, como veremos, dependerá de las necesidades concretas en cada caso.

Ø Algebraica

Se utiliza cuando se realizan operaciones algebraicas. Ejemplo con distintas formas en las que se puede expresar algebraicamente una misma función de tres variables.

a) F = [(A + BC’)’ + ABC]’ + AB’C

b) F = A’BC’ + AB’C’ + AB’C + ABC’

c) F = (A + B + C)(A + B + C’)(A + B’ + C’)(A’ + B’ + C’)

Ø Tabla de verdad

Una tabla de verdad contiene todos los valores posibles de una función lógica dependiendo del valor de sus variables. El número de combinaciones posibles para una función de n variables vendrá dado por 2ⁿ. Una función lógica puede representarse algebraicamente de distintas formas como acabamos de ver, pero sólo tiene una tabla de verdad. La siguiente tabla corresponde a la función lógica del punto anterior.

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

La forma más cómodo para ver la equivalencia entre una tabla de verdad y una expresión algebraica es cuando esta última se da en su forma canónica. Así, la función canónica de suma de productos

F = A’BC’ + AB’C’ + AB’C + ABC’

Ø Numérica

La representación numérica es una forma simplificada de representar las expresiones canónicas. Si consideramos el criterio de sustituir una variable sin negar por un 1 y una negada por un 0, podremos representar el término, ya sea una suma o un producto, por un número decimal equivalente al valor binario de la combinación. Por ejemplo, los siguientes términos canónicos se representarán del siguiente modo (observe que se toma el orden de A a D como de mayor a menor peso):

AB’CD = 1011₂ = 11₁₀

A’ + B + C’ + D’ = 0100₂ = 4₁₀

Ø Circuito lógico.

Es la representación gráfica que se utiliza en circuitos y esquemas electrónicos. En la siguiente figura se representan gráficamente se representa con símbolos no normalizados.

A

B

C

Símbolo de la multiplicación

Símbolo de la suma

El anterior diagrama es sacado de la ecuación:

[ a (b + c) + b (-a + c) + -c (-b . a) ] (-c . –b . –a )

F (a,b,c)=[a (b+c)+b(a+c)+c (b.a)](c.b.a)

CONCLUSIÓN

Al darnos cuenta de que el algebra Booleana es un tema que podemos aplicar en áreas mas complejas como lo puede ser la programación, se diseño este ensayo como un método fácil y preciso para aquellos que necesiten información para guiarse en los conceptos básicos de este tema en el área requerida.

Se espera que los consultores sobre el tema les sea de gran utilidad la información plasmada en este ensayo, que también lo encuentran en nuestro blog, al ser una manera fácil de adquirirlo por medio de la herramienta del internet.

BIBLIOGRAFÍA

Santamaría B. César A: “Algoritmos: conceptos básicos”, kimpres Ltda, 5º edición, 2002.

Faure, Robert: “Elementos de investigación operativa”, ediciones ICE, 1975, capitulo 5 paginas 67 – 78.

Apuntes tomados en clase, entre las fechas 13 y 15 de mayo del año en curso.

GOOGLE.WIKIPEDIA:

ü http://es.wikipedia.org/wiki/Algebra_booleana#.C3.81lgebra_de_Boole_aplicada_a_la_inform.C3.A1tica

ü http://es.wikipedia.org/wiki/Funci%C3%B3n_booleana

Dirección del blog