4.3.1 Circuitos Combinatorios
Un concepto
muy útil en computación es el de diagramas de compuertas lógicas, empezaremos por la más sencilla.
Definición. Un compuerta tipo y (AND) de dos variables a, b se representa por a ^ b ó a × b ó a · b y regresa 1 cuando los dos valores de a y b son 1.
a a ^ b = a × b = a · b b
Tablas:
a b a^b × 0 1 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 Definición. Una compuerta tipo ó (OR) de dos variables a, b se representa por a ∨ b ó a + b y regresa 1 cuando por lo menos alguno de a ó b es 1. Diagrama: a a ∨ b = a + b b
Tablas:
a b a Ú b + 0 1
1 1 1
1 0 1 0 0 1
0 1 1
0 0 0 1 1 1
Definición. Una compuerta muy importante es la tipo no (NOT) ó inversor representada por a, regresa 0 cuando la entrada es 1 y 1 cuando la entrada es 0.
Tabla
a a
1 0
0 1
a a
Ejemplo:
a b c Se representa por aÚ(b Ù c) ó por a + b · c
Algoritmo.
Para encontrar la expresión booleana correspondiente a un diagrama de compuertas lógicas se forma un árbol sintáctico invertido, las variables simples son las hojas y se forman las ramas de acuerdo a las siguientes reglas:
i) Si f es la entrada a un inversor, f es el padre de f.
ii) Si f1, f2 son las entradas de una compuerta y (AND) f1Ùf2 ( tambien puede ser f1 · f2 ) es el padre de f1, y f2.
iii) Si f1, f2 son la entrada de una de compuerta ó (OR) f1 Ú f2 (f1+f2) es el padre de f1, f2.
La fórmula en la raíz es la respuesta.
En el ejemplo anterior, el árbol es:
b
-
b c
Ù
a b Ù c
Ú
aÚ(bÙc)
También podemos analizar el problema contrario. Dada una expresión booleana construir el circuito de compuertas. Primero construimos el árbol sintáctico. Después ponemos una línea para cada variable distinta en las hojas y construimos en forma recursiva de las hojas a la raiz dibujando por cada rama:
i) un inversor NOT con entrada f si aparece f.
ii) una compuerta AND con entradas f1,f2 si aparece f1Ùf2
iii) una compuerta OR con entradas f1,f2 si aparece f1Úf2
Ejemplo: (a Ù b) Ú (a Ù c)
Ú
aÙb aÙc
Ù Ù
a b a b
-
a
a aÙb
a
b (aÙb)Ú(aÙc)
c
aÙc
El concepto de expresión booleana se puede formalizar:
Definición: Expresión Booleana. (B) 0,1,a,b,c,…son expresiones booleanas.
® Si A, B son expresiones ØA, AÚB, AÙB también lo son. En la práctica se evalúan las compuertas con una serie de “datos” ó valores de entrada, que pueden ser por ejemplo bytes. En este caso, la salida sigue las mismas reglas, evaluando bit por bit. Ejemplo: Evalúe la expresión boolena del primer ejemplo con: a = 00110011 b = 10101010 c = 10011001 primeramente b = 01010101 b Ù c = 00010001 \ a Ú (bÙc)=00110011
Propiedades de los circuitos:
Teorema: Sean Ø, Ú, Ù los operadores definidos previamente, entonces.
(a) Leyes asociativa:
(aÚb) Ú c = aÚ(bÚc), (aÙb) Ù c= aÙ (bÙc)
(b) Leyes conmutativas:
aÚb=bÚa, aÙb=bÙa
© Leyes distributivas:
aÙ(bÚc)=(aÙb)v(aÙc) , aÚ (bÙc)=(aÚb)Ù(aÚc)
(d) Leyes de elements neutros:
aÚo=a, a Ù1=a
(e) Leyes de complementos:
aÚa=1, aÙa=0
(f ) Leyes De Morgan:
aÚb = a Ù b, a Ù b = a Ú b
Demostración. La demostración de cualquiera de estas propiedades se puede hacer construyendo una tabla de verdad y comprobando que son equivalentes.
En general dos fórmulas con las mismas variables son equivalentes si tienen la misma tabla.
Definición. Dos circuitos combinatorios son equivalentes si dados x1,…xn como datos de entrada producen los mismos datos de salida.
Ejemplo y1 º y2
x1
y2
x2
x1
y2
x2
Como se puede ver, este ejemplo corresponde a la segunda Ley De Morgan.
En lógica de circuitos combinatorios se utilizan tambien algunos otros operadores.
Algunos otros operadores: x1 x2 x1 + x2 x1 x2 x1 ¯ x2 1 1 0 0 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 XOR NAND NOR
Ejemplo: Diseñe un circuito que calcule XOR
x1 + x2 = (x1 Ù x2 ) Ú (x1 v x2 )
x1
x2
x y x + y 1 1 0 1 0 1 0 1 1 0 0 0
| ⇐ | Tema Anterior: 4.3 Algebra Booleana |
| ⇒ | Siguiente Tema: 4.3.2 Propiedades Circuitos Combinatorios |
| Regresar al TEMARIO: Matematicas Computacion |