trabajo de lineal algebra booleana

34
UNIVERSIDAD NACIONAL DE INGENIERÍA FACULTAD DE INGENIERÍA MECÁNICA FUNCIONES BOOLEANAS Y COMPUERTAS AND, OR Y NOT Curso : Algebra lineal Profesora : Luque Sección : «A» Autor : LEON NUÑEZ RONNY MANUEL GUSTAVO GAMARRA AGUILAR

Upload: ronny-leon-nunez

Post on 26-Dec-2015

53 views

Category:

Documents


1 download

TRANSCRIPT

Page 1: Trabajo de Lineal Algebra Booleana

UNIVERSIDAD NACIONAL DE INGENIERÍA

FACULTAD DE INGENIERÍA MECÁNICA

FUNCIONES BOOLEANAS Y COMPUERTAS AND, OR Y NOT

Curso : Algebra lineal

Profesora : Luque

Sección : «A»

Autor : LEON NUÑEZ RONNY

MANUEL GUSTAVO GAMARRA AGUILAR

Rímac, 17 de enero del 2014

Page 2: Trabajo de Lineal Algebra Booleana

Dedicado a mis padres por el apoyo

incondicional que me brindan.

Page 3: Trabajo de Lineal Algebra Booleana

Gracias a los maestros por sus enseñanzas,

y a nuestros padres por sus consejos.

Page 4: Trabajo de Lineal Algebra Booleana

FUNCIONES BOOLEANAS Y COMPUERTAS AND, OR Y NOT

ÍNDICE

CÁPÍTULO I: TEREMAS Y PROPIEDADES DEL ALGEBRA DE BOOLE CÁPÍTULO II: FUNCIONES BOOLEANAS2.1. Representación de funciones lógicas.

2.2. Formas canónica y normalizadaCÁPÍTULO III: SIMPLIFICACION DE FUNCIONES BOOLEANAS3.1. Método del mapa de Karnaugh 3.1.1. De dos variables3.1.2. De tres variables3.1.3. De cuatro variablesCÁPÍTULO IV: COMPUERTAS LOGICASCÁPÍTULO V: PROBLEMAS RESUELTOS 5.1. Ejercicios resueltos I5.2. Ejercicios resueltos II BIBLIOGRAFÍA

Page 5: Trabajo de Lineal Algebra Booleana

CÁPÍTULO I: TEREMAS Y PROPIEDADES DEL ALGEBRA DE BOOLE

TEOREMA 1: El elemento complemento A es único.

TEOREMA 2: Para cada elemento de B se verifica:

A+1 = 1 A·0 = 0

TEOREMA 3: cada elemento identidad es el complemento del otro.

0=1

1=0

TEOREMA 4 (Idempotencia): para cada elemento de B, se verifica:

A+A=A

A·A=A

TEOREMA 5 (Involución): para cada elemento de B, se verifica:

A = A

TEOREMA 6 (Absorción): para cada par de elementos de B, se verifica:

A+A·B=A

A·(A+B)=A

TEOREMA 7: para cada par de elementos de B, se verifica:

A + A·B = A + B

A · (A + B) = A · B

TEOREMA 8 (Asociatividad): cada uno de los operadores binarios (+) y

(·) cumple la propiedad asociativa:

A+ (B+C) = (A+B)+C

A· (B·C) = (A·B) ·C

LEYES DE DEMORGAN: para cada par de elementos de B, se verifica:

A+B= A B

AB = A+B

Page 6: Trabajo de Lineal Algebra Booleana

CÁPÍTULO II: FUNCIONES BOOLEANAS

En matemáticas, una función booleana es una función cuyo dominio son

las palabras conformadas por los valores binarios 0 ó 1 ("falso" o

"verdadero", respectivamente), y cuyo dominio son ambos valores 0 y 1.

Formalmente, son las funciones de la forma ƒ : Bn → B, donde B = {0,1} y n

un entero no negativo correspondiente a la aridad de la función.

Una función booleana es un conjunto de variables relacionadas entre sí

mediante los operadores lógicos.

Una función booleana es también una variable booleana.

2.1. Representación de funciones lógicas.

2.1.1. Forma algebraica general:

F (A ,B ,C , D)=A+A BC+A BCD

Es la combinación de variables relacionadas por las operaciones lógicas.

Esta forma de representación tiene el inconveniente de que no es única,

pudiendo haber infinitas representaciones para una misma

función.

2.1.1. Mediante la tabla de verdad:

Son tablas en las cuales figuran todas las combinaciones posibles de las

variables de entrada y el valor correspondiente de la función para cada una

de ellas. Este tipo de representación elimina el inconveniente de la forma

anterior ya que toda función tiene una única tabla de verdad.

Page 7: Trabajo de Lineal Algebra Booleana

Una tabla de verdad, consta de tantas columnas de entrada como variables

tenga la función y una única columna de salida.

Para obtener la tabla de verdad por el método de columnas auxiliares para

obtener la función de salida, es muy aconsejable simplificar al máximo la

función dada

F (A ,B ,C , D)=A BCD+A BC D+A BC D

A B C D F0 0 0 0 00 0 0 1 00 0 1 0 00 0 1 1 00 1 0 0 00 1 0 1 00 1 1 0 10 1 1 1 11 0 0 0 01 0 0 1 11 0 1 0 01 0 1 1 01 1 0 0 01 1 0 1 01 1 1 0 01 1 1 1 0

Page 8: Trabajo de Lineal Algebra Booleana

2.2. Formas canónica y normalizada

X Y Z Termino Designación Termino Designación

0 0 0 X Y Z m0 X+Y +Z M0

0 0 1 X Y Z m1 X+Y +Z M1

0 1 0 X Y Z m2 X+Y +Z M2

0 1 1 X YZ m3 X+Y +Z M3

1 0 0 X Y Z m4 X+Y +Z M4

1 0 1 X Y Z m5 X+Y +Z M5

1 1 0 XY Z m6 X+Y +Z M6

1 1 1 XYZ m7 X+Y +Z M7

F1=X Y Z+X Y Z+XYZ

F2=X Y Z+X Y Z+XY Z

F1=m1+m 5+m7=M 0.M 2.M 3.M 4.M 6=∑ (1,5,7 )=∏ (0,2,3,4,6)

F2=m2+m 4+m6=M 0.M 1.M 3.M 5.M 7=∑ (2,4,6 )=∏ (0,1,3,5,7)

CÁPÍTULO III: SIMPLIFICACION DE FUNCIONES BOOLEANAS

X Y Z F1 F20 0 0 0 00 0 1 1 00 1 0 0 10 1 1 0 01 0 0 0 11 0 1 1 01 1 0 0 11 1 1 1 0

Page 9: Trabajo de Lineal Algebra Booleana

3.1. Método del mapa de Karnaugh

Un mapa de Karnaugh (también conocido como tabla de Karnaugh o

diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es un

diagrama utilizado para la simplificación de funciones algebraicas

Booleanas.

Este método consiste en formar diagramas de 2n cuadros, siendo n el

número de variables. Cada cuadro representa una de las diferentes

combinaciones posibles y se disponen de tal forma que se puede pasar

de un cuadro a otro en las direcciones horizontal o vertical, cambiando

únicamente una variable, ya sea en forma negada o directa.

Este método se emplea fundamentalmente para simplificar funciones

de hasta cuatro variables. Para un número superior utilizan otros

métodos como el numérico. A continuación pueden observarse los

diagramas, también llamados mapas de Karnaugh, para dos, tres y

cuatro variables.

Es una práctica común numerar cada celda con el número decimal

correspondiente al término canónico que albergue, para facilitar el

trabajo a la hora de plasmar una función canónica.

Para simplificar una función lógica por el método de Karnaugh se

seguirán los siguientes pasos:

1º) Se dibuja el diagrama correspondiente al número de variables de la

función a simplificar.

Page 10: Trabajo de Lineal Algebra Booleana

2º) Se coloca un 1 en los cuadros correspondientes a los términos

canónicos que forman parte de la función.

3º) Se agrupan mediante lazos los unos de casillas adyacentes

siguiendo estrictamente las siguientes reglas:

a) Dos casillas son adyacentes cuando se diferencian únicamente en

el estado de una sola variable.

b) Cada lazo debe contener el mayor número de unos posible,

siempre que dicho número sea potencia de dos (1, 2, 4, etc.)

c) Los lazos pueden quedar superpuestos y no importa que haya

cuadrículas que pertenezcan a dos o más lazos diferentes.

d) Se debe tratar de conseguir el menor número de lazos con el

mayor número de unos posible.

4º) La función simplificada tendrá tantos términos como lazos posea el

diagrama. Cada término se obtiene eliminando la o las variables que

cambien de estado en el mismo lazo.

3.1.1. De dos variablesEn el hay cuatro términos mínimos para dos variables es decir que el

mapa consiste en cuatro cuadrados uno para cada termino.

X Y 0 1 0

10

00 01

10 11

m0 m1

m2 m3

Page 11: Trabajo de Lineal Algebra Booleana

3.1.2. De tres variables

Hay ocho términos mínimos para las tres variables. El mapa consiste

en ocho cuadrados.

X Y 00 01 11 10

0

1

3.1.3. De cuatro variables

Consta de 16 términos y los cuadrados asignados a cada uno .

AB CD 00 01 11 10

00

01

11

10

m0 m1 m3 m2

m4 m5 m7 m6

000 001 011 010

100 101 111 110

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

Page 12: Trabajo de Lineal Algebra Booleana

CÁPÍTULO IV: COMPUERTAS LOGICAS

AND

F=XY

X F

Y

OR

F=X+Y

X F

Y

NAND

F=XY

X F

Y

NOR

F=X+Y

X F

Y

XOR

F=X⊕Y

X F

Y

NOR-exclusiva

F=X⊙Y

X F

Y

Page 13: Trabajo de Lineal Algebra Booleana

CÁPÍTULO V: PROBLEMAS RESULETOS

5.1. Ejercicios resueltos I1) Simplifique la expresión por medio de un mapa de karnaugh de cuatro

variables.a) F(A,B,C) = ∑ m=(0,1,2,4,5,6,8,9,12,13,14 )

AB CD 00 01 11 10

00

01

11

10

½ L2 L1

½ L2

½ L3

½ L3

Lazo 1

A= 0o1 B= 0o1 C=0 D= 0o1

C

Lazo 2

A=0 B= 0o1 C= 0o1 D=0

A D

Lazo 3

A= 0o1 B= 1 C= 0o1 D=0

BD

F=C+A D+B D

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

1 1 1

1 1 1

1 1 1

1 1

Page 14: Trabajo de Lineal Algebra Booleana

b) F(A,B,C) = A BC+BC D+ABC D+A BCF(A,B,C) = A BC (D+D)+BC D(A+A)+A BC D+A BC (D+D)F(A,B,C) = A BC D+A BC D+A BC D+A BC D+A BC D+A BC D+A BC D ¿F(A,B,C) = ∑ m=(0,1,2,6,8,9,10 )

AB CD 00 01 11 10

00

01

11

10

¼ L1 ½ L2 ¼ L1

L3

¼ L1 ½ L2 ¼ L1

Lazo 1

A= 0o1 B= 0 C=0 D= 0o1

BC

Lazo 2

A=0o1 B= 0 C= 0o1 D=0

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

1 1 1

1

1 1 1

Page 15: Trabajo de Lineal Algebra Booleana

BD

Lazo 3

A= 0 B= 0o1 C= 1 D=0

AC D

F=BC+B D+A C D

2) Simplificar la siguiente función booleana en suma de productos por medio de un mapa de karnaugh de 4 variables.Dibuje el circuito lógico con:a) Compuertas OR-ARb) Compuertas NAND

F(A,B,C) = ∑ m=(2,3.4,5,6,7,11,14,15)

AB CD 00 01 11 10

00

01

11

10

L1

L2

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

1 1

1 1 1 1

1 1

1

Page 16: Trabajo de Lineal Algebra Booleana

L3 L4

Lazo 1

A= 0 B= 0o1 C=1 D= 0o1

AC

Lazo 2

A=0o1 B= 1 C= 1 D=0o1

BC

Lazo 3

A= 0 B= 1 C= 0o1 D=0o1

A B

Lazo 4

A= 0o1 B= 0o1 C= 1 D=1

CD

F=AC+BC+A B+CD

Compuerta OR-AND

A

B

A

C F

B

C

C

D

Compuerta NAND

F=AC+BC+A B+CD

F=A B+A C+BC+CD

Page 17: Trabajo de Lineal Algebra Booleana

F= ´A B+A C+BC+CD

F=A B . AC . BC .CD

A

B

A

C F

B

C

C

D

3) Determine la expresión mínima para el siguiente mapa de karnaugh

e implemente su circuito lógico

AB CD 00 01 11 10

00

01

11

10

L2

L1

L3

1 0 1 1

1 0 0 1

0 0 0 0

1 0 1 1

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

1 0 1 1

1 0 0 1

0 0 0 0

1 0 1 1

Page 18: Trabajo de Lineal Algebra Booleana

Lazo 1

A= 0o1 B= 1 C=0o1 D= 1

BD

Lazo 2

A=0o1 B= 0o1 C= 0 D=1

C D

Lazo 3

A= 1 B= 1 C= 0o1 D=0o1

AB

F=AB+BD+C D

F=AB+BD+C D

F=AB. BD.C D

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

F=A D+BD+BC

Circuito lógico

A

D

B

D F

B

C

4) Simplifique la siguiente función booleana aplicando el mapa de karnaugh

y diseñe el circuito lógico correspondiente con compuertas NAND.

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

Page 19: Trabajo de Lineal Algebra Booleana

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

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

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

F ( A , B ,C ,D )=∏ (5,6,7,10,11,13,14,15 )=∑ (0,1,2,3,4,8,9,12)

AB CD 00 01 11 10

00

01

11

10

L1

½ L3

L2

½ L3

Lazo 1

A= 0 B= 0 C=0o1 D= 0o1

A B

Lazo 2

A=0o1 B= 0o1 C= 0 D=0

C D

Lazo 3

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

1 1 1 1

1 0 0 0

1 0 0 0

1 1 0 0

Page 20: Trabajo de Lineal Algebra Booleana

A= 0o1 B= 0 C= 0 D=0o1

BC

F=A B+C D+BC

F= ´A B+C D+BC

F=A B .C D . BC

A

B F

C

D

B

C

5) Simplificar la siguiente función booleana:F=( A ,B ,C ,D )=A C D+BCD+A BC D+ABD+A BC D+A D+BC

Utilizando el mapa de karnaugh. Implementar el circuito lógico correspondiente utilizando compuertas NAND.

F=( A ,B ,C ,D )=A C D+BCD+A BC D+ABD+A BC D+A D+BC

F ( A , B ,C ,D )=AC D(B+B)+BCD (A+A)+A BC D+ABD(C+C)+A BC D+A D(B+B)+BC (A+A)

F ( A , B ,C ,D )=ABC D+A BC D+ABCD+A BCD+A BC D+ABCD+ABC D+A BC D+AB D+A B D+A BC+A BC

F ( A , B ,C ,D )=ABC D+A BC D+ABCD+A BCD+A BC D+ABCD+ABC D+A BC D+AB D(C+C)+A B D(C+C)+A BC(D+D)+A BC(D+D)

F ( A , B ,C ,D )=ABC D+A BC D+ABCD+A BCD+A BC D+ABCD+ABC D+A BC D+ABC D+ABC D+A BC D+A BC D+A BCD+A BC D ¿+ABCD+A BC D

F=( A ,B ,C ,D )=∑ (2,3,5,7,8,9,10,11,12,13,14,15 )

Page 21: Trabajo de Lineal Algebra Booleana

AB CD 00 01 11 10

00

01

11

10

L1

½ L2

½ L2

Lazo 1

A= 0 B= 0 C=0 D= 0o1

A BC

Lazo 2

A=0 B=1 C= 0o1 D=0

A BD

F=A BC+A BD

F=A BC+A BD

F=A BC . A B D

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

0000 m0 0001 m1 0011 m3 0010 m2

0100 m4 0101 m5 0111 m7 0110 m6

1100 m12 1101 m13 1111 m15 1110 m14

1000 m8 1001 m9 1011 m11 1010 m10

0 0 1 1

0 1 1 0

1 1 1 1

1 1 1 1

Page 22: Trabajo de Lineal Algebra Booleana

F=A+A B+AD+AB+BD+AC+BC+CD

F=A+BD+BC+CD

Compuerta NAND

F= ´A+BD+BC+CD

F=A .BD .BC .CD

A

B

D F

B

C

C

D

Page 23: Trabajo de Lineal Algebra Booleana

5.2. Ejercicios resueltos II

Solución:

=> ∑ m(0,1,2,5,8,9,10)

Mapa de 4 variables

½Lazo 2

¼ lazo 1 ¼ lazo 1

Lazo 3

¼ lazo 1 ¼ lazo 1

½Lazo 2

Lazo 1 => a= (0,1) b=0 c= (0,1) d=0 = B’D’

Lazo 2 => a= (0,1) b=0 c=0 d= (0,1) = B’C’

111

1

111

Page 24: Trabajo de Lineal Algebra Booleana

Lazo 3 => a=0 b= (0,1) c=0 d=1 = A’C’D’

=>B’D’+ B’C’+ A’C’D’

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

= AB’D’+A’B’D’+AB’C’+A’B’C’+A’BC’D+A’BC’D+A’B’C’D

= AB’CD’+AB’C’D’+A’B’CD’+A’B’C’D’+AB’C’D+AB’C’D’+A’B’C’D+

A’B’C’D’+A’BC’D+A’B’C’D

m (0, 1, 2, 5, 8, 9,10)

a) A’B+AB’C’+ABC’= (A C’

A’B+AC’ (B+B’)+AB’C= (A C’

A’B+AC’+AB’C = (A C’

A’B+A (C’+B’C)= (A C’

A’B+A (C’+B’)= (A C’

A’B+AC’+AB’ = (A C’

(A C’= (A C’

b) F=AB’CD’+A’BCD’+AB’C’D+A’BC’D

F=AB’ (CD’+C’D)+A’B (CD’+C’D)

F= (AB’+A’B) (CD’+C’D)

F= (A (CD

Page 25: Trabajo de Lineal Algebra Booleana

a) AB’+C’D’+A’CD’

=AB’+D’ (C’+A’C)

=AB’+D’ (C’+A’)

=AB’+C’D’+A’D’

= ((AB’+C’D’+A’D’)’)’

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

b) AB’CD’+A’BCD’+AB’C’D+A’BC’D

=AB’ (CD’+C’D) +A’B (CD’+C’D)

= (AB’+A’B) (CD’+C’D) Complemento dos veces

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

 

Page 26: Trabajo de Lineal Algebra Booleana

a) F=A’BE+BCDE+BC’D’E+A’B’DE’+B’C’DE’

F=DE’ (A’B’+B’C’) +BE (CD+C’D’) +A’BE

F=DE’B’ (A’+C’) +BE+A’BE

F= DE’B’A’+DE’B’C’+BE (1+A’)

F=A’B’DE’+B’C’DE’+BE = (A’+C’) B’DE’+BE

F=BE+B’DE’

b) F=AB’CD’+A’BCD’+AB’C’D+A’BC’D

F=CD’ (AB’+A’B) +C’D (AB’+A’B)

F= (AB’+A’B) (CD’+C’D)

F= ((AB’+A’B)’+ (CD’+C’D)’) ’

Page 27: Trabajo de Lineal Algebra Booleana

a) = (A (B’+C) + (CD) ’) ’

= (A (B’+C) ’) ’.CD

= (A’+ (B’+C)).CD

= A’CD+B’CD+CD

= CD (A’+B’+1)

= CD

b) F=A’CD+B’CD+CD

F=A’CD (B’+B)+B’CD(A+A’)+CD(A+A’)(B+B’)

F=A’BCD+A’B’CD+AB’CD+A’B’CD+(ACD+A’CD)(B+B’)

F=A’BCD+A’B’CD+AB’CD+ABCD

F=CD

1

1

1

Page 28: Trabajo de Lineal Algebra Booleana

BIBLIOGRAFÍA

Matemática discreta /J. C. Ferrando, Valentín Gregori

Álgebra Booleana. Aplicaciones tecnológicas /Carlos Barco Gómez

Problemas de matemática discreta /Carmen Alegre

Diseño de sistemas digitales: introducción práctica/ Joan Oliver, Carles

Ferreri Ramis