En 1854 George Boole introdujo una notación simbólica para el tratamiento de variables cuyo valor podría ser verdadero o falso (variables binarias) Así el álgebra de Boole nos permite manipular relaciones proposicionales y cantidades binarias. Aplicada a las técnicas digitales se utiliza para la descripción y diseño de circuitos mas económicos. Las expresiones booleanas serán una representación de la función que realiza un circuito digital. En estas expresiones booleanas se utilizarán las tres operaciones básicas ( AND, OR NOT ) para construir expresiones matemáticas en las cuales estos operadores manejan variables booleanas (lo que quiere decir variables binarias).
Elementos del álgebra de Boole
Los símbolos elementales son:
· 0: representativo de FALSO
· 1: representativo de VERDADERO
Las operaciones fundamentales son:
· Conjunción u operación AND (se representa con · )
· Disyunción u operación OR (se representa con + )
· Complementación, Negación u operación NOT ( se representa con una barra sobre la variable, P)
Las variables son las proposiciones, que se representan o simbolizan por letras
Postulados:
Los postulados para las tres operaciones básicas, AND, OR Y NOT, son suficientes para deducir cualquier relación bolean.
OR | AND | NOT |
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1 | 0 · 0 = 0
0 · 1 = 0
1 · 0 = 0
1 · 1 = 1 |
|
Teoremas:
1. Regla del cero y la unidad a) X + 0 = X
b) X + 1 = 1 | c) X · 1 = X
d) X · 0 = 0 |
|
2. Idempotencia o potencias iguales a) X + X = X | b) X · X = X |
|
5. Conmutatividad a) conmutatividad del +
X + Y = Y + X | b) conmutatividad del ·
X · Y = Y · X |
|
6. Asociatividad a) asociatividad del +
X + (Y + Z) = (X + Y) + Z | b) asociatividad del ·
X · (Y · Z) = (X · Y) · Z |
|
7. Distribuitividad a) distribuitividad del +
X + (Y · Z) = (X + Y) · (X + Z) | b) distribuitividad del ·
X · (Y + Z) = (X · Y) + (X · Z) |
|
8. Leyes de absorción a) X · (X + Y)= X
b) X · ( + Y)= X·Y
c) · (X + Y)= ·Y
d) (X + Y) · (X + )= X | e) X + X·Y = X
f) X + ·Y = X + Y
g) + X·Y = + Y
h) X·Y + X· = X |
|
10. Teoremas generalizados de DeMorgan |
Representación de funciones booleanas
Existen infinitas maneras de representar una función booleana. Así por ejemplo la función G = X + Y Z puede también representarse como G = X + X + YZ.
Otras veces se suele utilizar la forma negada o el complemento de la función. Para esto es se niegan los literales y se intercambian los AND y OR .
|
|
| _ |
|
|
|
|
|
Por ejemplo, el complemento de: | A | + | B | C |
|
|
|
|
| _ |
|
|
| _ |
|
|
|
es: | A | ( | B | + | C | ) |
|
|
El complemento de una función no es la misma función, es la forma negada de la función.
En el álgebra de Boole es fundamental la existencia de una forma algebraica que proporcione explícitamente el valor de una función para todas las combinaciones de los valores de las variables. Es esta la forma canónica de la función.
Forma canónica de funciones booleanas
La importancia de la forma canónica estriba en el hecho de ser UNICA. Como vimos anteriormente una función puede tener infinidad de representaciones, pero solo una representación en forma canónica.
Existen dos formas canónicas de una función: Suma De Productos o Producto de Sumas. (También de una manera mas formal Suma de minterminos o Producto de maxterminos)
Para obtener algebraicamente la forma canónica de una función podemos utilizar los teoremas de expansión canónica:
Teorema 1: Para obtener la forma canónica de una función suma de productos se multiplicará por un termino de la forma (X + ) donde falte un literal para que el termino sea canónico.
Teorema 2: Para obtener la forma canónica de una función producto de sumas se sumará un termino de la forma X · donde falte un literal para que el termino sea canónico.
Forma canónica suma de productos:
Es aquella constituida exclusivamente por términos canónicos productos (minterminos) sumados que aparecen una sola vez.
|
| _ | _ |
|
|
| _ | _ |
|
| _ |
|
|
|
| _ |
|
|
|
|
Por ejemplo: F(X,Y,Z) | = | X | Y | Z | + | X | Y | Z | + | X | Y | Z | + | X | Y | Z | + | X | Y | Z |
Para simplificar la escritura en forma de suma canónica de productos, se utiliza una notación especial. A cada mintermino se le asocia un numero binario de n bits resultante de considerar como 0 las variables complementadas y como 1 las variables no complementadas. Así por ejemplo el mintermino Z corresponde a combinación X=0, Y=0, Z=1 que representa el numero binario 001, cuyo valor decimal es 1. A este mintermino lo identificaremos entonces como m1.
|
| _ | _ |
|
|
| _ | _ |
|
| _ |
|
|
|
| _ |
|
|
|
|
De esta forma, la función : F(X,Y,Z) | = | X | Y | Z | + | X | Y | Z | + | X | Y | Z | + | X | Y | Z | + | X | Y | Z |
se puede expresar como: F(X,YZ) = m(1, 4,5,6,7) que quiere decir la sumatoria de los minterminos 1,4,5,6,7
AUTOR: MITZI ZAMARRIPA RDZ.
