Tema 04 - Algebra de Boole

8/18/2019 Tema 04 - Algebra de Boole

1/43

Clase 04:

Algebra de Boole

Ing. Christian Lezama Cuellar

1


2/43

Introducción

George Boole

2

El matemático inglés George Boole nació el 2 denoviembre de 1815 en Lincoln y falleció el 8 dediciembre de 1864 en Ballintemple, Irlanda.

Boole recluyó la lógica a una álgebra simple.También trabajó en ecuaciones diferenciales, elcálculo de diferencias finitas y métodos generales

en probabilidad.


3/43

Algebra de BooleProporciona una notación para describir funciones lógicas y define unnúmero de operaciones que se pueden realizar con el fin desimplificarlas. El álgebra de Boole define variables, constantes y funciones para describir sistemas binarios, y una serie de teoremas quepermiten manipular expresiones lógicas.

• Constantes booleanas: Se definen dos: ‘0’ (estado FALSO) y ‘1’ (VERDADERO).

• Variables booleanas: Son magnitudes que pueden tomardiferentes valores en diferentes momentos. Pueden representarseñales de entrada o de salida y reciben nombres de caracteres

alfabéticos como: A, B, X, Y. Sólo pueden tomar los valores ‘0’ o ‘1’.• Funciones booleanas: Describen el comportamiento del sistema.

Cada operación lógica (suma, multiplicación, negación, ...) posee unanotación en el álgebra booleana, como se muestra en la Tabla 1.

3


4/43

Funciones lógicas elementales.

4


5/43

Algebra de BooleEl álgebra booleana es la teoría matemática que se aplica en la lógicacombinatoria.

Las variables booleanas son símbolos utilizados para representarmagnitudes lógicas y pueden tener sólo dos valores posibles: 1 (valoralto) ó 0 (valor bajo).

Operadores:▫ Operador AND “ . ”

▫ Operador OR “ + ”

▫ Operador NOT “ ¯ ”

5


6/43

Axioma: Propiedad Conmutativa A+B = B+AEl orden en la OR no importa

AB = BA

El orden en la AND no importa

6


7/43

Axioma: Propiedad asociativa

A + (B + C) = (A + B) + C Agrupar variables en la OR no importa

A.(B.C) = (A.B).C

Agrupar variables en la AND no importa

7


8/43

Axioma: Propiedad Distributiva

• A+(B.C) = (A+B)(A+C)

• A.(B + C) = (A.B) + (A.C)

8

U1 SN7432

U2 SN7432

U3 SN7408

A

B

(A+B)

(A+C)

(A+B).(A+C)

C

U7 SN7408

U8 SN7432 A

B

C (BC)

A+(BC)

=

U4 SN7408

U5 SN7408

U6 SN7432

(AB)

(AC)

(AB)+(AC)

B

C

AU9 SN7408

U10 SN7432

A

B

C (B+C)

A(B+C)

=


9/43

Axioma: Elemento identidad (0 para +)

A+0=AHacer una operación OR con 0 no cambia nada.

9

X=A

A

X

U11 SN7432 A

X=A


10/43

Axioma: Elemento identidad (1 para ·) A·1=A

Hacer una operación AND con 1 no cambia nada

10

A

X

X=A

U12 SN7408

T P 1

AX=A

V++


11/43

Axioma: Elemento complemento + =

O bien A o serán 1, luego la salida será 1

11

A

A

XX=1


12/43

Axioma: Elemento complemento ∗ =

Bien A o A son 0 luego la salida será 0.

12

A

A

XX=0


13/43

Teorema: A+1=1 (T. Complementación)

• Hacer una operación OR con 1 da siempre 1.

13

A

X

X=1


14/43

Teorema: A•0=0 (T. Complementación)

Hacer una operación AND con 0 siempre da 0

14

A

X

X=0


15/43

Teorema: A+A = A (T. Idempotencia)

Hacer una operación OR consigo mismo da elmismo resultado

15

A

A

X

A=A

6


16/43

Teorema: A•A = A (T. Idempotencia)

Hacer una operación AND consigo mismo da elmismo resultado

16

A

A

X

A=A


17/43

Teorema: = (T. Involución)

Si negamos algo dos veces volvemos al principio

17

A

XX=A

8


18/43

Teorema: A + AB = A (T. Absorción I)

18

A

B

X


19/43

Teorema A + = + (T. Absorción II)

• Si A es 1 la salida es 1 Si A es 0 la salida

19

AB

X

YX=Y

20


20/43

Leyes de De Morgan (2 variables)

De Morgan ayuda a simplificar circuitos digitalesusando NORs y NANDs

∗ = + + = ∗

20

Igual para n variables

21


21/43

Leyes de De Morgan (más de 2 variables)

+ + + = ∗ ∗ ∗

21

22


22/43

Análisis Booleano de Funciones Lógicas

• El propósito de este apartado es obtener expresiones booleanas simplificadas a partir de un circuito

• Se examina puerta a puerta a partir de sus entradas

• Se simplifica usando las leyes y propiedades booleanas.

22

23


23/43

Un conjunto B dotado con dos operaciones algebraicas, más (+) y por (×), esun álgebra de Boole, sí y sólo sí se verifican los siguientes postulados:

POSTULADOS

SUMA PRODUCTO

A + B = B + A (Conmutativa) A + (B + C) = (A + B) + C (Asociativa) A + (B · C) = (A + B) · (A + C) (Distributiva) A + 0 = A (Elemento neutro) A + A' = 1 (Complementario)

A · B = B · A (Conmutativa) A · (B · C) = (A · B) · C (Asociativa) A · (B + C) = (A · B) + (A · C) (Distributiva) A · 1 = A (Elemento neutro) A · A' = 0 (Complementario)

TEOREMAS

A + A = A (Idempotencia) A + 1 = 1 A + (A · B) = A (Absorción)(A + B)' = A' · B' (T. Morgan)(A')' = A A + (A' · B) = A + B(A · B) + (A · B') = A

A · A = A (Idempotencia) A · 0 = 0 A · (A + B) = A (Absorción)(A · B)' = A' + B' (T. Morgan)(A')' = A A ·(A' + B) = A · B(A + B) · (A + B') = A

23

24


24/43

Cálculo de la expresión algebraica desalida (ejemplo 1)

24


25/43

(A + B) (CD) = (A + B) + (CD) = A + B + CD

X e Y son

iguales

26


26/43

Cálculo de la expresión algebraica desalida (ejemplo 2)

26

X = (A+B) C + CD + B

= (A+B) C · CD + B

= (A+B) C · (CD + B)

= A B C · (C +D +B)

= A B C C + A B C D +A B C B

= A B C D


27/43

Loscircuitos

son iguales

28


28/43

Ejemplo 3

• Puerta a puerta a partir de sus entradas

28

X= AB+(C+D)

X= AB + C+ D

29


29/43

Ejemplo 4

29

X = (AB)(CD)

X = ABCD

30


30/43

Ejemplo 5

30

X = ABCD +A

Simplificando:

X = A + BCD

31


31/43

Ejemplo 6

31

32


32/43

• X = (AB+)BC

• Usando la propiedad distributiva:

• X = ABBC +BC

• X = ABC + BC

• X = ABC + 0•C

• X = ABC + 0

• X = ABC

32

33


33/43

Ejemplo 7

33

34


34/43

34

X = ( +AB) +((C+D))

X = (A + B) + ((C + D))

X = (A + B) + (BC + BD)

X = A + B + BC + BD

X = A + B + C + BD


35/43

Ejemplo 7

36


36/43

Operaciones Lógicas

Ejemplos: F(A, B, C)=• A.B.C = 1, si todas las variables son 1

= 0, si alguna es 0•

A+B+C = 1, si alguna variable es 1= 0, si todas son 0

3

37


37/43

Ejemplo 8

Puerta {A}, Ascensor {B}, Bajarse {Z}

Z=A.B’

A B Z

0 0 0

0 1 0

1 0 1

1 1 0

37

38


38/43

Ejercicios: simplificar e diseñar las funciones

3

))()()(( E D DC B E C C B A f

))(( E E D E CE DC D AC B f

)()()( ED D A E C D A DC D A EDC E C C DC C D E B E C B DC B f

E C DC D E B f

))()(( D E B E C DC f

))(( D E B D E C f

D D E ED E B D E DC CE CB f

BC DC D E EC f

BC D E EC f


39/43

Suma de productos

Y= A·B·C+B·C·D+A·C·D o directamente

Y= ABC+BCD+ACD

Producto de sumas

Y=(A+B+C)·(D+C)·(E+F)

Expresiones booleanas desde tablas de

verdad

40


40/43

Sumas de Productos (SP)

F= ABCD + ABCD + ABCD+ ABCD F es suma de productos

Sea una función F(ABCD) que sólo es 1 para los casos:0011, 1011, 1110, 1111

Cuando ABCD=0011, únicamente la

expresión producto ABCD es 1.

Cuando ABCD=1011, únicamente la

expresión producto ABCD es 1

…y así sucesivamente… resultando que

41


41/43

Productos de Sumas (PS)

Cuando ABCD=0010, sólo la

suma A+B+C+D es 0.

Cuando ABCD=0100, sólo la

suma A+B+C+D es 0, …

…y así sucesivamente…

La función F es 0 (o bien F es 1)

cuando ABCD=0010

o cuando ABCD=0100o cuando ABCD=0111

o cuando ABCD=1010

o cuando ABCD=1101

y en ningún otro caso más.

Sea una función F(ABCD) que

sólo es 0 para los casos:0010, 0100, 0111,

1010, 1101

F=ABCD+ABCD+ABCD+ABCD+ABCD

F=(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)

F es producto de sumas

De Morgan

42


42/43

Resumen

43


43/43

Bibliografía

• Diseño Digital – 3 Edición Morris Mano• http://books.google.com.pe/books?id=8WhBtfnaenkC&

printsec=frontcover&hl=es#v=onepage&q&f=false

• Logic and Boolean Algebra, Kathleen and HilbertLevitz

Tema 04 - Algebra de Boole

Documents

Transcript of Tema 04 - Algebra de Boole