UTN-

INGENIERÍA EN S ISTEMAS DE INFORMACIÓN

LÓGICA y E.DISCRETAS
 GEORGE BOOLE

 Lincoln, Reino Unido, 1815 - Ballintemple,

actual Irlanda, 1864) Matemático británico.
 Álgebra de Boole

Sea B un conjunto no vacío en el cual se definen dos

operaciones binarias que llamaremos suma lógica (+) y
producto lógico (•), una operación unitaria que llamaremos
complemento ( ´ o ‾ ) y dos elementos distintos 0 y 1.
El conjunto (B, +, •, 1 ,0 ,‫ )׳‬es un Álgebra de Boole si se
verifican los siguientes axiomas:
Ax.1: Leyes Conmutativas: a + b = b + a ; a . b = b . a
Ax.2: Leyes Distributivas: a.(b + c) = a . b + a . c ;
a+(b . c) = (a + b) . (a + c)
a  a  1 , a.a  0
Ax.3: Leyes de Identidad: a+0 = a ; a.1=a
Ax.4: Leyes del Complemento:
 Ejemplos de Algebra de Boole

• Ejemplo 1: El conjunto B={0,1} con las

operaciones booleanas dadas por las tablas, el
complemento de 1 es 0 y el complemento de
cero es 1.

+ 0 1 . 0 1
0 0 1 0 0 0
1 1 1 1 0 1
• Ejemplo 2: El conjunto Bn cuyos elementos son
secuencias de n bits con las operaciones booleanas del
ejemplo 1.Se suman y se multiplican elemento a elemento.
El complemento de 1 es 0 y el complemento de 0 es 1.

a =110101 0
b =101101 1
a+ b = 1 1 1 1 0 1 1
a.b =100101 0
a´ = 0 0 1 0 1 0 1
 Dualidad
El dual de un enunciado de un Álgebra de Boole se obtiene
al intercambiar 0 por 1, + por • y viceversa.
Ejemplos:
El dual de (1+a) . (b+0) = b es
(0.a) + (b.1) = b
El dual de (a + b)’ = a’ . b’ es
(a . b)’ = a’ + b’

Debido a la simetría de los axiomas de un Álgebra de Boole,

se cumple que el dual de los axiomas de B es el mismo
conjunto de axiomas.
 Principio de Dualidad

El dual de un Teorema de un
Álgebra de Boole es también
un Teorema
 Propiedades o Teoremas
• 1) Leyes de idempotencia: a + a=a ; a . a=a
• 2) Leyes de acotamiento: a+1=1 ; a.0=0
• 3) Leyes de absorción: [a+(a . b)] = a ; a.(a + b) = a
• 4) Leyes asociativas: (a + b)+c = a+(b + c) ;
• (a . b).c = a.(b . c)
• 5) Unicidad del complemento:
• Si a + x = 1 y a . x = 0 x=ā
• 0 de1 involución:
6) Ley y 1  0 (a’)’ = a
• 7) a  b  a .b , a.b  a  b
• 8) Leyes de De Morgan:
 Actividad
Demostrar las propiedades 1 y 2
• 1) Leyes de idempotencia: a + a=a ;
a . a=a
• 2) Leyes de acotamiento: a+1=1 ;
a.0=0
Demostramos la idempotencia

• 1) a + a = a
a = a+0 por Identidad
a = a +a . a’ por Comp.
a = (a + a) . (a + a’) Propiedad Distributiva
a = (a + a) . 1 por Comp.
a = a + a por Identidad
 Claude Elwood Shannon
(1.916 – 2.001)

Fue un ingeniero electrónico y matemático

estadounidense, recordado como “el padre de la
teoría de la información”
En su tesis de maestría en el MIT, demostró cómo el
álgebra booleana se podía utilizar en el análisis y la
síntesis de la conmutación y de los circuitos digitales.
 Circuitos Lógicos y el Álgebra
de Boole
El álgebra de Boole se utiliza para modelar los circuitos
de dispositivos electrónicos. Cada entrada o salida de
estos dispositivos se puede ver cómo un 0 o un 1.

 Circuitos combinacionales: son los circuitos donde las

señales de salida dependen únicamente de las señales de
entrada

 Los elementos básicos de los circuitos son las

Compuertas lógicas.

 Compuertas Lógicas: son circuitos elementales a partir de

los cuales se construyen los circuitos lógicos.
 FUNCIONES BOOLEANAS
Variables lógicas o binarias: son aquellas que
sólo pueden tomar los valores 0 (cero –
proposición falsa) o 1 (uno – proposición
verdadera). Las indicamos A, B, C, etc.

Funciones lógicas o booleanas:

Una función de Boole es una expresión
algebraica donde intervienen variables
binarias, los operadores binarios OR y AND, el
operador unitario NOT, paréntesis y el signo
igual.
 Compuertas lógicas
NOMBRE SÍMBOLO FUNCIÓN TABLA DE
VERDAD

AND
A B F
 1 1 1

Producto F=A.B 1 0 0
0 1 0
Lógico 0 0 0

A B F
Or F=A+B 1 1 1

 1 0 1
0 1 1
Suma 0 0 0
NOMBRE
Compuertas
SÍMBOLO
lógicas
FUNCIÓN TABLA DE
VERDAD

A F
Inversor A 1 0
NOT F=
0 1

-
Comple-
A B F
mento A.B
1 1 0

NAND F= 1 0 1
0 1 1
Comple-
NOMBRE SÍMBOLO FUNCIÓN TABLA DE
VERDAD
A B F
NOR A B 1 1 0
Comple- F= 1 0 0

mento de 0 1 0
0 0 1
OR
 EJEMPLO
 Ejemplo:

F  A.B.C  A.B.C  A.C
◦ (Expresión booleana)
ABC

FF
(Circuito)
 ACTIVIDAD
a) Aplicando axiomas y
propiedades del Álgebra de
Boole, simplificar F.
b) Verificar mediante tabla de
verdad.
c) Representar el circuito asociado
a la expresión simplificada.
F=ABC+AB + C
F´= AB + C
A B C ABC AB C F AB F´

1 1 1 1 0 0 0 0 1 1 1
1 1 0 0 1 1 0 0 1 1 1
1 0 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0
0 1 1 0 0 0 1 1 1 0 1
0 1 0 0 1 0 1 0 0 0 0
0 0 1 0 0 0 1 1 1 0 1
0 0 0 0 1 0 1 0 0 0 0
 FORMAS CANÓNICAS
O
NORMALIZADAS

FORMA NORMAL DISYUNTIVA (FND)

Función expresada como suma de minitérminos

FORMA NORMAL CONJUNTIVA (FNC)

Función expresada como producto de maxitérminos

 FORMAS CANÓNICAS
O
NORMALIZADAS

Términos mínimos o minitérminos de un producto

normalizado: se llama así a cada una de las
combinaciones posibles de variables binarias unidas por
el operador AND, pudiendo estar la variable en su
forma normal (A) o complementada ( A).

Actividad: Si consideramos dos variables A y B.

¿Cuántas combinaciones posibles existen?.¿ Y si son
“n” variables?
 FORMAS CANÓNICAS
O
NORMALIZADAS

Términos máximos o maxitérminos de una suma

normalizada: se llama así a cada una de las
combinaciones posibles de variables binarias unidas por
el operador OR, pudiendo estar la variable en su forma
normal (A) o complementada ( A).
TABLA DE MINITÉRMINOS CON TRES
VARIABLES
Variable complementada 0
Variable no complementada 1

A B C MINI
TÉRMINOS
A.B.C
0 0 0
A.B.C
0 0 1
A.B.C
0 1 0
A.B.C
0 1 1 A.B.C

1 0 0 A.B.C
1 0 1
A.B.C
A.B.C
1 1 0
1 1 1
TABLA DE MAXITÉRMINOS CON TRES
VARIABLES
Variable complementada 1
Variable no complementada 0

A B C MAXI
TÉRMINOS
A B C
0 0 0
A B C
0 0 1
A B C
0 1 0
A B C
0 1 1 A B C
1 0 0 A B C
1 0 1
A B C
A B C
1 1 0
1 1 1
 Una función de Boole puede ser expresada
algebraicamente a partir de una tabla de
verdad dada, conformando un término
mínimo por cada combinación de las
variables que producen un 1 en la función
para luego obtener la OR de todos los
términos.
 FORMAS CANÓNICAS

 FORMA NORMAL DISYUNTIVA FND

 FORMA NORMAL CONJUNTIVA FNC

 Ejemplo:
 Sea la tabla siguiente donde aparecen dos

funciones de tres variables F1 y F2


 FORMA NORMAL DISYUNTIVA (FND)

A B C MINI F1 F2
TÉRMI
ANOS
.B.C
0 0 0 A.B.C 0 0
0 0 1 A.B.C 1 0
0 1 0 A.B.C 0 0
A.B.C
0 1 1 0 1
A.B.C
1 0 0 1 0
A.B.C
1 0 1 A.B.C 0 1
1 1 0 0 1
1 1 1 1 1
 FND

 F1 : A.B.C  A.B.C  A.B.C

 F2 : A.B.C  A.B.C  A.B.C  A.B.C

 FORMA NORMAL CONJUNTIVA (FNC)
A B C MAXIT F1 F2
0 0 0 0 0
0 0 1 1 0
0 1 0 +C 0 0
0 1 1 + 0 1
1 0 0 +B+C 1 0
1 0 1 +B+ 0 1
1 1 0 ++C 0 1
1 1 1 + 1 1
 FNC

    
F1 :  A  B  C . A  B  C . A  B  C . A  B  C . A  B  C 
 F2 : A  B  C .A  B  C . A  B  C . A  B  C 
 FNC

    
F1 :  A  B  C . A  B  C . A  B  C . A  B  C . A  B  C 
 F2 : A  B  C .A  B  C . A  B  C . A  B  C 