Algebra Booleana

Algebra Booleana

Presenta: Marcos Omar Cruz Ortega

17/12/2008

2

Tabla de Contenido

1 Introducción al Algebra Booleana ............................................................................................... 3

2 Álgebra Booleana ........................................................................................................................ 4

2.1 Postulados del álgebra booleana ........................................................................................ 4

2.2 Ejemplos de álgebras de Boole ........................................................................................... 5

2.2.1 ÁLGEBRA DE CONJUNTOS ........................................................................................... 5

2.2.2 CIRCUITOS DE CONMUTACIÓN ................................................................................... 8

2.2.3 LÓGICA PROPOSICIONAL ............................................................................................. 9

2.3 Teoremas del algebra booleana ........................................................................................ 11

2.3.1 Ejemplos de simplificación de expresiones booleanas ............................................. 16

2.4 Funciones booleanas ......................................................................................................... 16

2.4.1 FUNCIONES BOOLEANAS DE UNA Y DOS VARIABLES ............................................... 18

2.4.2 SÍMBOLOS DE PUERTAS LÓGICAS .............................................................................. 19

2.4.3 EQUIVALENCIA ENTRE PUERTAS LÓGICAS ................................................................ 22

3 Modelo de John von Neumann (principios de 1950's).............................................................. 24

4 Concepto De Programa Almacenado ........................................................................................ 29

5 Lenguaje De Maquina Instrucciones y Datos ............................................................................ 30

5.1 Lenguaje de Máquina .................................................................................................... 30

5.2 Lenguaje Ensamblador .................................................................................................. 31

5.3 Ciclo De Ejecución De Instrucciones .................................................................................. 31

3

1 Introducción al Algebra Booleana

Un algebra booleana es una estructura matemática con dos operaciones binarias y

una unitaria que tiene características similares al algebra de números reales, pero que

difiere en algunos otros aspectos. En muchos de los casos el dominio consiste en dos

valores cero y uno (falso y verdadero). Para mayor facilidad en su manejo las

operaciones se representan por +y*, el operador unitario se puede representar mediante

una raya superior a’.

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.

4

2 Álgebra Booleana

La herramienta fundamental para el análisis y diseño de circuitos digitales es el

Álgebra Booleana.

Esta álgebra es un conjunto de reglas matemáticas (similares en algunos aspectos

al álgebra convencional), pero que tienen la virtud de corresponder al comportamiento de

circuitos basados en dispositivos de conmutación (interruptores, relevadores, transistores,

etc). En este capítulo se presentan los postulados que definen el álgebra booleana, se

presentan en forma de teoremas los resultados más importantes, se presentan también

los tres ejemplos clásicos de álgebras boolenas

(Lógica proposicional, álgebra de conjuntos, álgebra de switches) y herramientas

básicas como tablas de verdad y diagramas de Venn.

2.1 Postulados del álgebra booleana

El Álgebra de Boole, fue presentada originalmente por el inglés George Boole, en

el año de 1854 en su artículo "An Investigation of the Laws of Thoght ... ", sin embargo,

las primeras aplicaciones a circuitos de conmutación fueron desarrolladas por Claude

Shannon en su tesis doctoral "Análisis simbólico de los circuitos de conmutación y relés"

hasta 1938. A continuación se presentan los postulados fundamentales del álgebra de

Boole

Postulado 1. Definición.

El álgebra booleana es un sistema algebraico definido en un conjunto B, el cual

contiene dos o más elementos y entre los cuales se definen dos operaciones

denominadas "suma u operación OR" ( + ) y "producto o multiplicación u operación AND"

(), las cuales cumplen con las siguientes propiedades:

5

Postulado 2. Existencia de Neutros.

Existen en B el elemento neutro de la suma, denominado O y el neutro de la

multiplicación, denominado 1, tales que para cualquier elemento x de s: (a) x + O = x (b) x.

1 = x

Postulado 3. Conmutatividad.

Para cada x, y en B: (a) x+y = y+x (b) xy =yx

Postulado 4. Asociatividad.

Para cada x, y, z en B: (a) x + (y + z) = (x + y) + z (b) x(yz) = (xy) z

Postulado 5. Distributividad.

Para cada x, y, z en B: (a) x+(yz)=(x+y) (x+z) (b) x(y+z)=(xy)+(xz)

Postulado 6. Existencia de Complementos.

Para cada x en B existe un elemento único denotado x (también denotado x’), llamado

complemento de x tal que (a) x+x = 1 (b) x x = O

2.2 Ejemplos de álgebras de Boole

En un principio algunos de los postulados anteriores pueden parecer extraños,

especialmente aquellos que son diferentes al álgebra con número reales (como el 5a, el

6a y el 6b), y puede ser difícil encontrar situaciones de interés que cumplan al pie de la

letra con cada uno de ellos, sin embargo, existen varios ejemplos, de los cuales se

presentan los siguientes tres clásicos, en los cuales se verifica que se trata de álgebras

de Boole, es decir, que se cumple postulado por postulado.

2.2.1 ÁLGEBRA DE CONJUNTOS

1. Para este ejemplo el conjunto B es el conjunto de todos los conjuntos a tratar. La

suma es la unión de conjuntos (U) y la multiplicación es la intersección () de

conjuntos.

2. Existencia de neutros. El neutro de la unión es el conjunto vacío F , mientras que

el neutro de la intersección es el conjunto universo U, ya que para cualquier

conjunto arbitrario A, A U F = A y A U = A.

3. Conmutatividad. La unión y la intersección son conmutativas, ya que para cualquier par

de conjuntos A, B: A U B = B U A y A ∩B = B ∩A

6

4. Asociatividad. La unión y la intersección de conjuntos son asociativas, ya que para

cualesquiera tres conjuntos A, B, C: A U (B U C) = (A U B) U C y A (B C) = (A

B) C

5. Distributividad. La unión de conjuntos es distributiva sobre la intersección, y

viceversa, la intersección es distributiva sobre la unión, ya que para cualesquiera

tres conjuntos A, B, C: A U (B C) = (A U B) (A U C) y A (B U C) = (A B) U (A

C)

6. Existencia de complementos. El conjunto complemento Ac cumple con las

propiedades deseadas: A U Ac = U y A Ac = F

Algunos de los enunciados anteriores pueden ser difíciles de obtener, o recordar,

especialmente la distributividad, por ello, es conveniente tener en cuenta una herramienta

gráfica en la cual estos enunciados se vuelven evidentes casi a simple vista:

2.2.1.1 DIAGRAMAS DE VENN

En la siguiente figura se muestran diagramas de Venn para los conjuntos A, B, A U B y A ∩ B

7

A continuación se muestra el conjunto A y su complemento Ac.

Ejemplo.- En los siguientes diagramas de Venn se ilustra

...