Parciales inet 2010 con solucion montevideo matematica x edu






























































































































Profesorado de Informática - Ciencias de la Computación - INET – DFPD
Matemática Discreta usando el computador 2010 (Matemática I)
Matemática I

Primera Prueba Parcial

16 de julio de 2010
"INTENTO DE RESOLUCIÓN"
Ejercicio 1
(
)
a) Dados tres conjuntos A, B y C, demuestra que: A ∪ ( B ∩ C ) = C ∪ B ∩ A .
(
A∪(B ∩C) = A∩(B ∩C) = A∩ B ∪C
demostración:
aplicando
"De Morgan"
) y aplicando prop. conmutativa, lqqd.
aplicando otra
vez "De Morgan"
b) Analizar la veracidad de la siguiente afirmación: “Dados dos conjuntos distintos A y B, si
( A − B)
y
( B − A)
son finitos, entonces
Viendo estos dibujos "parece que" la unión de
( A ∩ B) ∩ ( A ∪ B)
( A − B)
y
( B − A)
es finito”. Justifique su respuesta.-
es igual a ( A ∩ B ) ∩ ( A ∪ B ) .
Si fueran iguales, entonces como ambos son finitos, la union de dos conjuntos finitos es finita.
Solo falta probarlo, porque los dibujitos no sirve como prueba.
Vamos a demostrarlo con una tabla de verdad.
Completarla !!
Ejercicio 2
a) Dado un conjunto A, definimos R ⊆ AxA tal que R es de orden parcial. Investigar si R y R
son también relaciones de orden parcial. ¿Qué ocurre si R fuese de orden total?. Justificar.-
Resolución: Si R es de orden parcial, es reflexiva, entonces
de orden parcial, ni de orden total.
−1
R es irreflexiva; entonces no puede ser
R −1 : Si R es reflexiva, R −1 también, por lo siguiente.
( a, b) ∈ R ⇒ (b, a ) ∈ R −1; (a, a ) ∈ R ⇒ ( a, a ) ∈ R −1
Veamos ahora
Si
Profesores: Saúl Tenenbaum y Germán Ferrari
http://www.x.edu.uy/ - http://matematicagerman.blogspot.com/
Página 1 de 1
Profesorado de Informática - Ciencias de la Computación - INET – DFPD
Matemática Discreta usando el computador 2010 (Matemática I)
Si R es antisimétrica, entonces
R −1
tambien:
Si a ≠ b y (a, b) ∈ R, ⇒ (b, a ) ∉ R porque R es antisimétrica;
Si a ≠ b y (a, b) ∈ R ⇒ (b, a ) ∈ R −1 

−1
 ⇒ R es antisimétrica.
Si (b, a ) ∉ R ⇒ (a, b) ∉ R −1


Veamos ahora que pasa con la propiedad transitiva:
Si ( a, b) ∈ R y (b, c) ∈ R ⇒ ( a, c ) ∈ R porque R es transitiva;
Si ( a, b) ∈ R ⇒ (b, a ) ∈ R −1 


Si (b, c ) ∈ R ⇒ (c, b) ∈ R −1  ⇒ R −1 es transitiva.

Si ( a, c ) ∈ R ⇒ (c, a ) ∈ R −1 

−1
Entonces R es reflexiva, antisimétrica y transitiva, entonces es de orden parcial.
¿Será de orden total? Como R es de orden total, quiere decir que para cualquier par de valores a y b
del conjunto, se cumple que
tambien de orden total.
aRb o bRa ⇒ bR −1a o aR −1b ; entonces la relación inversa es
b) Consideremos f : A → B una función y definamos una relación R binaria sobre A, de forma
tal que: ∀ x, y ∈ A: x R y ⇔ f(x)=f(y) . Demostrar que R es una relación de equivalencia.
Para probar que es una relación de equivalencia, hay que probar tres propiedades:
i) Reflexiva x R x ⇔ f(x)=f(x) se cumple porque la igualdad es una relación de equivalencia.
ii) Simétrica: si x R y ⇒ y R x
Si x R y ⇒ f(x)=f(y) ⇒ f(y)=f(x) por la prop simétrica de la igualdad ⇒ y R x
iii) Transitiva: x R y, y R z ⇒ x R z
Si x R y ⇒ f(x)=f(y) ; si y R z ⇒ f(y)=f(z) ⇒ por prop transitiva de la igualdad, f(x)=f(z).
Entonces
xRz.
Ejercicio 3
Definir en la línea de comandos de Haskell las siguientes relaciones, utilizando listas por
comprensión:
a) S definida sobre A donde
A = { x ∈ / − 5 ≤ x ≤ 5}
Respuesta: [ (x,y)| x<- [-5..5], y<- [-5..5], x*y>0
tal que
a S b ⇔ a.b > 0
]
b) R definida B={-3,-2,-1,0,1,2,3} tal que a R b ⇔ a − b = a
Respuesta: [ (x,y)| x<- [-3..3], y<- [-3..3], x-y==x^3-y^3 ]
Profesores: Saúl Tenenbaum y Germán Ferrari
http://www.x.edu.uy/ - http://matematicagerman.blogspot.com/
3
− b3 .
Página 2 de 2
Profesorado de Informática - Ciencias de la Computación - INET – DFPD
Matemática Discreta usando el computador 2010 (Matemática I)
Ejercicio 4
Dadas las siguientes relaciones, indicar cuales son de equivalencia.
a) Sobre el conjunto
×
se define una relación R tal que
( a, b ) R ( c, d ) ⇔ b − d = a2 − c2 .
Hallar [(0,0)], si corresponde y en caso contrario decir que propiedad/es no se verifica/n.-
Hay que probar las propiedades:
( a, b ) R ( a, b ) ⇔ b − b = a2 − a2 ⇔ 0 = 0 Se cumple.
ii)Simétrica: ( a, b ) R ( c, d ) ⇒ ( c, d ) R ( a, b )
( a, b ) R ( c, d ) ⇔ b − d = a2 − c2
( c, d ) R ( a, b ) ⇔ d − b = c2 − a2 Multiplicando la primera por (-1) se obtiene la segunda. Se cumple.
iii) Transitiva: ( a, b ) R ( c, d ) y además ( c, d ) R ( e, f ) ⇒ ( a, b ) R ( e, f )
( a, b ) R ( c, d ) ⇔ b − d = a2 − c2
( c, d ) R ( e, f ) ⇔ d − f = c2 − e2
b − f = a 2 − e2 ⇒ ( a, b ) R ( e, f )
Sumando:
i) Reflexiva, también llamada Idéntica:
Entonces cumple la propiedad transitiva y por lo tanto es una relación de equivalencia.
Para hallar la clase de equivalencia del (0,0) buscamos con que pares está relacionado el (0,0):
( a, b ) R ( 0,0) ⇔ b − 0 = a2 − 02
Entonces
b = a2
La clase de equivalencia del (0,0) son todos los pares (a,b) en los cuales
Esto es, en resumen, los pares de la forma
( 0, 0 )  =


( a, b ) = ( a, a2 )
b = a2 .
{( a, a ) , con a ∈ } Algunos elementos de este conjunto, a modo de ejemplo, son:
2
(0,0), (3,9), (-11, 121), (-4, 16), (4,16).........
el conjunto
, se define una relación T tal que a T b ⇔ a.b = a + b .
Hallar [5] si corresponde. ¿Están relacionado el 7 consigo mismo? ¿7x7 = 7 + 7 ?
(49 ≠ 14)
Entonces si no es reflexiva no es una relación de equivalencia.
b) En
Ejercicio 5
a) Determina si
f (2,1) = 5
f : × → / f ( a, b ) = a 2 + b 2
f (1, 2) = 5
f ( a, b ) = a 2 + b2 = −5
es inyectiva y/o sobreyectiva.-
Entonces f no es inyectiva.
Es imposible. Entonces f no es sobreyectiva.
Profesores: Saúl Tenenbaum y Germán Ferrari
http://www.x.edu.uy/ - http://matematicagerman.blogspot.com/
Página 3 de 3
Profesorado de Informática - Ciencias de la Computación - INET – DFPD
Matemática Discreta usando el computador 2010 (Matemática I)
b) Sean A={1,2,3} y B={2,3}. Clasificar la función f : A × B →
f : A× B →
/
definida por
f ( a, b ) = 3a − b .
f (1, 2) = 1
f (1,3) = 0
f (2, 2) = 4
f (2,3) = 3 Esta función es inyectiva. El conjunto imagen sólo tiene estos 6 valores.
f (3, 2) = 7
f (3,3) = 6
¿Será sobreyectiva? ¿Existen a y b enteros tales que f(a,b)=799 ?
Respuesta: NO. 799 no es uno de los 6 únicos valores que puede tomar la función.
Por lo tanto f no es sobreyectiva.
Ejercicio 6
a) Definir en Haskell una función sumacifras que dado un número natural de tres cifras devuelva la
suma de las mismas.- ejemplo: sumacifras 132 = 6.
(Indicar su tipo).
Soluciones:
Como la letra dice "dado un número natural de tres cifras" podemos suponer que la entrada ya es
un número natural. Entonces sólo tenemos que buscar como obtener la suma de sus cifras.
Para entenderlo un poco mejor, vamos a poner como ejemplo que queremos obtener la suma de las
cifras del número 456.
Para obtener el número 4, una forma de hacerlo es el cociente de dividir 456 entre 100.
div 456 100 = 4
Para obtener el número 6, una forma de hacerlo es el resto de dividir 456 entre 10.
mod 456 10 = 6
Entonces, hasta ahora tenemos: (hay que escribirlo en el block de notas: open text editor)
intento:: Int -> Int
intento a = div a 100 + mod a 10
Esta función suma las cifras de las unidades y de las centenas:
intento 456 = 4+6 = 10
intento 789 = 7+9 = 16
Volviendo al ejemplo del principio, ¿cómo haremos para conseguir el "5", cifra de la decenas?
Si hacemos "mod 456 100" el resultado es 56.
Entonces si buscamos el cociente de dividir 56 entre 10 nos dara 5
div 56 10 = 5
En resumen, mod 456 100 = 56
div 56 10 = 5
Haciendo todo junto,
div ( mod 456 10 ) 10 = 5
Lo que esta entre paréntesis vale 56.
Profesores: Saúl Tenenbaum y Germán Ferrari
http://www.x.edu.uy/ - http://matematicagerman.blogspot.com/
Página 4 de 4
Profesorado de Informática - Ciencias de la Computación - INET – DFPD
Matemática Discreta usando el computador 2010 (Matemática I)
Una respuesta a ejercicio es :
sumacifras :: Int -> Int
sumacifras a = div a 100 + mod a 10 + div (mod a 100) 10
Si queremos agregarle una condición para asegurarnos que la entrada sea un número natural:
sumacifras2 :: Int -> Int
sumacifras2 a = if a<0 then (error "los valores tienen que ser naturales") else (div a 100 + mod a
10 + div (mod a 100) 10)
De otra forma:
sumacifras3 :: Int -> Int
sumacifras3 a | a<0
| otherwise
=
error "los valores tienen que ser naturales"
= div a 100 + mod a 10 + div (mod a 100) 10
Si queremos agregarle la verificación de que sea efectivamente de 3 cifras quedaría asi:
sumacifras4 :: Int -> Int
sumacifras4 a | a<0
= error "los valores tienen que ser naturales"
| a > 999
= error "el número tiene que ser de 3 cifras"
| otherwise = div a 100 + mod a 10 + div (mod a 100) 10
b) Definir la función anterior que recibe dos naturales y devuelve el número natural anterior al
menor de ambos, si son diferentes de cero, y si alguno es cero devuelve cero. (Indicar su tipo).
Una respuesta es :
anterior :: Integer -> Integer -> Integer
anterior a b
| a<0
= error "los números tienen que ser naturales"
| a==0 || b==0
=0
| a <b
= a-1
| otherwise
= b-1
Profesores: Saúl Tenenbaum y Germán Ferrari
http://www.x.edu.uy/ - http://matematicagerman.blogspot.com/
Página 5 de 5








Comments