Matematica discreta universidad salesiana de bolivia ing. De sistemas



Descargar 2,9 Mb.
Página8/38
Fecha de conversión02.07.2017
Tamaño2,9 Mb.
1   ...   4   5   6   7   8   9   10   11   ...   38

2.7 Producto cartesiano de conjuntos


Un par ordenado de números es tal si los pares y son uno mismo si y sólo si .

Dados dos conjuntos y , definimos al conjunto producto ( o producto cartesiano) de y (en ese orden), representado por , como el conjunto

Ejemplo


Sean y . Así,

Ya que el producto cartesiano está formado de pares ordenados (donde el orden de los componentes importa), resulta:




2.8 Cuantificadores


Los cuantificadores sirven para indicar cuantos elementos de un conjunto dado cumplen con cierta propiedad. Tales cuantificadores son

  • El cuantificador universal, representado por . Este cuantificador se emplea para afirmar que todos los elementos de un conjunto cumplen con determinada propiedad. Se escribe



  • El cuantificador existencial se usa para indicar que al menos un elemento de un conjunto cumple con una propiedad. Se escribe

.

Se definen






Funciones


Artículo principal: Función matemática

Sean y dos conjuntos. Un subconjunto , se dice aplicación o función de en , lo que se representa por

siempre que se verifique








Si , el elemento se dice imagen de por , y el elemento se llama antecedente de por .

Sea una función . Se emplea la notación para representar a la imagen de por , y por tanto .

Sean las funciones   y   . Se define

,

y se dice que es el producto de composición de las funciones y .

Vemos que

y

por lo que


RELACION ENTRE LA TEORIA DE CONJUNTOS Y LA LOGICA PROPOSICIONAL

Existe una relación muy estrecha entre la Teoría de Conjuntos y la Lógica Proposicional.


Para mostrar dicha relación, denotemos por letras mayúsculas A,B ... los conjuntos y
por las correspondientes minúsculas a,b ... sus propiedades características
(es decir, la proposición lógica que caracteriza a los elementos de cada conjunto);
entonces se tiene la siguiente correspondencia:


conjuntos

A  B

A = B

A  B

A  B

A'

A  B

A  B

proposiciones

a  b

a b

a  b

a  b

a'

a  b'

a b

 
Además, el conjunto vacío se corresponde con una contradicción y el conjunto universal con una tautología.
Mediante esta correspondencia, todos los resultados sobre conjuntos se pueden reescribir en términos de lógica proposicional y viceversa; a modo de ejemplo:
 

 


A  ( A  B ) = A

a  ( b  c )  a

A  ( B  C ) = ( A  B )  ( A  C )

a  ( b  c )  ( a  b )  ( a  c )

( A  B )' = A'  B'

( a  b )'  a'  b'


TEMA: 3

Números Enteros - Inducción Matemática - Divisibilidad

Uno de los métodos de demostración de más importancia en matemáticas es el llamado de inducción completa o matemática que se utiliza generalmente para demostrar algunas fórmulas o teoremas matemáticos.



3.1 Principio de Inducción Matemática

3.1.1 Conjuntos Inductivos.

Intuitivamente se obtienen los enteros positivos, tomando como punto de partida un primero designado por "1" y formando 1 + 1 (llamado "2"), 2 + 1 (llamado "3"), y así sucesivamente.

En virtud de que no se puede depender del significado un poco oscuro de "y así sucesivamente" y de que se debe tener una base para proporcionar teoremas relativos a los enteros positivos, se da una definición del conjunto de los naturales, basada en el concepto de conjunto inductivo.
3.1.2 Definición. Un conjunto S de números es un conjunto inductivo sí y sólo sí S tiene las siguientes propiedades:

Ejemplo:

El conjunto de los números naturales es un conjunto inductivo.


Ejemplo:

El conjunto de los números Reales es un conjunto inductivo.


Ejemplo:

El conjunto  S1 = {1, 3, 5, 7, ...} no es un conjunto inductivo, porque no obstante que 

1 S1; (1+1)S1.

El conjunto  N es el conjunto de números con la propiedad de que si k es cualquier conjunto inductivo de números, entonces N k. Se dice a veces, que el conjunto de los números naturales, es el "más pequeño" conjunto inductivo de números.


3.2 Teorema fundamental de Inducción Matemática.

Sea Sn una función proposicional cuyo conjunto de referencia es N. Si Sn satisface las siguientes dos condiciones:



Entonces Sn es cierta para todo n N.

La condición S1 se le llama el Paso base y a la condición Sk; S k+1 se le llama Paso inductivo. A partir de este momento, " inducción" significara para nosotros " inducción matemática".


Demostración
Sea k el conjunto de todos los números naturales para el cual Sn es cierta. Es decir:

De i) se observa que 1 k.



De ii) se observa que  k k (k + 1)k.

Por tanto k es un conjunto inductivo y por la definición de k se sabe que k N.

De otra parte  N k. Por consiguiente  N = k, es decir Sn es cierta para todo n N. Ejemplo:

Demuestre que:


1 + 3 + 5 +................+ (2n - 1) = n².


  1. Probamos P(1):

(2*1 - 1) = 1²

1 = 1 


  1. Reemplazamos n = k:

1 + 3 + 5 +................+ (2k - 1) = k²




  1. Reemplazamos n = k+1:

1 + 3 + 5 +................+ [2(k+1) - 1] = (k+1)²

1 + 3 + 5 +................+ (2k + 1) = (k+1)²


  1. Llevamos el último término de P(k+1) y lo sumamos a P(k):

1 + 3 + 5 +................+ (2k - 1) = k² / + (2k + 1)

1 + 3 + 5 +.............+ (2k - 1) + (2k + 1) = k² + (2k + 1)

1 + 3 + 5 +.............+ (2k - 1) + (2k + 1) = (k+1)² 

Podemos determinar entonces que la fórmula es cierta y que se verifica para todos los valores de n, entero y positivo.

Ejemplo:

Demostrar que A2n - B2n es divisible por A + B, siendo n un número cualquiera entero y positivo.




  1. El teorema se cumple para n = 1, ya que A2 - B2 = (A + B)(A - B)

2. Supongamos que es cierto para n = k, entonces


A2k - B2k es divisible por A + B
3. Reemplazamos k+1 en n de manera que n = k+1:
A2( k + 1) - B2( k + 1) es divisible por A + B

A2 k + 2 - B2 k + 2 es divisible por A + B

A2 k + 2 - B2 k + 2 = A2(A2k – B2k) + B2k(A2 - B2)

Se deduce que A2k+2 - B2k+2 es divisible por A + B si lo es A2k - B2k.


Ejemplo:
Supongamos que deseamos probar la igualdad siguiente:
n

 (2k – 1) = n2

k=1

suma de los primeros n términos impares


n

 = 1 + 3 + 5 +......... + (2k – 1)

k=1

1

n = 1  (2*1 – 1) = 1 ^ 12 =1



k=1
2

n = 2  (2k – 1) = 1 + 3 = 4 ^ 22 = 4

k=1
3



n = 3  (2k – 1) = 1 + 3 + 5 = 9 ^ 32 = 9

k=1


En la expresión anterior podemos ir tomando y verificando con todos los valores de k, que la igualdad se cumple, pero esto no es una demostración válida. Para demostrar la validez de lo anterior, ocuparemos el principio de inducción matemática, que establece lo siguiente:

“Si una proposición q, expresada en términos de una variable k, cumple los siguientes pasos”:


1. es verdadera para k = 1

2. es verdadera para k = p

3. debera ser verdadera o válida para k = p + 1.
Si la proposición q cumple estos tres pasos, entonces siempre será válida.

Demostrar que:

n

 (2k – 1) = n2



k=1
Demostración:

1.- se demuestra para k=1

1

K=1  (2k – 1) = 1 ^ 12 = 1



k=1

2.- suponemos que se cumple esta igualdad para k=p

p

K= p  (2p – 1) = p2



k=1
p+1

3. deberá cumplirse  [2 (p + 1) – 1] = (p + 1)2

k=1
Aplicación p

 (2k – 1) = p2

k=1
1 + 3 + 5 +...................+ (2k – 1) = p2 / + [2 (p + 1) – 1]
1 + 3 + 5 +.........+ (2k – 1) + [2 (p + 1) – 1] = p2 + [2 (p + 1) – 1]

1 + 3 + 5 +..............+ (2k – 1) + (2 p +1) = p2 + (2 p + 1)

p+1

 [2 (p + 1) – 1] = (p + 1)2



k=1

Ejemplo:

Utilice la inducción matemática para demostrar que es divisible entre 4 para toda n = 1,2,.....

Si n = 1:

, que es divisible entre 4.

Supongamos que es divisible entre 4. Deberemos demostrar que es divisible entre 4. Ahora entonces para relacionar el caso (n +1) con el caso n, escribimos



 

Por hipótesis , es divisible entre 4 y como es divisible entre 4 , la suma



es divisible entre 4. Ahora como hemos verificado ya el paso base y el paso inductivo, el principio de inducción matemática nos dice que es divisible entre 4 para n = 1,2,....



Otros ejemplos:

Demuestre por el método de Inducción Matemática, cada una de las siguientes proposiciones:


a.- 3 + 6 + 9 +........ + 3n = 3 n (n + 1)

2

P(1): 3*1 = 3 * 1 (1+1)

2

3 = 3* (2)



2

3 = 3 
Entonces, p(1) es Verdadero.


P(k): 3 + 6 + 9 +............+ 3k = 3k (k + 1)

2

P(k+1): 3 + 6 + 9 +............+ 3(k+1) = 3 (k+1) (k+1+1)



2

3 + 6 + 9 +............+ 3(k+1) = 3 (k+1) (k+2)

2

P(k): 3 + 6 + 9 +.........+ 3k = 3k (k + 1) /+ 3(k+1)



2

3 + 6 + 9 +........+3K + 3 (k+1) = 3k (k + 1) +3(k+1)

2

= 3k² + 3k + 3k +3



2 2

= 3k² +9k +3

2 2

= 3 ( k2 +3k+2)



2

= 3 (k+1)(k+2) 

2
Entonces, es Verdadero, debido a que se llegó al último resultado de p(k+1).

b.- 1² + 3² +..........+ (2n - 1)² = 1n (2n -1) (2n +1)

3
P(1): (2*1 - 1)² = 1 *1 (2*1 -1) (2*1 +1)

3

(2 - 1)² = 1 (2 -1) (2 +1)



3
(1)² = 1 (1) (3)

3
1 = 1 


P(1) es Verdadero.

P(k): 1² + 3² +..........+ (2k - 1)² = 1 k (2k -1) (2k +1)

3

P(k+1): 1² + 3² +..........+ (2 (k+1) - 1)² = 1 (k+1)(2(k+1)-1) (2(k +1)+1)



3
1² + 3² +..........+ (2 (k+1) - 1)² = (1k+1) (2k+2-1) (2k +2+1)

3

1² + 3² +..........+ (2 (k+1) - 1)² = (1k+1) (2k+1) (2k+3)



3

1² + 3² +..........+ (2 k+2 - 1)² = (1k+1) ( 4k2 +6k+2k+3)

3
1² + 3² +..........+ (2 k +1 )² = 1 (k+1) ( 4k2 +8k+3)

3

1² + 3² +..........+ (2 k +1 )² = 1 [ 4k3 +12k2+11k+3 ]



3

1² + 3² +..........+ (2 k +1 )² = 4 k3 + 4k2 +11k +1

3
P(k): 1² + 3² +..........+ (2k - 1)² = 1 k (2k -1) (2k +1) /+(2k+1)2

3
1² + 3² +.....+ (2k -1)² + (2k+1)2 = 1 k (2k -1) (2k +1) + (2k+1)2

3

= k (4k2-1) + 4k2 +4k +1



3
= 4 k3 - k + 4k2 + 4k + 1

3
= 4 k3 + 4k2 +11k +1 

3

c.- 13 + 33 + ........... + ( 2n - 1)3 = n2 (2n2 - 1)
P(1): [( 2 * 1) - 1]3 = 12 [(2 * 12 )- 1]
( 2 - 1)3 = 1[ (2 * 1) - 1]
( 1)3 = 1 (2 - 1)
1 = 1 

P(k): 13 + 33 + ........ + ( 2k - 1)3 = k2 (2k2 - 1)


P(k+1): 13 + 33 + ... + ( 2 (k +1) - 1)3 = (k + 1 )2 (2 ( k +1 )2 - 1)

P(k+1): 13 + 33 + ... + ( 2 (k +1) - 1)3 = (k2 + 2k + 1 ) (2 ( k2 +2k + 1 ) - 1)


P(k+1): 13 + 33 + ... + ( 2 (k +1) - 1)3 = (k2 + 2k + 1 ) ( 2k2 +4k + 2 - 1 )
P(k+1): 13 + 33 + ... + ( 2 (k +1) - 1)3 = 2k4+ 8k3 + 11k2 + 6 k + 1

P(k): 13 + 33 + ....... + ( 2k - 1)3 = k2 (2k2 - 1) / + ( 2k + 1 )3


= k2 (2k2 - 1) + ( 2k + 1 )3
= 2k 4- k 2 +8k3 +12k2+6k +1
= 2k4 + 8k3 +11k2 + 6k +1 


d.- 13 + 23 + 33 + .......... + n 3 = 1 n2 ( n + 1 ) 2

4
P(1): 1 3 = 1 * 12 ( 1 + 1 ) 2

4
1 = 1 ( 2 ) 2

4
1 = 1 * 4

4

1 = 1 

P(k): 13 + 23 + 33 + .............. + k3 = 1 k2 ( k + 1 ) 2  Hipótesis

4


13 +23 + 33 + ..... + k3 + ( k + 1 ) 3 = 1 (k + 1 )2 ( k + 1 )2

4
Hipótesis

1 k2 (k + 1 )2 + ( k + 1 )3 =

4

( k +1 )2 [ 1 k2 + k + 1 ] =


( k + 1 )2 [ k2 + 4k + 4 ] =

4
( k + 1 )2 [ ( k + 2 )2 ] =

4
1 ( k + 1 )2 ( k + 2 )2 = 

4

e.- 3n + 5 divisible por 2


k = 1 31 + 5 = 3 + 5 = 8 / : 2 = 4

k =2 32 + 5 = 9 + 5 = 14 / : 2 = 7

k =p 3 p + 5 = 2 q

3 p + 5 = 2 q / * 3

3 ( 3 p + 5 ) = 6 q

3 p+1 + 15 = 6 q

3 p+1 + 5 = 6q - 10
3 p+1 + 5 = 2 ( 3q – 5 )

2
3 p+1 + 5 = 3q – 5 //

k = p + 1 3p+1 + 5 = 2q 


n

f.- k (k + 1) = n (n + 1) (n + 2)

k=1 3

1

Si k=1  k (k + 1) = 1 (1 + 1) (1 + 2)

k=1 3

= 2.


p

Si k=p  k (k + 1) = p (p + 1) (p + 2)

k=1 3

p+1

Si k=p+1  = (p + 1) (p + 2) (p + 3)

k=1 3
2 + 6 +1 +........ +p (p + 1)(p + 1)(p + 2) = p (p + 1) (p + 2) + (p + 1)(p + 2)

3
p+1

 k (k + 1) = (p + 1) (p + 2) (p + 3) 

k=1 3

1   ...   4   5   6   7   8   9   10   11   ...   38


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal