No es objeto de este curso un análisis profundo y formal de los postulados y teoremas del Algebra 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, X
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 boleana.
TEOREMAS ÁLGEBRA DE BOOLE
Dualidad
Los postulados y teoremas presentados anteriormente están representados en pares. La razón es que
cada teorema posee lo que llamamos un dual. El dual de una expresión se obtiene intercambiando las
ocurrencias de OR por AND, 0 por 1 y viceversa.. Si un teorema es valido, también lo será su dual, En
efecto siguiendo el dual de la demostración del teorema, se obtiene la demostración del dual del teorema.
Por ejemplo dado el postulado 0+0 = 0 se obtiene el dual haciendo 1·1 = 1
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.
Veamos antes algunos conceptos.
DEFINICIONES
Literal: se refiere a una variable o a su complemento (por ej. A,X,X')
termino producto: es un grupo de literales que se encuentran relacionados entre si por un AND
(por ej. A*B, C*A, X'*Y*Z)
termino suma: es un grupo de literales que se encuentran relacionados entre si por un OR
(por ej. A+B, C+A, X'+Y+Z)
termino normal: termino producto o termino suma en el que un literal no aparece mas de una vez
termino canónico: termino en el que se encuentra exactamente uno de cada uno de los literales de la
función. Si el termino canónico es un producto, se denominará mintermino. Si es una suma se
denominará maxtermino,
forma normal de una función: es la que está constituida por términos normales. Puede estar en la
forma suma de términos productos o productos de términos sumas.
forma canónica de una función: es aquella constituida exclusivamente por términos canónicos que
aparecen una sola vez.
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+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*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 (X'*Y'*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,Y,Z)=m(1,4,5,6,7) que quiere decir la sumatoria de los minterminos
1,4,5,6,7
Forma canónica producto de sumas:
Es aquella constituida exclusivamente por términos canónicos sumas (maxterminos) multiplicados que
aparecen una sola vez.
Por ejemplo F(X,Y,Z) = (X + Y + Z)× (X + Y' + Z)× (X + Y' + Z')
Análogamente al caso anterior, podemos simplificar la expresión de la función, indicando los
maxterminos. Sin embargo, en este caso se hace al contrario de antes. A cada maxtermino se le asocia
un numero binario de n bits resultante de considerar como 1 las variables complementadas y como 0 las
variables no complementadas. Así por ejemplo el maxtermino X' + Y + Z corresponde a combinación
X=1, Y=0, Z=0 que representa el numero binario 100, cuyo valor decimal es 4. A este maxtermino lo
identificaremos entonces como M4.
De esta forma la función F(X,Y,Z) = (X + Y + Z)× (X + Y' + Z)× (X + Y' + Z')
se puede expresar como: F(X,YZ) = II M(0,2,3) que quiere decir el producto de los maxterminos 0,2,3
En resumen, cada mintermino se asocia con la
combinación de entrada para la que la función
produciría un 1, y cada maxtérmino con la
combinación para la que produciría un 0.
En la tabla de la derecha se muestran los
minterminos y los maxterminos asociados con
cada combinación en una tabla de verdad de 3
variables. De acuerdo con esta tabla para
determinar el termino producto o suma se hace lo
siguiente: para los minterminos cada variable no
complementada se asocia con un 1 y cada
variable complementada se asocia con 0. Para los
maxtérminos la regla es la inversa.
Forma normal de funciones booleanas
Otra manera importante de expresar expresiones booleanas es la forma normal. Tiene la misma
estructura básica suma de productos o producto de sumas, pero no se requiere que los términos sean
minterminos o maxterminos.
Por ejemplo:
La siguiente es una forma normal suma de productos:
X × Y + X' × Y' × Z
La siguiente es una forma normal producto de sumas:
(X + Y) × (X' + Z) × (Y)
No hay comentarios:
Publicar un comentario