Matematicas Discretas h492b

Curso: Matemáticas Discretas.

M.C. Luis Enrique Castañuela Fuentes.

MATEMATICAS DISCRETAS

El contenido temático presentado en este trabajo consiste principalmente en Algebra Booleana, que forma en gran parte el contenido del curso de Matemáticas Discretas. Adicionalmente este material contiene un tutorial para el estudio de los temas aquí presentados por medio de una computadora.

OBJETIVOS. 1. Conocer los diferentes sistemas numéricos y realizar operaciones aritméticas en cada uno de ellos. 2. Entender las leyes, teoremas y operaciones del álgebra booleana y familiarizarse con la utilización de los mismos.

3. Aplicar las leyes y teoremas del álgebra booleana para reducir expresiones algebraicas.

DESCRIPCION BASE A TEMAS. I.- Sistemas numéricos y operacionales.

1.- Sistemas Posicionales. 1.1. Representación Polinomial. 2.- Conversión entre bases. 2.1. Base 10 a cualquier base. 2.2. Cualquier base a base 10. 2.3. De base B1 a base B2.

Pág.1



3.- Aritmética Simple. 3.1. Suma y resta de números en cualquier base. 3.2. Representación de números. 3.2.1. Magnitud y signo. 3.2.2. Complementos a la base. 3.2.3. Complementos a la base menos 1. 3.3. Suma de números positivos y negativos. 4.- Aritmética BCD. 4.1. Código BCD y exceso 3. 4.2. Operaciones aritméticas en BCD. 4.3. Operaciones aritméticas en exceso 3. 5.- Representación de números reales.

II.- Algebra Booleana. 1. Introducción. 2. Operaciones básicas. 3. Expresiones booleanas y tablas de verdad. 4. Teoremas básicos. 5. Leyes conmutativa, asociativa y distributiva. 6. Teorema de simplificación. 7. Descomposición y factorización de expresiones. 8. Inversión. 9. Dualidad. 10.Teorema de consenso. III.- Simplificación Algebraica, O – exclusivo y equivalencia. 1. Simplificación algebraica de expresiones. 2. Operación 0 – exclusivo y equivalencia. 3. Lógica positiva y negativa.

Pág.2



I.- SISTEMAS NUMERICOS Y OPERACIONES. Definición: Un sistema de números puede definirse como un conjunto de reglas y símbolos que sirven para representar cantidades, el sistema debe facilitar la realización de operaciones aritméticas. El sistema decimal y romano son los dos sistemas mas conocidos. El decimal es un ejemplo de un sistema posicional. Un sistema de números posicional consta de: 1. Una base  – 1 2.  guarismos diferentes representados por  . cada uno de estos guarismos es un símbolo que representa una cantidad entera entre 0 y -1 inclusive. Ejemplo: Base 10  = 10 10 guarismos diferentes 1, ,2, ...10 0,1,2,3,4,5,6,7,8,9 ( entre 0 y -1) Ejemplo : Base 5 =5 5 guarismos diferentes 1, 2, ... 5 0,1,2,3,4. Entre (0 y -1) El sistema de números incluirá un símbolo para separar la parte entera de la fraccionaria. Es el punto “.” La representación de una cantidad en forma general es:  = n,  n-1. . .2, 1, 0  -1, -2 . . .  -m Cada i representa el guarismo que ocupa la posición i dentro del número y  representa la base del sistema.

Pág.3



El valor que representa cada guarismo i dentro del número depende del lugar que ocupe relativa al punto que separa la parte fraccionaria y entera, este valor se da por:

V (i ) = V (i ) = i * i i * i Ejemplo: 3 1 -1-2



1 2 3 4 . 8 2 10

V (2)

= 2*102 = 200

2 0 El valor o cantidad que representa ʎ esta dado por: n

n

V (ʌ) = V (i) = i * i i=-m

i =-m

Ejemplo: 1234.8210 3 =1 2 =2 1 =3 0 =4  -1 = 8  -2 = 2 V(ʌ)= V(i) = i * 10i =-2*10-2+-1*10-1+0*100+1*101+ 2*102+ 3*103 =2*10-2+8*10-1+4*100+3*101+2*102+1*103 = 0.02 + 0.8 + 4 + 30 + 200 + 100 = 1234.82

Pág.4


X Ejemplo: X X X X

X X X X X

X X X X X

X X X X X

1) Base  10 5 4 8 3 16 2

X X X X X


X X X X X

X X X X X

Guarismos () 0,1,2,3,4,5,6,7,8,9 0,1,2,3,4 0,1,2,3 0,1,2,3,4,5,6,7 0,1,2 0,1,2,3,4,5,6,7,8,9,A,B,C D,E,F 0,1

2) Representación 30.10 110.5 132.4 36.8 1010.3 1E.16 11110.2

NUMEROS CON DIFERENTES BASES

DECIMAL 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15

BINARIO 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

OCTAL 00 01 02 03 04 05 06 07 10 11 12 13 14 15 16 17 Pág.5

HEXADEC. 0 1 2 3 4 5 6 7 8 9 A B C D E F



2.- Conversión entre Bases. 2.1.- Conversión de Base  a Base 10. Si la aritmética indicada en la expansión de series de potencia es hecho en base 10 entonces el resultado es el equivalente decimal del número. Ejemplo: 147.38 1.-

147.38

= 1 * 82 + 4 * 81 + 7 * 80 + 3 * 8-1 = 64 + 32 + 7 + 3/8 =103.37510

2.-

A2F16

= 10 * 162 + 2 * 161 + F * 160 = 2560 + 32 + 15 = 260710

3.-

1011.112

= 1 * 23 + 0 * 22 + 1 * 21 + 1 * 20 + 1 * 2-1 +1 *2-2 =8+0+2+1+½+¼ = 11.7510

2.2.- Conversión de Base 10 a Base . Se separa en parte entera y en parte fraccionaria para efectuar la conversión. Se utiliza el método de división. Suponer que la representación del valor deseado en el sistema de números con base  es la siguiente: V (ʌ) =n, n-1 n-2... 2 1 0 . -1 -2... -m =  nn + n-1n-1 + n-2 n-2 + 2 2 + 11 + 00 + -1-1 + -m-m 1.- Considerar primero la parte entera del número. ʌ e = n n-1n-2...2 10 V (ʌ e) = nn + n-1n-1 + ...22 + 11 + 0 Pág.6



2.- Dividir ʌ e entre  obteniendo un cociente Co y un residuo r0 dados por: V (ʌ e) =  nn-1 + n-1n-2 + ... 21 + 1 = Co, residuo = 1 

3.- Dividimos el cociente Co entre  Co = nn-2 + n-1n-3 + 31 + 2 = C1, residuo = 1  4.- Se continua hasta obtener como residuo n lo que equivale a un residuo cero. El remanente obtenido en cada división es el dígito buscado y el dígito menos significativo es obtenido primero.

Ejemplo: 5310 a binario 53/2 =26

remanente 1

26/2 =13

0

13/2 =6

1

6/2 =3

0

3/2 =1

1

1 /2=0

1

∴ 5310 =1101012

Pág.7



La conversión de una fracción decimal a Base R se efectúa usando multiplicaciones sucesivas. 1.- Separando la parte fraccionaria ʌ f = . -1-2...-m -1 V (ʌ f)=-1

+ -2-2... +-m-m

2.- Multiplicando por  obtenemos: V (ʌ f )*=-1-2-1 + -m-m+1 = -1 + F1 F1= Parte fraccional del resultado y -1 es la parte entera 3.- Multiplicando F1 por  da: F1R = -2 + -3 -1 + ... -m -m2 = -1 + F2 4.- Se multiplica sucesivamente hasta obtener el número suficiente de dígitos La parte entera obtenida en cada paso es uno de los dígitos y el dígito mas significante es obtenido primero. Ejemplo: Convertir .62510 a Binario. F= .625 x2 1.250 (a-1 = 1)

F1 = .250 x2 0.500 (a-2= 0)

F2=0.500 x2 1.000 (a-3=1)

∴ 62510=.1012 El proceso no siempre termina, pero el resultado final es cuando la fracción se repite.

Pág.8



Por ejemplo: Convertir 0.710 a Binario. 0.7 x2 1.4 1

.4 x2 .8 0

.8 x2 1.6 1

.6 x2 1.2 1

∴0.710 = 1011001102

.2 x2 .4 0

.4 x2 .8 0 ....

Se repite a partir de este punto.

2.3.- Conversión de Base “R” a base “S”.

CUIDADO CON LOS DÍGITOS, NINGUNO PUEDE SER MAYOR O IGUAL A LA BASE. La conversión entre dos diferentes bases de 10 puede hacerse directamente usando los procedimientos dados pero es mas sencillo convertir primero a decimal y luego a la nueva base.

Ejemplo: Convertir 231.34 a base 7. 231.3

=2*42 + 3*41 + 1 * 40 + 3*4-1 = 32 + 12 + 1 +.75 = 45.7510

45.7510 45/7 = 6 6/7 = 0

base 7 residuo =3 residuo =6

.75 .25 .75 .25 x7 x7 x7 x7 5.25 1.75 5.25 1.75 5 1 5 1

∴ 231.34 =63.51551...7 Otra forma aplicable solo a bases binaria, octal y hexadecimal.

Pág.9



a.- conversión de binario a octal y al revés. 1. Cada dígito octal le corresponde exactamente 3 dígitos binarios (bits). 2. Empezando en el punto binario, los bits son divididos en grupos de 3. 3. Cada grupo de 3 es reemplazado por un dígito octal. EJEMPLO: 11 010 111 110 . 001 12 011 010 111 110 . 001 100 3 2 7 6 1 4 =3276.148 Caso contrario: 3247.618

Binario 3 2 4 7 011 010 100 111

.

6 1 110 001

=11010100111.110001

b.- Conversión de binario a Hexadecimal. 1. Se divide el número binario en grupos de 4 bits. 2. Se reemplaza por el número hexadecimal. 16

Ejemplo: 100 1101 . 0101 112 0100 1101 . 0101 1100 4

D 5 = 4D.5C16

Caso contrario:

3A7B.F1

C

2

3 A 7 B . F 0011 1010 0111 1100 1111

1 0001

Pág.10



1.3.- Aritmética Simple. 1.3.1.- Suma y resta de números en cualquier base. a.- Tablas de suma en algunos números de base diferente. Base 2 0 0 1

Base3

1

0 1 2

0 1 1 10

0 0 1 2 2 2 10 11

Base 4 0 1 2 3 0 1 2 3

0 1 2 3

1 2 3 10

2 3 10 11

Base 5 0 1 2

3 10 11 12

0 1 2 3 4

0 1 2 3 4

1 2 3 4 10

2 3 4 10 11

3 4 3 4 10 11 12

4 10 11 12 13

Ejemplos de Sumas. 1341.325 +3412.145 10304.015

4317.109 +7381.469 12708.569

ABCD.1816 +CAFE.AB16 176CB.C316

1357.658 +1177.158 2557.028

Pág.11

1717.458 +3434.558 5354.228

123.3217 +315.6067 442.2307



b.- Tablas para resta de números. Base 2 0

Base 3 1

0

0 11 1 0

0 1

0 1 2

0 1 2 3 4 5 6 7

1

2

3

4

5

6

7

0 17 16 15 14 13 12 11 1 0 17 16 15 14 13 12 2 1 0 17 16 15 14 13 3 2 1 0 17 16 15 14 4 3 2 1 0 17 16 15 5 4 3 2 1 0 17 16 6 5 4 3 2 1 0 17 7 6 5 4 3 2 1 0

Ejemplos de Restas: 1 11 4256. 117 -1443. 157 2512. 637

111 1 4 3 1 .125 - 3 3 3 .305 1 0 4 2 .325

Pág.12

2

0 12 11 1 0 12 0 1 0

Base 8 0

1

1 AB1F.C16 -1789 .B16 9396 .116



c.- Aritmética Binaria. La tabla de adición puede expresarse: 0+0=0 0+1=1 1+0=1 1+1=0

y se lleva un 1 de acarreo a la próxima columna.

La tabla de sustracción puede expresarse también: 0-0=0 0-1=1 y se lleva un 1 de acarreo a la próxima 1-0=1 columna. 1 – 1= 0 El acarreo de 1 en la columna equivale a restar 1 de esa columna.

Ejemplos: Suma: 111 1 1 0 12 +1 0 1 12 1 1 0 0 02

111111111 1 0 1 1 1 0 1 0 1 1 02 +0 1 1 0 1 1 0 1 0 1 12 1 0 0 1 0 1 0 0 0 0 0 12

Resta: 1 1 1 1 0 12 - 1 0 0 1 12 0 1 0 1 02

1111 1 0 0 0 02 1 12 1 1 0 12

111 1 1 1 0 0 12 1 0 1 12 1 0 1 1 1 02

Pág.13

1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 . 0 1 02 - 0 1 0 1 0 1 0 1. 1 0 12 0 1 0 1 1 1 1 1 . 1 0 12



La tabla de multiplicación para números binarios es: 0x0=0 0x1=0 1x0=0 1x1=1 Ejemplo: 1101 1011 1101 1101 0000 1101 10001111 División: 1 1011  1 0 0 1 0 0 0 1 11

Pág.14



1.3.2.- Representación de Números. (La diferencia es para los números negativos) Las computadoras digitales manejan cuatro tipos básicos de datos: 1. 2. 3. 4.

Números enteros con signo. Números reales con signo. Números BCD. Caracteres.

La cantidad de bits usada para representar cada uno depende de el tipo de dato y del equipo computacional. Información de otra clase se maneja agrupando los tipos de datos anteriores en estructuras mas complejas.

1.- Representación de Números Enteros. Para manejar números enteros con signo internamente en la computadora digital se usan 3 representaciones: a. Magnitud y signo. b. Complementos a 2 (complementos a la base) c. Complementos a 1 (complementos a la base disminuida) Magnitud y signo es la mas sencilla pero crea mas problemas para realizar operaciones aritméticas, fue usada en las primeras computadoras, ahora ha caído en desuso. Los de complementos tienen relativa facilidad de uso, siendo la mas usada la de complementos a 2. a. Magnitud y signo. Se usa un bit para el signo y „n‟ bits para la magnitud. n n-1 0 S  Magnitud 0 = número positivo.

Los „n‟ bits de la

magnitud 1 = número negativo.

Pág.15

Son el valor absoluto de la cantidad representada expre-



sado en binario. n

n

Rango: -(2 -1) 2 -1 n = 4 -15 15 1111 01111 Debe existir un bit = s Para el signo. Cantidad mayor en este formato = 2 n-1-1 Cantidad menor en este formato = -(2n-1-1)

Ejemplos: Utilizando 8 bits

* 8avo bit = signo * 0 – 7 bit = magnitud

Decimal 127 78 25 1 2 0 Represent. –0 -1 -25 -78 -127

Rep. en Magnitud y Signo 01111111 01001110 00011001 Si n=7 00000001 rango de cantidades 00000000 = 2n-1 = 127 a 10000000 - (2n-1) = -127 10000001 10011001 11001110 11111111

b.- Complementos a 2. Formato n n–1 S 

0 Magnitud

1. Un número positivo N se representa por un 0 seguido de la magnitud, igual que en magnitud y signo -. 2. Un número negativo, -N, es representado por su complemento a 2, N*, N* = 2n –N

n = longitud de la palabra N = Valor absoluto de la cantidad = N Pág.16



Ejemplo 1: -3  si n = 4 bits y N=-3= 3  N* = 2n -N  N* = 24-3 = 16-3 = 13 = 1101 Ejemplo 2: -1  si n = 8 bits y N = 1 N* = 28 –N = 256 – 1 =255 = 11111111 Ejemplo 3: -1 con n = bits N = 1 N* = 24 –1 = 16 – 1 = 15 = 1111 Rango: 4º signo 1 – 3 mayor n = 4 mayor 2n-1 = 7 menor = -2n = - 6 Para complementos a 2 se presenta el mismo caso para bit mas a la izquierda, es 1 para números negativos. El número mayor que se puede representar en este formato es 2n-1 ya que solamente se dispone de un bits para la magnitud. El menor número que puede ser representado es –2n lo que corresponde a 1 en el bit de signo y ceros en los bits de magnitud. El cero tiene una representación única en el formato.

Usando 8 bits en total. 127 78 25 1

01111111 01001110 00011001 00000001

0 -1 -25 -127 -128

Pág.17

00000000 11111111 11100111 10000001 10000000



c.- Complementos a 1. n

n –1 S 

0 Magnitud

Un número negativo , -N representado en complemento a 1 por N, se define por: N = ( 2n-1) – N n = longitud de palabra N = valor absoluto de la cantidad a representar Ejemplo 1: -0 n=4 y N=0 N = (24-1) – 0 = 15 =1111 Ejemplo 2: -1 para n = 4 N = 1 N = (256 – 1) – 1 = 254 = 11111110 En este formato el cero ite 2 representaciones (-0 y +0). El mayor valor que se puede representar es 2n-1 y el menor es –(2n-1) Ejemplos: 127 78 25 1 0 -0 -1 -25 -78 -127

01111111 01001110 00011001 00000001 00000000 11111111 11111110 11100110 10110001 10000000

Pág.18



Resumen de la presentación.

+N

Enteros Positivos (Todos los Sistemas)

+0 +1 +2 +3 +4 +5 +6 +7

0000 0001 0010 0011 0100 0101 0110 0111

-N

-0 -1 -2 -3 -4 -5 -6 -7 -8

Longitud de la palabra n = 4 Ent. Neg. Ent. Neg. Ent. Neg. Signo y Complement Complement Magnitud. a a 2 N* 1N 1000 ---1111 1001 1111 1110 1010 1110 1101 1011 1101 1100 1100 1100 1011 1101 1011 1010 1110 1010 1001 1111 1001 1000 ---1000* ----

Todos tienen un 1 en la Posición mas a la izq.

-8 no tiene Representación en N para 4 bits.

Otra forma Otra forma para formar De encontrar N* de N es iniciar en el Complementos lado derecho y complementar a 1 es complementar todos los bits a la izquierda, +N cambiando er del 1 1,menos*. 1s por 0s y 0s por 1s 1.3.3.- Sumas de números positivos y negativos.

a.- La adición usando complementos a 2 se lleva como si todos los números fueran positivos y cualquier acarreo de la posición del signo se ignora. Esto siempre d el resultado correcto excepto cuando ocurre un overflow. Overflow = desbordamiento.

Pág.19



Cuando la longitud de la palabra es “n” bits, ocurre un overflow cuando la representación de la suma incluyendo el signo requiere mas de “n” bits. Los casos que pueden presentarse para sumas de números son los siguientes : para n = 4 1.-Sum <2n-1 +3 0011 +4 0100 +7 0111 2.-Sum≥2n-1 +5 0101 +6 0110 +11 1011

suma

de 2 números positivos.

suma de 2 números positivos.

error por overflow +11 requiere 5 bits incluido el signo.

3.-Suma de un número positivo y uno negativo (número negativo de magnitud mayor) +5 0101 -6 1010 -1 1111 4.-Mismo caso anterior con número positivo de mayor magnitud. -5 1011 +6 0110 +1(1) 0001 Respuesta correcta cuando el acarreo de bit del signo es ignorado *esto no es overflow. 5.- Adición de 2 números negativos, sum≤2n-1 -3 1101 -4 1100 -7(1) 1001 Respuesta correcta cuando el ultimo acarreo es ignorado *esto no es overflow. 6.- Adición de 2 números negativos, sum >2 n-1 -5 1011 -6 1010 -11(1) 0101 Incorrecto debido a overflow –11 requiere 5 bits incluyendo el signo. Pág.20



b.- Suma con Complementos a 1´s. Similar a la anterior solo que en cambio de descartar el último acarreo se adiciona a la suma de “n” bits en la posición mas a la derecha. Los casos posibles para n = 4 son: 1° y 2° igual que en los complementos a 2. 3° Adición de números positivos y negativos (número negativo de mayor magnitud).

+5 -6 -1

0101 1001 1110

Respuesta correcta.

4.-Mismo caso anterior (número positivo de mayor magnitud).

-5 1010 +6 0110 +1 (1) 0000 ↳

1 0001

acarreo final Respuesta correcta, no hay overflow.

5.-Adición de 2 números negativos,sum2n-1

-3 1100 -4 1011 -7 (1)0111 ↳

1 1000

acarreo final. Respuesta correcta, no overflow.

Pág.21



6.-Adición de 2 números negativos, sum≥2n-1 -5 1010 -6 1001 -11(1) 0011 ↳

1 0100

acarreo final. Respuesta incorrecta debido al overflow.

Último bit indica positivo Lo cual es un error en este caso. Un overflow ocurre si sumamos 2 números positivos dando uno negativo como respuesta o al contrario.

1.4.- Representación de números reales. Para representar números reales en una computadora digital se debe determinar el orden de magnitud de las cantidades con las que se desea trabajar y la precisión con que se desean representar. Por ejemplo: Orden de 1030 y 10-30 con cierto grado de precisión. Para facilitar el manejo de estas cantidades se utiliza la notación científica. Un número expresado consta de: 3.14E+16

parte entera mayor que Cero y Y menor Que 10.

parte potencia de 10 fracc. la cant. de dígitos Depende de La precisión Que se desea.

Unidas se denomina Mantisa. Pág.22



Formato general de la notación científica.  Sdo . d-1 d-2 ...d-m X 10E di = dígitos S = signo (+,-) do = entera d-1...d-m = fracción m = depende de la precisión deseada. E = número entero con signo. En ciertos casos (como 1/3) es imposible representar la cantidad exacta, esto produce errores de representación. De estos existen 2 tipos: 1. Error absoluto : no da idea acerca de la precisión de la representación. 2. Error relativo : da una idea clara de la precisión de una representación. Ejemplo: Cantidad 10 10000000

Error Absoluto Error Relativo 1 0.1=10% 1 0.000001=0.0001%

La representación de números reales en las computadoras digitales es utilizando formas parecidas a la notación científica. Una de estas es: ⋀= S 0. -1 -2 ... -m2 X10E = S ⋀m X102E

signo de

mantisa normalizada

la mantisa en binarioʌm es un número mayor que 2-1 y menor que 1

exponente entero con signo (E) que indica la potencia a la que tiene que elevarse la base (102)

(2-1≤^m<1) Ejemplo: con 8 bits significativos 125= 11111012 = + 0.111110102 X 1027 -0.0625=-0.00012 = -0.100000002 X10-3

Pág.23



El formato de las computadoras digitales para esta notación es el siguiente: 1bit S 

ebits mbits e  m Exponente Mantisa

0=positivo Exponente binario E 1=negativo polarizado en 2e-1 la

Mantisa normalizada en binario usando m bits

polarización se usa (2-1≤m<1) para evitar tener un bit de signo para el exponente. Para obtener este número Binario sin signo (e) se Suma la polarización (2e-1) al exponente con signo E. Para obtener el exponente con signo se resta la polarización al número binario sin signo e. Pasos para representar un número real en este formato: 1. Representar el número binario. 2. Expresar el número binario como una mantisa normalizada multiplicada por la base (102) elevada a la potencia E. 3. Obtener la mantisa m con m bits, añadir ceros o truncar según el caso para tener los m bits. 4. Sumar la polarización (2e-1) al exponente E para obtener el exponente polarizado e. 5. Determinar el bit de signo del número. 6. Ensamblar el signo, exponente y mantisa en el formato. Ejemplo: Representar el número –2441.5 en el formato anterior usando 7 bits para el exponente y de 16 bits para la mantisa. 1° Rep. en binario -2441.5 = 100110001001.12

Pág.24



2° Mantisa normalizada -0. -10010001001.12 =-0.10011000100112 X 10212 3° Mantisa con m bits (m = 16) .10011000100110002 4° Sumar polarización. E = 12, polarización = 2e-1 = 27-1 =26 =64 Exponente polarizado: 12 + 64 = 76 = 10011002 =e 5° bit del signo número negativo bit del signo = 1 6° Ensamblar el formato. 1  1001100 S



1001100010011

exponente



000

mantisa

Ejemplo 2: Representar 0,2 en este formato. 1.- 0,2 = 0.0011001100110011...2 (serie infinita) 2.= 0.11001100110011001100...2 X 10-2 3.- m= .11001100110011012 Cuando es necesario truncar se hace lo siguiente:  Si el bit que ocupa la posición –m(1) es cero, se truncan los bits.  Si el bit que ocupa la posición –m(1) es uno, se redondea la mantisa (se le suma 2-(m+1). 4.-E = 2, polarización = 2e-1 = 64 exponente polarizado = -2 + 64 = 62 = 01111102= e 5.- Bit del signo = 0 6.- 0  0111110  1100110011001101 S exponente mantisa

Pág.25



La precisión de este formato es 2-m+1, se tienen m-1 bits significativos, la precisión depende exclusivamente del número de bits de que se disponga para la mantisa. 1.5.- Aritmética BCD. 1.- Código BCD. La mayoría de las aplicaciones istrativas que requieren exactitud en cierto número de cifras decimales usan la representación de datos en BCD – Binary Coded Decimal – Esta forma utiliza 4 bits para representar o codificar cada signo del número decimal que se desea y el cual es como sigue: Dígito 0 1 2 3 4 5 6 7 8 9

BCD 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

Para representar números en BCD se fija el número de dígitos enteros y decimales que se desea usar y se asignan 4 bits por cada dígito.

Ejemplo:

937.25

1001 0011 0111 . 0010 0101

Pág.26

Representación BCD ó 8421.



2.- Aritmética en BCD. Suma: 2 números en BCD con un dígito cada una. Si R = resultado  Caso 1:

0≤ R≤9 resultado correcto El resultado es de un solo dígito por lo tanto requiere de solo 4 bits para representarlo.

Caso 2:

R >9

Su representación requiere de 2 dígitos. Para obtener el resultado correcto se suma un 6 que representa el complemento a 2 de 10.

Ejemplos: 2 +5 7

0010 0101 0111

137 +381 518

0001 0011 0101

3 +6 9

0011 1000 1011 0111 (1) 0001

0011 0110 1001

0111 DCB 0001 DCB 1000

R = 0101 0001 1000 7 +5 (1)2

9 +8 (1) 7

0111 0101 1100 + 0110 (1) 0010

sumar 6

1001 1000 (1) 0001 ↓ 0110 (1) 0111

Pág.27



2.- ALGEBRA BOLEANA 1.-Introduccion El álgebra boleana es el álgebra de la lógica. Fue creada por el matemático inglés George Boole (1815-1864) en el año de 1854.

El álgebra boleana es útil para estudiar el diseño lógico de sistemas digitales entre los cuales están las computadoras, esto se debe a que los dispositivos involucrados en computación son esencialmente dispositivos en dos estados y en álgebra boleana todos los valores de las variables asumen solo uno de los valores. VARIABLES BOLEANAS Los símbolos “0” y “1” son usados para representar esos valores, estos no son valores binarios, no tienen valor numérico. El símbolo “0” puede representar un bajo voltaje o Falso y el símbolo “1” puede representar un alto voltaje o Verdadero.

2.- OPERACIONES BÁSICAS Existen 3 operaciones básicas: 1°- AND 2°- OR

Y O

. +

 

3°- NOT

NO

,

ó~

1°- Operación AND Se representa por: A· B = AB = AB Se define por

A 0 0 1 1

B 0 1 0 1

Se lee “A y B”

AB 0 0 0 1 Para que el valor de la operación  sea 1 los 2 operandos deben ser 1. Pág.28



La compuerta lógica que ejecuta la operación AND es: A B

Otra representación con switches

C= A*B

=0 =1 1

AND opera en serie

A 2

AND B

2° Operación OR Se representa por: A + B = A  B Se lee “ A ó B” Se define por

A 0 0 1 1

B 0 1 0 1

A+B 0 1 Igual a 1 cuando cualquiera 1 de los operandos es 1. 1

La compuerta lógica que ejecuta la operación OR se representa por: A

A B

OR opera en paralelo

C=A+B

2 B

3° Operación NO Representación A´, Se lee “no A ó A complemento” Se define A A´ 0 1 0´ = 1 1 0 1´ = 0 Un nombre alterno para el complemento es “ el inverso”. Simbólicamente se representa: X  o X´

Pág.29



Jerarquía de Operaciones: Primero los de mayor jerarquía. 1.-Paréntesis, primero los mas internos y luego hacia fuera. En ausencia del paréntesis. 1°NOT 2°AND 3°OR

3.-Expresiones Booleanas y tablas de verdad. Las expresiones booleanas se forman aplicando las operaciones básicas a una o más variables o constantes. Ejemplo de expresiones son:

AB´ + C AC + D´+ BE

Cada expresión corresponde a una red de compuertas lógicas. Ejemplo 1: AB´ + C AB1+C

A B1 B

CC C C C

Ejemplo 2: AC + D´ + BE A(C+D)

A(C+D)1

C+D A A(C+D)1+BE

C D BE B E

Una expresión es evaluada sustituyendo un 1 o un 0 en cada variable.

Pág.30



Si A = B = C = 1 y D = E = 0 la expresión AC+D1+BE = 11+0´ + 1.0 =1.1´+ 0 = 0+0 = 0 literal Cada aparición de una variable o su complemento se denomina una “literal”. La siguiente expresión tiene 3 variables y 10 literales. Abć + a´b + a´bc´ + bć´ Cuando la expresión se realiza usando compuertas lógicas cada literal en la expresión corresponde a una entrada de la compuerta. Una “ Tabla de Verdad” especifica los valores de una expresión booleana para cada combinación posible de valores de las variables en la expresión.

Ejemplo 1: A

´

F=A1 + B

A B

A 0 0 1 1

TABLA DE VERDAD B A1 F=A1+B 0 1 1 1 1 1 0 0 0 1 0 1

La tabla de verdad especifica la salida de la red para todas las posibles combinaciones de valores de entrada de A y B.

Pág.31



Ejemplo 2: AB´ + C A B C 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

B´

AB´

AB´ + C

A+C

B´+ C

1 1 0 0 1 1 0 0

0 0 0 0 1 1 0 0

0 1 0 1 1 1 0 1

0 1 0 1 1 1 1 1

1 1 0 1 1 1 0 1

(A+C) (B´+C) 0 1 0 1 1 1 0 1

Dos expresiones son iguales si tienen el mismo valor para cada posible combinación de variables  AB´ + C = ( A + C ) ( B + C )

4.- Teoremas Básicos: 1.- Teoremas del elemento identidad. 1a. A + 0 = A 1b. A * 1 = A

1a 1b

2.- Teoremas de idempotencia. 2a. A + A = A 2b. A * A = A

2a 2b

3.- Teoremas utilizando ceros y unos 3a. A + 1 = 1 3b. A * 0 = 0

3a 3b

4.- Teoremas en complementación. 4a. A + A1 = 1 4b. A * A1 = 0 4c. ( A1)1 = A

4a 4b 4c Pág.32



5.- Teoremas de DeMorgan. 5a. (A + B )1 = A1 * B1 5b. (A * B )1 = A1 + B1

5a 5b

6.- Teoremas de conmutatividad. 6a. A + B = B + A 6b. A * B = B * a

6a 6b

7.- Teoremas de asociatividad. 7a. A + (B+C) = (A+B) + C = A + B + C 7b. A* (B*C) = (A*B) * C = A* B * C

7a 7b

8.- Teoremas de distributividad. 8a. A + (B * C) = (A + B) (A + C) 8b. A * (B + C) = (A* B) + (A*C) 9.- Teorema de absorción. 9a. A + A * B = A 9b. A * (a + B) = a

8a 8b

9a 9b

10.- Teoremas de simplificación. 10a. A * B + A * B1 = A 10b. (A + B) (A + B1) = a

10a 10b

11a. A + A1B = A + B 11b. A* ( A1 + B) = A * B

11a 11b

11.- Teoremas de Concenso. 12a. AB + A1C + BC = AB + A1C 12b. (A+B)(A1+C)(B+C)=(A+B)(A1+C)

Pág.33

12a 12b



PRUEBAS DE LOS TEOREMAS 1° Por inducción. 2° Por deducción. 1° Prueba por inducción, utilizando tablas de verdad A 0 0 1 1

B 0 1 0 1

A´ 1 1 0 0

B´ 1 0 1 0

A´+B´ 1 1 1 0

(A*B) 0 0 0 1

(A*B)´ 1 1 1 0

2° Prueba por deducción, utilizando los mismos teoremas 2a. A + A = A

A + A = (A + A) * 1 = (A + A) * (A + A1) = A + A1A de X + YZ = (X+Y)(X+Z) =A+0 =A

9a. A + A* B = A

3.-

A * B + A * B´

=A * 1 + A * B =A(1 + B) =A (B + 1) de X + 1 = 1 =A * 1 =A

=A = A*( B + B´ ) = A*1 =A

Pág.34



DEMOSTRACIÓN DE IGUALDADES  a ( ab + c ) = ab + ac = (a *ab) + ac =a*a*b+a*c =a*b+ a*c

de 8b de 7b de 2b

 a ( a´ b + c ) = ac = a * a1 * b + a * c =0*b+a*c =a*c

de 8b de 4b de 3b

 ab1c + a1b1c=b 1c = b1c

de 10a

 ac + a(bc +c1) = a = ac + abc + ac1 = a ( c + bc + c1) = a (bc + 1) = a (1) =a

de 8b a la segunda expresión factor común de 4a de 3a de 1b

A= bć y B = a

SIMPLIFICACIÓN: 1.-

 = XY(Z + Z´ ) + XÝ´Z´

f = X´ Y´ Z´ + XYZ´ + XY

= X1 * Y1 *(Z + Z1) + X* Y * (Z + Z´ ) = X´ * Y´ * 1 + X * Y * 1 = XÝ´ + XY

2.-

de 9b de 4a de 1b

f = a´bć + a´bc´+abć´+abc´ = ´ ´

a b c + a´bc´ + abc´ + abć´ + abc´ = a´bć + (a + a´ 9 b c´ +a c´ (b´ + b) =a´bć + 1 * bc´ + ac´ * 1 = a´bć + bc´ + ac´

Pág.35

de 2a de 9b de 4a de 1b


3.-


f= (X1 + X2 + X3) (X1 + X2´ + X3)(X1´ + X2 + X3)(X1´ + X2 + X´3) =(X1 + X3)(X1´ + X2) de 11b ´ ´ =X1X1 + X1X2 + X1 X3 + X2X3 9b ´ =X1X2 + X1 X3 +X2X3 4b y 1ª ´ = X1X2 + X1 X3 13a

TEOREMAS DE SIMPLIFICACIÓN: 1° X + XY = X 2° XY + XY1 = X 3° (X + Y1)=XY

De 3°.

9a 10a 11a

X(X + Y) = XX (X +Y) (X + Y1) = X XY1 + Y = X + Y

9b 10b 11b

Simplificación de una compuerta lógica.

Y = A(A1 +B)

=

AB (A1+B)

A´ A

Y=A(A1+B)

B B A

Este circuito equivale a

Cualquier expresión puede ser sustituida por X y Y en los teoremas.

SIMPLIFICAR: 1.-

Z=A´BC+A´

Forma X + XY = X X = A´

y

Y = BC

 ABC + A´ = A´

Pág.36



Z=A + BĆ + D + EFA + BĆ + D+EF´

2.-

X

Y

X

Y´

(X + Y)(X + Y´ )= X

 Z= A+ BĆ 3.-

Z=(AB+C) (B´ D+C´ E´ ) + (AB+C)´ Y´

X

+

(X Y´ ) + Y = X + Y

Y

Z= (B´D + CÉ´ ) + (AB+C)´

4.-

5.-

ABC´ + (ABC´ )´ = A + A´ =1

Z

de 4ª.

= (AB + CD´ )(AB + D´ E )

de 8a (A + B) (A + C) = A + BC

= AB + CD´ E 6.-

Z

= A + BĆ + D´ (A + BĆ)

de 9a

A + AB = A

= A + BĆ 7.-

AB´ (C + D) + (C + D)´

de 11a. A + A´B = A + B

= (C +D)´ + AB´ 8.-

(EF)´ + AB + C´D´(EF)

de 11b. A*(A´+B) = A * B

=(EF)*(AB + C´ D´ )

Pág.37



DESCOMPOSICIÓN Y FACTORIZACIÓN DE EXPRESIONES DESCOMPOSICIÓN:  Para descomposición se usan las dos leyes distributivas.  Con esto se obtiene una suma de productos.  La suma de productos es el resultado final de la descomposición.

Ejemplo:

AB´+CD´ E+AC´ E´

Para descomponer: 1° aplicar la ley distributiva cuando sea posible (X+Y)(X+Z)=X+YZ 8a Ejemplo: Descomponer: 

X

=A

Y

= BC

Z

=D+E

(A+BC) (A+D+E)

= A + BC*(D+E) = A + BCD + BCE

Otra forma seria multiplicar todo y luego eliminar términos redundantes = A +AD+AE+ABC+BCD+BCE =A(1+D+E+BC) + BCD + BCE =A +BCD + BCE

Pág.38



 FACTORIZACION:  Pueden utilizarse las 2 leyes distributivas.  El objeto es obtener un producto de sumas. Ejemplo: (A + B1)(C + D´ +E)(A+C´ +E´ ) Una expresión esta completamente factorizada si y solo si esta en forma de producto de sumas. Ejemplos: Factorizar:  A + B´ C D

Forma : X + YZ = (X+Y) (X+Y) donde: X = A Y = B´ Z = CD

=(A+B1 )(A+CD) Todavía puede factorizarse

X=A Y=C Z = CD

= (A + B1)(A+C)(A+D)

 AB´ +C´ D 

X = AB´

Y = C´

Z=D

= (AB1 +C´ )(AB´ +D) =(A + C´ )+(B´ + C´  (A + D)(B´ +D)  C´ D + C´ E´ + G´ H 1° De 8b (A*B)+(A*C)=A*(B+C) = C´ (D+E´ ) + G´ H 2° La ley distributiva

Pág.39

X+Z = (X+Y) (X+Z)



= (C´ (D+Z´ ) + G´ (C´ (D+E´ ) +H) X = C´ (D+E´ ) G´ H Y=C´ Z=D + E´ =(G´ H+C´ )(G´ H+D+E´ )

Aplicando otra vez

=(C´ +G´ )(C´ +H)(D+E´ +G´ )(D+E´ +H)

Ejemplos: DESCOMPOSICIÓN:  (A + B) (A+C´ ) (A+D) (BC´ D+E)

(X+Y)(X+Z) = X + YZ

= (A+BC´ ) (A+D) (BC´D+E) = (A +BC´ D) (BC´ D+E) = (BC´ D +A) (BC´ D+E) = ABC´ D + AE + BC´ D*BC´ D + BC´ DE = BC´ D +AE = BC´ D+AE = BC´ D+AE  (A + B´ + C) (B´ + C + D) (A´ + C) = (B´ + C) + (A * D) (A´ + C) = (B´ + C + A) (B´ + C + D) (A´ + C) = (B´ + C) (A * D) (A´ + C) = (A´ + C) (B´ + C) + (A´ + C) (A * D) = A´B´ + AĆ + CB´ + C + A´D + AC + CD = A´B´ + C (A´ + B´ + 1 + DA + D) + A´ D = A´B´ + C + A´ D

Pág.40



INVERSIÓN: El inverso o complemento de cualquier expresión booleana se encuentra aplicando los teoremas de DeMorgan. 5a. (X+Y) ´ = XÝ´ 5b. (XY) ´ = X´+Y´

el complemento del producto es la suma de los complementos

Ejemplo: Encontrar el inverso o complemento.  (A´+B)C´ = (AB´)C´ = (AB´) ´ + C

= (A´ + B)C´´ = (A´ + B´) + (C´) ´ = AB´ + C  (AB´ + C)D´ + E´ = (AB´ + C)D´´ (E) ´ = (AB´+C) ´+(D´) ´*E´ = (AB´) ´*C´ +D)* E ´ = (A´+B) * C´ + D)*E´ II.- 9 DUALIDAD: Para formar el dual se hace lo siguiente: 1.-Intercambiar los operadores AND POR OR OR POR AND 2.-Intercambiar los 0s por 1s y 1s por 0s. 3.-Las variables se dejan igual. Ejemplo: (a + B) ´ = A´*B´ inverso A + A´ = 1 = A*A´ = 0 II.- 10 TEOREMA DEL CONCENSO:  Muy útil en simplificar ecuaciones booleanas, se utiliza para eliminar términos redundantes.  Una expresión de la forma Pág.41



XY + X´Z + YZ El término YZ es redundante y puede ser eliminado dando el siguiente resultado. =XY + X´Z  El término eliminado se denomina “Término de Concenso”. Ejemplos: Encontrar el concenso de:  ab + ać TC = bc ´ ´  abd + b de TC = ade´  ab´d + a´bd´ TC = 0 Simplificar: x y x´z yz a´b´ + ac + bc´ + b´ c + ab TC: bć TC: ab Ambos términos de concenso pueden ser eliminados.  = a´b´ + ac + bc´ E = xyz + x ´z´ + xyz´ + xý´z =xz + xy + xý´+ yz xy + x´z + yz = xy + xz Ejemplos: 

a´b´ + ac + bc´ + bć + ab = a´b´ + ac + bc´

x z

x y

TC

 (a + b + c´) (a + b +d´) (b + c + d´) z)

(x + y) (x´ + z) (y + z) = (x + y) (x´ +

Pág.42


z

x´


y

x

TC= a + b + d´

y

=(a + b + c´) (b+ c + d´)  Otra forma , utilizada cuando no se pueden eliminar términos 1 2 3 4 ´ ´ ´ F= ABCD + B CDE + A B + BCE´ Unico término De aquí.

de los TC encontrados ninguno se Encuentra en la expresión original no puede ser eliminada.

Secuencia: 1° Si adicionamos el TC ACDE obtenido de 1 y 2 queda:

____ _____ ´ ´ F = ABCD + B CDE + A B + BCE + ACDE ´

B1CDE ABCD

ACDE =A´B´ + BCE´ + ACDE

TEOREMA DE CONCENSO: Ejemplos: AC´D ____

____

ABC1 BC1D1

BC´D´ + ABC´ + AC´D + AB´D + A´BD´ = ABC´ + AB´D + A´BD´

Pág.43



UNIDAD III. SIMPLIFICACION ALGEBRAICA-OR EXCLUSIVO Y EQUIVALENCIA A. SIMPLIFICACION ALGEBRAICA.1.-Se utilizan los teoremas del álgebra booleana. 2.-La simplificación ayuda a reducir los costos de los circuitos. 3.-En adición a descomposición y factorización, tres formas básicas de simplificación son: 3.1- Combinando Términos. 3.2- Eliminando Términos. 3.3- Eliminando Literales. 3.1- Combinando Términos: Se utiliza XY + XY´ = X para combinar Ejemplo: abc´d´ + abcd´ x = abd´ y = c y´ = c´ = abd´ NOTA: En la combinación los 2 términos a combinar deben tener exactamente las mismas variables y exactamente una de las variables debe aparecer normal en un término y complementada en el otro. 3.2- Eliminando Términos: 1°- Utilizando: X + XY = X para eliminar términos redundantes. 2°- Tratar de aplicar el teorema del Concenso XY + X´Z + YZ = XY + X´Z para eliminar el término de concenso. a´b ¦ y = c  = a´b

Ejemplo 1:

a´b + a´bc

Ejemplo 2:

a´ bc´ + bcd + a´ bd

X=C Y = bd Z =a´ b XY + X´ Z + YZ = XY +

X´ Z Pág.44



= bcd + a´ + a´ bc´

3.3- Eliminando Literales: Utilizando X + X´ Y = X + Y Si es necesario primero se factoriza antes de aplicar el teorema. Ejemplo: A´ B + A´ BĆ´ D´ + ABCD´ = A´ (B + B´ C´ D) + ABCD´ =A´ (B + C´ D) + ABCD´ =A´ B + A´ C´ D + ABCD´ =B(A´ + CD´) + A´ C´ D =B(A + CD´ ) + A´ C´ D =AB + BCD´ + A´ C´ D

Factorización utilizando el teorema

Ejemplo: Simplificar:  xy + xýz´ + yz  (xy´ + z) (x + y´ ) z x x´ III.- 2. PRUEBA DE VALIDEZ DE UNA EXPRESIÓN Se utiliza para determinar si una ecuación es válida para todas las combinaciones de valores de las variables. Métodos para determinar la validez: 1°- Construir una tabla de verdad y evaluar ambos lados de la ecuación para todas las combinaciones posibles de valores de las variables. 2°- Manipular un lado de la ecuación aplicando los teoremas hasta llegar a una expresión idéntica a la del lado derecho. 3°- Reducir ambos lados de la ecuación independientemente a la misma expresión.

Pág.45



Ejemplo 1. Con la tabla de verdad. 2.Mostrar que A´BD´ + BCD + ABC´ + AB´ D = BC´ D´ + AD + A´ BC Pasos: 1°- Iniciamos con el lado izquierdo adicionando términos de concenso. 2°- Combinamos términos. 3°- Eliminamos términos por concenso.       

=A´ BD´ + BCD + ABC´ + AB´ D + BC´ D´ + A´ BC + ABD

1°-

2°-

Combinación de Términos : XY + XY´ = X

 De ⊀ y 7 AB´D + ABD X=AD ´ ´ ´ ´ ´ ´ = A BD + BCD + ABC + BC D + A BC + AD Repitiendo:      

Y=B =AD

AD + A´BD´ + BCD + ABC´ + BC´D´ + A´BC = y 6 =de 5 y 1 se elimina por TC de 5 y 6 = AD + BC´D´ + A´BC III.-3.OPERACIÓN O-EXCLUSIVO Y EQUIVALENCIA A. OPERACIÓN O-EXCLUSIVO

Pág.46


1°-


Se

define :

0 0=0 0 1 2

1=1 0=1 1=0

2°- Tabla de verdad: X Y X Y 0 0 1 1

0 1 0 1

0 1 1 0

 X + Y = 1 solo sí X = 1 ó Y = 1, no ambos. 3°- Expresado en términos de AND´S Y OR´S: X Y = XY´ + X´ Y  X Y

4°- Símbolo: 5°- Teoremas 14.1 14.2 14.3 14.4

X

Y

X X X X

0=X 1=X´ X=0 X´=1 14.5 X

14.6 (X Z)=X Y Ley Asociativa. 14.7 X(Y 14.8 (X XÝ´

Conmutativa. Y) Z

Z)=XY

Y=Y X Ley Z=X (Y

XZ Ley Distributiva.

Y)´= X

Y´= X´

B. OPERACIÓN EQUIVALENCIA 1°- Se define:  (00)=1 (01)=0 Pág.47

Y = XY +



(10)=0 (11)=1 2°- Tabla de verdad. XY X Y XY 0 0 1 0 1 0 1 0 0 1 1 1 (XY)=1 si y solo si X=Y 3°- Expresando en términos de AND´S y OR‟S (XY)=XY+XÝ´ La operación equivalencia es el complemento de X-OR (X + Y)´=(XÝ + XY´)´=(XÝ´)´*(XY´)´=(X+Y´)(X´+Y)=XY+XÝ´=(XY)  4°- Símbolo: X y

XY

Ya que la equivalencia es el complemento Del X-OR se tiene otra representación para la equivalencia.

Para simplificar expresiones que aplica  y  (X Y)= XY´ + XÝ  (X  Y)=XY + XÝ´ Ejemplo: Simplificar:

contengan 

F=(A´BC) + (B + AC´)  = A´BC + A´BĆ´ + BAC´ + BÁC´ = A´BC + (A + B´) C´ + B (A´ + C) + AB Ć = A´BC + AC´ + BĆ´ + ABĆ´ + A´B + BC Pág.48

 primero se



= B(AĆ + A´ + C) + C´ (A+B´ + AB´) = B(A´+C) + C´(A + B´)

Pág.49

Matematicas Discretas h492b

Overview 4q3b3c

More details 26j3b

Related Documents 171j1w

Matematicas Discretas h492b

Matematicas Discretas h492b

Matematicas Discretas h492b

Matematicas Discretas h492b

Aplicacion De Matematicas Discretas 3s1h2n

Arboles Matematicas Discretas 2tp4o

More Documents from "Microcom Mx" 27462r

Matematicas Discretas h492b

Tabla Normal 4w4w6g

Nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn.docx 1d2n5x

Mi Primer Startup 5k2o2u

Architects Design Checklist 5u3i5p

Proyecto De Aula Buen Vivir 2gx3g