Algebra Booleana
Algebra Booleana
Algebra Booleana
MATERIA
MATEMATICAS DISCRETAS
TRABAJO
INVESTIGACION UNIDAD 4. ALGEBRA BOOLEANA
INTEGRANTES
ALVARO DEL ANGEL HERNANDEZ
MAXIMILIANO GUZMÁN ARGÜELLES
GRUPO
A
SEMESTRE
PRIMERO
FECHA DE ENTREGA
20 DE NOVIEMBRE DE 2022.
1
INDICE
• Introducción………………………………………………..………………3.
TEMAS
lógicos……………………………………………………………………...25.
• Conclusiones………………………………………………………………27.
• Bibliografías………………………………………………………………28.
2
INTRODUCCION
El álgebra booleana o álgebra de Boole es la notación algebraica usada para el tratamiento de variables
binarias. El álgebra booleana fue introducida en 1854 por el matemático ingles George Boole (1815 –
1864), quien fue un autodidacta erudito de la época. Su inquietud surgió de una disputa existente entre
Augustus De Morgan y William Hamilton, acerca de los parámetros que definen a este sistema lógico.
George Boole argumentó que la definición de los valores numéricos 0 y 1 corresponde, en el campo de la
electrónica digital, lo cual la hace bastante presente en la contemporaneidad. Se rige por el concepto de las
compuertas lógicas, donde las operaciones conocidas en el álgebra tradicional se ven notablemente
afectadas.
3
4.1 Teoremas y postulados.
El álgebra booleana es un álgebra, que trata con números binarios y variables binarias. Por lo tanto,
también se le llama Álgebra binaria o Álgebra lógica. Un matemático, llamado George Boole, había
desarrollado este álgebra en 1854. Las variables utilizadas en este álgebra también se denominan variables
booleanas.
El rango de voltajes correspondiente a la lógica 'Alta' se representa con '1' y el rango de voltajes
Postulados Booleano
Considere los números binarios 0 y 1, la variable booleana (x) y su complemento (x '). La variable
booleana o su complemento se conoce como literal. Las cuatro operaciones lógicas O posibles entre estos
x +
0=xx+
1=1x+
x=xx+
x '= 1
Del mismo modo, a continuación se muestran las cuatro operaciones lógicas Y posibles entre esos literales
y números binarios.
x.1 = x
4
x.0 = 0 xx
=x
x.x '= 0
Estos son los simples postulados booleanos. Podemos verificar estos postulados fácilmente, sustituyendo
decir, (x ')' = x.
Las siguientes son las tres leyes básicas del álgebra booleana.
1. Ley conmutativa
2. Ley asociativa
3. Ley distributiva
5
Ley conmutativa
Si cualquier operación lógica de dos variables booleanas da el mismo resultado independientemente del
orden de esas dos variables, entonces esa operación lógica se dice que es conmutativa . Las operaciones
x + y = y + x xy
= yx
El símbolo '+' indica una operación OR lógica. Del mismo modo, el símbolo '.' Indica una operación AND
lógica y es opcional para representar. La ley conmutativa obedece a las operaciones lógicas y lógicas Y.
Ley asociativa
Si primero se realiza una operación lógica de cualquiera de las dos variables booleanas y luego se realiza
la misma operación con la variable restante da el mismo resultado, entonces se dice que la operación
lógica es asociativa . Las operaciones lógicas OR y lógicas AND de tres variables booleanas x, y & z se
muestran a continuación.
x + (y + z) = (x + y) + z
x. (yz) = (xy) .z
6
Ley distributiva
Si cualquier operación lógica se puede distribuir a todos los términos presentes en la función booleana,
entonces se dice que esa operación lógica es Distributiva . La distribución de las operaciones lógicas OR y
x. (y + z) = xy + xz x +
(yz) = (x + y). (x + z)
Estas son las leyes básicas del álgebra booleana. Podemos verificar estas leyes fácilmente, sustituyendo
1. Teorema de dualidad
2. Teorema de DeMorgan
Teorema de dualidad
Este teorema establece que el doble de la función booleana se obtiene al intercambiar el operador lógico
AND con el operador lógico OR y los ceros con los unos. Para cada función booleana, habrá una función
dual correspondiente.
Hagamos las ecuaciones booleanas (relaciones) que discutimos en la sección de postulados booleanos y
las leyes básicas en dos grupos. La siguiente tabla muestra estos dos grupos.
7
En cada fila, hay dos ecuaciones booleanas y son duales entre sí. Podemos verificar todas estas ecuaciones
booleanas de Group1 y Group2 usando el teorema de dualidad.
Teorema de DeMorgan
Este teorema es útil para encontrar el complemento de la función booleana . Indica que el complemento de
OR lógico de al menos dos variables booleanas es igual al AND lógico de cada variable complementada.
El teorema de DeMorgan con 2 variables booleanas xey puede representarse como
(x + y) '= x'.y'
El doble de la función booleana anterior es
(xy) '= x' + y '
8
Por lo tanto, el complemento de AND lógico de dos variables booleanas es igual al OR lógico de cada
variable complementada. De manera similar, podemos aplicar el teorema de DeMorgan para más de 2
variables booleanas también.
Hasta ahora, discutimos los postulados, las leyes básicas y los teoremas del álgebra de Boole. Ahora,
Ejemplo 1
Método 1
Paso 1 : en primer y segundo término r es común y en tercer y cuarto término pq es común. Entonces,
tome los términos comunes usando la ley distributiva .
f = (p'q + pq ') r + pq (r' + r)
9
Paso 2 : los términos presentes en el primer paréntesis se pueden simplificar a la operación Ex-OR.
Los términos presentes en el segundo paréntesis se pueden simplificar a '1' usando el postulado
booleano
⇒ f = (p ⊕q) r + pq (1)
Paso 3 - El primer término no se puede simplificar más. Pero, el segundo término se puede
⇒ f = (p ⊕q) r + pq
Método 2
Paso 1 - Usa el postulado booleano , x + x = x. Eso significa que la operación OR lógica con
cualquier variable booleana 'n' veces será igual a la misma variable. Entonces, podemos escribir el
Paso 3 - Use el postulado booleano , x + x '= 1 para simplificar los términos presentes en cada
paréntesis.
Paso 4 - Use el postulado booleano , x.1 = x para simplificar los tres términos anteriores.
⇒ f = qr + pr + pq
10
⇒ f = pq + qr + pr
Entonces, tenemos dos funciones booleanas diferentes después de simplificar la función booleana
dada en cada método. Funcionalmente, esas dos funciones booleanas son iguales. Entonces, según
Ejemplo 2
11
4.2 Optimización de expresiones booleanas.
Utilizando expresiones booleanas, vamos a definir Funciones booleanas, que son exactamente
iguales a las funciones matemáticas a las que estamos habituados pero con la particularidad de que
las variables son booleanas y que los valores devueltos por la función también son booleanos, es
decir, una función booleana sólo puede tomar los valores ’0’ ó ’1’
Como hemos hecho antes, vamos a ver un ejemplo utilizando una función matemática de las que
f ( x ) = x2 + 1
Se trata de una función Real que tiene una variable Real (x). Para cada valor de x, obtenemos el
· f(0) = 1
· f(1) = 2
· f(2) = 5
· f(3) = 10
Como es una función Real, obtenemos como valores de la función Núme ros Reales. También
12
Como estamos acostumbrados a trabajar con este tipo de funciones, nos resultan sencillas. Ahora
vamos a definir funciones booleanas. Para ello hay que tener en mente que trabajaremos con
variables booleanas y que por tanto usaremos las operaciones + y * del Algebra de Boole, y que
como ya sabemos, nada tienen que ver con las operaciones suma y producto a las que estamos
habituados.
El valor devuelto por la función es el negado del que se le pasa por la variable. Como la variable A
es booleana, sólo puede tomar los valores ‟0‟ y ‟1‟. Los que la función F toma son:
Vamos a definir una función un poco más compleja, usando dos variables booleanas, A y B
¿Cuando vale F(0,0)? sólo hay que sustituir en la función los valores de A y B por ‟0‟,
obteniéndose:
13
4.3 Aplicación del algebra booleana (Compuertas lógicas)
El álgebra booleana como cálculo de dos valores es fundamental para los circuitos de computadora,
Computadoras A principios del siglo XX, varios ingenieros eléctricos reconocieron intuitivamente
que el álgebra de Boole era análogo al comportamiento de ciertos tipos de circuitos eléctricos.
Claude Shannon demostró formalmente que tal comportamiento era lógicamente equivalente al
conmutación .
Hoy en día, todas las computadoras modernas de propósito general realizan sus funciones utilizando
lógica booleana de dos valores; es decir, sus circuitos eléctricos son una manifestación física de la
lógica booleana de dos valores. Lo logran de varias maneras: como voltajes en cables en circuitos
14
Por supuesto, es posible codificar más de dos símbolos en cualquier medio dado. Por ejemplo, uno
cable, o agujeros de diferentes tamaños en una tarjeta perforada. En la práctica, las restricciones
estrictas de alta velocidad, pequeño tamaño y baja potencia se combinan para hacer del ruido un
factor importante. Esto hace que sea difícil distinguir entre símbolos cuando hay varios símbolos
posibles que podrían aparecer en un solo sitio. En lugar de intentar distinguir entre cuatro voltajes
en un cable, los diseñadores digitales se han establecido en dos voltajes por cable, alto y bajo.
Las computadoras usan circuitos booleanos de dos valores por las razones anteriores. Las
programación, los programadores trabajan con la estructura digital de bajo nivel del registros de
datos . Estos registros funcionan con voltajes, donde cero voltios representan 0 booleano, y un
voltaje de referencia (a menudo + 5V, + 3.3V, + 1.8V) representa booleano 1. Estos lenguajes
admiten operaciones numéricas y operaciones lógicas. En este contexto, "numérico" significa que la
computadora trata las secuencias de bits como números binarios(base dos números) y ejecuta
operaciones aritméticas como sumar, restar, multiplicar o dividir. "Lógico" se refiere a las
operaciones lógicas booleanas de disyunción, conjunción y negación entre dos secuencias de bits,
en las que cada bit en una secuencia se compara simplemente con su contraparte en la otra
secuencia. Por lo tanto, los programadores tienen la opción de trabajar y aplicar las reglas de
álgebra numérica o álgebra booleana según sea necesario. Una característica diferenciadora
15
Otras áreas donde dos valores son una buena opción son la ley y las matemáticas. En la
conversación relajada de todos los días, se aceptan respuestas complejas o con matices como
"quizás" o "solo los fines de semana". En situaciones más específicas, como un tribunal de justicia o
matemáticas basadas en teoremas, se considera ventajoso formular preguntas para admitir una
falsa. —Y no permitir ninguna otra respuesta. Por muy importante que sea la camisa de fuerza que
se ha convertido en una característica central de la lógica tanto matemática como judicial, haciendo
que la lógica de dos valores merezca organización y estudio por derecho propio.
permitir múltiples grados de membresía, como novatos, asociados y completos. Sin embargo, con
conjuntos, un elemento está dentro o fuera. Los candidatos para ser miembros de un conjunto
funcionan igual que los cables de una computadora digital: cada candidato es miembro o no
matemático, estas consideraciones se combinan para hacer que el álgebra de dos valores sea de
conjuntos.
reemplazando el dominio booleano {0, 1} con el intervalo de la unidad [0,1], en cuyo caso, en lugar
de solo tomar los valores 0 o 1, cualquier valor entre y incluyendo 0 y 1 pueden ser asumidos.
Morgan . La interpretación de estos valores como valores de verdad lógica produce una lógica de
múltiples valores, que forma la base de la lógica difusa y la lógica probabilística . En estas
16
interpretaciones, un valor se interpreta como el "grado" de verdad, en qué medida una proposición
Operaciones booleanas
La aplicación original para operaciones booleanas fue la lógica matemática , donde combina los
Los lenguajes naturales como el inglés tienen palabras para varias operaciones booleanas, en
sinónimo de y no . Cuando se usan para combinar afirmaciones situacionales como "el bloque está
sobre la mesa" y "los gatos beben leche", que ingenuamente son verdaderos o falsos, los
significados de estos conectivos lógicosA menudo tienen el significado de sus contrapartes lógicas.
Sin embargo, con descripciones de comportamientos como "Jim caminó por la puerta", uno
comienza a notar diferencias como la falta de conmutación, por ejemplo, la conjunción de "Jim
abrió la puerta" con "Jim entró por la puerta" en ese orden es no es equivalente a su conjunción en
la otra orden, desde y generalmente significa y luego en tales casos. Las preguntas pueden ser
similares: el orden "¿Es el cielo azul y por qué el cielo es azul?" Tiene más sentido que el orden
pescar o cortar cebotienden a ser asimétricas por la implicación de que una alternativa es menos
preferible. Los sustantivos unidos como el té y la leche generalmente describen la agregación como
con la unión establecida, mientras que el té o la leche es una opción. Sin embargo, el contexto puede
revertir estos sentidos, ya que entre sus opciones están el café y el té, lo que generalmente significa
lo mismo que sus opciones son el café o el té (alternativas). La doble negación, como en "No me
gusta la leche", rara vez significa literalmente "Me gusta la leche", sino que conlleva algún tipo de
cobertura, como para dar a entender que existe una tercera posibilidad. "No no P" se puede
interpretar libremente como "seguramente P", y aunque P necesariamente implica "no P "Lógica
17
intuicionista . En vista del uso altamente idiosincrásico de las conjunciones en lenguajes naturales,
Las operaciones booleanas se utilizan en lógica digital para combinar los bits transportados en
binarias idénticas para combinar dos vectores de bit cada uno de n bit, las operaciones de bit
individuales pueden entenderse colectivamente como una sola operación en valores de un álgebra
La teoría de conjuntos ingenua interpreta las operaciones booleanas como acciones en subconjuntos
paralelo a las combinaciones de coordenadas de los vectores de bits, con la unión de dos conjuntos
computadora basadas en gráficos de trama , que utilizan bit blit para manipular regiones enteras que
consisten en píxeles , y dependen de las operaciones booleanas para especificar cómo se debe
combinar la región de origen con el destino, normalmente Con la ayuda de una tercera región
llamada la máscara . Modernas tarjetas de vídeo ofrecen todo 2 2 3 = 256 operaciones ternarias para
este propósito, con la opción de operación como un parámetro de un byte (8 bits). Las constantes
SRC = 0xaa o 10101010, DST = 0xcc o 11001100, y MSK = 0xf0 o 11110000 permiten
operaciones booleanas como (SRC ^ DST) y MSK (que significa XOR el origen y el destino y
luego Y el resultado con la máscara) para ser escrito directamente como una constante que denota
un byte calculado en tiempo de compilación, 0x60 en el ejemplo (SRC ^ DST) y MSK, 0x66 si solo
18
SRC ^ DST, etc. En el tiempo de ejecución, la tarjeta de video interpreta el byte como la operación
raster indicada por la expresión original de una manera uniforme que requiere un hardware
expresión.
Los sistemas de modelado sólido para diseño asistido por computadora ofrecen una variedad de
métodos para construir objetos a partir de otros objetos, uno de ellos es la combinación de
operaciones booleanas. En este método, el espacio en el que existen los objetos se entiende como un
conjunto S de voxels (el análogo tridimensional de los píxeles en gráficos bidimensionales) y las
formas se definen como subconjuntos de S, permitiendo que los objetos se combinen como
conjuntos a través de unión, intersección, etc. Un uso obvio es en la construcción de una forma
compleja a partir de formas simples simplemente como la unión de esta última. Otro uso es en la
escultura entendida como remoción de material: cualquier operación de rectificado, fresado, fresado
o taladrado que se puede realizar con maquinaria física en materiales físicos puede simularse en la
diferencia de conjuntos, elimina los elementos de y de los de x. Por lo tanto, dadas las dos formas,
una para ser mecanizada y la otra para el material a remover, el resultado de mecanizar la primera
19
4.3.1 Mini y maxi términos.
Minitérminos
Para una función booleana de n variables x1,...xn, un producto booleano en el que cada una de las n
variables aparece una sola vez (negada o sin negar) es llamado minterms. Es decir, un minterms es
una expresión lógica de n variables consistente únicamente en el operador conjunción lógica (AND)
Por ejemplo, abc, ab'c y abc' son ejemplos de minterms para una función booleana con las tres
variables a, b y c.
En general, uno asigna a cada minterm (escribiendo las variables que lo componen en el mismo
orden), un índice basado en el valor binario del minterm. un término negado, como a' es
ejemplo, se asociaría el número 6 con a b c'(1102), y nombraríamos la expresión con el nombre m6.
Función equivalente
Se puede observar que cada minterm solo devuelve 'verdadero' con una sola entrada de las posibles.
Por ejemplo, el minterm 5, a b' c, es verdadero solo cuando a y c son ciertos y bes falso - la entrada
a = 1, b = 0, c = 1 da resultado 1.
Si tenemos una tabla de verdad de una función lógica, es posible escribir la función como "suma de
20
a b f(a, b)
001
010
101
110
Observamos que las filas con resultado 1 son la primera y la tercera, entonces podremos escribir f
f(a,b) = m0 + m2 = (a'b')+(ab')
Maxitérminos
Un maxterm es una expresión lógica de n variables que consiste únicamente en la disyunción lógica
y el operador complemento o negación. Los maxterms són una expresión dual de los minterms. En
a+b'+c
a'+b+c
m1' = M1
21
(a'b)' = a+b'
Para indexar maxterms lo haremos justo de la forma contraria a la que seguimos con los minterms.
Se asigna a cada maxterm un índice basado en el complemento del número binario que representa
(otra vez asegurándonos que las variables se escriben en el mismo orden, usualmente alfabético).
Por ejemplo, podemos asignar M6 (Maxterm 6) al maxterm a'+b'+c. De forma similar M0 de tres
Función equivalente
Se puede ver fácilmente que un maxterm sólo da como resultado un cero para una única entrada de
la función lógica. Por ejemplo, el maxterm 5, a'+b+c', es falso solo cuando a y cson ciertos y b es
Si tenemos una tabla de verdad de una función lógica, es posible escribir la función como "producto
a b f(a, b)
001
010
101
110
Observamos que las filas que tiene como salida un 0 son la segunda y la cuarta, entonces podemos
f(a,b) = M1 M3 = (a+b')(a'+b')
22
Mapa de Karnaugh
equivalente a resolver las simplificaciones por teoremas. Sin embargo, mucha gente considera que
Los mapas de Karnaugh pueden aplicarse a dos, tres, cuatro y cinco variables. Para más variables, la
simplificación resulta tan complicada que conviene en ese caso utilizar teoremas mejor. Para efectos
El Álgebra de Boole, resuelve problemas que dependiendo del número de términos que tenía la
función canónica, siendo el número de compuertas lógicas utilizadas igual al número de términos
obtenidos MÁS UNO; por lo tanto, los circuitos obtenidos son de dos niveles de conmutación con
un tiempo mínimo de retardo, pero que de ninguna manera es el más sencillo ni el más económico.
Los mapas de Karnaugh es uno de los métodos más prácticos. Se puede decir que es el más
poderoso, cuando el número de variables de entrada es menor o igual a seis; más allá, ya no es tan
práctico. En general, el mapa de Karnaugh se considera como la forma gráfica de una tabla de
cómo se obtiene el mapa. Esto nace de la representación geométrica de los números binarios. Un
número binario de n bits, puede representarse por lo que se denomina un punto en un espacio N.
Para entender lo que se quiere decir con esto, considérese el conjunto de los números binarios de un
bit, es decir 0 o 1. Este conjunto puede representarse por dos puntos en un espacio 1; esto es, por
23
Introducción de método de Quine-McCluskey
- Una expresión más simple es más fácil de entender y tiene menos posibilidades de error a la
hora de su interpretación.
- Una expresión simplificada suelen ser más eficiente y efectiva cuando se implementan en la
número de variables, no es el caso del método de Karnaugh, que se hace impracticable con más de
cinco variables. En nuestro caso, como el máximo número de variables será cuatro podremos
Una expresión booleana se compone de variables y términos. Para este método las variables sólo
podrán tener un valor numérico de cero (el correspondiente al valor de verdad false) o uno (el
Como notación se designará x si la variable contiene el valor uno, x’ en caso deque contenga el
valor cero.
Por otra parte, las variables se relacionarán entre sí únicamente mediante operaciones lógicas and
para formar términos y mediante or para relacionarse con otros términos constituyendo una suma de
productos.
- Cada variable se usa una vez en cada término. A dichos términos se les llama términoscanónicos.
24
x’y z se representa con 011, donde x = 0, y = 1, z = 1 x y’z se representa con 101, donde x = 1, y =
0, z = 1 Circuito Combinacional
Un circuito combinacional, como su nombre lo sugiere es un circuito cuya salida depende solamente
Analizando el circuito, con compuertas digitales, que se muestra a continuación, se puede ver que la
salida de cada una de las compuertas que se muestra depende únicamente de sus entradas.
manipulan señales eléctricas, tales como las compuertas y los circuitos lógicos.
Un bloque lógico es una representación simbólica gráfica de una o más variables de entrada a un
operador lógico para obtener una señal de salida. En electrónica, estos bloques lógicos son las
compuertas.
25
Las compuertas lógicas pueden recibir una o más señales de entrada.
En la compuerta anterior, A y B son señales que entran a la compuerta y pueden tener un valor de 1
ó 0 dependiendo de si existe o no la señal. Estos dos generan una sola salida, que también es 1 ó 0
Las compuertas básicas AND, OR y NOT son equivalentes alos conectores 'Y', 'O' y 'NO' de la
Generalmente, los circuitos digitales se construyen con compuertas NAND y NOR, pues son más
fáciles de encontrar en el mercado, son más comunes desde el punto de vista del hardware y están
Compuerta NAND
26
CONCLUCIONES
27
BIBLIOGRAFIAS
28