Respuestas Unidad 2

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 10

Matemática Discreta Guía de ejercicios

RESPUESTAS UNIDAD 2:

PARTE I: CONJUNTOS

Ej.1)

a) A = { -3, -2, -1, 0, 1, 2, 3 } B = { -1, 0, 1, 2, 3, 4, 5 } C = { 1, 2, 4, 8 }


b) A  B = {-1, 0, 1, 2, 3 } , A  C = { 1, 2 } ,
B  C = { 1, 2, 4 }, A  B  C = { 1, 2}
c) A  B = { -3, -2, -1, 0, 1, 2, 3, 4, 5 } A  C = { -3, -2, -1, 0, 1, 2, 3, 4, 8 }
B  C = { -1, 0, 1, 2, 3, 4, 5, 8 } A  B  C = { -3, -2, -1, 0, 1, 2, 3, 4, 5, 8 }
d) A – B = { -3, -2 } B – A = { 4, 5 } A – C = { -3, -2, -1, 0, 3 }
C –A = { 4, 8 } B –C = { -1, 0, 3, 5 } C–B={8}
e) U = { x  Z / │ x │  8 } = { -8,-7,-6,-5,-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8 }
A = { -8,-7,-6,-5,-4, 4, 5, 6, 7, 8 } B = { -8,-7,-6,-5,-4, -3, -2, 6, 7, 8 }
C = { -8,-7,-6,-5,-4, -3, -2, -1, 0, 3, 5, 6, 7 }
f) Diagrama de Venn:

Ej.2)
a) FALSO j) VERDADERO
b) FALSO k) FALSO
c) VERDADERO l) FALSO
d) FALSO m) FALSO
e) VERDADERO n) VERDADERO
f) FALSO o) FALSO
g) VERDADERO
h) VERDADERO
i) VERDADERO

Ing. María Alicia Piñeiro Pág. 18


Matemática Discreta Guía de ejercicios

Ej.3)
a) Los que aprobaron únicamente matemática
son 280.

b) b.1) Los que leen solo ciencia ficción son 10.


b.2) Los que no leen ninguno de los tres géneros son 10.
b.3) Los que leen por lo menos dos géneros distintos son 13.
b.4) Los que leen novelas y cuentos pero no ciencia ficción son 5.

c) c.1) 28 personas consumen solo bombones


c.2) 56 personas consumen alfajores y
bombones
c.3) Ninguna persona consume solo alfajores
c.4) 20 personas consumen alfajores y
cupcakes pero no bombones
c.5) 30 personas no consumen ninguno de los
tres productos

Ing. María Alicia Piñeiro Pág. 2


Matemática Discreta Guía de ejercicios

Ej.4) Hay muchos ejemplos, aquí mostramos solo uno de cada uno:

a) A = { x  |R / x > 2 } y B=Z
b) A = { x  Z / x > 4 } y B={xZ/ x9}
c) A = { x  Z / x es par } y B = Z  AB y B – A = { x  Z / x es impar }
d) A = { x  Z / │x│ 3 } y B = Z  A  B y B – A = { -2, -1, 0, 1, 2 }

Ej.5)
a) P(A) = {  , {1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4},{1,2,3},
{1,2,4}, {1,3,4}, {2,3, 4}, {1,2,3, 4} }

b) Por ejemplo:   {1}  {1,2}  {1,2,3}  {1,2,3, 4}

c) El complemento de cada X se halla X = A – X , por ejemplo el complemento de {3} es


{1,2,4}, el de {2,4} es {1,3}, etc.

d) Hay cuatro intersecciones posibles con B:  , {1}, {3} o {1,3}

Quedan agrupados en cuatro clases:

1) Los que su intersección con B es  :  , {2}, {4}, {2,4}

2) Los que su intersección con B es {1} : {1} , {1,2}, {1,4}, {1,2,4}

3) Los que su intersección con B es {3} : {3} , {2,3}, {3,4}, {2,3,4}

4) Los que su intersección con B es {1,3} : {1,3} , {1,2,3}, {1,3,4}, {1,2,3,4}

Ej.6) Puede haber varias formas correctas de demostrar los ejercicios, en este caso
mostramos una de ellas para cada ítem, pero si has hecho otra, consulta con tus docentes
para saber si es correcta. En las formas que te mostramos, trata de justificar cada paso con
alguna definición o propiedad conocida:

a)  x: x  ( A  B)  x  A  x  B 
xA

Ing. María Alicia Piñeiro Pág. 3


Matemática Discreta Guía de ejercicios

b)  x: x  ( A  B )  C  x  ( A  B )  x  C 
[xAxB]xC
(xA xC)(xBxC)
 x  ( A  C )  x  (B  C) 
 x  ( A  C )  ( B  C)

c)  x: x  [ A  ( A  B )]  x  A  x  ( A  B )  x  A  [x  A  x  B ]  x  A

d)  x: x  ( X  Y ) U ( Y - X ) 
 x(XY)x(Y-X) 
 [xX xY] [xY xX]
 xY [xXxX]
x  Y  V x  Y

e)  x: x  X Y  x X  x Y  ~ ( x  X )  ~ ( x  Y) 

 ~ ( x  X  x  Y )  ~ ( x  X  Y )  x  XUY

f)  x: x  A – ( B  C )  x  A  ~ [ x  (B  C) ] 
xA  ~[xBxC]  xA  [xBxC] 
 [ x  A  x  B ]  [ x  A  x  C ]  x  ( A – B)  x  ( A – C ) 
x (A–B)(A–C)

Ing. María Alicia Piñeiro Pág. 4


Matemática Discreta Guía de ejercicios

Ej.7) Al igual que en los ejercicios anteriores, puede haber muchas formas de demostrar
estos ejercicios, por eso puedes consultar con tus docentes para saber si lo has hecho bien.
Lo que te recuerdo es que cuando tenemos condicionales, consideramos verdadera la
hipótesis o antecedente, y debemos demostrar la tesis o consecuente. Pero nunca podemos
asumir la tesis verdadera antes de probarla!!! Te mostramos una forma de demostrar cada
una, lo que falta es justificar cada paso con la definición o propiedad usada.

a) HIP) A  C  B  D
TESIS) A U B  C U D
DEM)  x: x  A U B  x  A  x  B  x  C  x  D  x  C U D

b) HIP) ( A – B ) U ( A  B ) = B
TESIS) B  A
DEM)  x: x  B  x  ( A – B ) U ( A  B )  x  ( A – B )  x  ( A  B ) 
[xAxB] [xAxB]  xA  [xB xB ]xA

c) HIP) A =C  ( B U C)
TESIS) A  B
DEM)  x: x  A  x C  ( B U C)  x C  x  ( B U C) 
 x C  [ x  B x  C ]  [ x C  x  B ]  [ x C x  C ] 
 [ x C  x  B ] F  [ x C  x B ]  x  B

Ing. María Alicia Piñeiro Pág. 5


Matemática Discreta Guía de ejercicios

d) PRIMER CONDICIONAL: HIP) Y  X


TESIS) X  Y = 
DEM)  x: x  X  Y  x X  x  Y 
Por HIP  x X  x  X  x X  X 

x  X  Y   (1)

Y la otra es trivial:  X  Y (2)


Por lo tanto, se cumple la igualdad: X  Y = 
SEGUNDO CONDICIONAL: HIP) X  Y = 
TESIS) Y  X
DEM)  x: x  Y  x  Y  V
 xY  [xXxX]
 x  Y  [ x  X  x X ] 
 [ x  Y  x  X ]  [ x  Y  x X ]
 [ x  Y  x  X ]  [ x X  x  Y ] 
 [ x  Y  x  X ]  [ x X  Y ] 
 [ x  Y  x  X ]  [ x  ] 
 [xY xX] F 
 xY xX  xX

e) En este caso que también es un bicondicional, vamos a demostrar en forma


conjuntista, que es otra forma correcta. Partimos de la primer igualdad y vamos
aplicando propiedades en ambos miembros:

A UB = B  ( A UB )  B = B  B  ( A  B ) U (B  B ) =  


 (AB)U = A B=

Ej.8) Para este ejercicio que también puede demostrarse de varias formas, lo que hay que
tener en claro es la definición de partes de un conjunto, que es el conjunto formado por todos
los subconjuntos de dicho conjunto:

a)  X: X  P(A  B )  XAB XA  XB


 X  P(A)  X  P(B)  X  P(A)  P(B)

Ing. María Alicia Piñeiro Pág. 6


Matemática Discreta Guía de ejercicios

b)  X: X  P(A)  P(B )  X  P(A)  X  P(B)  X  A  X  B 


 X  A  B  X  P(A  B)
Notar que un paso es solo valido de ida y no de vuelta, por eso solo se cumple esta
inclusión y no la igualdad. Se puede dar contraejemplo de la otra inclusión.

c) Para probar este ejercicio, una de las formas es por métodos de conteo:

Si │A│= n, los subconjuntos de A pueden tener hasta n elementos, vamos a ir


considerando en orden de cardinal:

Subconjuntos de 0 elementos: solo el 

Subconjuntos de 1 elementos: tantos como elementos, o sea n

n
Subconjuntos de 2 elementos: tantos como formas de elegir 2 de un total de n:  
2

n
Subconjuntos de 3 elementos: tantos como formas de elegir 3 de un total de n:  
3

n
En general, subconjuntos de h elementos hay:  
h

 n  n  n n
Y ahora debemos sumar todos:   +   +   +…+  
 0  1   2  n

Esta suma por Binomio de Newton es igual a: (1 + 1)n = 2n  │P(A)│= 2n

Sino también, podemos probarla por Inducción. Te proponemos que lo hagas luego de
estudiar ese tema.

PRODUCTO CARTESIANO

Ej.9) Halle A X B y B X A en los siguientes casos. ¿Son iguales?

a) A X B = { (0;0) , (0;1) , (1;0) , (1;1) , (2;0) , (2;1) , (3;0) , (3;1) }


B X A = { (0;0) , (0;1) , (0;2) , (0;3) , (1;0) , (1;1) , (1;2) , (1;3) }
No son iguales. Tampoco son disjuntos.
b) A X B =  y BXA= Son iguales.
c) A X B = { (q0; x), (q0; y), (q0; z), (q1; x), (q1; y), (q1; z), (q2; x), (q2; y), (q2; z) }
B X A = { (x; q0), (x; q1), (x; q2), (y; q0), (y; q1), (y; q2), (z; q0), (z; q1), (z; q2) }

Ing. María Alicia Piñeiro Pág. 7


Matemática Discreta Guía de ejercicios

No son iguales, son disjuntos.


d) A X B = { (x; 0) / x  N } y B X A = { (0; x) / x  N }
No son iguales, son disjuntos.
e) A X B = { (x;y) / x  Z  y  Z } B X A = { (x;y) / x  Z  y  Z }
Son iguales.

Ej.10)

a) FALSO. Dar contraejemplo


b) VERDADERO. Demostrar en forma genérica
c) VERDADERO. Demostrar en forma genérica
d) FALSO. Dar contraejemplo con uno solo 
e) FALSO. Dar contraejemplo con B = 

PARTE II: INDUCCION

Ej.11) a) S1 = 20 = 1 S2 : 20 + 21 = 3 S3 = 20 + 21 + 22 = 7 S4 = 20 + 21 + 22 +23 = 15

b) Al sumar las primeras n potencias de 2, obtenemos de resultado: 2n+1 - 1


Es decir  n  N0 : 20 + 21 + 22 + … + 2n = 2n+1 - 1
c) Demostración por Inducción Completa.

Paso base: n= 0: 20 = 1  20+1 – 1 = 2 – 1 = 1 p(0) es V


Paso inductivo: HIP IND) 20 + 21 + 22 + … + 2h = 2h+1 – 1
TESIS IND) 20 + 21 + 22 + … + 2h + 2h+1 = 2h+2 – 1
DEM) Partiendo del primer miembro de la tesis inductiva, trataremos de llegar al segundo:

20 + 21 + 22 + … + 2h + 2h+1 = asociativa ( 20 + 21 + 22 + … + 2h ) + 2h+1 =

= HIP IND
( 2h+1 – 1) + 2h+1 = CONMUT Y ASOC
( 2h+1 + 2h+1 ) - 1 = 2 • 2h+1 - 1 =

= PROD POTENCIA IGUAL BASE


2h+2 – 1 LLEGAMOS AL SEGUNDO MIEMBRO!!!

Ing. María Alicia Piñeiro Pág. 8


Matemática Discreta Guía de ejercicios

Ej.12) Hay varias formas de demostrar, pero recuerda que nunca debes considerar la tesis
verdadera hasta haberlo probado. Guíate por el ejercicio anterior y trata de hacerlo, cualquier
duda puedes consultar a tus docentes.

Ej.13) Demostraremos una para que tengas de ejemplo, intenta las otras. Cualquier duda
consulta a tus docentes.

d)  n  |N  n  3 : (2n)! > 8n-1 n2


Paso base: n = 3:
p(1): (2  3)! > 83-1  32
Veamos si p(1) es verdadera, calcularemos los dos miembros:
Primer miembro de p(1): (2  3)! = 6! = 720
Segundo miembro de p(1): 83-1  32 = 64  9 = 576
Como 720  576, entonces v [p(1)] = V

Paso inductivo:
Hip. Ind.: n=h (2h)! > 8h-1 h2
Tesis Ind: n = h+1 (2(h+1))! > 8h (h+1)2

Dem.) Para demostrar la tesis, partimos del primer miembro de la misma y trataremos de
probar que es mayor que el segundo.
(2(h+1))! = (2h + 2)! =(1) (2h+2) (2h+1) (2h)! (2) (4h2 + 6 h + 2)  8h-1 h2 (3)
(3) (h2 + 2 h + 1) 8h  8-1  h2 >(4) 8h (h+1)2  8-1  h2 >(5) 8h (h+1)2

Con lo cual quedó demostrado que: 2(h+1))! > 8h (h+1)2

Justificaciones de cada paso:

(1) Usamos la definición recursiva de factorial


(2) Distribuimos el producto de (2h+2)(2h+1) y utilizamos la hipótesis inductiva
(3) Acotamos la expresión (4h2 + 6 h + 2) por una expresión menor (h2+ 2 h + 1) ya que resulta conveniente
para lo que debemos probar
(4) Escribimos el cuadrado de una suma que teníamos desarrollado
(5) Dado que como h  3 entonces h2  9 y como 9 > 8 por lo tanto h2  8

Ing. María Alicia Piñeiro Pág. 9


Matemática Discreta Guía de ejercicios

Ej.14) Demostraremos una para que tengas de ejemplo, intenta hacer las otras. Cualquier
duda consulta a tus docentes.
a)  n  |N: 23n - 18n = 5 k con k  Z
Paso base: n =1: 231 – 181 = 5 = 5  1  1Z Entonces p(1) es verdadera
Paso inductivo:
Hip. Ind: 23h – 18h = 5 k ,kZ
Tesis Ind: 23h+1 – 18h+1 = 5 t , t  Z (observar que no debe ser el mismo entero)

Dem.) 23h+1 – 18h+1 = 23h  23 – 18h  18 = 23h  ( 5 + 18 ) – 18h  18 =

= 5  23h + 18  ( 23h – 18h ) = 5  23h + 18  5 k = 5  (23h + 18 k ) = 5 t

Pues 23h + 18 k  Z por ser productos y suma de enteros.

Por lo tanto, por principio de inducción,  n  N se cumple p(n) es verdadera

Ej.15) Al igual que en los ejercicios anteriores demostraremos una para que tengas de
referencia y te queda la otra para intentar.
n n
a) A i  B =  ( A  B)
i lo podemos escribir de esta forma, para poder interpretarlo
i 1 i 1

mejor: (A1  A2  ….  An )  B = (A1  B )  (A2  B )  …  (An  B )

Ahora lo vamos a demostrar:

Paso base: n =1: A1  B = A 1  B Entonces p(1) es verdadera

Paso inductivo:

Hip. Ind: (A1  A2  ….  Ah )  B = (A1  B )  (A2  B )  …  (Ah  B )


Tesis Ind: (A1  A2  ….  Ah+1 )  B = (A1  B )  (A2  B )  …  (Ah+1  B )

Dem.) Partimos del primer miembro de La tesis:


(A1  A2  ….  Ah+1 )  B = [ (A1  A2  ….  Ah )  Ah+1 ]  B =
Distribuyendo: = [ (A1  A2  ….  Ah )  B ]  ( Ah+1  B ) =
Por hip. Ind. = [ (A1  B )  (A2  B )  …  (Ah  B ) ]  ( Ah+1  B ) =
Por asociativa: (A1  B )  (A2  B )  …  (Ah+1  B )
LLEGAMOS AL SEGUNDO MIEMBRO!!!

Ing. María Alicia Piñeiro Pág. 10

También podría gustarte