FACULTAD DE INGENIERÍA
CARRERA DE INGENIERÍA DE SISTEMAS
ALGEBRA DE BOOLE
ESTRUCTURA DISCRETAS DE COMPUTACIÓN
AGENDA
ÁLGEBRA BOOLEANA
❑ Operaciones booleanas básicas. Función y expresión booleana. Leyes
booleanas. Álgebra Booleana y Compuertas Lógicas.
❑ La tabla de entrada/salida de un circuito.
❑ La expresión booleana correspondiente a un circuito.
❑ El circuito correspondiente a una expresión booleana.
❑ Encontrar un circuito que corresponda a una determinada tabla de
entrada / salida.
❑ Simplificación Circuitos Combinacionales. Compuertas universales NAND
y NOR.
Algebra de Boole
Denominada también algebra de la lógica.
El sistema matemático denominado algebra booleana, es un método simbólico de
estudiar relaciones lógicas.
El Álgebra de Boole es toda clase o conjunto de elementos que pueden tomar dos
valores perfectamente diferenciados, que designaremos por “0” y “1” y que están
relacionas por dos operaciones binarias denominadas suma (+) y producto (.).
Algebra de Boole
Operaciones Lógicas Básicas:
Sea un conjunto formado por solo dos elementos que designaremos por “0” y “1”.
Llamaremos variables lógicas a las que toman solo los valores del conjunto, es decir “0” o
“1”.
En dicho conjunto se definen tres operaciones básicas:
DISYUNCIÓN (Suma Lógica)
Denominada también operación “O” (OR) u “o inclusivo”. Esta operación responde a la
siguiente tabla:
p q p+q
1 1 1
1 0 1
0 1 1
0 0 0
Algebra de Boole
CONJUNCIÓN (Producto Lógico)
Denominada también operación “Y” (AND). Esta operación responde a la
siguiente tabla:
p q p.q
1 1 1
1 0 0
0 1 0
0 0 0
Algebra de Boole
NEGACIÓN LÓGICA
Denominada también operación NOT. Esta operación corresponde a la
siguiente tabla:
p ഥ
𝒑
1 0
0 1
Algebra de Boole
TEOREMAS TEOREMAS
REGLA DEL CERO Y LA UNIDAD ASOCIATIVIDAD
a) X + 0 = X c) X . 1 = X a) Asociatividad del + b) Asociatividad del .
b) X + 1 = 1 d) X . 0 = 0 X + (Y + Z) = (Y + X) + Z X . (Y . Z) = (Y . X) . Z
IDEMPOTENCIA O POTENCIAS IGUALES DISTRIBUTIVA
a) X + X = X b) X . X = X a) Distributiva del + b) Distributiva del .
CONMUTATIVIDAD X + (Y . Z) = (X + Y) . (X + Z) X . (Y + Z) = (X . Y) + (X . Z)
a) Conmutatividad del + Conmutatividad del .
X+Y=Y+X X.Y=Y.X
Representación de Funciones Booleanas
Existe infinitas maneras de representar una función booleana:
Por ejemplo, la función G = X + Y . Z podría representarse como: G=X+X+Y.Z
Otras veces se suele utilizar la forma negada o el complemento de la función. Para
ello, se niegan los literales y se intercambia el AND por OR y viceversa.
Por ejemplo, el complemento de: ത 𝐶
𝐴 + 𝐵. es 𝐴ҧ . (𝐵 + 𝐶)ҧ
El complemento de una función no es la misma función, es la forma negada de la
función.
Algunas Nociones Básicas
❑ Literal: se refiere a una variable o a su complemento (ejm: 𝐴, 𝑋, 𝑋).
ത
❑ Término Producto: es un grupo de literales que se encuentran
ത 𝑌. 𝑍).
relacionados entre si por un AND (ejm: 𝐴. 𝐵, 𝐶. 𝐴, 𝑋.
❑ Término Suma: es un grupo de literales que se encuentran relacionados
entre si por un OR (ejm: 𝐴 + 𝐵, 𝐶 + 𝐴, 𝑋ത + 𝑌 + 𝑍).
❑ Término Normal: término producto o término suma en el que un literal
no aparece más de una vez.
Algunas Nociones Básicas
❑ Término Canónico: término en el que se encuentra exactamente uno de
cada uno de los literales de la función. Si el término canónico es un
producto se denominará mintérmino. Si es una suma se denominará
maxtérmino.
❑ Forma Normal de una Función: es la que está constituida por términos
normales. Puede estar en su forma suma de términos productos o
productos de términos sumas.
❑ Forma Canónica de una Función: es aquella constituida exclusivamente
por términos canónicos que aparecen una sola vez.
Algunas Nociones Básicas
Ejemplo 1
Expresar la siguiente función como una suma de mintérminos.
Hay dos formas de resolver este problema.
Ejemplo 1
❑ Forma 1: Se puede obtener la tabla de verdad de la expresión y entonces tomar los
minterminos.
Ejemplo 1
❑ Forma 2: Aplicando los teoremas de expansión canónica para las variables faltantes.
Ejemplo 2
Expresar la siguiente función como productos de maxtérminos.
Hay dos formas de resolver este problema.
Ejemplo 2
❑ Forma 1: Se puede obtener la tabla de verdad de la expresión y entonces tomar los
maxtérminos.
Ejemplo 2
❑ Forma 2: Aplicando los teoremas de expansión canónica
Compuertas Lógicas
Susanna S. EPP, Discrete Mathematics with Applications Fourth Edition pag. 67 y 75
Ejemplo 3
Indique la salida de los circuitos mostrados a continuación para las señales de entrada dadas.
* Figura 1 * Figura 2
Señales de entrada: P = 0 y Q = 1 Señales de entrada: P = 1 Q = 0 y R = 1
* Figuras 1 y 2: pag 68 Libro: Discrete Mathematics with Applications
Ejemplo 3
Solución:
a) b)
Para construir toda la tabla de entrada / salida de un circuito, trace a través del circuito para
encontrar las señales de salida correspondientes para cada posible combinación de señales
de entrada.
Ejemplo 4
Construya la tabla de entrada / salida para el siguiente circuito.
Solución:
Enumerar las cuatro combinaciones posibles de señales de entrada, y encontrar la salida
para cada uno por trazado a través del circuito.
Ejemplo 5
ENCONTRAR UNA EXPRESIÓN BOOLEANA PARA UN CIRCUITO.
Encuentre las expresiones booleanas que corresponden a los circuitos que se muestran a
continuación. Un punto indica una soldadura de dos alambres; se supone que los cables
que cruzan sin un punto no se tocan.
Ejemplo 5
Solución:
Trace a través del circuito de izquierda a derecha, indicando la salida de cada puerta
simbólicamente, como se muestra a continuación.
P+Q
P.Q
Ejemplo 6
CIRCUITOS DE CONSTRUCCIÓN PARA EXPRESIONES BOOLEANAS
Construir circuitos para las siguientes expresiones booleanas
Solución:
NOT
AND
OR
NOT
Susanna S. EPP, Discrete Mathematics with Applications Fourth Edition pag. 70 -71
Ejemplo 7
Encontrar un circuito que corresponde a una determinada tabla de entrada / salida
Diseñe un circuito para la siguiente tabla de entrada / salida
