Introduccin
Las lgebras booleanas, estudiadas por primera vez en
detalle
por
George
Boole,
las matemticas que
ha
constituyen
pasado
un
ocupar
rea
un
de
lugar
prominente con el advenimiento de la computadora digital.
Son
usadas
ampliamente
en
el diseo de circuitos de distribucin y computadoras, y sus
aplicaciones van en aumento en muchas otras reas. En el
nivel
de lgica digital
de
una
computadora,
lo
que
comnmente
se
llama hardware, y que est formado por los componentes electrnicos de la
mquina,
se
trabaja
con
diferencias
de
tensin,
las
cuales
generan funciones que son calculadas por los circuitos que forman el nivel.
stas funciones, en la etapa de disea del hardware, son interpretadas como
funciones
de
Boole.
En el presente trabajo se intenta dar una definicin de lo que es un lgebra de
Boole; se tratan las funciones booleanas, haciendo una correlacin con las
frmulas proposicionales. Asimismo, se plantean dos formas cannicas de las
funciones booleanas, que son tiles para varios propsitos, tales como el de
determinar si dos expresiones representan o no la misma funcin. Pero para
otros propsitos son a menudo engorrosas, por tener ms operaciones que las
necesarias. Particularmente, cuando estamos construyendo los circuitos
electrnicos con que implementar funciones booleanas, el problema de
determinar una expresin mnima para una funcin es a menudo crucial. No
resultan
de
la
misma eficiencia en dinero y tiempo,
principalmente,
dos
funciones las cuales calculan lo mismo pero donde una tiene menos variables y
lo hace en menor tiempo. Como solucin a este problema, se plantea un
mtodo de
simplificacin,
que
hace
uso
de
unos diagramas especiales
llamados mapas o diagramas de Karnaugh, y el cual tiene la limitacin
de poder trabajar adecuadamente slo con pocas variables. Se realizan estas
presentaciones con el fin de demostrar la afinidad existente entre el lgebra de
Boole y la lgica proposicional, y con el objeto de cimentar el procedimiento de
simplificacin presentado en la lgica de proposiciones.
Cuando Boole estudio la relacin entre las propiedades de los conjuntos y la
lgica, observo que eran similares a las propiedades de los nmeros reales.
Propiedades de cerradura:
En conjuntos: Si A y B son conjuntos, entonces AUB es un conjunto.
Si A y B son conjuntos, entonces AB es un conjunto.
En lgica: si p y q son proposiciones, entonces pq es una proposicin.
Si p y q son proposiciones, entonces pq es una proposicin.
En los nmeros reales: si a y b son nmeros reales, entonces a+b es un
nmero
real.
Si a y b son nmeros reales, entonces ab es un nmero real.
Propiedades conmutativas:
En conjuntos: si A y B son conjuntos,
Si A y B son conjuntos, entonces AB = BA.
En lgica: si p y q son proposiciones,
si p y q son proposiciones, entonces pq = qp
entonces
entonces
AUB
BUA.
pq
qp.
En los nmeros reales: si ay b son nmeros reales, entonces a+b = b+a.
si a y b son nmeros reales, entonces ab =ba.
Propiedades asociativas:
En conjuntos: (AUB) UC = AU (BUC).
(AB) C = A (BC).
En lgica: (pq) r = p (qr).
(pq) r = p (qr).
En los nmeros reales: (a+b)+c = a+(b+c).
(a.b).c = a.(b.c).
Boole se percat de que la analoga no se mantena para todas las propiedades
de campo de los nmeros reales. Solo hay una propiedad distributiva en los
nmeros reales. Solo hay una propiedad distributiva en los nmeros reales. La
multiplicacin se distribuye en la adicin, pero no a la inversa. En conjuntos y
lgica, hay dos propiedades distributivas.
Propiedades distributivas:
En conjuntos: A U (BC) = (AUB) (AUC) y A (BUC) = (AB) U (AC).
En lgica: p (qr) = (pq) (pr) y p (qr) = (pq) (pr).
En los nmeros reales: a. (b+c) = (a.b) + (a.c)
En lgebra booleana, que es el lgebra tanto de conjuntos como de la lgica,
se usa el signo + en lugar de U o , y se usa . (*) en lugar de o . Tambin, se
usa 1 en lugar de o V, y 0 se usa en lugar de o F. el 1 y el 0 son
smbolos y no el 1 y el 0 del sistema de los nmeros reales. Por tanto, un
enunciado puede expresar una propiedad tanto en conjuntos como en lgica.
Notacin de algebra booleana:
Algebra booleana
+
.
0
1
Conjuntos
U
Lgica
~
F
T
Las propiedades del algebra booleana, expresadas en notacin, son:
Propiedades del algebra booleana.
Propiedades conmutativas: A+B = B+A
A.B = B.A
Propiedades asociativas: (A+B) +C = A+(B+C)
(A.B).C = A.(B.C)
Propiedades distributivas: A .( B+C) = A . B + A . C
A+(B.C) = (A+B) . (A+C)
Propiedades idempotencia: A+A=A
A.A=A
Propiedades de complementacin: A+A=1
A.A=0
Leyes De Morgan: (A+B)=A.B
(A.B) = A+B
Leyes del doble complemento: (A)=A
Leyes de absorcin: A.(A+B) = A
A+(A.B) = A
Propiedades en que participan 0 y 1:
A+1=1
A.0=0
0=1
A+0=A
1=0
A.1=A
Circuitos.
En 1938, Claude Shannon descubri que el lgebra booleana tiene una
importante
aplicacin
en
el
diseo
de
circuitos
elctricos.
Las lneas representan conectores o alambres que conducen corriente elctrica.
La corriente no puede fluir de un extremo al otro del circuito si el interruptor
que est en medio se encuentra abierto. Se dice que el interruptor esta
apagado. Si el interruptor se pasa a la posicin de encendido (por ejemplo
si se cierra el interruptor), entonces la corriente fluir.
Apagado
Encendido
En ocasiones, el interruptor estar abierto o cerrado. El circuito se dibuja con
un hueco en el sitio donde se colocara el interruptor y se marca con una letra
del alfabeto para indicar que se trata de un interruptor variable (por ejemplo,
que puede estar encendido o apagado).
A
Interruptor variable
En el mismo circuito puede haber dos interruptores o ms. Los interruptores
pueden estar combinados en serie (extremo con extremo) y en paralelo
(lateralmente). Para ir de un extremo a otro de un circuito en serie, la corriente
debe fluir por A y por B. para ir de un extremo a otro de un circuito en paralelo,
la corriente debe fluir por A o por B.
Circuito en serie
B
Circuito
en paralelo
De los interruptores que operan de tal modo que uno est cerrado cuando el
otro est abierto, se dice que estn en estado opuesto. La notacin de algebra
booleana se aplica en los circuitos con interruptores variables. Por tanto, A . B
o AB denotan dos interruptores en serie (la corriente debe fluir por A y por B),
A+B denota dos interruptores en paralelo (la corriente debe fluir por A o por B),
y A denota un interruptor en la condicin opuesta a la de A (si la corriente
fluye por A, no fluye por A).
Notacin y diagramas de conmutacin.
Notacin
A.B
A+B
Descripcin
Dos interruptores
en serie.
Dos interruptores
en paralelo.
Diagrama
A
A
B
Interruptor en
condicin opuesta a
la de A.
A
A
Algebra Booleana
Los circuitos digitales (lgicos) operan en modo binario donde cada voltaje de
entrada y salida es un 0 o un 1; las designaciones 0 y 1 representan intervalos
predefinidos de voltaje. Esta caracterstica de los circuitos lgicos nos permite
utilizar el lgebra booleana como herramienta para el anlisis y diseo de
sistemas digitales.
El lgebra booleana difiere de manera importante del algebra ordinaria en que
constantes y variables booleanas solo pueden tener dos valores posibles, 0 y 1.
Una variable booleana esuna cantidad que puede, en diferentes ocasiones, ser
igual a 0 o a 1. Las variables booleanas se emplean con frecuencia para
representar el nivel de voltaje presente en un alambre o en las terminales de
entrada y salida de un circuito. Por ejemplo, en cierto sistema digital el valor
booleano de 0 podra asignarle cualquier voltaje en el intervalo de 0 a 0.8 V, en
tanto que el valor booleano de 1 podra asignarle cualquier voltaje de 2 a 5V.
As pues, el 0 y 1 booleanos no representa nmeros sino que en su lugar
representan el estado de una variable de voltaje o bien lo que se conoce como
su nivel lgico. En el campo de la lgica digital se emplean otros trminos
como sinnimos de 0 y 1. Algunos de los ms comunes se representan en la
siguiente tabla.
0 Lgico
Falso
Desactivado
Bajo
No
Interruptor
abierto
1 Lgico
Verdadero
Activado
Alto
Si
Interruptor
cerrado
El lgebra booleana se utiliza para expresar los efectos que los diversos
circuitos digitales ejercen sobre las entradas lgicas y para manipular variables
lgicas con objeto de determinar el mejor mtodo de ejecucin de cierta
funcin de un circuito. Se utilizan literales para representar las variables
lgicas. Por ejemplo, Apodra representar cierta entrada o salida de un circuito
digital y en cualquier instante debemos tener A=0 o A=1: si no es uno es el
otro.
Ya que solo puede haber dos valores, el lgebra booleana es relativamente
fcil de manejar en comparacin con la ordinaria. En el lgebra booleana no
hay fracciones, decimales, numero negativos, races cuadradas, races cubicas,
logaritmos, numero imaginarios, etc. De hecho en el lgebra booleana solo
existen
tres
operaciones
bsicas:
OR,
AND,
NOT.
Estas operaciones bsicas se llaman operaciones lgicas. Es posible
construir circuitos digitales llamados compuertas lgicas que con diodos,
transistores y resistencias conectados de cierta manera hacen que la salida del
circuito sea el resultado de una operacin lgica bsica (AND, OR, NOT) sobre
la entrada.
Nota: Las Compuertas Lgicas son los circuitos lgicos ms fundamentales y se
desarrollan mediante el Algebra Booleana.
Operaciones Lgicas Fundamentales
Se puede decir que los sistemas digitales en general, con toda su
complejidad y potencia operativa que pueden tener, internamente se
fundamentan en solo tres tipos de operaciones lgicas.
Suma Lgica
Su expresin matemtica en lgebra de Boole es:
A+B
A y B son variaciones binarias y que, por tanto, solo pueden tomar los estados
1 y 0. La operacin se define por la tabla siguiente:
A
0
0
1
1
0
1
0
1
A+
B
0
1
1
1
O sea, el resultado de la suma lgica vale 1 cuando las variables A o B valen 1,
o bien las dos a la vez estn en 1.
En la suma binaria aritmtica, cuando A y B valen 1 el resultado es 1, en
cambio en la suma aritmtica el resultado es 0 y se produce un acarreo. La
suma lgica y la suma aritmtica no son lo mismo.
Producto Lgico
Su expresin matemtica en lgebra Boole es:
AB
El punto significa la operacin producto, aunque normalmente no se pone. La
operacin se define por la tabla siguiente
A
0
0
1
B
0
1
0
AB
0
0
0
El resultado vale 1, solo cuando las dos variables estn en 1. Basta que una
variable este en 0 para que el resultado tambin este.
Complementacin
Su expresin matemtica en lgebra Boole es:
Esta operacin se aplica sobre una sola variable y su expresin lgica es igual a
la variable en cuestin con una rayita encima. La operacin se define por la
tabla siguiente
A
0
1
1
0
La complementacin tambin suele denominar inversin y negacin.
PUERTAS LGICAS
Aspectos Fundamentales Sobre Lgica de Contactos.
Antes de empezar el estudio de las puertas lgicas, introduciremos ciertas
cuestiones importantes sobre la realizacin de las funciones lgicas mediante
circuitos con interruptores, ya que la asociacin de circuitos elctricos a las
expresiones lgicas facilita enormemente la comprensin de los circuitos
lgicos, adems de que tambin se pueden hacer prcticamente asi.
Las premisas bsicas de asimilacin son:
Cero lgico (0): Circuito abierto (no hay paso de corriente).
Uno lgico (1): Circuito cerrado (pasa la corriente).
Variable: Interruptor(abierto:0, cerrado:1).
Complementacin (variable negada): Interruptor normalmente cerrado
(NC); en reposo circula la corriente (el paso de corriente se interrumpe al
activarlo).
Operacin suma lgica: Interruptor en paralelo.
Operacin producto lgico: Interruptor en serie.
Operaciones y Compuertas OR, AND y NOT
Operacin OR
Supongamos que A y B representan dos variables lgicas independientes.
Cuando A y B se combinan con la operacin OR, el resultado, x, se puede
representar como:
x=A+B
En esta operacin el signo + no representa la adicin ordinaria; en su lugar
denota la operacin OR cuyas reglas se dan en la tabla de verdad que se ve a
continuacin:
A
Podemos decir que la 0
ser 1 si una o ms 0
1
La expresin x=A+B se lee
1
Lo ms importante que
signo + representa la operacin
arriba.
B
0
1
0
1
x=A
+B
0
1
1
1
operacin OR el resultado
variables es un 1.
como x es igual a A o B.
debe recordarse es que el
OR, como lo define la tabla de verdad de
Compuerta OR
En un circuito digital la compuerta OR, es un circuito que tiene dos o ms
entradas y cuya salida es igual a la suma OR de las entradas. La imagen a
continuacin muestra el smbolo correspondiente a una compuerta OR de dos
entradas.
x=A
Las entradas A y B son niveles de voltaje lgicos y la salida xes un nivel de
voltaje lgico cuyo valor es el resultado de la operacin OR de A y B; esto es,
x=A+B. En otras palabras, la compuerta OR opera en tal forma que su salida
es ALTA (nivel lgico 1)si la entrada A, B o ambas estn en un nivel lgico 1.
La salida de la compuerta OR ser BAJA (nivel lgico 0) si todas sus entradas
estn en el nivel lgico 0.
Esta misma idea puede ampliarse a ms de dos entradas. La figura a
continuacin muestra una compuerta OR de tres entradas y su tabla de verdad.
El anlisis de esta tabla muestra una vez ms que la salida ser 1 en cualquier
caso donde una o ms entradas sean 1. Este principio general es el mismo que
rige para compuertas OR con cualquier nmero de entradas.
Mediante el uso del lenguaje del lgebra booleana, la salida x puede
expresarse como x=A+B+C, donde una vez ms debe hacerse hincapi en el
signo + que representa la operacin OR. L a salida de cualquier
compuerta OR se puede expresar como al suma OR de todas sus entradas.
Resumen de la operacin OR:
La operacin OR produce un resultado de 1 cuando cualquiera de las
variables de entrada es 1.
La operacin OR genera un resultado de 0 solo cuando todas las
variables de entrada son 0.
En la operacin OR, 1+1=1, 1+1+1=1, etc.Operacin AND
Si dos variables lgicas A y B se combinan mediante la expresin AND, el
resultado, x, se puede expresar como:
X=AB
En esta expresin el signo representa la operacin booleana de AND, cuyas
reglas se dan en la tabla de verdad que se ve a continuacin:
A
0
0
1
1
0
1
0
1
x=A
B
0
0
0
1
Podemos decir que en la operacin AND el resultado ser 1 solo si todas las
entradas son 1; en los dems casos el resultado ser 0.
La expresin x=AB se lee x es igual a A AND B. El signo de multiplicacin
por lo general se omite como en el lgebra ordinaria, de modo que la expresin
se transforma en x=AB. Lo ms importante que debe recordarse es que la
operacin AND es igual que la operacin ordinaria de multiplicacin,
donde las variables pueden ser 0 o 1.
Compuerta AND
La salida de la compuerta AND es igual al producto AND de las entradas lgicas
(A y B); es decir, x=AB. En otras palabras, la compuerta AND es un circuito que
opera en forma tal que su salida es ALTA solo cuando todas sus entradas son
ALTAS. En todos los otros casos la salida de la compuerta AND es BAJA.
x=
Esta misma operacin es caracterstica de las compuertas ANS con ms de dos
entradas.
Resumen de la operacin AND.
La operacin AND se ejecuta exactamente igual que la multiplicacin
ordinaria de unos y ceros.
Una salida igual a 1 ocurre slo en el caso de que todas las entradas
sean 1.
La salida es 0 en cualquier caso donde una o ms entradas sean 0.
Operacin NOT
La operacin NOT diferente de las dems operaciones OR y AND en que esta
puede efectuarse con una sola variable de entrada. Por ejemplo, si la variable
A se somete a la operacin NOT, el resultado x se puede expresar como:
x=
Donde la barra sobrepuesta representa la operacin NOT. Esta expresin se lee
x es igual a NO A o x es igual a A x= la inversa de A, o tambin x es
igual al complemento de A. Cada
una
de
estas
se
utiliza
0
1
frecuentemente y todas indican
que el valor lgico de x= es
1 0
opuesto al valor lgico de
A.
11= Ya que NOT
0 1=0
01= Ya que NOT
1
0=1
La operacin NOT tambin se conoce como inversin o complementacin y
estos trminos se utilizan como sinnimos. Aunque siempre emplearemos el
indicador de barra sobrepuesta para representar una inversin, es importante
mencionar que otro indicador de inversin es el smbolo primo (). Es decir:
A=
Ambos deben reconocerse como indicadores de la operacin de inversin.
Compuerta NOT (INVERSOR)
Este circuito siempre tiene una entrada y su nivel lgico de salida siempre es
contrario al nivel de esta entrada.
x=
La presencia de un crculo
pequeo siempre denota la
inversin.
Resumen de Operaciones Booleanas
OR
0+0=0
0+1=1
1+0=1
1+1=1
Representacin Grafica
AND
00=0
01=0
10=0
11=1
NOT
00=1
10=0
Descripcin Algebraica de Circuitos Lgicos
Cualquier circuito lgico, sin importar que tan complejo sea, puede describirse
completamente mediante las operaciones que se definieron anteriormente, ya
que los circuitos de las compuertas OR, AND, NOT son elementos bsicos de los
sistemas digitales.
A
B
x=AB
Por ejemplo, considerando el circuito de la figura. Este circuito tiene tres
entradas A, B y C y una sola salida, x. Al utilizar la expresin booleana para
cada compuerta, podemos determinar con facilidad la expresin para la salida.
La expresin para la salida de la compuerta AND se escribe AB. Esta salida
AND se conecta como entrada a la compuerta OR junto con C, otra entrada. La
compuerta OR opera con sus entradas de forma tal que su salida sea la suma
OR de las entradas. As, podemos expresar la salida OR como x=AB+C (Esta
expresin final podra escribirse mejor como x=C+AB, ya que no importa que
el trmino de la suma OR se escriba primero).
En ocasiones, puede existir confusin con respecto de cul operacin se
efecta primero. La expresin AB+C se puede interpretar de dos formas
distintas: (1) AB se opera con OR con C, o bien (2) A se opera con AND con el
termino B+C. Para evitar esta confusin, se entender que si una expresin
contiene las operaciones AND y OR, las operaciones AND se efectan
primero, a menos que haya un parntesis en la expresin, en cuyo
caso, la operacin dentro del parntesis se realiza primero. Esta es la
misma regla que se emplea en el lgebra ordinaria para determinar el orden de
las operaciones.
A+
C
Circuito lgico
cuya expresin
x=(A+B) requiere
parntesis.
Considerando el circuito anterior. La expresin para la salida de la compuerta
OR es simplemente A+B. Esta salida sirve como entrada en la compuerta AND
junto con otra entrada, C. De este modo expresamos la salida de la compuerta
AND como x=(A+B) C. Observe el uso del parntesis aqu para indicar que A y
B se operan con OR primero, antes de que su suma OR realice la operacin
AND con C. Sin los parntesis esta expresin se interpretara incorrectamente,
ya que A+BC significa que A se opera con OR con el producto BC.
Circuitos que contienen INVERSOR
Siempre que un INVERSOR se encuentra presente en un diagrama de circuitos
lgicos, su expresin de salida es simplemente igual a la expresin de entrada
con una barra sobre ella.
A
x=
+B
Circuitos que
utilizan
inversin.
EL circuito se alimenta a travs de un INVERSOR, cuya salida es . La salida del
INVERSOR se alimenta de una compuerta OR junto con B, de modo que la
salida OR es igual a +B. N. Se nota que el inversor solo transforma la A y B
solo se us en la Suma del OR.
A+
x=A+
En este circuito la salida de la compuerta OR es igual a A+B y se alimenta a
travs de un INVERSOR. La salida del INVERSOR es por consiguiente igual a
(A+B),
ya
que
invierte
la
expresin
de
entrada
completa.
1
No es lo mismo (+B) que (A+B). La expresion (A+B) significa que A se opera
con OR con B y luego su suma OR se invierte, mientras que la expresin (+B1 )
indica que A y B se invierten y los resultados de ambos operan con OR.
Ejemplos de circuitos donde se usan los 3 operadores:
A
B
C
BC
A+D
D
A+D
x=BC(A+D)
A+B
(A+B)C
(A+B)C
B
C
D+(A+B)C
x=[D+(A+B)C] E]
E
Evaluacin de las Salidas de los Circuitos Lgicos
Una vez que se obtiene la expresin booleana para la salida de un circuito, el
nivel lgico de la salida se puede determinar para cualquier valor de las
entradas de circuitos. Por ejemplo, en el caso x=BC(A+D), donde A=0, B=1,
C=1, D=1. Cmo sucede en el algebra ordinaria, el valor de x se puede
determinar sustituyendo los valores de las variables en la expresin y
efectuando las operaciones que se indiquen en la siguiente manera:
x=BC(A+D)
=0011(0+1)
=111(0+1)
=111(10)
=1110
=0
En general, siempre deben seguirse los siguientes lineamientos cuando se
evalua una expresin booleana:
Realizar todas las inversiones de trminos simples; es decir 00 =1 o bien
10=0.
Efectuar todas las operaciones dentro del parntesis.
Efectuar una operacin AND antes de una OR a menos que los
parntesis indiquen lo contrario.
Si una expresin tiene una barra sobre ella, efectu las operaciones de la
expresin primero y luego invierta el resultado.
Determinacin del Nivel de Salida a Partir de un Diagrama
Tambin se puede determinar en forma directa el nivel lgico de salida para los
niveles de entrada dados, a partir de un diagrama de circuitos, si usar la
expresin booleana. Se utiliza frecuentemente durante la deteccin de fallas o
el anlisis de un sistema lgico, ya que tambin indica cual de todas las salidas
1
A=0
de la compuerta supuestamente es la salida
1 final.
B=1
C=1
0
1
D=1
x=0
Implantacin de Circuitos a Partir de Expresiones
Booleanas
Si la operacin de un circuito se define por medio de una expresin booleana,
se puede implantar directamente un diagrama de circuito lgico a partir de esa
expresin. Por ejemplo, si necesitramos un circuito que se definiera por
x=ABC, inmediatamente sabramos que solo se necesita una compuerta AND
de tres entradas. Si se necesita un circuito que se definiera por x=A+B0 ,
emplearamos una compuerta OR de dos entradas con un INVERSOR en una
entrada. El mismo razonamiento que se aplica en estos casos aislados se
puede aplicar tambin a circuitos ms complejos.
Supongamos que deseamos construir un circuito cuya salida es
x=AC+AC0+BC. Esta expresin booleana contiene tres trminos (AC,BC0 ,BC),
los cuales se operan todos con OR. Esto nos indica que se requiere una
compuerta OR de tres entradas que sean iguales a AC, BC0 y BC,
respectivamente.
A
A
B
x=AC+ACC+
Cada entrada de la compuerta OR es un trmino del producto AND, lo que
significa que se puede usar una compuerta AND con entradas adecuadas para
generar cada trmino.
Tambin se nota que las expresiones son
complementarias, a si que se usara INVERSORES en las entradas antes de que
lleguen a la entrada AND.
A
C
CC
BCC
B
C
x=AC+BCC
+BC
Compuertas NOR y NAND
Otros dos tipos de compuertas lgicas, NOR y NAND, se utilizan extensamente
en los circuitos digitales. Estas compuertas combinan las operaciones bsicas
AND, OR y NOT, las cuales facilitan su descripcin mediante las operaciones de
algebra booleana.
Compuerta NOR
Es igual al smbolo de la operacin OR excepto que tiene un crculo pequeo en
la salida, que corresponde la operacin de inversin. De este modo, la
compuerta NOR opera como una compuerta OR seguida de un INVERSOR.
A
0
0
1
1
OR
B
A+B
0
0
1
1
0
1
Denota
1
1
Inversi
n
NOR
A+B
1
0
0
0
Esta operacin es equivalente a:
Compuerta NAND
Es igual al smbolo de la operacin AND excepto que tiene un crculo pequeo
en la salida, que corresponde la operacin de inversin. De este modo, la
compuerta
NAND
opera
como
una
AND
NAN
compuerta
AND seguida de un INVERSOR.
D
A
B
AB
AB
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
Denota
Inversi
n
Esta operacin es equivalente a:
Teoremas y Postulados
Teoremas de Boole
Los postulados son las teoras y reglas que ya existen y los teoremas son las
afirmaciones que pueden ser demostrados con los postulados.
Teoremas.
Teoremas con operacin AND
Teorema 1.- Si cualquier variable (x) se opera con AND con un 0, el resultado
tiene que ser 0.
x0
=0
Teorema 2.- Si cualquier variable (x) se opera con AND con un 1, el resultado
tiene que ser la variable (x).
x1
=x
Teorema 3.- Si una entrada de variable (x) se opera con AND, el resultado
tiene que ser la variable (x).
xx
=x
Teorema 4.- Si una entrada de variable (x) se opera con AND y en una
entrada del AND hay un INVERSOR, el resultado tiene que ser 0.
xxC
=0
x
0
Teoremas con operacin OR
Teorema 5.- Si cualquier variable (x) se opera con OR con un 0, el resultado
tiene que ser la variable (x).
x+0
=x
Teorema 6.- Si cualquier variable (x) se opera con OR con un 1, el resultado
tiene que ser 1.
x+1
=1
Teorema 7.- Si una entrada de variable (x) se opera con OR, el resultado tiene
que ser la variable (x).
x+x
=x
Teorema 8.- Si una entrada de variable (x) se opera con OR y en una entrada
del OR hay un inversor, el resultado tiene que ser 1.
x+xC
=1
Teoremas con Mltiples Variables
Teorema 9.-
x+y=y+x
Teorema 10.xy=yx
Los teoremas 9 y 19 se denominan Leyes Conmutativas. Estas leyes
indican que no importa el orden en que operamos dos variables con OR
y AND; el resultado es el mismo.
Teorema 11.x+(y+z)=(x+y)+z=x+y+
Teorema 12.x(yz)=(xy)z=xyz
Los teoremas 11 y 12 se denominan Leyes Asociativa. Estas leyes
afirman que podemos agrupar las variables en una expresin AND o en
una OR en la forma que se desee.
Teorema 13 a.x(y+z)=xy+xz
Teorema 13 b.(w+x)(y+z)=wy+xy+wz+xz
El teorema 13 es la Ley Distributiva. Esta ley afirma que una expresin
puede desarrollarse multiplicando termino a trmino, como en el algebra
ordinaria. Este teorema indica asimismo que podemos factorizar una
expresin. Es decir, si tenemos una suma de dos (o ms) trminos, y
cada uno contiene una variable comn, esta se puede factorizar como
en el algebra ordinaria.
Todos estos teoremas booleanos pueden ser de utilidad para simplificar
una expresin lgica; es decir, para reducir el nmero de trminos de la
expresin. Cuando se hace esto, la expresin reducida producir un
circuito menos complejo que el que la expresin original habra
generado.
Teoremas de DeMorgan
Dos de los teoremas mas importantes del algebra booleana fueron
enunciados por el eminente matemtico DeMorgan. Los Teoremas de
DeMorgan son de extrema utilidad en la simplificacin de expresiones
en las cuales se invierte un producto o suma de variables.
Teorema 16.(x+y)= xC yC
El teorema 16 afirma que invertir la suma OR de dos variables es lo
mismo que invertir cada variable por separado y luego operarlas con
AND.
Teorema 17
(xy)= xC + yC
El teorema 17 afirma que invertir el producto AND de dos variables es lo
mismo que invertir cada variable por separado y luego operarlas con OR.
Cada teorema de DeMorgan se puede demostrar rpidamente
verificando todas las combinaciones de x, y.
Implicaciones de los Teoremas de DeMorgan
Teorema 16.-
x
y
x
+
x
y
xC yC =
x+y
xC +yC =
xy
x
y
xC yC =
x+y
Teorema 17.-
x
y
xC +yC =
x+y
Mini y maxi trminos.
Mini trminos
Es un producto booleano en la que cada variable aparece slo una vez; es
decir, es una expresin lgica que se compone de variables y los operadores
lgicos AND y NOT. P. ejemplo. ABC y ABC.
Para una funcin booleana de n variables x1,...xn, unproducto booleano en el
que cada una de las n variables aparece una sola vez (negada o sin negar) es
llamado mini trmino. Es decir, un mini trmino es una expresin lgica
de n variables consistente nicamente en el operadorconjuncin lgica (AND) y
el operador complemento o negacin (NOT).
Por ejemplo,
,
y
son ejemplos de mini trminos para una funcin
booleana con las tres variables , y .
Maxi trminos
Es una expresin lgica que se compone de variables y los operadores lgicos
OR y NOT. P. ejemplo. A+B+C y A+B+C.
Un maxi trmino es una expresin lgica de n variables que consiste
nicamente en la disyuncin lgica y el operador complemento o negacin. Los
maxi trminos son una expresin dual de los mini trminos. En vez de usar
operaciones AND utilizamos operaciones OR y procedemos de forma similar.
Por ejemplo, los siguientes trminos cannicos son maxi trminos:
