Post on 29-Jun-2015
REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA EDUCAIOacuteN
INSTITUTO UNIVERSITARIO DE TECNOLOGIA INDUSTRIAL
ldquoRODOLFO LOERO ARISMENDIrdquo
IUTIRLA
EXTENCIOacuteN PUNTO FIJO
Realizado por
Alfonso Loacutepez 17666726
Introduccioacuten
En este trabajo nos enfocamos en las teoriacuteas funciones y aplicaciones del
algebra booleana con el fin de encontrar respuestas a nuestras interrogantes para la
posterior aplicacioacuten en el desarrollo de los programas informaacuteticos
Para ello vamos a estudiar su concepto caracteriacutesticas leyes fundamentales
procedimientos y aplicaciones para la misma
Definiciones
La herramienta fundamental para el anaacutelisis y disentildeo de circuitos digitales es el Aacutelgebra
Booleana Esta aacutelgebra es un conjunto de reglas matemaacuteticas (similares en algunos
aspectos al algebra convencional) pero que tienen la virtud de corresponder al
comportamiento de circuitos basados en dispositivos de conmutacioacuten (interruptores
relevadores transistores etc) En este capiacutetulo se presentan los postulados que definen
el aacutelgebra booleana se presentan en forma de teoremas los resultados maacutes importantes
se presentan tambieacuten los tres ejemplos claacutesicos de aacutelgebras boolenas (loacutegica
proposicional aacutelgebra de conjuntos aacutelgebra de switches) y herramientas baacutesicas como
tablas de verdad y diagramas de Venn
El aacutelgebra booleana es un sistema matemaacutetico deductivo centrado en los valores cero y
uno (falso y verdadero) Un operador binario ordm definido en eacuteste juego de valores
acepta un par de entradas y produce un solo valor booleano por ejemplo el operador
booleano AND acepta dos entradas booleanas y produce una sola salida booleana
Para cualquier sistema algebraico existen una serie de postulados iniciales de aquiacute se
pueden deducir reglas adicionales teoremas y otras propiedades del sistema el aacutelgebra
booleana a menudo emplea los siguientes postulados
Cerrado El sistema booleano se considera cerrado con respecto a un operador
binario si para cada par de valores booleanos se produce un solo resultado
booleano
Conmutativo Se dice que un operador binario ordm es conmutativo si A ordm B = B ordm
A para todos los posibles valores de A y B
Asociativo Se dice que un operador binario ordm es asociativo si (A ordm B) ordm C = A
ordm (B ordm C) para todos los valores booleanos A B y C
Distributivo Dos operadores binarios ordm y son distributivos si A ordm (B
C) = (A ordm B) (A ordm C) para todos los valores booleanos A B y C
Identidad Un valor booleano I se dice que es un elemento de identidad con
respecto a un operador binario ordm si A ordm I = A
Inverso Un valor booleano I es un elemento inverso con respecto a un operador
booleano ordm si A ordm I = B y B es diferente de A es decir B es el valor opuesto
de A
Principio de dualidad
El concepto de dualidad permite formalizar este hecho a toda relacioacuten o ley loacutegica le
corresponderaacute su dual formada mediante el intercambio de los operadores unioacuten (suma
loacutegica) con los de interseccioacuten (producto loacutegico) y de los 1 con los 0
Ademaacutes hay que cambiar cada variable por su negada Esto causa confusioacuten al aplicarlo
en los teoremas baacutesicos pero es totalmente necesario para la correcta aplicacioacuten del
principio de dualidad Veacutease que esto no modifica la tabla adjunta
Adicioacuten Producto
1
2
3
4
5
6
7
8
9
Funciones Booleanas
En forma similar a como se define en los cursos de aacutelgebra de nuacutemeros reales es
posible definir una relacioacuten de dependencia de una variable booleana o variable loacutegica
con otras variables booleanas independientes Es decir es posible definir funciones
booleanas o funciones loacutegicas
Definicioacuten Sean X1X2Xn variables booleanas es decir variables que pueden
tomar el valor de 0 o de 1 entonces la expresioacuten
Y = f(X1X2Xn) denota una dependencia funcional de la variable dependiente Y
respecto a las variables independientes X1X2Xn es decir el valor (0 o 1) que toma
la variable Y depende de la combinacioacuten de n valores (1rsquos y 0rsquos) que tomen las n
variables X1X2Xn
Ejemplo La siguiente es una funcioacuten booleana
Y= f(ABC) = AB + AC + A C
Esta funcioacuten se puede evaluar para diversos valores de sus variables independientes A
B C
Si A = 1 B = 0 C = 0 entonces Y= f(100) = 10 + 00 + 11 = 1
Si A = 1 B = 1 C = 0 entonces Y= f(110) = 11 + 00 + 11 = 1
Si A = 0 B = 1 C = 0 entonces Y= f(010) = 01 + 10 + 01 = 0 etc
A diferencia de las funciones de variable real las cuales no pueden representarse
completamente usando una tabla de valores las funciones booleanas siacute quedan
totalmente especificadas por una tabla que incluya todas las posibles combinaciones de
valores que pueden tomar las variables independientes dicha tabla se denomina tabla de
verdad y es completamente equivalente a la expresioacuten booleana ya que incluye todas
sus posibilidades
Ejemplo La siguiente es la tabla de verdad para la funcioacuten del ejemplo anterior
A B C f(ABC)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
En general para una funcioacuten de n variables puesto que hay n variables y cada variable
tiene dos posibles valores hay 2n maneras de asignar estos valores a las n variables asiacute
la tabla de verdad tendraacute 2n renglones
Por ejemplo en el ejemplo anterior f(ABC) es una funcioacuten de 3 variables por lo que
tenemos 23 = 8 diferentes combinaciones de las entradas y por lo tanto 8 renglones de la
tabla de verdad
FUNCIONES BOOLEANAS DE UNA y DOS VARIABLES
En el caso de funciones de variable real seriacutea imposible tratar de mencionar todas las
posibles funciones de una o maacutes variables sin embargo en el caso de funciones
booleanas se puede hacer un listado completo de todas y cada una de las funciones para
cierto nuacutemero de variables a continuacioacuten se hace una lista de eacutestas para los casos de 0
1 y 2 variables independientes
Funciones de cero variables
Estas son las funciones constantes y soacutelo hay dos
f0 = 0 Funcioacuten constante cero
f1 = 1 Funcioacuten constante uno
Funciones de una variable
Ademaacutes de las funciones constantes ahora se pueden definir otras dos
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Introduccioacuten
En este trabajo nos enfocamos en las teoriacuteas funciones y aplicaciones del
algebra booleana con el fin de encontrar respuestas a nuestras interrogantes para la
posterior aplicacioacuten en el desarrollo de los programas informaacuteticos
Para ello vamos a estudiar su concepto caracteriacutesticas leyes fundamentales
procedimientos y aplicaciones para la misma
Definiciones
La herramienta fundamental para el anaacutelisis y disentildeo de circuitos digitales es el Aacutelgebra
Booleana Esta aacutelgebra es un conjunto de reglas matemaacuteticas (similares en algunos
aspectos al algebra convencional) pero que tienen la virtud de corresponder al
comportamiento de circuitos basados en dispositivos de conmutacioacuten (interruptores
relevadores transistores etc) En este capiacutetulo se presentan los postulados que definen
el aacutelgebra booleana se presentan en forma de teoremas los resultados maacutes importantes
se presentan tambieacuten los tres ejemplos claacutesicos de aacutelgebras boolenas (loacutegica
proposicional aacutelgebra de conjuntos aacutelgebra de switches) y herramientas baacutesicas como
tablas de verdad y diagramas de Venn
El aacutelgebra booleana es un sistema matemaacutetico deductivo centrado en los valores cero y
uno (falso y verdadero) Un operador binario ordm definido en eacuteste juego de valores
acepta un par de entradas y produce un solo valor booleano por ejemplo el operador
booleano AND acepta dos entradas booleanas y produce una sola salida booleana
Para cualquier sistema algebraico existen una serie de postulados iniciales de aquiacute se
pueden deducir reglas adicionales teoremas y otras propiedades del sistema el aacutelgebra
booleana a menudo emplea los siguientes postulados
Cerrado El sistema booleano se considera cerrado con respecto a un operador
binario si para cada par de valores booleanos se produce un solo resultado
booleano
Conmutativo Se dice que un operador binario ordm es conmutativo si A ordm B = B ordm
A para todos los posibles valores de A y B
Asociativo Se dice que un operador binario ordm es asociativo si (A ordm B) ordm C = A
ordm (B ordm C) para todos los valores booleanos A B y C
Distributivo Dos operadores binarios ordm y son distributivos si A ordm (B
C) = (A ordm B) (A ordm C) para todos los valores booleanos A B y C
Identidad Un valor booleano I se dice que es un elemento de identidad con
respecto a un operador binario ordm si A ordm I = A
Inverso Un valor booleano I es un elemento inverso con respecto a un operador
booleano ordm si A ordm I = B y B es diferente de A es decir B es el valor opuesto
de A
Principio de dualidad
El concepto de dualidad permite formalizar este hecho a toda relacioacuten o ley loacutegica le
corresponderaacute su dual formada mediante el intercambio de los operadores unioacuten (suma
loacutegica) con los de interseccioacuten (producto loacutegico) y de los 1 con los 0
Ademaacutes hay que cambiar cada variable por su negada Esto causa confusioacuten al aplicarlo
en los teoremas baacutesicos pero es totalmente necesario para la correcta aplicacioacuten del
principio de dualidad Veacutease que esto no modifica la tabla adjunta
Adicioacuten Producto
1
2
3
4
5
6
7
8
9
Funciones Booleanas
En forma similar a como se define en los cursos de aacutelgebra de nuacutemeros reales es
posible definir una relacioacuten de dependencia de una variable booleana o variable loacutegica
con otras variables booleanas independientes Es decir es posible definir funciones
booleanas o funciones loacutegicas
Definicioacuten Sean X1X2Xn variables booleanas es decir variables que pueden
tomar el valor de 0 o de 1 entonces la expresioacuten
Y = f(X1X2Xn) denota una dependencia funcional de la variable dependiente Y
respecto a las variables independientes X1X2Xn es decir el valor (0 o 1) que toma
la variable Y depende de la combinacioacuten de n valores (1rsquos y 0rsquos) que tomen las n
variables X1X2Xn
Ejemplo La siguiente es una funcioacuten booleana
Y= f(ABC) = AB + AC + A C
Esta funcioacuten se puede evaluar para diversos valores de sus variables independientes A
B C
Si A = 1 B = 0 C = 0 entonces Y= f(100) = 10 + 00 + 11 = 1
Si A = 1 B = 1 C = 0 entonces Y= f(110) = 11 + 00 + 11 = 1
Si A = 0 B = 1 C = 0 entonces Y= f(010) = 01 + 10 + 01 = 0 etc
A diferencia de las funciones de variable real las cuales no pueden representarse
completamente usando una tabla de valores las funciones booleanas siacute quedan
totalmente especificadas por una tabla que incluya todas las posibles combinaciones de
valores que pueden tomar las variables independientes dicha tabla se denomina tabla de
verdad y es completamente equivalente a la expresioacuten booleana ya que incluye todas
sus posibilidades
Ejemplo La siguiente es la tabla de verdad para la funcioacuten del ejemplo anterior
A B C f(ABC)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
En general para una funcioacuten de n variables puesto que hay n variables y cada variable
tiene dos posibles valores hay 2n maneras de asignar estos valores a las n variables asiacute
la tabla de verdad tendraacute 2n renglones
Por ejemplo en el ejemplo anterior f(ABC) es una funcioacuten de 3 variables por lo que
tenemos 23 = 8 diferentes combinaciones de las entradas y por lo tanto 8 renglones de la
tabla de verdad
FUNCIONES BOOLEANAS DE UNA y DOS VARIABLES
En el caso de funciones de variable real seriacutea imposible tratar de mencionar todas las
posibles funciones de una o maacutes variables sin embargo en el caso de funciones
booleanas se puede hacer un listado completo de todas y cada una de las funciones para
cierto nuacutemero de variables a continuacioacuten se hace una lista de eacutestas para los casos de 0
1 y 2 variables independientes
Funciones de cero variables
Estas son las funciones constantes y soacutelo hay dos
f0 = 0 Funcioacuten constante cero
f1 = 1 Funcioacuten constante uno
Funciones de una variable
Ademaacutes de las funciones constantes ahora se pueden definir otras dos
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Definiciones
La herramienta fundamental para el anaacutelisis y disentildeo de circuitos digitales es el Aacutelgebra
Booleana Esta aacutelgebra es un conjunto de reglas matemaacuteticas (similares en algunos
aspectos al algebra convencional) pero que tienen la virtud de corresponder al
comportamiento de circuitos basados en dispositivos de conmutacioacuten (interruptores
relevadores transistores etc) En este capiacutetulo se presentan los postulados que definen
el aacutelgebra booleana se presentan en forma de teoremas los resultados maacutes importantes
se presentan tambieacuten los tres ejemplos claacutesicos de aacutelgebras boolenas (loacutegica
proposicional aacutelgebra de conjuntos aacutelgebra de switches) y herramientas baacutesicas como
tablas de verdad y diagramas de Venn
El aacutelgebra booleana es un sistema matemaacutetico deductivo centrado en los valores cero y
uno (falso y verdadero) Un operador binario ordm definido en eacuteste juego de valores
acepta un par de entradas y produce un solo valor booleano por ejemplo el operador
booleano AND acepta dos entradas booleanas y produce una sola salida booleana
Para cualquier sistema algebraico existen una serie de postulados iniciales de aquiacute se
pueden deducir reglas adicionales teoremas y otras propiedades del sistema el aacutelgebra
booleana a menudo emplea los siguientes postulados
Cerrado El sistema booleano se considera cerrado con respecto a un operador
binario si para cada par de valores booleanos se produce un solo resultado
booleano
Conmutativo Se dice que un operador binario ordm es conmutativo si A ordm B = B ordm
A para todos los posibles valores de A y B
Asociativo Se dice que un operador binario ordm es asociativo si (A ordm B) ordm C = A
ordm (B ordm C) para todos los valores booleanos A B y C
Distributivo Dos operadores binarios ordm y son distributivos si A ordm (B
C) = (A ordm B) (A ordm C) para todos los valores booleanos A B y C
Identidad Un valor booleano I se dice que es un elemento de identidad con
respecto a un operador binario ordm si A ordm I = A
Inverso Un valor booleano I es un elemento inverso con respecto a un operador
booleano ordm si A ordm I = B y B es diferente de A es decir B es el valor opuesto
de A
Principio de dualidad
El concepto de dualidad permite formalizar este hecho a toda relacioacuten o ley loacutegica le
corresponderaacute su dual formada mediante el intercambio de los operadores unioacuten (suma
loacutegica) con los de interseccioacuten (producto loacutegico) y de los 1 con los 0
Ademaacutes hay que cambiar cada variable por su negada Esto causa confusioacuten al aplicarlo
en los teoremas baacutesicos pero es totalmente necesario para la correcta aplicacioacuten del
principio de dualidad Veacutease que esto no modifica la tabla adjunta
Adicioacuten Producto
1
2
3
4
5
6
7
8
9
Funciones Booleanas
En forma similar a como se define en los cursos de aacutelgebra de nuacutemeros reales es
posible definir una relacioacuten de dependencia de una variable booleana o variable loacutegica
con otras variables booleanas independientes Es decir es posible definir funciones
booleanas o funciones loacutegicas
Definicioacuten Sean X1X2Xn variables booleanas es decir variables que pueden
tomar el valor de 0 o de 1 entonces la expresioacuten
Y = f(X1X2Xn) denota una dependencia funcional de la variable dependiente Y
respecto a las variables independientes X1X2Xn es decir el valor (0 o 1) que toma
la variable Y depende de la combinacioacuten de n valores (1rsquos y 0rsquos) que tomen las n
variables X1X2Xn
Ejemplo La siguiente es una funcioacuten booleana
Y= f(ABC) = AB + AC + A C
Esta funcioacuten se puede evaluar para diversos valores de sus variables independientes A
B C
Si A = 1 B = 0 C = 0 entonces Y= f(100) = 10 + 00 + 11 = 1
Si A = 1 B = 1 C = 0 entonces Y= f(110) = 11 + 00 + 11 = 1
Si A = 0 B = 1 C = 0 entonces Y= f(010) = 01 + 10 + 01 = 0 etc
A diferencia de las funciones de variable real las cuales no pueden representarse
completamente usando una tabla de valores las funciones booleanas siacute quedan
totalmente especificadas por una tabla que incluya todas las posibles combinaciones de
valores que pueden tomar las variables independientes dicha tabla se denomina tabla de
verdad y es completamente equivalente a la expresioacuten booleana ya que incluye todas
sus posibilidades
Ejemplo La siguiente es la tabla de verdad para la funcioacuten del ejemplo anterior
A B C f(ABC)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
En general para una funcioacuten de n variables puesto que hay n variables y cada variable
tiene dos posibles valores hay 2n maneras de asignar estos valores a las n variables asiacute
la tabla de verdad tendraacute 2n renglones
Por ejemplo en el ejemplo anterior f(ABC) es una funcioacuten de 3 variables por lo que
tenemos 23 = 8 diferentes combinaciones de las entradas y por lo tanto 8 renglones de la
tabla de verdad
FUNCIONES BOOLEANAS DE UNA y DOS VARIABLES
En el caso de funciones de variable real seriacutea imposible tratar de mencionar todas las
posibles funciones de una o maacutes variables sin embargo en el caso de funciones
booleanas se puede hacer un listado completo de todas y cada una de las funciones para
cierto nuacutemero de variables a continuacioacuten se hace una lista de eacutestas para los casos de 0
1 y 2 variables independientes
Funciones de cero variables
Estas son las funciones constantes y soacutelo hay dos
f0 = 0 Funcioacuten constante cero
f1 = 1 Funcioacuten constante uno
Funciones de una variable
Ademaacutes de las funciones constantes ahora se pueden definir otras dos
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Inverso Un valor booleano I es un elemento inverso con respecto a un operador
booleano ordm si A ordm I = B y B es diferente de A es decir B es el valor opuesto
de A
Principio de dualidad
El concepto de dualidad permite formalizar este hecho a toda relacioacuten o ley loacutegica le
corresponderaacute su dual formada mediante el intercambio de los operadores unioacuten (suma
loacutegica) con los de interseccioacuten (producto loacutegico) y de los 1 con los 0
Ademaacutes hay que cambiar cada variable por su negada Esto causa confusioacuten al aplicarlo
en los teoremas baacutesicos pero es totalmente necesario para la correcta aplicacioacuten del
principio de dualidad Veacutease que esto no modifica la tabla adjunta
Adicioacuten Producto
1
2
3
4
5
6
7
8
9
Funciones Booleanas
En forma similar a como se define en los cursos de aacutelgebra de nuacutemeros reales es
posible definir una relacioacuten de dependencia de una variable booleana o variable loacutegica
con otras variables booleanas independientes Es decir es posible definir funciones
booleanas o funciones loacutegicas
Definicioacuten Sean X1X2Xn variables booleanas es decir variables que pueden
tomar el valor de 0 o de 1 entonces la expresioacuten
Y = f(X1X2Xn) denota una dependencia funcional de la variable dependiente Y
respecto a las variables independientes X1X2Xn es decir el valor (0 o 1) que toma
la variable Y depende de la combinacioacuten de n valores (1rsquos y 0rsquos) que tomen las n
variables X1X2Xn
Ejemplo La siguiente es una funcioacuten booleana
Y= f(ABC) = AB + AC + A C
Esta funcioacuten se puede evaluar para diversos valores de sus variables independientes A
B C
Si A = 1 B = 0 C = 0 entonces Y= f(100) = 10 + 00 + 11 = 1
Si A = 1 B = 1 C = 0 entonces Y= f(110) = 11 + 00 + 11 = 1
Si A = 0 B = 1 C = 0 entonces Y= f(010) = 01 + 10 + 01 = 0 etc
A diferencia de las funciones de variable real las cuales no pueden representarse
completamente usando una tabla de valores las funciones booleanas siacute quedan
totalmente especificadas por una tabla que incluya todas las posibles combinaciones de
valores que pueden tomar las variables independientes dicha tabla se denomina tabla de
verdad y es completamente equivalente a la expresioacuten booleana ya que incluye todas
sus posibilidades
Ejemplo La siguiente es la tabla de verdad para la funcioacuten del ejemplo anterior
A B C f(ABC)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
En general para una funcioacuten de n variables puesto que hay n variables y cada variable
tiene dos posibles valores hay 2n maneras de asignar estos valores a las n variables asiacute
la tabla de verdad tendraacute 2n renglones
Por ejemplo en el ejemplo anterior f(ABC) es una funcioacuten de 3 variables por lo que
tenemos 23 = 8 diferentes combinaciones de las entradas y por lo tanto 8 renglones de la
tabla de verdad
FUNCIONES BOOLEANAS DE UNA y DOS VARIABLES
En el caso de funciones de variable real seriacutea imposible tratar de mencionar todas las
posibles funciones de una o maacutes variables sin embargo en el caso de funciones
booleanas se puede hacer un listado completo de todas y cada una de las funciones para
cierto nuacutemero de variables a continuacioacuten se hace una lista de eacutestas para los casos de 0
1 y 2 variables independientes
Funciones de cero variables
Estas son las funciones constantes y soacutelo hay dos
f0 = 0 Funcioacuten constante cero
f1 = 1 Funcioacuten constante uno
Funciones de una variable
Ademaacutes de las funciones constantes ahora se pueden definir otras dos
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Funciones Booleanas
En forma similar a como se define en los cursos de aacutelgebra de nuacutemeros reales es
posible definir una relacioacuten de dependencia de una variable booleana o variable loacutegica
con otras variables booleanas independientes Es decir es posible definir funciones
booleanas o funciones loacutegicas
Definicioacuten Sean X1X2Xn variables booleanas es decir variables que pueden
tomar el valor de 0 o de 1 entonces la expresioacuten
Y = f(X1X2Xn) denota una dependencia funcional de la variable dependiente Y
respecto a las variables independientes X1X2Xn es decir el valor (0 o 1) que toma
la variable Y depende de la combinacioacuten de n valores (1rsquos y 0rsquos) que tomen las n
variables X1X2Xn
Ejemplo La siguiente es una funcioacuten booleana
Y= f(ABC) = AB + AC + A C
Esta funcioacuten se puede evaluar para diversos valores de sus variables independientes A
B C
Si A = 1 B = 0 C = 0 entonces Y= f(100) = 10 + 00 + 11 = 1
Si A = 1 B = 1 C = 0 entonces Y= f(110) = 11 + 00 + 11 = 1
Si A = 0 B = 1 C = 0 entonces Y= f(010) = 01 + 10 + 01 = 0 etc
A diferencia de las funciones de variable real las cuales no pueden representarse
completamente usando una tabla de valores las funciones booleanas siacute quedan
totalmente especificadas por una tabla que incluya todas las posibles combinaciones de
valores que pueden tomar las variables independientes dicha tabla se denomina tabla de
verdad y es completamente equivalente a la expresioacuten booleana ya que incluye todas
sus posibilidades
Ejemplo La siguiente es la tabla de verdad para la funcioacuten del ejemplo anterior
A B C f(ABC)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
En general para una funcioacuten de n variables puesto que hay n variables y cada variable
tiene dos posibles valores hay 2n maneras de asignar estos valores a las n variables asiacute
la tabla de verdad tendraacute 2n renglones
Por ejemplo en el ejemplo anterior f(ABC) es una funcioacuten de 3 variables por lo que
tenemos 23 = 8 diferentes combinaciones de las entradas y por lo tanto 8 renglones de la
tabla de verdad
FUNCIONES BOOLEANAS DE UNA y DOS VARIABLES
En el caso de funciones de variable real seriacutea imposible tratar de mencionar todas las
posibles funciones de una o maacutes variables sin embargo en el caso de funciones
booleanas se puede hacer un listado completo de todas y cada una de las funciones para
cierto nuacutemero de variables a continuacioacuten se hace una lista de eacutestas para los casos de 0
1 y 2 variables independientes
Funciones de cero variables
Estas son las funciones constantes y soacutelo hay dos
f0 = 0 Funcioacuten constante cero
f1 = 1 Funcioacuten constante uno
Funciones de una variable
Ademaacutes de las funciones constantes ahora se pueden definir otras dos
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
A B C f(ABC)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
En general para una funcioacuten de n variables puesto que hay n variables y cada variable
tiene dos posibles valores hay 2n maneras de asignar estos valores a las n variables asiacute
la tabla de verdad tendraacute 2n renglones
Por ejemplo en el ejemplo anterior f(ABC) es una funcioacuten de 3 variables por lo que
tenemos 23 = 8 diferentes combinaciones de las entradas y por lo tanto 8 renglones de la
tabla de verdad
FUNCIONES BOOLEANAS DE UNA y DOS VARIABLES
En el caso de funciones de variable real seriacutea imposible tratar de mencionar todas las
posibles funciones de una o maacutes variables sin embargo en el caso de funciones
booleanas se puede hacer un listado completo de todas y cada una de las funciones para
cierto nuacutemero de variables a continuacioacuten se hace una lista de eacutestas para los casos de 0
1 y 2 variables independientes
Funciones de cero variables
Estas son las funciones constantes y soacutelo hay dos
f0 = 0 Funcioacuten constante cero
f1 = 1 Funcioacuten constante uno
Funciones de una variable
Ademaacutes de las funciones constantes ahora se pueden definir otras dos
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
f0(A) = 0 Funcioacuten constante cero
f1(A) = A Funcioacuten identidad
f2(A) = A Funcioacuten complemento negacioacuten
f3(A) = 1 Funcioacuten constante uno
Funciones de dos variables
En este caso se pueden definir 16 funciones diferentes las cuales incluyen las cuatro
anteriores y otras doce maacutes En las siguiente tabla se muestra un resumen de las
dieciseacuteis funciones de dos variables incluyendo su nombre su tabla de verdad y su
expresioacuten loacutegica (booleana)
Const
CERO AND Identidad Identidad EXOR OR
A B 0 AB A B A A B B A Aring B A + B
0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
NOR EQUIVAL
ENCIA NOT NOT NAND Const
UNO
A B A + B A B B A + B A A + B A B 1
0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1
OBSERVACIOacuteN
Ciertamente las expresiones loacutegicas que aparecen en la tabla anterior no son uacutenicas ya
que una misma funcioacuten loacutegica puede tener diferentes representaciones algebraicas
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Circuitos Logicos
Se dice que una variable tiene valor booleano cuando en general la variable contiene
un 0 loacutegico o un 1 loacutegico Esto en la mayoriacutea de los lenguajes de programacioacuten se
traduce en false (falso) o true (verdadero) respectivamente
Una variable puede no ser de tipo booleano y guardar valores que en principio no son
booleanos ya que globalmente los compiladores trabajan con esos otros valores
numeacutericos normalmente aunque tambieacuten algunos permiten cambios desde incluso
caracteres finalizando en valor booleano
El 0 loacutegico
El valor booleano de negacioacuten suele ser representado como false aunque tambieacuten
permite y equivale al valor natural entero y decimal (exacto) 0 asiacute como la cadena
false e incluso la cadena 0
El 1 loacutegico
En cambio el resto de valores apuntan al valor booleano de afirmacioacuten representado
normalmente como true ya que por definicioacuten el valor 1 se tiene cuando no es 0
Cualquier nuacutemero distinto de cero se comporta como un 1 loacutegico y lo mismo sucede
con casi cualquier cadena (menos la false en caso de ser eacutesta la correspondiente al 0
loacutegico)
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Simplificacioacuten
FUNCION NOT
NOT (Verdadero) = Falso
NOT (Falso) = Verdadero
FUNCION OR
Falso OR Falso = Falso
Falso OR Verdadero = Verdadero
Verdadero OR Falso = Verdadero
Verdadero OR Verdadero = Verdadero
FUNCION XOR (OR EXCLUSIVA)
Falso XOR Falso = Verdadero
Falso XOR Verdadero = Falso
Verdadero XOR Falso = Falso
Verdadero XOR Verdadero = Verdadero
FUNCION AND
Falso AND Falso = Falso
Falso AND Verdadero = Falso
Verdadero AND Falso = Falso
Verdadero AND Verdadero = Verdadero
FUNCION IMPLICANCIA (ENTONCES)
Falso ENTONCES Falso = Verdadero
Falso ENTONCES Verdadero = Falso
Verdadero ENTONCES Falso = Verdadero
Verdadero ENTONCES Verdadero = Verdadero
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Factorizacion
Veamos un ejemplo
F(abcd) = Σ m (569101314)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot bmiddot c middotd +a middot b middot c middotd (1)
= a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot c middotd middot (b + b) +a middot c middotd middot (b + b)
= a middot b middot c middotd + a middot bmiddotcmiddotd +a middot c middot d +a middot cmiddotd
= cmiddotd middot(a middot b +a) +cmiddotd middot (a +a middot b)
= c middotd middot (a + b) + cmiddot d middot (a + b)
= (c middotd +cmiddotd) middot (a + b) (2)
= a middot c middotd +a middotcmiddotd + bmiddot c middotd + bmiddotcmiddotd (3)
(1) 6 AND de 4 entradas + 1 OR de 6 entradas
(2) 2 OR de 2 entradas + 3 AND de 2 entradas
(3) 4 AND de 3 entradas + 1 OR de 4 entradas
Observaciones El circuito (2) es maacutes simple pero debe notarse que las sentildeales A y B en
el caso (2) pasan a traveacutes de 3 niveles previo a procesar la salida
Cualquier suma de producto o producto de suma puede realizarse por circuitos de 2
niveles donde estos pueden ser AND - OR OR - AND NAND - NANDNOR - NOR
Este tipo de expresiones se dice una expresioacuten de 2ordm orden o circuito de 2ordm orden
Un circuito como el (2) que corresponde a uno de mayor orden se dice un circuito
factorizado Este nombre proviene del hecho de que el proceso a partir de uno de 2ordm
orden es muy similar a un proceso de factorizacioacuten del aacutelgebra convencional
Este tipo de factorizacioacuten se basa principalmente en prueba y error y en la habilidad
para recordar que cierto tipo de productos tienen dicha factorizacioacuten
A continuacioacuten se desarrolla un proceso de minimizacioacuten en el cual se
obtienen expresiones de 2ordm orden
Definicioacuten Una expresioacuten suma de productos de 2ordm orden se diraacute miacutenima si
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
a) No existe una expresioacuten equivalente con menos productos
b) No hay una expresioacuten equivalente que contenga el mismo nuacutemero de productos pero
con menos cantidad de variables Igual enunciado vale para expresiones de producto de
sumas en las cuales se debe reemplazar producto por suma y viceversa
1048583 Nota Puede existir maacutes de una representacioacuten miacutenima
Ejemplo
A) Sea f(abc) = Σm (0146)
= a middot b middot c +a middot b middotc +a middot b middot c +amiddotbmiddot c
Notemos que los 2 primeros teacuterminos se combinan para dar
a middot b middot c +a middot b middotc = a middot b middot(c +c)
= a middot b
y los otros 2 dan
a middot bmiddot c +a middot bmiddot c = a middot c(b + b)
= a middot c
Por lo tanto f= a middot b +amiddot c
Observaciones
i) m0 y m1 son adyacentes en ellos soacutelo cambia la variable ldquocrdquo
ii) al unir m0 y m1 observamos que no aparece la variable que marca la distancia entre
ambos minterm es decir la variable ldquocrdquo
iii) igual caso entre m4 y m6
B) Sea f(abcd) = Σm(57101315)
= a middot bmiddot c middotd +a middot bmiddotcmiddotd +a middot bmiddot cmiddotd +a middotbmiddot c middotd +a middot bmiddotcmiddotd
m5 m7 m10 m13 m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre siacute
m5+m7+m13+m15 = a middot bmiddot c middotd + a middot bmiddotcmiddotd +a middot bmiddot c middotd +a middot bmiddotcmiddotd
= bd
Luego en la agrupacioacuten restante se han eliminado A y C las
cuales son las variables que cambian de valor Asiacute agrupando 2k minterm
adyacentes pueden eliminarse k variables de una funcioacuten
Por lo tanto
f(abcd)= bmiddotd +a middot bmiddot c middotd
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Leyes
1 Ley de idempotencia
2 Ley de involucioacuten
3 Ley conmutativa
4 Ley asociativa
5 Ley distributiva
6 Ley de cancelacioacuten
7 Leyes de De Morgan
Teorema de Morgan
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Las leyes de De Morgan declaran que la suma de n variables globalmente negadas (o
invertidas) es igual al producto de las n variables negadas individualmente y que
inversamente el producto de n variables globalmente negadas es igual a la suma de las
n variables negadas individualmente
Demostracioacuten formal
si y solo si y
para cualquier x oacute
oacute
Por lo tanto
inclusioacuten
oacute
Con proposiciones
La prueba utiliza la asociatividad y la distributividad de las leyes y
Verdad
Si verdad por n
Aplicaciones
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Debido a que los computadores trabajan con informacioacuten binaria la herramienta
matemaacutetica adecuada para el anaacutelisis y disentildeo de su funcionamiento en el algebra de
boole en su forma bivalente aunque fue desarrollada inicialmente para el estudio de la
loacutegica Ha sido a partir de 1938 fecha en que CE Shanon publico su obre Analisis
simboacutelico de circuitos con reles estableciendo los primeros conceptos de la actual teoriacutea
de computacioacuten cuando se ha producido un aumento considerable en el numero de
trabajos de aplicacioacuten del algebra de boole a los computadores digitales Hoy en diacutea
esta herramienta resulta fundamental para el desarrollo de computadores ya que con su
ayuda el anaacutelisis y siacutentesis de combinaciones complejas de circuitos logicos puede
realizarse con rapidez y eficacia
La relacioacuten que existe entre la loacutegica booleana y los sistemas de coacutemputo es fuerte de
hecho se da una relacioacuten uno a uno entre las funciones booleanas y los circuitos
electroacutenicos de compuertas digitales Para cada funcioacuten booleana es posible disentildear un
circuito electroacutenico y viceversa como las funciones booleanas solo requieren de los
operadores AND OR y NOT podemos construir nuestros circuitos utilizando
exclusivamente eacutestos operadores utilizando las compuertas loacutegicas homoacutenimas Un
hecho interesante es que es posible implementar cualquier circuito electroacutenico
utilizando una sola compuerta eacutesta es la compuerta NAND Para probar que podemos
construir cualquier funcioacuten booleana utilizando soacutelo compuertas NAND necesitamos
demostrar coacutemo construir un inversor (NOT) una compuerta AND y una compuerta OR
a partir de una compuerta NAND ya que como se dijo es posible implementar
cualquier funcioacuten booleana utilizando soacutelo los operadores booleanos AND OR y NOT
Para construir un inversor simplemente conectamos juntas las dos entradas de una
compuerta NAND Una vez que tenemos un inversor construir una compuerta AND es
faacutecil soacutelo invertimos la salida de una compuerta NAND despueacutes de todo NOT ( NOT
(A AND B)) es equivalente a A AND B Por supuesto se requieren dos compuertas
NAND para construir una sola compuerta AND nadie ha dicho que los circuitos
implementados soacutelo utilizando compuertas NAND sean lo oacuteptimo solo se ha dicho que
es posible hacerlo La otra compuerta que necesitamos sintetizar es la compuerta loacutegica
OR esto es sencillo si utilizamos los teoremas de De Morgan que en siacutentesis se logra
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
en tres pasos primero se reemplazan todos los bull por + despueacutes se invierte cada
literal y por uacuteltimo se niega la totalidad de la expresioacuten
A OR B
A AND BPrimer paso para aplicar el teorema de De Morgan
A AND BSegundo paso para aplicar el teorema de De Morgan
(A AND B)Tercer paso para aplicar el teorema de De Morgan
(A AND B) = A NAND BDefinicioacuten de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita bien
hay dos buenas razones la primera es que las compuertas NAND son las maacutes
econoacutemicas y en segundo lugar es preferible construir circuitos complejos utilizando los
mismos bloques baacutesicos Observen que es posible construir cualquier circuito loacutegico
utilizando soacutelo compuertas de tipo NOR (NOR = NOT(A OR B)) La correspondencia
entre la loacutegica NAND y la NOR es ortogonal(o sea que esta en aacutengulo recto) entre la
correspondencia de sus formas canoacutenicas Mientras que la loacutegica NOR es uacutetil en
muchos circuitos la mayoriacutea de los disentildeadores utilizan loacutegica NAND
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana
Conclusioacuten
Hemos tomado como conclusioacuten el significado del algebra bolleana y de ello
hemos aprendido su funcioacuten aplicacioacuten y la forma correcta de emplearla para los
distintos dispositivos electroacutenicos como los micro procesadores y las puertas de enlace
que para su manejo es fundamental el algebra booleana