Apuntes de Matemática Discreta



Descargar 434.85 Kb.
Página1/3
Fecha de conversión26.06.2018
Tamaño434.85 Kb.
  1   2   3


www.monografias.com
Apuntes de Matemática Discreta


  1. Preposición, Tablas de verdad, Tautología y Contradicción

  2. Relación de pertenencia

  3. Conjunto de partes

  4. Partición

  5. Inducción matemática

  6. Sucesiones por recurrencia

  7. Reglas de divisibilidad

  8. Cambio de base

  9. Producto cartesiano

  10. Relaciones

  11. Funciones

  12. Relaciones definidas de un conjunto en si mismo

  13. Clausura de una relación

  14. Composición de funciones

  15. Relación de equivalencia

  16. Conjunto cociente

  17. Operaciones binarias

  18. Conjuntos ordenados

  19. Grupos

  20. Subgrupos

  21. Redes, subredes, átomos

  22. Lenguajes

  23. Autómatas finitos


LÓGICA Y CÁLCULO PROPORCIONAL:

Preposición: Cualquier frase susceptible de adquirir un valor de verdad. En general se compone de la siguiente manera: (SUJETO + VERBO + PREDICADO)
Tablas de verdad:

P

Q




PQ

PQ

PQ

PQ

PQ





















V

V

V

V

F

V

V

V

F

F

V

V

F

F

F

V

F

V

V

F

V

F

F

F

F

F

V

V


























Tautología: El valor de verdad de toda la columna es Verdadero.

Contradicción: El valor de verdad de toda la columna es Falso.

-----------------------------------------------

Tautología: ~Contradicción.

Contradicción: ~Tautología.



Si el antecedente de una implicación es Falso, el valor de verdad es Verdadero
Leyes de De Morgan:


P

Q




(PQ)









(~P  Q)






















V

V

V

V

V




V

F

F

V

F




F

V

V

V

V




F

F

V

V

V



























P

Q




~ (PQ)









~P  ~Q































V

V

F

V

V

F

F

F




V

F

F

V

V

F

F

V




F

V

F

V

V

V

F

F




F

F

V

F

V

V

V

V






























Cuantificadores:

Hay dos tipos:

El cuantificador Universal (“Para todo”) y el cuantificador existencial (“Existe”).

Hay proposiciones como por ejemplo: “5 > 2”; “X toma el mismo valor que Y”; “5²=20”; a las que podemos adjudicarle un valor de verdad (Verdadero o Falso), y hay expresiones que incluyen variables como x²+2x-3 = 0 que no podemos decir que sean proposiciones, puesto que si x=1 resulta verdadero, pero su x=0 entonces resulta falso.

Si decimos “ x: x²+2x-3= 0”, ahora si es una proposición y es falsa, puesto que podemos mostrar el contraejemplo, dándole a x el valor “0”.

La expresión: “ x / x²+2x-3 = 0” es también una proposición y en este caso es verdadera.
N


p1




V

F

V

p2

V

F

F

p3

V

F

V

p4

V

F

V







C

V

F

F



egación de los cuantificadores:
~ ( x: P(x) )   x: ~ P(x)

~ ( x: P(x) )  x: ~ P(x)


(p1, ^ p2 ^ p3 ^ p4)  C

Relación de pertenencia:

Se define de elemento a conjunto. A la izquierda del signo (pertenece) debe haber un elemento y a la derecha del signo un conjunto. Para que la expresión sea verdadera el elemento de la izquierda debe ser alguno de los elementos del conjunto de la derecha.

El (conjunto vacío) es el que no contiene ningún elemento.

 (cardinal) es la cantidad de elementos que posee un conjunto.


Sea A = {a; b}
  A FALSO

a  A VERDADERO

{a}  A FALSO

b  A FALSO

{b}  A VERDADERO



 = {x A ^ x A }

 = { }


  = 0


Inclusión: Igualdad:
A  B  x  A  x  B A = B  (A  B ^ B  A )


  A VERDADERO

a  A NO VÁLIDO

{a}  A VERDADERO

b  A NO VÁLIDO

{b}  A FALSO

{b}  A VERDADERO






A  B {x/x  A  x  B}

A  B {x/x  A ^ x  B}

A - B {x/x  A ^ x  B}

A  B (A  B) – (A  B)

à = {x  A }


CONJUNTO DE PARTES

Dado un conjunto A, llamamos P(A) (partes de A), a un conjunto cuyos elementos son todos los subconjuntos posibles del conjunto A.

El conjunto vacío es subconjunto trivial de cualquier conjunto, y el mismo conjunto A es subconjunto impropio de si mismo. Todos los otros subconjuntos se llaman propios. En nuestro caso:


 A = 3  P(A) = 8

A

En general:  P(A) = 2


Por este motivo el conjunto de partes se llama también Conjunto Potencia.

A =   = 0

P(A) {0;A}  = 2º = 1

A = {a}  = 1

P(A) {0;A}  = 2¹ = 2

Partición:

Dado un conjunto “A ” y otro conjunto “P”, cuyos elementos son a su vez conjuntos a los cuales llamamos Pi.


P = {P1, P2, P3, … Pn}
Decimos que P es una partición de A si se cumple que la intersección de dos elementos cualquiera de P es siempre el conjunto vacío; la unión de todos los elementos de P es el conjunto A. Por último, ningún elemento de P es el conjunto vacío.
Condiciones:

1º) Pi ^ Pj =  si i  j

n

2º) U Pi = A



i = 1

3º) Pi  0  i


Ejemplificación:

Sea A = {1,2,3,4,5,6}


P1 = {1,2,3,4; 5,6} Es partición

P2 = {2,4; 1,6; 3,5} Es partición


P3 = {1,3,5; 1,2,4,6}

No es partición puesto que no cumple con la primera condición: el elemento “1” se repite.


P4 = { ;2,4,5,6; 1,3}

No es partición puesto que no cumple con la tercera condición: el elemento “” no puede formar parte de una partición.


P5 = {1,3,5,7; 2,4,6}

No es partición puesto que no cumple con la segunda condición: el elemento “7” al conjunto A.

Si todos los conjuntos Py que son elementos de P tienen en el mismo cardinal, decimos que es una Partición Regular.
INDUCCIÓN MATEMÁTICA:

Quinto postulado de Peano:

Si [P1 es Verdadero y {Ph  P(h+1)} es verdadero]  Pn n  N



Sumatoria:

4

 (3i + 1) = 4+7+10+13 = 24



i=1
5

 (2i - 2) = -1+0+2+6+14+30 = 51

i=0
6

 (2i - 2) = -1+0+2+6+14+30+62 = 113

i=1
Ejemplificación:
n+1 k n

 3 = 3/2 (3 - 1)

k=2
1) n = 1

n+1 1 1


 3 = 3/2 (3 - 1)

k=2
3 = (3/2)  2


3 = 3

Dándole a “n” el valor de 1, la igualdad es válida.

2) Hipótesis:

n = h
h k h

 3 = 3/2 (3 - 1) Esto se considera válido siempre

k=2
3) Tesis:


n = h+1
h +1 k h+1

 3 = 3/2 (3 - 1) Este es el término al que se desea llegar

k=2
4) Demostración:
h k h h+1

 3 = 3/2 (3 - 1) + 3 Se copia la hipótesis y se agrega el término h+1

k=2 reemplazando “k” por “h+1”
Se comienza a igualar para llegar a la Tesis
h h+1

= 3/2 [(3 -1) + 2/3 * 3 ]

h h

= 3/2 [3 -1 + 2 * 3 ]



h

= 3/2 [3 * 3 - 1]

h+1

= 3/2 [3 + 1]


Finalmente, este término resulta idéntico a la Tesis y la igualdad queda demostrada.
Inducción completa en propiedades expresadas con una desigualdad:

Sea A  B una propiedad donde A es una función de n y B también.

Primero debemos probarlo para n=1 y si se cumple, por hipótesis

A (h)  B (h)

A (h+1)  B (h+1)

Para demostrarlo, partimos de A (h)  B (h) y hacemos lo necesario para transformar A(h) en A (h+1). Una vez que en el primer término tenemos A (h+1), aún haciendo todas las operaciones matemáticas posibles, difícilmente nos quede en el segundo término B (h+1). Generalmente lo que queda es la expresión A (h+1)  C(h). Entonces lo que debemos hacer es probar C(h)  B (h+1).

De ambas expresiones concluimos que por ser de orden transitivas A (h+1)  B (h+1).
SUCESIONES POR RECURRENCIA O RECURSIÓN:

an = 3an-1 + 2an-2 +5



El orden de una sucesión tiene que ver con la cantidad de términos anteriores que se utilizan. En el ejemplo tenemos una sucesión de 2º orden. El grado se relaciona con el exponente al que están elevados an - i. Por último, la sucesión es homogénea si no hay ningún término independiente. En el caso anterior es no homogénea.
Ejemplificación:


Expresión

Grado

Orden

Homogeneidad













an = 3an-1 - 2





No homogénea

an = a²n-1





Homogénea

an = 1-a³n-1





No homogénea

an = 4an-1 – 2a²n-2





Homogénea

an = a³n-2 + 1





No homogénea

an = an-1 + an-2+ an-3





Homogénea

an = 4an-5 + 2an-3 + an-1





Homogénea














Resolución de ecuaciones homogéneas de primer grado, segundo orden:

  1. Se pasan al primer miembro los términos an, an-1, an-2, los cuales también podrían figurar como an+2, an+1, an

  2. Se reemplaza an por r², an-1 por r y an-2 por 1, quedando una ecuación de segundo grado con raíces reales y distintas de r1 y r2.

n n

  1. Se plantea a = u · r1 + v · r2




  1. Debemos tener como dato los valores de los dos primeros términos de la sucesión:

A0 = k y A1 = k’. Utilizando estos datos ordenamos el sistema de 2x2: u + v = k y u·r1 + u·r2 = k’. La resolución de este sistema no da como resultado los valores u0 y v0, que son números reales conocidos.


n n

an = u0 · r1 + v0 · r2

e) la solución general es:




Ejemplificación:


1an - 2/3an-1 - 1/3an-2


r² -2/3r -1/3*1

an= 2/3an-1 +1/3an-2

a0 = 2 Esto es dato

a1= 5


Primero efectuamos el cambio de variable de la manera indicada
1

r² - 2/3 r - 1/3 = 0

-1/3
Aplicamos la fórmula para resolver ecuaciones cuadráticas.
Luego reemplazamos los valores de las raíces en la fórmula general:

n n


a = u · 1 + v · (-1/3)
Ahora debemos usar los datos que nos dieron par resolver el problema: El polinomio especializado en 0 da como resultado 2, y especializado en 1 da 5 (Ver llave al inicio del problema donde se aclara cuales son los datos). Por lo tanto podemos elaborar el siguiente sistema de ecuaciones:

u + v =2
u - 1/3 = 5

Resolviéndolo, obtenemos que:

v = -9/4


u = 17/4

Por último, escribimos la ecuación general, que en nuestro ejemplo es así:

n n

an = 17/4 · 1 + -9/4 · (-1/3)


REGLAS DE DIVISIBILIDAD:



  1. Si A·B = C, siendo A, B y C  Z, decimos que C es múltiplo de A, también de B, y A y B son divisores de C. Es decir, para que C sea múltiplo de A debe existir un B tal que A·B=C. para que A sea divisor de C debe existir un B tal que A·B = C




  1. 0 es múltiplo de cualquier número, porque  0  0 · A = 0




  1. 0 no es divisor de ningún número, puesto que A : 0 = ?  0 · ? = A




  1. 1 es divisor de cualquier entero, puesto que N : 1 = N




  1. 1 es múltiplo de 1 y -1







 D = d · c + r, siendor < d

7
Cociente por exceso:
D = d (c + 1) + r – d

D = dc + d + r – d

D = dc + r
)






27 = 4·6 + 3 27 = 4·7 - 1

Por defecto Por exceso

+

8) El conjunto de divisores de n está formado por todos los Z que lo dividen exactamente. Por ejemplo:


D6 = {1,2,3,6} D42 = {1,2,3,6,7,14,42} D13 = {1,13}
+

D0 = Z - {0} D1 = {1}


9) Decimos que un número es primo cuando tiene dos divisores: “1” y él mismo.

10) Decimos que un número es compuesto cuando tiene más de dos divisores, pero no infinitos.

11) El 0 y el 1 no son primos ni compuestos.

12) El teorema fundamental de la aritmética dice que cada número puede descomponerse en un producto único de factores primos. Por ejemplo:


6 = 2·3 42 = 2·3·4 13 = 13 36 = 2·2·3·3 = 2²·3²
Para abreviar la escritura usamos notación exponencial.

13) El Máximo Común Divisor (MCD) entre dos números es el mayor número que figura en el conjunto divisores de A  divisores de B. MCD(a,b) = (a, b)

Max (Da  Db)
14) El Mínimo Común Múltiplo (MCM) es el mínimo elemento perteneciente a la intersección de múltiplos de A y B. MCM(a,b) = [a,b] Min (Ma  Mb)
15) El MCM entre A y B = A·B

MCD (a,b)



Compartir con tus amigos:
  1   2   3


La base de datos está protegida por derechos de autor ©composi.info 2017
enviar mensaje

    Página principal