Algebra boole
Se dice que un conjunto de elementos B, en el que existen definidas dos
operaciones binarias (que representaremos por + y por ) tiene estructura de
lgebra de Boole si y solo si se cumplen los siguientes cuatro postulados:
Leyes bsicas de algebra de Boole
1.- Propiedad conmutativa:
A+B=B+A
AB=BA
2. Propiedad distributiva:
A (B+C) = A B + A C
A + B C = (A+B) (A+C)
3. Elementos neutros diferentes
A+0=A
A1=A
4. Siempre existe el complemento de A, denominado A
A + A = 1
A A = 0
Principio de dualidad: cualquier teorema o identidad algebraica deducible de los
postulados anteriores puede transformarse en un segundo teorema o identidad
vlida sin ms que intercambiar (+) por () y 1 por 0.
Constante: cualquier elemento del conjunto b
Variable: smbolo que representa un elemento arbitrario del lgebra, ya sea
constante o frmula completa.
Teoremas:
Teorema 1: el elemento complemento A es nico.
Teorema de los elementos nulos: para cada elemento de B se verifica:
A+1 = 1
A0 = 0
Teorema 3: cada elemento identidad es el complemento del otro.
0=1
1=0
Teorema de idempotencia: para cada elemento de B, se verifica:
A+A=A
AA=A
Teorema de involucin: para cada elemento de B, se verifica:
(A) = A
Teorema de absorcin: para cada par de elementos de B, se verifica:
A+AB=A
A(A+B)=A
Teorema 7: para cada par de elementos de B, se verifica:
A + AB = A + B
A (A + B) = A B
Leyes de demorgan: para cada par de elementos de B, se verifica:
(A+B) = AB
(AB) = A + B
Teorema de asociatividad: cada uno de los operadores binarios (+) y ()
cumplela propiedad asociativa:
A+(B+C) = (A+B)+C
A(BC) = (AB)C
Funciones en el lgebra de Boole
Funcin completa es una funcin que se encuentra definida para todas
las combinaciones de las variables de entrada.
Tabla de la VERDAD: forma de representacin de funciones, dando el valor de
la funcin para cada combinacin de entrada.
Frmulas de conmutacin: expresin de una funcin
1 y 0 son frmulas
Xi es una frmula si pertenece a {0,1}
Si A es una frmula, A tambin lo es
Si A y B son frmulas, A+B y A B tambin lo son
Nada ms es una frmula, a menos que sigan los puntos anteriores un
nmero finito de pasos.
Cada frmula describe una nica funcin.
Dos frmulas son equivalentes (A=B) si expresan la misma funcin de
conmutacin.
Un LITERAL es una variable A o complemento de una variable A
Un TRMINO PRODUCTO es una operacin AND de un nmero de
literales.
Una frmula normal disyuntiva es una suma de trminos productos.
Un TRMINO SUMA es una operacin OR de un nmero de literales.
Una frmula normal conjuntiva es un producto de trminos sumas.
Tablas de verdad
Estas tablas pueden construirse haciendo una interpretacin de los
signos lgicos ,, , , , ,como: no, o, y, sientonces, s y slo si,
respectivamente. La interpretacin corresponde al sentido que estas
operaciones tienen dentro del razonamiento.
Puede establecerse una correspondencia entre los resultados de estas
tablas y la deduccin lgico matemtica. En consecuencia, las tablas de
verdad constituyen un mtodo de decisin para chequear si una proposicin
es o no un teorema.
Para la construccin de la tabla se asignar el valor 1(uno) a una
proposicin cierta y 0 (cero) a una proposicin falsa.
Negacin: El valor de verdad de la negacin es el contrario de la
proposicin negada.
P
Disyuncin: La disyuncin solamente es falsa si lo son sus dos
componentes.
P
PQ
Conjuncin: Solamente si las componentes de la conjuncin son ciertas, la
conjuncin es cierta.
P
PQ
Condicional: El condicional solamente es falso cuando el antecedente es
verdadero y el consecuente es falso. De la verdad no se puede seguir la
falsedad.
P
P Q
Bicondicional: El bicondicional solamente es cierto si sus componentes
tienen el mismo valor de verdad.
P
P Q
Se denomina tautologa una proposicin que es cierta para cualquier
valor de verdad de sus componentes. Por tanto, la ltima columna de su
tabla de verdad estar formada nicamente por unos.
Contradiccin es la negacin de una tautologa, luego es una
proposicin falsa cuales quiera sea el valor de verdad de sus componentes.
La ltima columna de la tabla de verdad de una contradiccin estar
formada nicamente por ceros.
Expresiones booleanas
Las expresiones booleanas se usan para determinar si un conjunto de
una o ms condiciones es verdadero o falso, y el resultado de su evaluacin
es un valor de verdad. Los operandos de una expresin booleana pueden
ser cualquiera de los siguientes:
Expresiones relacionales: que comparan dos valores y determinan si
existe o no una cierta relacin entre ellos (ver ms adelante), tal como
mfn<10;
Funciones booleanas: tal como p(v24), que regresa un valor de verdad
(estos se explican bajo "Funciones booleanas").
Las expresiones relacionales permiten determinar si una relacin dada
se verifica entre dos valores. La forma general de una expresin relacional
es:
Expresin-1 operador-de-relacin expresin-2
donde:
expresin-1 es una expresin numrica o de cadena
operador-de-relacin es uno de los siguientes:
o
= Igual
o <> No igual (diferente de)
o < Menor que
o <= Menor o igual que
o > Mayor que
o >= Mayor o igual que
o : Contiene (puede ser usado slo en expresiones de cadena)
expresin-2 es una expresin del mismo tipo que expresin-1, o sea,
expresin-1 y expresin-2 deben ser ambas expresiones numricas o
ambas expresiones de cadena.
Los operadores de relacin =
convencional cuando se aplican a
lmites de precisin de los valores
numricas"). Cuando se comparan
siguientes reglas:
<> < <= > >= tienen su significado
expresiones numricas (dentro de los
numricos definidos bajo "Expresiones
expresiones de cadena, se aplican las
Excepto por el operador ":" (contiene), las cadenas se comparan
exactamente en la forma en que ocurren, o sea, las letras maysculas y
minsculas se comparan de acuerdo con el cdigo ASCII que les
corresponde ([Link]. A ser considerada menor que a);
Dos expresiones de cadena no son consideradas iguales, a menos que
tengan la misma longitud. Si dos expresiones generan cadenas de
diferente longitud que son idnticas, carcter por carcter, hasta el total
de la longitud de la ms corta, entonces, la ms corta ser considerada
menor que la ms larga.
El operador : (contiene), busca una cadena de caracteres (definida por
expresin-2) en otra cadena (definida por expresin-1). Si el segundo
operando existe en cualquier parte del segundo operando, el resultado es
Verdadero (TRUE). Este operador es insensible al hecho de que los
caracteres se hallen en maysculas o minsculas: por lo que las letras
minsculas se consideran iguales a su letra mayscula correspondiente.
Por ejemplo, el resultado de:
v10 : 'qumica'
Ser Verdadero (True) si, y slo si, el campo 10 contiene la cadena
qumica. En caso contrario, el resultado ser Falso (False). Ntese que el
segundo operando puede ser cualquier cadena o carcter, y no necesita ser
una palabra como tal. Por lo tanto, en este ejemplo, el resultado ser
Verdadero no slo si el campo 10 contiene la palabra qumica, sino tambin
si contuviera bioqumica, fotoqumicas, qumicamente, etc.
Los operandos de una expresin booleana pueden combinarse con los
operadores siguientes:
NOT (NO) Este operador produce el valor Verdadero, si su operando es
Falso; y el valor Falso, si su operando es Verdadero. El operador NOT
slo puede usarse como operador signo +, o sea, siempre se aplica a la
expresin booleana que le sigue;
AND (Y) Este operador produce el valor Verdadero si ambos operandos
son Verdadero. Si cualquiera de los dos operandos es Falso, entonces
el resultado ser Falso;
OR (O) Este operador realiza una operacin O-inclusivo. El resultado es
Verdadero si cualquiera de los dos operandos, o ambos son Verdadero.
En caso contrario, es Falso.
Al evaluar expresiones booleanas, y en ausencia de parntesis,
CDS/ISIS ejecutar las operaciones NOT en primer lugar, despus las
operaciones AND, y finalmente las OR. Las series de dos o ms operadores
del mismo nivel, se ejecutan de izquierda a derecha. Se pueden usar
parntesis para alterar el orden de evaluacin: las expresiones dentro de
parntesis se evalan antes, y las expresiones entre parntesis internos a
otros, son evaluadas antes que las expresiones externas a los parntesis.
La figura presenta ejemplos de expresiones booleanas.
Compuerta AND:
Cada compuerta tiene una o dos variables de entrada designadas por A
y B y una salida binaria designada por x. La compuerta AND produce la
unin lgica AND: esto es: la salida es 1 si la entrada A y la entrada B estn
ambas en el binario 1: de otra manera, la salida es 0. Estas condiciones
tambin son especificadas en la tabla de verdad para la compuerta AND. La
tabla muestra que la salida x es 1 solamente cuando ambas entradas A y B
estn en 1 . El smbolo de operacin algebraico de la funcin AND es el
mismo que el smbolo de la multiplicacin de la aritmtica ordinaria (*).
Podemos utilizar o un punto entre las variables o concatenar las variables
sin ningn smbolo de operacin entre ellas. Las compuertas AND pueden
tener ms de dos entradas y por definicin, la salida es 1 si cualquier
entrada es 1.
Compuerta OR:
La compuerta OR produce la funcin OR inclusiva, esto es, la salida es 1
si la entrada A o la entrada B o ambas entradas son 1; de otra manera, la
salida es 0. El smbolo algebraico de la funcin OR (+), similar a la
operacin de aritmtica de suma. Las compuertas OR pueden tener ms de
dos entradas y por definicin la salida es 1 si cualquier entrada es 1.
Compuerta NOT (Inversor):
El circuito inversor invierte el sentido lgico de una seal binaria.
Produce el NOT,. o funcin complemento. El smbolo algebraico utilizado
para el complemento es una barra sobra el smbolo de la variable binaria. Si
la variable binaria posee un valor 0, la compuerta NOT cambia su estado al
valor 1 y viceversa. El crculo pequeo en la salida de un smbolo grfico de
un inversor designa un complemento lgico. Es decir cambia los valores
binarios 1 a 0 y viceversa.
Compuerta Separador:
Un smbolo tringulo por s mismo designa un circuito separador no
produce ninguna funcin lgica particular puesto que el valor binario de la
salida es el mismo de la entrada. Este circuito se utiliza simplemente para
amplificacin de la seal. Por ejemplo, un separador que utiliza i volt para el
binario 1 producir una salida de 3 volt cuando la entrada es 3 volt. Sin
embargo, la corriente suministrada en la entrada es mucho ms pequea
que la corriente producida en la salida. De sta manera, un separador
puede excitar muchas otras compuertas que requieren una cantidad mayor
de corriente que de otra manera no se encontrara en la pequea cantidad
de corriente aplicada a la entrada del separador.
Compuerta NAND:
Es el complemento de la funcin AND, como se indica por el smbolo
grfico que consiste en un smbolo grfico AND seguido por un pequeo
crculo. La designacin NAND se deriva de la abreviacin NOT - AND. Una
designacin ms adecuada habra sido AND invertido puesto que Es la
funcin AND la que se ha invertido.
Compuerta NOR:
La compuerta NOR es el complemento de la compuerta OR y utiliza un
smbolo grfico OR seguido de un crculo pequeo. Tanto las
compuertas NAND como la NOR pueden tener ms de dos entradas, y la
salida es siempre
respectivamente.
el
complemento
de
las
funciones AND u
OR,
Compuerta OR exclusivo (XOR):
La compuerta OR exclusiva tiene un smbolo grfico similar a la
compuerta OR excepto por una lnea adicional curva en el lado de la
entrada. La salida de esta compuerta es 1 si cada entrada es 1 pero excluye
la combinacin cuando las dos entradas son 1. La funcin OR exclusivo
tiene su propio smbolo grfico o puede expresarse en trminos de
operaciones complementarias AND, OR .
Compuerta NOR exclusivo (XOR):
El NOR exclusivo como se indica por el crculo pequeo en el smbolo
grfico. La salida de sta compuerta es 1 solamente si ambas entradas son
tienen el mismo valor binario. Nosotros nos referiremos a la
funcin NOR exclusivo como la funcin de equivalencia. Puesto que las
funciones OR exclusivo y funciones de equivalencia no son siempre el
complemento la una de la otra. Un nombre ms adecuado para la
operacin OR exclusivo sera la de una funcin impar; esto es, la salida es 1
si un nmero impar de entrada es 1. As en una funcin OR (impar)
exclusiva de tres entradas, la salida es 1 si solamente la entrada es 1 o si
todas las entradas son 1. La funcin de equivalencia es una funcin par;
esto es, su salida es 1 si un nmero par de entradas es 0. Para un funcin
de equivalencia de tres entradas, la salida es 1 si ninguna de las entradas
son 0 ( todas las entradas son 1 ) o si dos de las entradas son 0 ( una
entrada es 1 Una investigacin cuidadosa revelar que el OR exclusivo y
las funciones de equivalencia son el complemento la una de la otra cuando
las compuertas tienen un nmero par de entradas, pero las dos funciones
son iguales cuando el nmero de entradas es impar. Estas dos compuertas
estn comnmente disponibles con dos entradas y solamente en forma rara
se encuentran con tres o ms entradas.
Mtodos de simplificacin
Por simplificacin de una funcin lgica se entiende la obtencin de su mnima
expresin. A la hora de implementar fsicamente una funcin lgica se suele simplificar
para reducir as la complejidad del circuito.
A continuacin se indican los modos ms usuales de simplificar una funcin lgica.
Algebraico
Para la simplificacin por este mtodo no slo bastar con conocer todas
las propiedades y teoremas del lgebra de Boole, adems se debe desarrollar
una cierta habilidad lgico-matemtica que se adquiere fundamentalmente con
la experiencia.
Como ejemplo se simplificar la siguiente funcin:
F = AC + ABC + BC + ABC + ABC
Observando cada uno de los sumando podemos ver que hay factores comunes
en los sumandos 2 con 5 y 4 con 5 que conllevan simplificacin:
F = AC + BC + BC(A + A) + AC(B + B)
Note que el trmino 5 se ha tomado dos veces, de acuerdo con la propiedad
que dice que A + A = A. Aplicando las propiedades del lgebra de Boole (A + A'
= 1 y A . 1 = A), queda F = AC + BC + BC + AC
Repitiendo nuevamente el proceso,
F = A( C + C) + B( C + C) = A + B
No siempre las funciones son tan fciles de simplificar como la anterior. El
mtodo algebraico, por lo general, no resulta cmodo para los no expertos, a
los cuales, una vez simplificada una ecuacin le pueden quedar serias dudas
de haber conseguido la mxima simplificacin.
Mapa de Karnaugh
Este mtodo consiste en formar diagramas de 2n cuadros, siendo n el
nmero de variables. Cada cuadro representa una de las diferentes
combinaciones posibles y se disponen de tal forma que se puede pasar de un
cuadro a otro en las direcciones horizontal o vertical, cambiando nicamente
una variable, ya sea en forma negada o directa.
Este mtodo se emplea fundamentalmente para simplificar funciones de
hasta cuatro variables. Para un nmero superior utilizan otros mtodos como el
numrico. A continuacin pueden observarse los diagramas, tambin llamados
mapas de Karnaugh, para dos, tres y cuatro variables.
Mapas de Karnaugh para dos, tres y cuatro variables
Es una prctica comn numerar cada celda con el nmero decimal
correspondiente al trmino cannico que albergue, para facilitar el trabajo a
la hora de plasmar una funcin cannica.
Para simplificar una funcin lgica por el mtodo de Karnaugh se seguirn
los siguientes pasos:
1) Se dibuja el diagrama correspondiente al nmero de variables de la
funcin a simplificar.
2) Se coloca un 1 en los cuadros correspondientes a los trminos
cannicos que forman parte de la funcin.
3) Se agrupan mediante lazos los unos de casillas adyacentes siguiendo
estrictamente las siguientes reglas:
a) Dos casillas son adyacentes cuando se diferencian nicamente en el
estado de una sola variable.
b) Cada lazo debe contener el mayor nmero de unos posible, siempre que
dicho nmero sea potencia de dos (1, 2, 4, etc.)
c) Los lazos pueden quedar superpuestos y no importa que haya
cuadrculas que pertenezcan a dos o ms lazos diferentes.
d) Se debe tratar de conseguir el menor nmero de lazos con el mayor
nmero de unos posible.
4) La funcin simplificada tendr tantos trminos como lazos posea el
diagrama. Cada trmino se obtiene eliminando la o las variables que
cambien de estado en el mismo lazo.
A modo de ejemplo se realizan dos simplificaciones de una misma funcin a
partir de sus dos formas cannicas:
F = 3(0,2,3,4,7) = 3(1,2,6)
De acuerdo con los pasos vistos anteriormente, el diagrama de cada
funcin quedar del siguiente modo:
Simplificacin de una funcin de tres variables
La funcin simplificada tendr tres sumandos en un caso y dos
productos en el otro. Si nos fijamos en el mapa correspondiente a la suma
de productos, observamos que en el lazo 1 cambia la variable A (en la celda
0 es negada y en la 4 directa), en el lazo 2 es la C y en el lazo 3 vuelve a
ser A. por lo tanto, la ecuacin simplificada es:
F = BC + AB + BC
Razonando de modo similar en el mapa de productos de sumas, nos
quedar lo siguiente:
F = (B + C)(A + B + C)
Numrico de Quine-McCluskey
El algoritmo Quine-McCluskey permite la simplificacin de funciones
lgicas de cualquier nmero de variables y es el que se utiliza para disear
aplicaciones informticas en las que se necesite obtener funciones
simplificadas.
A continuacin se indican los pasos a seguir en este mtodo a partir de un
ejemplo.
1) Se expresa la funcin a simplificar en su forma cannica de suma de
productos.
Sea la siguiente funcin a simplificar:
F = S4 (0,1,2,3,5,9,11,12,13,15)
2) Se forma una tabla con el valor decimal de la combinacin, el estado de
las variables y el ndice (nmero de unos que contiene el estado de las
variables).
Comb.
Estado
ndice
0
0000
0001
0010
0011
0101
1001
11
1011
12
1100
13
1101
15
1111
3) Se agrupan las combinaciones cuyos estados difieren en una sola
variable, sustituyndola por un guion bajo (_). Las combinaciones utilizadas
se marcan con un aspa (X). Hay que fijarse en las combinaciones cuya
diferencia entre sus respectivos ndices es la unidad.
Agrupacin de las combinaciones
4) Se repite el proceso anterior las veces que sean necesarias y se van
eliminando estados idnticos.
Nueva agrupacin de las combinaciones
5) Se forma una tabla con las combinaciones finales y las no agrupadas.
Se toman como filas las combinaciones finales y las no agrupadas y como
columnas los valores decimales de dichas combinaciones. Cada celda que
contenga el valor decimal de una combinacin se marca con un aspa. A
continuacin nos fijamos en aquellas columnas con una sola aspa; sus
combinaciones sern esenciales. Finalmente se toman aquellas
combinaciones de los valores decimales no seleccionados, teniendo
precaucin de no tomar aquellas combinaciones cuyos valores decimales
hayan sido ya tomados en otras combinaciones. La funcin simplificada final
viene dada por las combinaciones esenciales y estas ltimas.