viernes, 5 de diciembre de 2014

Bienvenidos al BLOG!

Este blog tiene como objetivo ayudar al estudiante durante su busqueda de conociemiento acerca de la materia de MATEMATICAS DISCRETAS,fue un trabajo que se realizo por JAIR BECERRA SANCHEZ alumno del Tecnologico del estado de QUERETARO  por la materia de MATEMATICAS DISCRETAS la cual es impartida por el prof NICOLAS HIGAREDA SISNEROS.


   En lo personal este blog me deja una grata experiencia porque al ser elaborado me permite repasar los temas vistos en clase y asu vez es una herramienta que me servira en un futuro ya que es una buena herramienta hecha por buenas fuentes de consulta.

    Estos temas como ingeniero en sistemas tiene que ser vistos y ami me ayudaron y espero que ayuden de la misma manera a cualquier persona que pueda ver este blog.
    Sin mas que decir termino esta pequeña introduccion esperando sea de utilidad este blog para todos.


Temario

Los temas que se abarcan en este Blog son los siguientes:

Bibliografias

BIBLIOGRAFIA

Matemáticas discretas – con aplicación a las ciencias de la computación
   JEAN-PAUL TREMBLAY
       ISBN: 0-070605142-6

Matemáticas discretas
   RICHARD JOHNSONBAUGH
      ISBN: 0-02-360720-3


Matemáticas discretas-sexta edición
 RICHARD JOHNSONBAUGH
      PEARSON EDUCACIÓN, México, 2005
         ISBN: 970-26-0637-3
            Área: Universitarios 
               Formato: 21 x 27 cm     paginas 696

LINKS



1 Sistemas numéricos


Sistemas de numeración
Un sistema de numeración es un conjunto de símbolos y reglas que permi­ten representar datos numéricos. Los sistemas de numeración actuales son sistemas posicionales, que se caracterizan porque un símbo­lo tiene distinto valor según la posición que ocupa en la cifra.

1.1  Sistemas numéricos (Binario, Octal, Decimal,Hexadecimal)


Sistema Numérico de Base 10  
Los sistemas numéricos están compuestos por símbolos y por las normas utilizadas
para interpretar estos símbolos. El sistema numérico que se usa más a menudo
 es el sistema numérico decimal, o de
Base 10. El sistema numérico de Base 10 usa diez símbolos: 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9.
Estos símbolos se pueden combinar para representar todos los valores numéricos
 posibles.


Sistema Numérico de Base 2    

Los computadores reconocen y procesan datos utilizando el sistema numérico binario, o de Base 2
.  El sistema numérico binario usa sólo dos símbolos, 0 y 1 (ENCENDIDO/APAGADO ),
en lugar de los diez símbolos que se utilizan en el sistema numérico decimal.

Ejemplo: 

101102 =  22
Sistema Numérico de Base 8    

El inconveniente de la codificación binaria es que la representación de algunos números resulta muy larga.
 Por este motivo se utilizan otros sistemas de numeración que resulten más cómodos de escribir:
 el sistema octal y el sistema hexadecimal. Afortunadamente, resulta muy fácil convertir un número
 binario a octal o a hexadecimal.

En el sistema octal, usa ocho dígitos diferentes: 0, 1, 2, 3, 4, 5, 6 y 7. Ejemplo:

El número octal 2738 = 149610
Sistema Numérico de Base 16 (Hexadecimal)

El sistema hexadecimal usa dieciséis símbolos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F.
 Se utilizan los caracteres A, B, C, D, E y F representando las cantidades decima­les
10, 11, 12, 13, 14 y 15 respectivamente, porque no hay dígitos mayores que 9
 en el sistema decimal. 

Ejemplo:

El número hexadecimal 1A3F16 = 671910

1.2 Conversiones entre sistemas numéricos.

BINARIO A DECIMAL

Para realizar la conversión de binario a decimal, realice lo siguiente: 1. Inicie por el lado derecho del número en binario, cada cifra multiplíquela por 2 elevado a la potencia consecutiva (comenzando por la potencia 0, 20). 2. Después de realizar cada una de las multiplicaciones, sume todas y el número resultante será el equivalente al sistema decimal. Ejemplos: • (Los números de arriba indican la potencia a la que hay que elevar 2) También se puede optar por utilizar los valores que presenta cada posición del número binario a ser transformado, comenzando de derecha a izquierda, y sumando los valores de las posiciones que tienen un 1. Ejemplo El número binario 1010010 corresponde en decimal al 82. Se puede representar de la siguiente manera: entonces se suman los números 64, 16 y 2:
BINARIO A OCTAL

Para realizar la conversión de binario a octal, realice lo siguiente: 1) Agrupe la cantidad binaria en grupos de 3 en 3 iniciando por el lado derecho. Si al terminar de agrupar no completa 3 dígitos, entonces agregue ceros a la izquierda. 2) Posteriormente vea el valor que corresponde de acuerdo a la tabla: Número en binario 000 001 010 011 100 101 110 111 Número en octal 0 1 2 3 4 5 6 7 3) La cantidad correspondiente en octal se agrupa de izquierda a derecha. Ejemplos • 110111 (binario) = 67 (octal). Proceso: 111 = 7 110 = 6 Agrupe de izquierda a derecha: 67


BINARIO A HEXADECIMA

Para realizar la conversión de binario a hexadecimal, realice lo siguiente: 1) Agrupe la cantidad binaria en grupos de 4 en 4 iniciando por el lado derecho. Si al terminar de agrupar no completa 4 dígitos, entonces agregue ceros a la izquierda. 2) Posteriormente vea el valor que corresponde de acuerdo a la tabla: Número en binario 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Número en hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F 3) La cantidad correspondiente en hexadecimal se agrupa de derecha a izquierda. Ejemplos • 110111010 (binario) = 1BA (hexadecimal). Proceso: 1010 = A 1011 = B 1 entonces agregue 0001 = 1 Agrupe de derecha a izquierda: 1BA • 11011110101 (binario) = 6F5 (hexadecimal). Proceso: 0101 = 5 1111 = F 110 entonces agregue 0110 = 6 Agrupe de derecha a izquierda: 6F5


DECIMAL A BINARIO

Se divide el número del sistema decimal entre 2, cuyo resultado entero se vuelve a dividir entre 2, y así sucesivamente hasta que el dividendo sea menor que el divisor, 2. Es decir, cuando el número a dividir sea 1 finaliza la división. A continuación se ordenan los restos empezando desde el último al primero, simplemente se colocan en orden inverso a como aparecen en la división, se les da la vuelta. Éste será el número binario que buscamos. Ejemplo Transformar el número decimal 131 en binario. El método es muy simple: 131 dividido entre 2 da 65 y el resto es igual a 1 65 dividido entre 2 da 32 y el resto es igual a 1 32 dividido entre 2 da 16 y el resto es igual a 0 16 dividido entre 2 da 8 y el resto es igual a 0 8 dividido entre 2 da 4 y el resto es igual a 0 4 dividido entre 2 da 2 y el resto es igual a 0 2 dividido entre 2 da 1 y el resto es igual a 0 1 dividido entre 2 da 0 y el resto es igual a 1 -> Ordenamos los restos, del último al primero: 10000011


DECIMAL A OCTAL

Para la conversión de numero decimal a octal se hace con la misma técnica que se utiliza para la conversión del binario, pero ahora dividiremos entre 8. Ejemplo: Decimal a Octal:
1476:8=184 resto 4
184:8=23 resto 0
23:8=2 resto 7
El numero es octal=2704


DECIMAL A HEXADECIMAL

Se divide el número decimal y los cocientes sucesivos entre 16. El último cociente y , la secuencia de todos los restos obtenidos escritos en orden inverso es el número expresado en sistema hexadecimal. Ejemplos:
Decimal=15321
15321:16=957 resto 9
957:16= 59 resto 13 (13 es D en hexa)
59:16=3 resto 11 (11 es B en hexa)
Entonces:
Hexadecimal=3BD9
OCTAL A BINARIO
Solo tenemos q aprender y no esta difícil debes aprender a contar de 0 a 7 en binario
0 = 000 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 6 = 110 7 = 111
para aprenderlas más fácil fíjate como en la última columna los dígitos se van alternando 0,1,0,1,0,1 etc.. En la penúltima columna van 0,0,1,1,0,0,1,1 etc. y en la antepenúltima columna van 0,0,0,0,1,1,1,1, como ves es sumamente fácil. Es sencillo tomas el número en octal y le sacas su equivalencia binaria a cada digito en tres bits. Ejemplo
456 octal a binario 4 = 100 5 = 101 6 = 110 por tanto el 456 octal a binario queda: 100101110


OCTAL A DECIMAL

La conversión de un número octal a decimal es igualmente sencilla, conociendo el peso de cada posición en una cifra octal. Por ejemplo, para convertir el número 2378 a decimal basta con desarrollar el valor de cada dígito: 2*8^2 + 3*8^1 + 7*8^0 = 128 + 24 + 7 = 159 en base 10 237 en base 8 = 159 en base 10


OCTAL A HEXADECIMAL
Convierte al número octal en su equivalente binario y luego convertir el número binario en su número hexadecimal equivalente de la tabla de conversión produce el valor resultante. En el siguiente ejemplo permite comprender cómo realizar octal en hexadecimal de conversión Ejemplo:
Convertir el número octal (7 5 2) 8
<br< HEXADECIMAL A BINARIO <br< cada="" dígito="" hexadecimal="" puede="" representar="" uno="" de="" dieciseis="" valores="" entre="" 0="" y="" 1510.="" como="" sólo="" tenemos="" diez="" dígitos="" decimales,="" necesitamos="" inventar="" seis="" adicionales="" para="" los="" 1010="" en="" lugar="" crear="" nuevos="" simbolos="" estos="" dígitos,="" utilizamos="" las="" letras="" a="" la="" f.="" conversión="" binario="" es="" sencilla,="" considere="" siguiente="" tabla:=""
0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F
Esta tabla contiene toda la información necesaria para convertir de binario a hexadecimal y visceversa. Para convertir un número hexadecimal en binario, simplemente sustituya los correspondientes cuatro bits para cada dígito hexadecimal, por ejemplo, para convertir 0ABCDh en un valor binario: Ejemplo:
0 A B C D (Hexadecimal)
0000 1010 1011 1100 1101 (Binario) 
HEXADECIMAL A DECIMAL

Convertir el numero hexadecimal 2B6 a su equivalente decimal.
1. Multiplicamos el valor de posición de cada columna por el dígito hexadecimal correspondiente. 2. El resultado del número decimal equivalente se obtiene, sumando todos los productos obtenidos en el paso anterior. 
HEXADECIMAL A OCTAL
El hexdecimal octal conversión puede realizarse fácilmente en dos pasos. Convertir el hexadecimal en su equivalente binario es el primer paso y convertir al número binario número octal equivalente de la tabla de conversión es el segundo paso para realizar la tarea. El siguiente ejemplo permite que entienda cómo realizar el hex para conversión octal
Tabla de conversión entre decimal, binario, hexadecimal y octal Decimal Binario Hexadecimal octal 0 00000 0 0 1 00001 1 1 2 00010 2 2 3 00011 3 3 4 00100 4 4 5 00101 5 5 6 00110 6 6 7 00111 7 7 8 01000 8 10 9 01001 9 11 10 01010 A 12 11 01011 B 13 12 01100 C 14 13 01101 D 15 



1.3 Operaciones básicas (Suma, Resta,Multiplicación, Divisió

Operaciones con números binarios[editar]
Suma de números binarios[editar]
La tabla de sumar para números binarios es la siguiente:
  +
  0
  1
  0
  0
  1
  1
  1
10
Las posibles combinaciones al sumar dos bits son:
  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 10
Note que al sumar 1 + 1 es 102, es decir, llevamos 1 a la siguiente posición de la izquierda (acarreo). Esto es equivalente en el sistema decimal a sumar 9 + 1, que da 10: cero en la posición que estamos sumando y un 1 de acarreo a la siguiente posición.
Ejemplo
        1
      10011000
    + 00010101
    ———————————
      10101101
Se puede convertir la operación binaria en una operación decimal, resolver la decimal, y después transformar el resultado en un (número) binario. Operamos como en el sistema decimal: comenzamos a sumar desde la derecha, en nuestro ejemplo, 1 + 1 = 10, entonces escribimos 0 en la fila del resultado y llevamos1 (este "1" se llama acarreo o arrastre). A continuación se suma el acarreo a la siguiente columna: 1 + 0 + 0 = 1, y seguimos hasta terminar todas las columnas (exactamente como en decimal).
Resta de números binarios[editar]
El algoritmo de la resta en sistema binario es el mismo que en el sistema decimal. Pero conviene repasar la operación de restar en decimal para comprender la operación binaria, que es más sencilla. Los términos que intervienen en la resta se llaman minuendo, sustraendo y diferencia.
Las restas básicas 0 - 0, 1 - 0 y 1 - 1 son evidentes:
  • 0 - 0 = 0
  • 1 - 0 = 1
  • 1 - 1 = 0
  • 0 - 1 = 1 (se transforma en 10 - 1 = 1) (en sistema decimal equivale a 2 - 1 = 1)
La resta 0 - 1 se resuelve igual que en el sistema decimal, tomando una unidad prestada de la posición siguiente: 0 - 1 = 1 y me llevo 1 (este valor se resta al resultado que obtenga, entre el minuendo y el sustraendo de la siguiente columna), lo que equivale a decir en el sistema decimal, 2 - 1 = 1.
Ejemplos
        10001                           11011001   
       -01010                          -10101011
                                  
       ——————                          —————————
        00111                           00101110
En sistema decimal sería: 17 - 10 = 7 y 217 - 171 = 46.
Para simplificar las restas y reducir la posibilidad de cometer errores hay varios métodos:
  • Dividir los números largos en grupos. En el siguiente ejemplo, vemos cómo se divide una resta larga en tres restas cortas:
        100110011101             1001     1001     1101
       -010101110010            -0101    -0111    -0010
       —————————————      =     —————    —————    —————
        010000101011             0100     0010     1011
  • Utilizando el complemento a dos (C2). La resta de dos números binarios puede obtenerse sumando al minuendo el «complemento a dos» del sustraendo.
Ejemplo
La siguiente resta, 91 - 46 = 45, en binario es:
        1011011                                             1011011
       -0101110       el C2 de 0101110 es 1010010          +1010010
       ————————                                            ————————
        0101101                                            10101101
En el resultado nos sobra un bit, que se desborda por la izquierda. Pero, como el número resultante no puede ser más largo que el minuendo, el bit sobrante se desprecia.
Un último ejemplo: vamos a restar 219 - 23 = 196, directamente y utilizando el complemento a dos:
        11011011                                            11011011
       -00010111       el C2 de 00010111 es 11101001       +11101001
       —————————                                           —————————
        11000100                                           111000100
Y, despreciando el bit que se desborda por la izquierda, llegamos al resultado correcto: 11000100 en binario, 196 en decimal.
  • Utilizando el complemento a uno. La resta de dos números binarios puede obtenerse sumando al minuendo el complemento a uno del sustraendo y a su vez sumarle el bit que se desborda.
Producto de números binarios[
La tabla de multiplicar para números binarios es la siguiente:
  ·
  0
  1
  0
  0
  0
  1
  0
  1
El algoritmo del producto en binario es igual que en números decimales; aunque se lleva a cabo con más sencillez, ya que el 0 multiplicado por cualquier número da 0, y el 1 es el elemento neutro del producto.
Por ejemplo, multipliquemos 10110 por 1001:
        10110      
         1001                   
    —————————         
        10110              
       00000               
      00000               
     10110               
    —————————          
     11000110
En sistemas electrónicos, donde suelen usarse números mayores, se utiliza el método llamado algoritmo de Booth.
                 11101111
                   111011
                __________
                 11101111
                11101111
               00000000
              11101111
             11101111
            11101111
           ______________
           11011100010101
División de números binarios[editar]
La división en binario es similar a la decimal; la única diferencia es que a la hora de hacer las restas, dentro de la división, éstas deben ser realizadas en binario.
Ejemplo
Dividir 100010010 (274) entre 1101 (13):
 100010010 /1101 = 010101
 -0000      
———————
 10001
 -1101
———————
  01000
 - 0000
 ———————
   10000
  - 1101
  ———————
    00111
   - 0000
   ———————
     01110
    - 1101
    ———————
     00001


SISTEMA OCTAL

(SUMA)

Este sistema solo puede trabajar con los números
1, 2, 3, 4, 5, 6, 7




LA RESTA DEL SISTEMA OCTAL






MULTIPLICACIÓN EN SISTEMA OCTAL




DIVISIÓN EN SISTEMA OCTAL


Operaciones en Sistema Hexadecimal

En el sistema hexadecimal, al igual que en el sistema decimal, binario y octal, se pueden hacer diversas operaciones matemáticas. Entre ellas se encuentra la resta entre dos números en sistema hexadecimal, la que se puede hacer con el método de complemento a 15 o también utilizando el complemento a 16. Además de éstas, debemos manejar adecuadamente la suma en sistema hexadecimal, explicada a continuación:

 

Hexadecimal
Decimal
A
10
B
11
C
12
D
13
E
14
F
15


Suma

·                     9 + 7 = 16 (16 – 16 = 0 y nos llevamos 1)
En este caso la respuesta obtenida, 16, no está entre el 0 y el 15, por lo que tenemos que restarle 16. Por lo tanto, la respuesta obtenida será 10 (sistema hexadecimal).
Hay que tener cuidado de utilizar correctamente las letras, ya que operar a la vez con letras y números puede crear confusiones.

·                     A + 6 = 16 (16 - 16 = 0 y nos llevamos 1)
Ocurre lo mismo que en el ejemplo anterior.

·                     A + A = 20 ( 20 – 16 = 4 y nos llevamos 1)
La respuesta es 20 y no está entre el 0 y el 15, por lo que tenemos que restarle 16. Por lo tanto, la respuesta obtenida será 14 (sistema hexadecimal).
Hay que tener cuidado de utilizar correctamente las letras, ya que operar a la vez con letras y números puede crear confusiones.

·                     F + E = 29 ( 29 – 16 =D y nos llevamos 1)
La respuesta es 29 y no está entre el 0 y el 15, por lo que tenemos que restarle 16. Por lo tanto, la respuesta obtenida será 1D (sistema hexadecimal).
Hay que tener cuidado de utilizar correctamente las letras, ya que operar a la vez con letras y números puede crear confusiones.
·                     Ahora haremos una operación más complicada:
·                     A + 2 = 12 (12 corresponde a C)
Ten en cuenta que puedes comprobar los resultados utilizando una calculadora científica.

Resta hexadecimal

Complemento C15

Podemos hacer la resta de dos números hexadecimales utilizando el complemento a 15. Para ello tendremos que sumar al minuendo el complemento a quince del sustraendo, y finalmente sumarle el bit de overflow (bit que se desborda).
Para entender la resta en complemento a 15 lo analizaremos con un ejemplo. Ésta es la resta que tenemos que resolver:
      A4FC9
    -   DE8
    —————————
     ¿?¿?¿?¿?
Primero tenemos que hacer que el minuendo y el sustraendo tengan la misma cantidad de números. Para ello, añadiremos ceros al sustraendo hasta que sean suficientes.
      A4FC9
    - 00DE8
    —————————
     ¿?¿?¿?¿?
Después, crearemos un nuevo número con la misma cantidad de números que el nuevo sustraendo. Como en el sistema hexadecimal el mayor número que tenemos es el 15, que corresponde a la letra F, tendremos que escribir la F tantas veces como números tiene el sustraendo.
      FFFFF
    - 00DE8
    —————————
      FF217
La resta se hace siguiendo las normas generales de la resta común. La diferencia obtenida se denomina el complemento a 15. Recuerda el valor correspondiente a cada letra al operar.
Ahora tendremos que sumar el minuendo y el complemento a 15 utilizando la suma en sistema hexadecimal, mencionada anteriormente.
      A4FC9
    + FF217
    —————————
     1A41E0
Con la suma obtenemos el resultado 1A41E0, pero no es la respuesta final. Te habrás dado cuenta que este nuevo número tiene más cifras que los números iniciales que teníamos que restar. Tenemos que quitar el número de la izquierda (en este caso, el 1) y sumarlo.
      A41E0
    +     1
    —————————
      A41E1
La respuesta es A41E1.