Programacin
LGEBRA DE BOOLE
Introduccin a la Programacin
Algebra de Boole
Programacin
Cuatro sillas se ubican en una fila, segn muestra
la siguiente figura:
Cada silla puede estar ocupada (1) o vaca (0).
Escriba una funcin lgica F(A,B,C,D) que ha de
ser igual a 1 si y slo si hay dos sillas adyacentes
que se encuentren vacas.
Introduccin
Programacin
En 1815 George Boole propuso una
herramienta matemtica que llamamos
lgebra de Boole.
Luego en 1938 Claude Shannon propuso
que con esta lgebra es posible modelar
los llamados Sistemas Digitales.
pero qu es un lgebra?
y cmo es el lgebra de Boole?
lgebras
Programacin
Son estructuras matemticas de la siguiente
forma:
A = ({........}, + , ,...)
conjunto operaciones
constantes (elementos del
conjunto)
variables (representan
elementos del conjunto)
Ejemplos de lgebras
Programacin
lgebra de los enteros con la suma y el
producto:
Ejemplo de expresin algebraica:
variables
constante
operaciones
Ejemplos de lgebras
Programacin
lgebra de los valores lgicos:
Ejemplo de expresin algebraica:
variables
constante
operaciones
Ejemplos de lgebras
Programacin
lgebra de Boole (valores booleanos):
Ejemplo de expresin algebraica:
variables
constante
operaciones
lgebra de Boole en el computador
Programacin
mundo real
valores
lgicos
valores
booleanos
(bits)
computador
Operaciones lgicas y operaciones booleanas
Programacin
F V F V
F F V F F F F V
V V V V F V V F
+ 0 1 0 1
0 0 1 0 0 0 0 1
1 1 1 1 0 1 1 0
Variables lgicas variables booleanas
Programacin
Ejemplo:
falso - 0
p = hoy est lloviendo verdadero - 1
falso - 0
q = me encontrar con ella en el bar
verdadero - 1
falso - 0
r = hay clases en Enero
verdadero - 1
etc.
Identificacin de variables lgicas o booleanas
Programacin
En un torneo de magos, se enfrentan Harry Potter y el mago Merln. El
pblico se encuentra dividido en sus pronsticos sobre quin ser el
ganador en tal especial evento. Las personas mayores de 40 aos y
que no han ledo a J.K. Rowling, se inclinan por pensar que el mago
Merln ser el justo ganador Aquellos que han visto todas las
pelculas de Harry Potter y leyeron a J.K. Rowling, no dudan que ste
ser el ganador. Aquellas personas que tienen 40 aos o menos, que
no conocen a Harry Potter ni por la pelcula ni por los libros de J.K.
Rowling, se inclinarn necesariamente por Merln. Finalmente, las
personas con edades 40 aos y menores, que no han ledo a J.K.
Rowling, pero se han visto todas las pelculas de Harry, creen que ste
ganar el torneo.
Variables relevantes:
a= ser mayor de 40 aos
b= haber ledo a J.K.Rowling
c= haber visto las pelculas de Harry Potter
d= creer que Harry Potter ganar la batalla (variable de salida)
Identificacin de variables lgicas o booleanas
Programacin
Un estudiante de la Universidad del Tamarugo, en plena pampa de la
I regin, consulta por Internet la Gua de Ingreso y encuentra que
puede matricularse en un determinado curso si cumple las siguientes
condiciones:
- Estudia Ingeniera en Minas y es de bajos recursos econmicos
- O tiene aprobado como mnimo el 60 % de sus asignaturas y es muy
buen estudiante
-O tiene aprobado menos del 60 % de sus asignaturas y es de bajos
recursos econmicos
-O tiene aprobado como mnimo el 60 % de sus asignaturas y estudia
Ingeniera en Minas.
Identifique las variables relevantes de entrada y la variable de salida
Analoga con circuito elctrico
Programacin
La flecha indica el sentido
de circulacin de corriente
Interruptor abierto, o en
posicin de desconexin
Interruptor cerrado, o en
posicin de conexin
Circuito elctrico
Programacin
Ejemplo:
El interruptor est
abierto (desconexin).
No hay paso de
corriente
El interruptor est
cerrado (conexin). Hay
paso de corriente
Circuitos en Serie
(y lgico, booleana)
Programacin
Circuitos en Serie
Todos los interruptores de un circuito en serie deben
estar cerrados para que pueda circular la corriente:
Los dos interruptores A y B deben estar cerrados para
que pueda circular la corriente por este circuito.
A B CORRIENTE Cuatro combinaciones
posibles con dos
Abierto Abierto No pasa
interruptores
Abierto Cerrado No pasa
Cerrado Abierto No pasa
Cerrado Cerrado Pasa
Circuitos en Serie
(y lgico, booleana)
Programacin
Introduzcamos ahora la siguiente notacin:
0 significa interruptor abierto o no circula corriente.
1 significa interruptor cerrado o circula la corriente.
representa la operacin lgica Y. Por ejemplo, A B
se lee A Y B.
A B CORRIENTE AB
0 0 0
0 1 0
1 0 0
1 1 1
Circuitos en Paralelo
(o lgico, + booleana)
Programacin
Circuitos en Paralelo
En los circuitos en paralelo basta que uno de los
interruptores est cerrado para que pueda circular la
corriente.
En este circuito habr flujo o paso de corriente si A, o B, o
ambos, estn cerrados.
A B CORRIENTE
Abierto Abierto No pasa
Abierto Cerrado Pasa
Cerrado Abierto Pasa
Cerrado Cerrado Pasa
Circuitos en Paralelo
(o lgico, + booleana)
Programacin
Introduzcamos ahora la siguiente notacin:
0 significa interruptor abierto o no circula corriente.
1 significa interruptor cerrado o circula la corriente.
+ representa la operacin lgica O. Por ejemplo, A+B se
lee A O B.
A B CORRIENTE A+B
0 0 0
0 1 1
1 0 1
1 1 1
Circuitos en Serie y
Circuitos en Paralelo
Programacin
Ejercicios: Obtenga las funciones lgicas que
(1) representan cada uno de los siguientes circuitos:
(2)
(3)
Funciones Booleanas
Programacin
Entradas Salidas Expresiones
booleanas
A A+B
AB
_
B A
Cmo se forma una funcin?
- Algebra de valores lgicos y lgebra de Boole
Cmo se implementa la funcin?
- Depende de la tecnologa
Cmo se simplifica la funcin?
- Algebra de Boole
Tabla de Verdad para la suma booleana
Programacin
Funcin Suma (+):
corresponde al O (en espaol) lgico ENTRADAS SALIDA
OR (en ingls)
A B A+B
Tabla de verdad: (AYUDE A
COMPLETARLA..) 0 0 0
0 1 1
1 0 1
1 + 1 = 1 !!!
1 1 1
A+B
A OR B Tabla de Verdad
Tabla de Verdad para el producto booleano
Programacin
Funcin Producto ():
Corresponde al Y (en espaol) lgico ENTRADAS SALIDA
AND (en ingls)
Tabla de verdad: (AYUDE A A B A B
COMPLETARLA..)
0 0 0
0 1 0
1 0 0
PQ 1 1 1
P AND Q
Tabla de Verdad para el complemento booleano
Programacin
Funcin Complemento ( , ~ ):
Corresponde al NO (en espaol) lgico
NOT (en ingls) ENTRADA SALIDA
Tabla de verdad: (AYUDE A
COMPLETARLA..) A A
0 1
1 0
NOT A A
Conversin Tabla de Verdad a Expresin
Lgica
Programacin
Observe la tabla de verdad
Considere cada combinacin de entradas cuya
salida sea 1.
Las combinaciones elegidas se formarn como
suma de productos de esas entradas.
Si una entrada vale 0, la variable se muestra
como complementada. Si vale 1, la variable se
muestra sin complementar.
Ejemplo de Conversin
Programacin
Sea la siguiente tabla de verdad:
Encontrar la expresin booleana de la
salida (C)
Solucin:
De la explicacin anterior, se consideran
slo los estados de A y B para cada lnea
en la que C es 1, se organizan como
productos (funcin AND) y se unen
mediante la funcin OR (suma).
C=AB+AB
mintrmino
Otro ejemplo:
Programacin
Sea la siguiente Tabla de verdad:
Encontrar la expresin booleana de
la salida (f)
Ejercicio
Programacin
Expresar como suma de mintrminos las funciones
dadas en la siguiente tabla de verdad:
Ejercicio
Programacin
Un circuito de control industrial tiene cuatro
entradas: A, B, C, D que activan una nica
salida X, de acuerdo a las siguientes
condiciones de operacin:
i) Si C y A se encuentran activas (1) al mismo tiempo, la salida
(X) estar activa.
ii) Si D est inactiva y A est activa, y al menos una de las
restantes entradas se encuentra activa, la salida (X) estar
activa.
iii) Si D y A se encuentran inactivas al mismo tiempo y al
menos una de las restantes entradas se encuentra activa, la
salida estar activa.
iv) Cualquier otra combinacin distinta a las anteriores
ocasionar que la salida se encuentre inactiva (0)
Obtenga la tabla de verdad y la funcin
booleana para la salida X.
Teoremas Booleanos
Programacin
El lgebra de Boole define varios teoremas para
simplificar expresiones booleanas
Ley conmutativa:
AB=BA
A + B = B+A
Ley asociativa:
A(BC) = (AB)C
A+(B+C)=(A+B)+C
Ley distributiva:
A(B+C) = AB + AC
A + BC = (A+B) (A + C)
Teoremas Booleanos
Programacin
Ley de la absorcin:
A + AB= A
A(A+B)=A
Leyes de DeMorgan:
A+B=AB
AB = A + B
Teoremas Booleanos
Programacin
Operacin suma lgica (OR):
El resultado es 1 si alguno de los sumandos es 1
1+A=1
0+A=A
A+A=A
A+A=1
Teoremas Booleanos
Programacin
Operacin producto lgico (AND):
El resultado es 0 si alguno de los elementos es 0
1. A = A
0.A=0
A.A=A
A.A=0
Teoremas Booleanos
Programacin
Operacin Negacin (NOT):
0=1
1=0
A=A
Simplificacin de Funciones usando Teoremas y
Propiedades
Programacin
Se desea reducir la siguiente expresin,
haciendo uso de los teoremas booleanos.
D = BC + ABC + ABC + ABC
Solucin: D = BC + ABC + ABC + ABC
D = BC + ABC + BC(A + A)
D = BC + ABC + BC
D = ABC + C(B + B)
D = AB + C
EJERCICIOS
Programacin
Cuatro sillas se ubican en una fila, segn
muestra la siguiente figura:
Cada silla puede estar ocupada (1) o vaca (0).
Escriba una funcin lgica F(A,B,C,D) que ha de ser igual a 1 si
y slo si hay dos o ms sillas adyacentes que se encuentren
vacas. Para encontrar la funcin lgica, usted debe obtener:
a) Una Tabla de Verdad.
b) La funcin booleana que representa la tabla obtenida.
d) La expresin mnima en suma de productos mediante el uso de
propiedades booleanas
EJERCICIOS
Programacin
Un circuito de control industrial tiene cuatro entradas: A,
B, C, D que activan una nica salida X, de acuerdo a las
siguientes condiciones de operacin:
i) C y A pueden encontrarse activas (1) al mismo tiempo.
ii) Si D est inactiva y A est activa, y al menos una de las
restantes entradas se encuentra activa, la salida (X) estar
activa.
iii) Si D y A se encuentran inactivas al mismo tiempo y al menos
una de las restantes entradas se encuentra activa, la salida
estar activa.
iv) Cualquier otra combinacin distinta a las anteriores
ocasionar que la salida se encuentre inactiva (0)
Obtenga la tabla de verdad para la salida X
Obtenga la funcin booleana que representa la salida x
Obtener la expresin mnima en forma de suma de
productos, usando propiedades del lgebra de Boole.
EJERCICIOS
Programacin
Un estudiante ser seleccionado para participar en un programa
experimental si pertenece, al menos, a uno de los grupos siguientes:
Varn, no de 2 ciclo, chileno
De 2 ciclo, chileno, no sabe programar
Varn, de 2 ciclo, chileno
Mujer, de 2 ciclo, sabe programar
No de 2 ciclo, chileno, no sabe programar
Mujer, no de 2 ciclo, chilena
De lo anterior desarrolle lo siguiente:
Represente el problema anterior mediante una tabla de verdad.
Deduzca la funcin en base a sumas de mintrminos.
Se pide encontrar mediante propiedades del Algebra de Boole, una funcin mnima
que permita seleccionar al candidato.
EJERCICIOS
Programacin
Se desea disear un sistema de control de calidad de un producto. El
producto se somete a cuatro pruebas: A, B, C y D. El producto se
declarar Rechazado, Apto, Bueno o Excelente en funcin de los
siguientes criterios:
Rechazado: Si pasa una o ninguna prueba
Apto: Si pasa la prueba A y alguna de las otras tres pruebas
Bueno: Si pasa la prueba A y dos de las otras tres pruebas
Excelente: Si pasa las cuatro pruebas
Un producto slo puede pertenecer a una nica categora.
Escribir la tabla de verdad del sistema.
Expresar cada variable de salida en forma de suma de productos.
Simplificar la funcin correspondiente a la variable de salida
Rechazado usando las propiedades del Algebra de Boole.
Ejercicios
Programacin
Simplifique las siguientes funciones a la mnima
expresin usando slo las propiedades del
Algebra de Boole.
(
f = A BC + A + B + C + A BC D )
( )(
f = ( AB + C + D ) C + D C + D + E )
( )(
f = X ZY + X ZY + Z X Y (Z + X ) + Y Z + Y X Z )
f = (((A + BC )(C + BC ))+ ((AB + C )(AB + BC )))
