Álgebra De Conmutación. Puertas Lógicas
Enviado por rafa_16 • 7 de Febrero de 2012 • 3.389 Palabras (14 Páginas) • 616 Visitas
Tema 3 Álgebra de Conmutación. Puertas Lógicas
3.1. Álgebra Booleana.
3.1.1. Postulados
3.1.2. Teoremas
3.2. Funciones Lógicas
3.3. Formas canónicas: Mintéminos y Maxtérminos
3.4. Optimización de Funciones Lógicas
3.4.1. Mapas de Karnaugh
3.4.2. Simplificación mediante mapas de Karnaugh.
3.4.3. Simplificación de funciones incompletamente específicadas.
3.5. Bases de Implementación: Puertas Lógicas. Estándares.
3.5.1. Funciones básicas.
3.5.2. Simbologías de representación
3.5.3. Suficiencia de los operadores NAND y NOR
3. 1. Álgebra Booleana.
El álgebra de Boole es una estructura matemática que resulta muy adecuada para el diseño de los Sistemas Digitales.
La forma más simple de definir un álgebra de Boole es a partir de un conjunto de postulados básicos o axiomas. Estos axiomas no tienen demostración y además han de ser independientes unos de otros y no pueden contradecirse.
3.1.1. Postulados
El matemático Huntington propuso el siguiente conjunto de postulados independientes y consistentes para definir un álgebra de Boole.
POSTULADO 1:
Se define un conjunto de elementos C={a,b,c,d…}, donde tales elementos pueden estar sujetos a relaciones de equivalencia (a=b). Este conjunto debe tener al menos dos elementos distintos.
POSTULADO 2:
Se definen dos leyes o reglas de composición interna denotadas por “+” y “•” tales que:
POSTULADO 3:
Existen en el conjunto C dos elementos distintos 0 y 1 llamados neutros tales que:
POSTULADO 4
Las leyes de composición interna “+” y “•” son ambas conmutativas es decir:
POSTULADO 5
Cada una de estas leyes de composición interna es distributiva respecto de la otra, es decir:
POSTULADO 6
Para cualquier elemento de C existe un único elemento simétrico (complementario o inverso) que también pertenece a C, es decir:
Este conjunto de axiomas no es el único para definir el álgebra de Boole. Existen muchos conjuntos que pueden verificar estas propiedades, por ejemplo dado un conjunto cualquiera A, un álgebra de Boole se podría definir sobre el conjunto de partes de A, las operaciones de unión e intersección y sería un álgebra de Boole.
El conjunto C que nosotros utilizaremos tendrá como elementos variables binarias que solo pueden tomar valores 0 y 1. Esto da lugar a un caso particular de un álgebra de Boole, denominada álgebra de Conmutación.
Puede observarse que entre los postulados del álgebra de Boole, que hemos establecido, no se incluye la propiedad asociativa, el motivo es que puede demostrarse a partir de ellos y por tanto no pueden incluirse entre ellos porque dejarían de ser independientes.
Entre los postulados existe una cierta simetría o dualidad entre las dos leyes de composición interna, en efecto, las dos afirmaciones que se hacen en cada postulado son idénticas si sustituimos el 0 por el 1 y la operación “+” por “•”.
3.1.1. Teoremas
Vamos a exponer una serie de propiedades o teoremas que se deducen de los postulados planteados anteriormente. En dichos teoremas también se verifica esa propiedad de dualidad.
TEOREMA 1
Dualmente
Demostración:
Dualmente:
TEOREMA 2: Idempotencia
Dualmente
Demostración:
Dualmente:
TEOREMA 3: Absorción
Dualmente
Demostración:
Dualmente
TEOREMA 4: Involución
Demostración:
TEOREMA 5:
Dualmente
Demostración:
Dualmente
TEOREMA 6: Asociativa
Dualmente
Demostración:
}
Por tanto
La demostración de la parte dual sería análoga, basta con intercambiar las operaciones “+” y “•”.
TEOREMA 7: Leyes de D’Morgan
Demostración:
Sabemos que
Por tanto
La demostración de la parte dual sería análoga, basta con intercambiar las operaciones “+” y “•”.
3.2. Funciones Lógicas
Se define una variable booleana (o variable de Boole) como una variable matemática que puede asumir sólo dos valores el 0 y el 1.
Una función Booleana (o función lógica) es una expresión formada por un conjunto de variables booleanas relacionadas entre sí por las operaciones definidas en el álgebra de Boole. Dicha función sólo podrá tomar el valor lógico 0 o 1, por tanto puede también ser considerada como una variable booleana.
TEOREMA 8
Dada una función booleana de n variables dicha función es posible descomponerla como:
O bien como:
DEMOSTRACIÓN
Sabemos que por ser una variable de Boole necesariamente se ha de verificar que ó por tanto ó .
Si
y
Sumando ambas ecuaciones miembro a miembro tendremos:
Si
y
Sumando ambas ecuaciones miembro a miembro tendremos:
Por tanto se verifica para cualquier valor de la variable
Otra forma de demostrarlo sería:
Multiplicamos (1) por y (2) por
Sumando miembro a miembro las dos igualdades:
La parte dual también quedaría demostrada.
3.3. Formas canónicas
Se denominan términos canónicos ( o formas canónicas) a expresiones algebraicas en las cuales solo aparece una de las dos operaciones del Álgebra de Boole.
Una función de Boole de n variables puede descomponerse en una expresión de 2n términos canónicos. La función booleana podrá expresarse como una suma de productos canónicos o bien como un producto de sumas canónicas.
Supongamos que n=3, aplicando el teorema 8 repetidas veces tendremos que:
Por lo tanto:
Operando llegamos a que:
A los productos se les llama términos canónicos producto o mintérminos y se denotan por:
Así pues:
En general una función f de n variables puede expresarse como:
La función puede descomponerse también
...