Final de matemática discreta. U.T.N.F.R.B.A. (página 3)

FINAL DE MATEMÁTICA DISCRETA. 30 / 07/ 02

1. Explicar:

a. porqué puede asegurarse que si v y w son dos vértices de un digrafo finito y si hay camino de v a w entonces hay camino simple de v a w.

b. porqué la relación S no permite ordenar el conjunto ℝ pero en cambio permite construir una partición del mismo :

x S y sii | ent(x) | = | ent(y) |

c. el error que se comete en la siguiente derivación:

2. Demostrar:

a. " a. b, c Î Z: " n Î Z+:( a º n b Ù c º n d) Þ a.(c +e) º n b.(d +e)

b. que en toda álgebra de Boole (A, +, •,, 0, 1) : " x, y, z Î A: (x ≼ z Þ )

3. Analizar el valor de verdad de las siguientes proposiciones(Justificar las respuestas)

a. La cantidad de matrices 3×3 con coeficientes en {1, 2, 3, 4, 5, 6} en las cuales los elementos de la segunda columna forman una sucesión estrictamente creciente o los elementos de la primera columna forman una sucesión estrictamente decreciente es 1.866.240.

b. = 2048

c. Dada la tabla de pesos correspondiente a un grafo ponderado G:

Es posible hallar:

1. al menos tres árboles generadores mínimos distintos
2. un subgrafo bipartido y fuertemente conexo

Observaciones

• Para aprobar el examen se necesita resolver correctamente cuatro ítems.
• Al terminar el examen podrás ver la resolución del mismo en cartelera
• Recordá que podés aclarar tus dudas suscribiéndote al grupo de consulta

RESOLUCIÓN FINAL MATEMÁTICA DISCRETA 30 / 07 / 02

1. Explicar:

a.

Dado que por hipótesis hay camino desde el vértice v al vértice w:

caso 1: si el camino es simple nada habría que probar.

caso 2: si el camino no es simple habría que probar que es posible encontrar a partir del mismo un camino que sea simple.

Al no ser simple al menos un vértice se repetirá en el camino:

y entonces sorteando la repetición señalada quedará el camino:

Si este nuevo camino de v a w fuera simple ya quedaría probado, caso contrario habría que repetir el proceso (eliminación de repetición de vértices) hasta obtener un camino simple.

Observación: una prueba formal se esto se haría por ejemplo por inducción sobre la longitud del camino.

b.

• La relación S no permite ordenar el conjunto ℝ debido a que no es una relación antisimétrica, es decir que del hecho de que x S y Ù y S x no se desprende que necesariamente x = y.

Por ejemplo 3,4 S –2,6 y –2, 6 S 3, 4 (|ent(3,4)| = |ent(-2,6)| = 3) y sin

embargo 3,4 ¹ –2,6

• La relación S permite "partir" el conjunto ℝ debido a que S es una relación de equivalencia :
• • S es reflexiva: x S x sii

(por ser la igualdad reflexiva)

• • S es simétrica:
• x S y Û |ent(x)| = |ent(y)| Û |ent(y)| = |ent(x)| sii y S x  
• • S es transitiva

x S y Ù y S z Û |ent(x)| = |ent(y)| Ù |ent(y)| = |ent(z)| Þ  

Þ |ent(x)| = |ent(z)| Û x S z

 y entonces el conjunto cociente correspondiente a esta relación de equivalencia constituirá una partición del conjunto ℝ. Así pues:

" a Î ℝ : Cl (a) = {x Î ℝ / x ~ a} = {x Î ℝ / |ent(x)| = |ent(a)|}

y entonces ℝ / S = { Cl (a) / a Î Z0+}

La partición sería del tipo:

 Con

[0,1) = , [1,2), [-1,0) = , , [2,3), [-2,-1) = ……

c.

El error radica en el hecho de que la particularización aplicada en las premisas

no tiene porqué ser sobre la misma constante. Si por ejemplo se considerara el siguiente diccionario en el universo de los números enteros Z:

p(x): x es un número entero.

q(x): x es un entero par

r(x): x es un entero impar

definido sobre U = R

si bien es correcta la particularización ya que 2 es una raíz del esquema , no es correcta la particularización porque 2 no es una raíz del esquema .

FINAL DE MATEMÁTICA DISCRETA. U.T.N. F.R.B.A. 19 / 12 / 02

EN TODOS LOS EJERCICIOS RECUADRAR LA ÚNICA RESPUESTA CORRECTA. EL EXAMEN SE APRUEBA CON AL MENOS 9 (NUEVE) RESPUESTAS CORRECTAS. SOLO SE SUMAN LAS RESPUESTAS CORRECTAS, LAS INCORRECTAS NO RESTAN PUNTOS.

1. a) 25 – 1

   b) 232 – 33

   c) (32)! – 1

   d) C32,2 – 33

2. La cantidad de funciones booleanas distintas f : {0,1}5 ® {0,1} formadas por más de un minitérmino es:
3. La cantidad total (T) de formas de completar este examen y la cantidad de formas con las que se aprueba (A) son:

1. a) cl(1) (mód. 3)

   b) cl(3) (mód. 10)

   c) Z+

   d) cl(2) (mód. 3)

2. En el desarrollo de (3×2 – )10 todos los términos tienen grado perteneciente a:

   c1: "A no es idempotente o A es ortogonal" c2:"A es ortogonal y B es idempotente"

   c3:"B no es ortogonal o A es ortogonal" c4:"B es idempotente y B no es ortogonal"

   Es válida:

   a) c1

   b) c2

   c) c3

   d) c4

3. Dadas las premisas: "Todas las matrices ortogonales son inversibles. Existen matrices idempotentes que no son inversibles. A es una matriz inversible. B es una matriz no inversible". Y las siguientes conclusiones:

   a) v(p) = F

   b) v(q) = V

   c) v (r) = F

   d) v (p Ù r) = F

4. Sabiendo que v(~ p ® (q Ù r)) = F Ù v(~ r Ú q) = V , NO se puede asegurar:

   a) 6

   b) 30

   c) 36

   d) 210

5. Sea A = {a,b,c,d} , (P(A), Í ) es un Algebra de Boole isomorfa a (Dn, ½ ) siendo n:
6. En toda Algebra de Boole, " y: " x: " z se cumple lo indicado:

8) Dadas dos relaciones R y S definidas en un conjunto A, si R y S son de orden entonces también lo es:

9) Dada la relación de equivalencia en |R tal que x R y Û ½ x2 – 8 ½ = ½ y2 – 8 ½ , NO es posible hallar clase de equivalencia de cardinal:

10)Dadas las siguientes proposiciones:

1. En todo conjunto totalmente ordenado, cada par de elementos tiene ínfimo y supremo.
2. Si (A, ) es un buen orden entonces (A, ) es un orden total.
3. Todo conjunto acotado es finito.

Son verdaderas:

11) Si dados a, b Î Z , $ s, t Î Z / 3 = s a + t b entonces se puede asegurar que:

12) Dada la siguiente matriz de pesos, indique cuál de las afirmaciones es verdadera:

13) De las siguientes afirmaciones sobre grafos:

I: Si en un grafo hay ciclo de Euler entonces también hay camino de Euler no cerrado.

II: Es posible construir un grafo simple con 12 vértices y 70 aristas.

III: Un grafo simple con 8 vértices y 13 aristas puede no ser conexo.

Son verdaderas:

14) En Z – {0} de a | r y a | s se desprende necesariamente lo indicado:

15) Sabiendo que cada ejercicio de este examen se califica únicamente como B (bien), M (mal) o Æ (en caso de no responder), definimos la relación: ejercicioi R ejercicioj Û tienen la misma calificación. Si un alumno responde todas las preguntas, se puede asegurar que la cantidad de clases de equivalencia es:

………………………………………………..

Firma del alumno

Resolución Final de Matemática Discreta 19/12/2002

1. a) 25 – 1

   b) 232 – 33

   c) (32)! – 1

   d) C32,2 – 33

   La respuesta correcta es la B

   JUSTIFICACION:

   Como la función tiene dominio en {0,1}5 significa que hay 32 elementos (o renglones de la tabla) a los que hay que asignarles una imagen. Dicha imagen puede ser 0 o 1. Es decir que tenemos que colocar ceros y unos en 32 lugares. El orden en que lo hagamos es relevante ya que sería una función distinta.

   Por lo tanto, el total de funciones booleanas es V ’2,32 = 2 32

   Pero como el enunciado dice que deben estar formadas por más de un minitérmino, debemos restar la función nula (la que tiene todos ceros, ningún minitérmino) y las 32 funciones que están formadas por un minitérmino distinto cada una.

   Por lo tanto la cantidad de funciones pedida es: 2 32 – 33

2. La cantidad de funciones booleanas distintas f : {0,1}5 ® {0,1} formadas por más de un minitérmino es:
3. La cantidad total (T) de formas de completar este examen y la cantidad de formas con las que se aprueba (A) son:

La respuesta correcta es la C

JUSTIFICACION:

Primero vamos a averiguar la cantidad total de formas de completar el examen.

Son 15 preguntas y cada una de ellas se puede responder de 4 formas distintas (a, b, c o d).

Es decir que tenemos 15 lugares para llenar con 4 letras, que por supuesto se pueden repetir, y además el orden es relevante ya que si por ejemplo hay 3 respuestas con A, no es lo mismo que sean los 3 primeros ejercicios u otros tres.

Por lo tanto la cantidad total de formas de completar el examen es T = V ‘ 4,15 = 415

Ahora calculemos de todas esas formas, con cuántas se aprueba el examen. Recordemos que se debe tener por lo menos 9 respuestas correctas.

Es decir que hay varias posibilidades para aprobar:

Con 9 correctas y 6 incorrectas , con 10 correctas y 5 incorrectas , etc. hasta 15 correctas.

En cada uno de esos casos, primero veamos de cuantas formas pueden estar las correctas:

Sea i =cantidad de respuestas correctas Þ de las 15 elijo las i correctas :

Una vez que se tiene la cantidad de formas en que pueden estar ubicadas las respuestas correctas, veamos de cuantas formas pueden estar las incorrectas. Quedan 3 opciones para cada una (ya que sacamos la correcta): V’3,15-i = 3 15-i

O sea que para i respuestas correctas, la cantidad total de formas es: 3 15-i

Pero como i puede ir desde 9 hasta 15, nos queda finalmente: A =

1. a) cl(1) (mód. 3)

   b) cl(3) (mód. 10)

   c) Z+

   d) cl(2) (mód. 3)

   La respuesta correcta es la D

   JUSTIFICACION:

   Calculemos la expresión de un término genérico: Th+1 = (3 x2)h

   Th+1 = 3h (-1)10-h x2h x-(10-h) Þ Th+1 = 3h (-1)10-h x2h-10+h

   El exponente de la x es 3 h -10 = 3 h – 12 + 2 = 3 ( h – 4 ) + 2 que es igual a un múltiplo de 3 sumado 2. Por lo tanto pertenecen a la clase del 2 módulo 3.

2. En el desarrollo de (3×2 – )10 todos los términos tienen grado perteneciente a:

   c1: "A no es idempotente o A es ortogonal" c2:"A es ortogonal y B es idempotente"

   c3:"B no es ortogonal o A es ortogonal" c4:"B es idempotente y B no es ortogonal"

   Es válida:

   a) c1

   b) c2

   c) c3

   d) c4

   La respuesta correcta es la C

   JUSTIFICACION:

   Tomando el siguiente diccionario sobre el Universal de matrices!

   ort(x) = "x es ortogonal"

   inv(x) = "x es inversible"

   id(x) = "x es idempotente"

   Las premisas se pueden escribir de la siguiente manera:

   1. " x : [ ort(x) ® inv(x)]

   2. $ x: [ id(x) Ù ~ inv(x)]

   3. inv(A)

   4. ~ inv(B)

   Sobre la matriz A nada puede afirmarse, ya que solo cumple el consecuente de la primera premisa, y no se puede tener en cuenta la recíproca.

   Sobre la matriz B, si particularizamos la premisa 1: ort(B) ® inv(B)

   y aplicamos Modus Tollens con la 4: ~ ort(B)

   Respecto de si B es idempotente o no, nada puede afirmarse.

   Por lo tanto de las conclusiones presentadas:

   c1: "A no es idempotente o A es ortogonal" c2:"A es ortogonal y B es idempotente"

   c3:"B no es ortogonal o A es ortogonal" c4:"B es idempotente y B no es ortogonal"

   La única que se infiere de las premisas es la 3, ya que al ser una disyunción con una de las partes verdadera, es verdadera.

3. Dadas las premisas: "Todas las matrices ortogonales son inversibles. Existen matrices idempotentes que no son inversibles. A es una matriz inversible. B es una matriz no inversible". Y las siguientes conclusiones:

   a) v(p) = F

   b) v(q) = V

   c) v (r) = F

   d) v (p Ù r) = F

   La respuesta correcta es la B

   JUSTIFICACION:

   La única forma de que ~ p ® q Ù r sea falsa es que el antecedente sea verdadero y el consecuente falso. O sea que ~ p es V con lo cual p es falsa. Y al menos una de q y r debe ser falsa. (I)

   Analicemos el otro dato: como ~ r Ú q es verdadera, significa que q es verdadera o r es falsa.(II)

   Si q es verdadera, para que se cumpla (I) debe ser r falsa.

   Si q es falsa, para que se cumpla (II) debe ser r falsa.

   O sea que r sí o sí es falsa. La única que no puede afirmar el valor de verdad es q.

4. Sabiendo que v(~ p ® q Ù r) = F Ù v(~ r Ú q) = V , NO se puede asegurar:

   a) 6

   b) 30

   c) 36

   d) 210

   e) ninguna

   La respuesta correcta es la D

   JUSTIFICACION:

   Comencemos viendo que P(A) tiene 16 elementos. Es decir debemos buscar algún conjunto de dicho cardinal y que sea Algebra de Boole. Con eso es suficiente ya que todas las Algebras de Boole de determinado cardinal son isomorfas.

   Al descomponer los números presentados como producto de sus factores primos, obtenemos:

   6 = 2 · 3 30 = 2 · 3 · 5 36 = 22 · 32 210 = 2 · 3 · 5 · 7

   Si bien (D6, ½ ) es un Algebra de Boole, sólo tiene 4 elementos.

   Lo mismo ocurre con (D30, ½ ) que es un Algebra de Boole de 8 elementos.

   (D36, ½ ) ni siquiera es un Algebra de Boole pues tiene 9 elementos.

   Y finalmente (D210, ½ ) es un Algebra de Boole de 16 elementos, y por lo tanto isomorfa a la de P(A) dada.

5. Sea A = {a,b,c,d} , (P(A), Í ) es un Algebra de Boole isomorfa a (Dn, ½ ) siendo n:
6. En toda Algebra de Boole, " y: " x: " z se cumple lo indicado:

La respuesta correcta es la A

JUSTIFICACION:

1. Como x z Ù x ` z Þ x + z = z Ù x +` z = ` z Þ

2. Þ ( x + z ) · (x +` z) = z · ` z

   Þ x + ( z · ` z) = 0A Þ x + 0A = 0A Þ x = 0A

   En principio como esta es correcta y solo hay una correcta,

   en conclusión las demás son falsas.

   Igualmente daremos contraejemplos de las otras tres:

   se cumple el antecedente 2 · 3 = 1 pero no se cumple el consecuente.

3. en ( D30 , ½ ) siendo 0A = 1 tomando x = 2 Ù y = 3,

   2 · 5 = 1 Ù 3 · 5 = 1 pero no se cumple el consecuente.

4. también en ( D30 , ½ ) tomando x = 2 Ù y = 3 Ù z = 5, se cumple que x · z y · z ya que
5. También tomemos (D30, ½ ) con x = 2 ; y = 15 ; z = 3 Þ ` z = 10

2 15 + 10 ya que 2 30 es verdadero pero sin embargo 2 15

1. a) R Ç S

   b) R U S

   c) R-1 U R

   d) ` S

   La respuesta correcta es la A

   JUSTIFICACION:

   Primero daremos contraejemplos para descartar las otras opciones:

   En A = { a, b, c} consideremos R = { (a,a), (b,b), (c,c) , (a,b), (a,c) }

   S = { (a,a), (b,b), (c,c) , (b,a) } ambas son claramente de orden.

   Sin embargo: R U S == { (a,a), (b,b), (c,c) , (a,b), (a,c), (b,a) } NO es antisimétrica pues (a,b) y (b,a) pertenecen a la relación y a ¹ b

   R-1 U R = { (a,a), (b,b), (c,c) , (b,a), (c,a) } U { (a,a), (b,b), (c,c) , (a,b), (a,c) } =

   = { (a,a), (b,b), (c,c) , (a,b), (b,a), (a,c), (c,a) } tampoco es antisimétrica.

   ` S ni siquiera es reflexiva.

   Por lo tanto, queda la opción A o ninguna (la E). Ahora demostraremos que la A es verdadera:

   i) " x Î A : (x,x) Î R Ù (x,x) Î S por hipótesis ya que R y S son de orden

   Þ por def. de Ç : (x,x) Î R Ç S Þ R Ç S es reflexiva

   ii) " x, y Î A : (x,y) Î R Ç S Ù (y,x) Î R Ç S Þ por def. de Ç

   Þ (x,y) Î R Ù (x,y) Î S Ù (y,x) Î R Ù (y,x) Î S Þ por conmutativa y asociativa de la Ù

   Þ [(x,y) Î R Ù (y,x) Î R ] Ù [(x,y) Î S Ù (y,x) Î S] Þ por hipótesis R y S son de orden

   Þ x = y Ù x = y Þ R Ç S es antisimétrica

   ii) " x, y , z Î A : (x,y) Î R Ç S Ù (y,z) Î R Ç S Þ por def. de Ç

   Þ (x,y) Î R Ù (x,y) Î S Ù (y,z) Î R Ù (y,z) Î S Þ por conmutativa y asociativa de la Ù

   Þ [(x,y) Î R Ù (y,z) Î R ] Ù [(x,y) Î S Ù (y,z) Î S] Þ por hipótesis R y S son de orden

   Þ (x,z) Î R Ù (x,z) Î S Þ por def. de Ç Þ (x,z) Î R Ç S Þ R Ç S es transitiva

   R Ç S es de orden

2. Dadas dos relaciones R y S definidas en un conjunto A, si R y S son de orden entonces también lo es:

   a) 1

   b) 2

   c) 3

   d) 4

   La respuesta correcta es la A

   JUSTIFICACION:

   Vamos a plantear una clase de equivalencia genérica: Cl(a) = { x Î |R / x R a }

   Analicemos un poco x R a Û ½ x2 – 8 ½ = ½ a2 – 8 ½ Û x2 – 8 = a2 – 8 Ú x2 – 8 = – a2 + 8

   Þ x2 = a2 Ú x2 + a2 = 16 Þ x = a Ú x = -a Ú x2 + a2 = 16

   Lo cual significa que por lo menos en la cl(a) están a y -a, en algunos casos habrá más elementos de acuerdo a las soluciones de x2 + a2 = 16, que puede ser una más o dos más.

   En el caso del cero: Cl(0) = { 0 , 4 , -4 }

   Cl(1) = { 1 , -1 , , –} Cl(5) = { 5 , -5 }

3. Dada la relación de equivalencia en |R tal que x R y Û ½ x2 – 8 ½ = ½ y2 – 8 ½ , NO es posible hallar clase de equivalencia de cardinal:
4. Dadas las siguientes proposiciones:

1. En todo conjunto totalmente ordenado, cada par de elementos tiene ínfimo y supremo.
2. Si (A, ) es un buen orden entonces (A, ) es un orden total.
3. Todo conjunto acotado es finito.

Son verdaderas:

La respuesta correcta es la B

JUSTIFICACION:

La i) es verdadera ya que en cada par de elementos, al estar totalmente ordenado el conjunto, uno de ellos precede al otro, por lo tanto el primero es el ínfimo y el segundo el supremo.

La ii) es verdadera ya que si el conjunto está bien ordenado, significa que cada subconjunto tiene primer elemento. En particular " a, b: {a,b} tiene primer elemento. Si es a, entonces a b. Si es b entonces b a. Es decir a y b no son incomparables. Por lo tanto es orden total.

La iii) no es cierta ya que por ejemplo tomando el intervalo real [0,1) con la relación £ está acotado ya que [1, + ¥ ) son cotas superiores, pero sin embargo tiene infinitos elementos.

1. a) mcd(a,b) = 3

   b) mcd(a,b) ¹ 1

   c) mcd(a,b) = 1

   d) sa º 3 (mód b)

   La respuesta correcta es la D

   JUSTIFICACION:

   Daremos un contraejemplo para las opciones a) y b): 3 = 1 · 7 + (-5) · 2 pero mcd(7,2) = 1

   Otro contraejemplo para la c) : 3 = 2 · 9 + (-1) · 15 y sin embargo mcd(9,15) = 3

   Como debe haber una correcta, seguro es la d). Igualmente la demostraremos:

   Por hipótesis 3 = s a + t b Þ 3 – sa = t b Þ b ½ 3 – sa Þ 3 º s a (b) Þ s a º 3 (b)

2. Si dados a, b Î Z , $ s, t Î Z / 3 = s a + t b entonces se puede asegurar que:

   D0 =

   a) Existe un camino mínimo entre el vértice "1" y el "3". b) En el grafo subyacente al mismo y tomando las aristas con pesos en valor absoluto, el camino mínimo del vértice "1" al vértice "5" tiene longitud 7. c) En el grafo subyacente al mismo y tomando las aristas con pesos en valor absoluto, no existe un subgrafo isomorfo a K4. d) En el grafo subyacente al mismo y tomando las aristas con pesos en valor absoluto hay más de un árbol generador mínimo.

   La respuesta correcta es la D

   JUSTIFICACION:

   La a) es falsa ya que hay un ciclo negativo formado por (3, 2, 6, 5, 4, 3), lo cual significa que una vez que del 1 se llega al 3, luego se pueden dar infinitas vueltas por este ciclo y seguir bajando el costo. (Hacer el diagrama)

   La b) es falsa ya que el camino (1,3,6,5) tiene longitud 2.

   La c) es falsa, ya que con los vértices 1, 2, 3, 6 y sus aristas incidentes (eliminando una de las dos paralelas) se forma el K4.

   La d) es verdadera, ya que hay dos árboles generadores mínimos:

   {5,6} { 2,4} {1,3} {6,1} {3,2} y {5,6} { 2,4} {1,3} {6,1} {1,2}

3. Dada la siguiente matriz de pesos, indique cuál de las afirmaciones es verdadera::

   I: Si en un grafo hay ciclo de Euler entonces también hay ciclo de Hamilton.

   II: Es posible construir un grafo simple con 12 vértices y 70 aristas.

   III: Un grafo simple con 8 vértices y 13 aristas puede no ser conexo.

   Son verdaderas:

   a) I y III

   b) II y III

   c) sólo III

   d) sólo I

   e) ninguna

   La respuesta correcta es la C

   JUSTIFICACION:

   Primero refutaremos la i y ii

   Para la i)

   Este grafo tiene ciclo de Euler ya que todos sus vértices son

   de grado par. Sin embargo no tiene ciclo de Hamilton, ya que

   por el vértice que es punto de corte( el del medio) se necesitaría pasar más de una vez para poder cerrar el camino.

   Para la ii) El K12 es el grafo simple de 12 vértices con la mayor cantidad de aristas posibles, y dicha cantidad es: ½ A ½ = 66

   La iii) es verdadera. Por ejemplo:

   Este grafo es simple,

   tiene 8 vértices y 13 aristas

   y no es conexo.

4. De las siguientes afirmaciones sobre grafos:

   a) a | (r + .s –1)

   b) a | (r2 + 3.s + 1)

   c) a | r2 + 3.s

   d) a | r. s + 1

   La respuesta correcta es la C

   JUSTIFICACION:

   Refutaremos las tres opciones incorrectas con contraejemplos:

   a) 3 ½ 6 Ù 3 ½ 12 pero no es cierto que 3 ½ 6+12-1

   c) 3 ½ 6 Ù 3 ½ 12 y tampoco es cierto que 3 ½ 62+3 · 12 + 1

   d) 3 ½ 6 Ù 3 ½ 12 y tampoco se cumple que 3 ½ 6 · 12 +1

   Ahora demostramos la verdadera:

   Si a ½ r Ù a ½ s Þ r = a · k Ù s = a · t con k, t Î Z

   Þ r2 = a · a · k2 = a · p con p Î Z Ù 3 s = a · ( 3 t )

   Þ r2 + 3 s = a · p + a · ( 3 t ) = a · ( p + 3 t) siendo p + 3 t Î Z

   Þ a ½ r2 + 3 s

5. En Z – {0} de a | r y a | s se desprende necesariamente lo indicado:
6. Sabiendo que cada ejercicio de este examen se califica únicamente como B (bien), M (mal) o Æ (en caso de no responder), definimos la relación: ejercicioi R ejercicioj Û tienen la misma calificación. Si un alumno responde todas las preguntas, se puede asegurar que la cantidad de clases de equivalencia es:

La respuesta correcta es la B

JUSTIFICACION:

Si el alumno respondió todas las preguntas, lo máximo es que haya 2 clases ( B y M), ya que ninguna respuesta entra en la categoría Æ . No se puede afirmar que sean 2 clases, ya que por ejemplo si respondió todo bien, habría una sola clase de equivalencia (B).

FINAL DE MATEMÁTICA DISCRETA. U.T.N.F.R.B.A. 16 / 07 / 02

EN TODOS LOS EJERCICIOS RECUADRAR LA ÚNICA RESPUESTA CORRECTA. EL EXAMEN SE APRUEBA CON AL MENOS OCHO (8) RESPUESTAS CORRECTAS. DEBE HABER MÁS RESPUESTAS CORRECTAS QUE INCORRECTAS PARA APROBAR EL EXAMEN.

1 La cantidad de lados que posee un polígono cuyo número de diagonales es 119 es:

a. 60 b. 17 c. 12 d. 70

2 La suma resulta ser igual a : a. 3n b. 3n+1 c. 2n+1 d. 4n

3 A la asamblea universitaria asistieron 135 estudiantes, 20 graduados , 35 no docentes y 50 docentes. La cantidad de comisiones mixtas de 10 miembros que se puedan formar con al menos 4 docentes para el tratamiento de cuestiones académicas es de:

a. b. c.d.

4 De los esquemas proposicionales : A:" x: (p (x)® q (x)) y B: $ x: (p (x) Ù r (x)), se infiere en forma válida:

a. " x: (r (x)® q (x)) b. $ x: (r (x) Ù q (x)) c. " x: (r (x)® p (x)) d. " x: (p (x)® r (x))

5 Con la interpretación indicada se puede justificar que el esquema de razonamiento

" x: (p (x)® q (x)) , $ x: (p (x) Ù r (x)) " x: (r (x)® p (x)) es inválido:

a. , , , r(x): b. U = R, p(x) : |x| < 7, q(x): |x| <10, r(x): |x| <5

c. U = R, p(x) : |x| < 7, q(x): |x| <10, r(x): |x| > 5

d. , , , r(x):

6 La proposición indicada en R , resulta ser falsa:

a. b.

c. d.

7 Las álgebras de Boole indicadas resultan ser isomorfas:

a.y b.y

c. y d. y

8 La forma normal disyuntiva correspondiente a la función booleana f: {0, 1}3 ® {0, 1}/

f ((x, y, z)) = se reduce a la cantidad de minitéminos indicada:

a. 2 b. 3 c. 5 d. 4

9 Es posible determinar un álgebra de Boole para valores determinados de a, b y c en el cual:

a. de a . b = a y a . c = a no se infiera que necesariamente a . (b + c) = a

b. de a . c ≼ b . d no se infiera que necesariamente a ≼ b y c ≼ d

c. de a ≼ b y c ≼ d no se infiera que necesariamente a + c ≼ b + d

d.

10 La ecuación 116.x º 8 admite:

a. una única solución en Z 44 y ninguna solución en Z 15 b. ninguna solución en Z 44 y una solución en Z 15

c. dos soluciones en Z 20 y una solución en Z 15 d. cuatro soluciones en Z 20 y cuatro soluciones en Z 44

11 Sean a y b enteros con b ¹ 0. Si a – b = 175 y la división de a por b tiene cociente 15 y resto 7 entonces:

a. (a, b) = 3 b. [a, b] = 2200 c. [a, b] =2160 d. (a, b) = 1

12 La proposición indicada es verdadera:

a. En Z: " a, b, c ¹ 0: (b, c) = (b, a. c) b. En Z: " a ¹ 0: a. x º a. y (n) entonces x º y (n)

c. En Z: Si (a, b) = 1 entonces (a + b, a. b) = 1 d. En Z: " a, b ¹ 0: [a, b] = a. b

13. Dada la matriz asociada a una relación definida en A = {a, b, c}: con a, b, c Î {0, 1}:

a. la relación es reflexiva si a = 0 b. la relación es simétrica sii a = 1 y b = 0

c. la relación es antisimétrica sii a = b = 0 d. la relación es transitiva únicamente en el caso en que a = 0

14. Dada la relación de equivalencia definida en R2: (a, b) R (c, d) sii |a. b | = |c. d |, el conjunto indicado puede asumirse como conjunto cociente:

a. {cl ((0, x)) / x ³ 0} b. {cl ((x, 0)) / x £ 0} c. {cl ((1, x)) / x > 0} d. {cl ((1, x)) / x ³ 0}

15 El conjunto indicado constituye una partición de :

a. A = {Ck: (x, y) Î : x2 + y2 ³ k2 , k ³ 0} b. B = {Ck :(x, y) Î : x2 + y2 = k2 , k ³ 0}

c. C = {Ck : (x, y) Î : x2 + y2 £ k2 , k ³ 0} d. D = {Ck: (x, y) Î : x2 + y2 > k2 , k ³ 0}

16 La cantidad de formas de ordenar "totalmente " el conjunto A = {a, b, c, d, e, f} es de:

a. 120 b. 320 c. 420 d. 720

17 El conjunto ordenado (A, £ ) con A = {x Î R / x = 2 / (n + 3), nÎ N}Í R satisface lo indicado:

a. Admite mínimo y está totalmente ordenado b. Admite máximo y está parcialmente ordenado

c. Admite máximo y no está bien ordenado

d. Carece de cotas inferiores y de mínimo

18 Si se considera el grafo indicado a través de su función de incidencia

Es posible determinar :

a. dos caminos eulerianos no cerrados.

b. dos subgrafos diferentes de modo tal que sean acíclicos y conexos y tengan los mismos vértices del grafo.

c. un subgrafo fuertemente conexo con |V| = 4

d. un grafo bipartido isomorfo al mismo

19 Sea la matriz resultante de la aplicación del algoritmo de Floyd a un digrafo con |V| = 4 . la información dada por la misma es correcta:

1. El vértice (4) es un vértice fuente
2. El vértice (3) es un vértice pozo

c. No es posible determinar camino desde el vértice (4) al vértice (3)

d. La distancia entre el vértice (2) y el vértice (3) es 3.

20 En el grafo ponderado es posible hallar:

a. un único árbol generador mínimo de costo 107

b. exactamente dos árboles generadores mínimos de costo 107

c. exactamente tres árboles generadores mínimos de costo 107

d. exactamente cuatro árboles generadores mínimos de costo 107

FINAL DE MATEMÁTICA DISCRETA. U.T.N.F.R.B.A. 18 / 02 / 03

Ejercicio Nº 1.

Determinar:

a. dos funciones booleanas distintas f, g : {0,1}4 ® {0,1} de modo tal que su forma normal conjuntiva se reduzca a tres maxitérminos.

b. la validez del siguiente razonamiento:

"Todas los grafos completos son conexos. Existen grafos simples que no son conexos. Por lo tanto: existen grafos simples que no son completos"

(si es válido probar la validez por el método demostrativo, caso contrario definir interpretación que muestre que es inválido)

Ejercicio Nº 2.

Responder a lo pedido en cada caso:

a. Probar que la siguiente proposición es verdadera: " n Î N > 1: " Î Zn : $ Î Zn : + =

(considerar que + = )

b. Mostrar que dado el conjunto ordenado (N – {1}, |), no es cierto que todo subconjunto no vacío tenga ínfimo.

c. Dar un ejemplo de grafo simple que responda a las condiciones indicadas: tenga al menos dos vértices con la misma valencia, exactamente tres puntos de articulación – puntos de corte y admita al menos dos árboles generadores distintos.

Ejercicio Nº 3.

¿Verdadero o falso? (justificar)

a. La clase de equivalencia de la matriz correspondiente a la relación de equivalencia definida en M2x2 con M = {1,2,3,4,5,6,7,8,9,10} en la forma A R B sii a11 + a22 = b11 + b22, consta de exactamente 500 matrices.

b. En toda álgebra de Boole y cualquiera sea el valor de a, b y c: a ≼ b. Þ a ≼ b +

c. Dados a, b Î Z , si existen s, t Î Z tal que 5 = s a + t b, entonces se puede asegurar que 5 es el máximo común divisor entre a y b.

Observaciones

• • Es suficiente resolver en forma correcta cuatro ítems para aprobar
• Al terminar el examen podrás ver la resolución del mismo en cartelera
• Recordá que podés aclarar tus dudas suscribiéndote al grupo de consulta

RESOLUCIÓN FINAL MATEMÁTICA DISCRETA 18 / 02 / 03

Ejercicio Nº 1.

a. Basta considerar dos funciones booleanas a través de dos tablas de entrada – salida y en función de las "TRES SALIDAS NULAS" determinar los maxitérminos correspondientes y multiplicar los mismos para dar la expresión de cada una de las funciones:

b. RAZONAMIENTO VÁLIDO

Habrá que considerar en primer lugar el esquema del razonamiento al cual el razonamiento planteado responde y analizar la validez del mismo:

Sobre el universo de definición U = {x / x es grafo}y con el diccionario:

t(x): x es completo

c(x): x es conexo

s(x): x es simple

el esquema será: " x: (t(x) ® c(x)), $ x: (s(x) Ù ~c(x)) ∴ $ x: (s(x) Ù ~t(x))

Si ahora se asocia a cada uno de los esquemas el conjunto de verdad correspondiente:

Para ver el gráfico seleccione la opción "Descargar" del menú superior

En términos de conjuntos:

• La primera premisa diría que T Í C
• La segunda premisa diría que S Ç ¹ Æ
• La conclusión diría que S Ç

¹ Æ

El diagrama de Venn que responde a las afirmaciones precedentes mostrarían que la conclusión es válida. Resta hacer la prueba formal:

D /

1. $ x: (s(x) Ù ~c(x)) (premisa)
2. (s(a) Ù ~c(a)) (particularización existencial en 1.)
3. " x: (t(x) ® c(x)) (premisa)
4. (t(a) ® c(a)) (particularización universal en 3.)
5. ~c(a) (ley de simplificación en 2.)
6. ~ t(a) (modus tollens entre 4 – 5)
7. s (a) (ley de simplificación en 2.)
8. s (a) Ù ~ t(a) (ley de combinación entre 7 – 8)

9. $ x: (s(x) Ù ~t(x)) (generalización existencial en 8.)

Ejercicio Nº 2.

a. Efectivamente la asignación (n, , ) satisface lo planteado ya que

+ =

b. Basta considerar por ejemplo el conjunto A = {5, 7, 8} Í N que al carecer de conjunto minorante (conjunto de cotas inferiores):

~ $ c Î N – {1}: (c | 5 Ù c | 7 Ù c | 8) (5, 7 y 8 son primos entre sí)

carece de ínfimo

c. Dado que en todo grafo simple "existen al menos dos vértices con la misma valencia" (resultado del práctico del módulo D), habrá que ocuparse sólo de las dos condiciones restantes. Así por ejemplo el grafo indicado cumple con lo pedido:

• Los únicos puntos de articulación son: b, d y f
• Pueden señalarse exactamente tres árboles generadores distintos

(aristas marcadas con trazo grueso)

   Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Ejercicio Nº 3.

a. VERDADERA

Dado que cl = = ,

las matrices pertenecientes a esta clase serán de la forma:

y como a, b, c, d, e, f, g, h, j e i pueden tomar 10 valores distintos, por el principio del producto cada una de ellas da lugar a 10. 10 = 100 matrices diferentes, por lo que en total la clase indicada tendrá efectivamente 500 elementos

b. VERDADERA

H) a ≼ b. T) a ≼ b +

(recordar que x ≼ y sii x + y = y sii x. y = x)

D/

1. por H) a ≼ b.

2. b. ≼ b + debido a que b. + (b + ) = b +

d/ b. + (b + ) = (b. + b) + = b +

 3. finalmente por ser la relación transitiva, de 1. y 2. resulta a ≼ b +

c. FALSA

Si se considera por ejemplo que a = 1 y b = 5, efectivamente con s = 0 y t = 1 se cumple que

5 = 0.1 + 1. 5 pero sin embargo (1, 5) = 1 ¹ 5

FINAL MATEMATICA DISCRETA (COD. 952020). U.T.N.F.R.B.A. 25 / 02/ 03

Ejercicio Nº 1

En caso de ser posible y en forma justificada señalar:

a. dos clases de equivalencia diferentes correspondientes a la relación de equivalencia definida en Z2 x Z2 en la forma: (a, b) R (c, d) sii a º c (mód 3).

b. un conjunto parcialmente ordenado, de modo que sea álgebra de Boole, definiendo con precisión las operaciones que le dan dicha estructura.

c. Un conjunto con al menos cinco elementos de modo tal que sea verdadera la proposición:

$ x:" y:(x < y ® x2 < y2 )

Ejercicio Nº 2

Demostrar:

a. que si u y v son vértices de un dígrafo D y si hay un camino en D de u a v, entonces hay un camino acíclico de u a v.

b. que si |A| = n entonces |P(a)| = 2n

Ejercicio Nº 3

Responder en forma justificada a los siguientes interrogantes:

a. ¿cuántos números naturales menores que 10000 son múltiplos de 7 pero no son pares ni múltiplos de 3?

b. si un ferretero desea poner en cajas 12.028 bulones y 12.772 tornillos de modo que cada caja contenga el mismo número de bulones o de tornillos y además el mayor número posible de ellas. ¿Cuál es el número de bulones y de tornillos que debe contener cada caja?

c. ¿Es posible hallar al menos tres árboles isomorfos al árbol indicado?

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 Observaciones

• Es suficiente resolver en forma correcta cuatro ítems para aprobar
• Al terminar el examen podrás ver la resolución del mismo en cartelera
• El enunciado y su resolución será cargado en

RESOLUCIÓN FINAL MATEMÁTICA DISCRETA 18 / 02 / 03

Ejercicio Nº 1.

a.

Teniendo en cuenta que Z3 = {}, bastará elegir como representantes de clases diferentes a los pares (3, 1) y (25, 10) con

cl((3, 1)) = {(x, y) Î Z2 / x º 3 0} y cl((25, 10)) = {(x, y) Î Z2 / x º 3 1}

b.

Por ejemplo el conjunto (P(A), Í ) con A = {a, b, c} tiene los atributos de:

• estar ordenado ya que la relación Í es reflexiva antisimétrica y transitiva
• estar parcialmente ordenado ya que por ejemplo {a} ⋢ {b} y {b} ⋢ {a}.
• ser álgebra de Boole, debido a que las operaciones:
• • x + y = x È y
  • x . y = x Ç y
  • 

= A – x

le dan la estructura mencionada ya que:

• la unión e intersección de conjuntos son operaciones binarias
• la complementación es una operación unitaria
• cumplen (teoría de conjuntos) con los axiomas que caracterizan a un álgebra de Boole:
• • ley conmutativa: la intersección y unión de conjuntos son operaciones conmutativas
  • ley asociativa: la intersección y unión de conjuntos son operaciones asociativas
  • ley distributiva: la intersección es distributiva respecto de la unión y viceversa.
  • ley de identidad: el neutro aditivo es el conjunto vacío y el neutro multiplicativo es el conjunto A.
  • ley de complementación: efectivamente

x È = A y x Ç = Æ

c. Bastará elegir un conjunto de 5 elementos que tenga entre ellos a "·0", por ejemplo A = {0, 1, 2, 3, 4}, debido a que (0, y) satisface el condicional planteado porque cada vez que el antecedente es verdadero, necesariamente el consecuente también lo será.

Ejercicio Nº 2.

a.

Entre todos los caminos posibles de u a v consideremos uno de longitud menor (n) C = (x1, x2, x3, ….xi…..xj…xn, xn+1) con x1= u y xn+1 = v.

Si xi.= xj con 1 ≤ i  j ≤ n +1, entonces el camino xi…..xj. es cerrado y el camino que se obtiene omitiendo esa parte también va de u a v, pero como tendría longitud menor que C ese camino sería imposible, con lo cual

xi ¹ xj…si i ¹ j, por lo que el camino considerado es acíclico.

b.

Dado que P(A está formado por subconjuntos de A de cardinales respectivos:

0, 1, 2, 3, …n, la cantidad de subconjuntos estará determinada por la suma:

= = (1 + 1)n = 2 n

Ejercicio Nº 3

a.

Adoptando la notación para caracterizar a los múltiplos de "a"

(en este caso naturales menores que 10.000)

habrá que calcular en primer lugar:

||, || y || y teniendo en cuenta que los conjuntos mencionados no son disjuntos dos a dos (tienen elementos en común) la respuesta estará dada por la suma:

|| – || – ||+ ||

(la intersección triple se le suma una vez para compensar el hecho de que se la restó dos veces)

|| = 1428 7.1, 7.2, ……7. 1428

|| = 714 14.1, 14.2, …..14. 714 (con 14 = [7,2])

|| = 476 21.1, 21.2, 21. 476 (con 21 = [7,3])

|| = 238 42.1, 42.2, ….42. 238 (con 42 = [7,2,3])

Finalmente reemplazando quedará:

|| – || – ||+ || = 1428 – 714 – 476 + 238 = 476

b.

El ferretero puede poner los bulones en cajas de 2 unidades, de 4 unidades, de 31 unidades, etc., en definitiva puede agruparlas en cajas que contengan cualquier divisor de 12.028. Igualmente ocurre con los tornillos , cajas de 2 unidades, de 4 unidades, etc, todos los divisores de 12.772.

Puesto que el número de una caja de bulones debe ser el mismo que el de una caja de tornillos, estamos buscando un divisor común, que además se nos pide que sea el mayor posible, este número es el M.C.D.(12.028,12.772)=124

Luego las cajas deben contener 124 unidades de bulones o 124 unidades de tornillos.

c.

Efectivamente es posible responder a lo pedido. Basta considerar tres árboles con raíz asociados al árbol dado como por ejemplo: Ta, Tc y Te. Sus matrices de adyacencia coincidirán con la ordenación: a, b, c, d, e, f (por ejemplo)

FINAL DE MATEMÁTICA DISCRETA. U.T.N. 21 / 02 / 02.

1. Explicar en forma clara y precisa porqué…

a. no significan lo mismo los siguientes enunciados: y .

b. un álgebra de Boole con conjunto subyacente finito tiene necesariamente un número par de elementos.

c. el conjunto de rectas del plano P = { r: y = x + i; i Î R} constituye una partición de .

2. Responder a los siguientes requerimientos:

a. Construir un árbol de modo tal que los caminos de la raíz a cada hoja, coincidan con los caminos eulerianos del digrafo indicado entre dos vértices fijos elegidos convenientemente.

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

1. Dado el esquema de razonamiento:

Para ver la fórmula seleccione la opción "Descargar" del menú superior

y la interpretación:

¿puede afirmarse si la conclusión es válida o no? (justificar)

c. Una agencia de viaje quiere regalar un viaje de fin de semana a Colonia a los clientes que tengan número de cuil del tipo: 27 – abcdefgh – 6. ¿A cuántos a lo sumo tendrá que premiar si además se exige que las cifras a-b-c-d-e-f-g-h- formen una sucesión estrictamente creciente con valores del 1 al 9?

3. Demostrar:

a. que si la suma de dos números naturales primos es primo, entonces uno y sólo uno de ellos debe ser igual a 2.

2. que los elementos maximales distintos de un conjunto ordenado deben ser incomparables.

RESOLUCIÓN FINAL DE MATEMÁTICA DISCRETA . 21 / 02 / 02

Grupo para consultas:

1.

2. Efectivamente los enunciados

Para ver la fórmula seleccione la opción "Descargar" del menú superior

tienen significados distintos.

El esquema que caracteriza al enunciado es del tipo:

entendiéndose con esto que satisface p(x, y) con recorriendo el universo de definición.

Por otro lado, el esquema que caracteriza al enunciado es del tipo: , entendiéndose con esto que satisface p(x, y) con elemento determinado del universo de definición y recorriendo el universo de definición.

Así por ejemplo:

• si se considera la interpretación:

no es lo mismo decir que toda persona ama a alguien que decir que hay al menos una persona que ama a cualquier otra

o bien

• si se considera la interpretación:

El primer enunciado es verdadero: ya que todo entero mayor que 1 admite algún múltiplo (todo entero admite por ejemplo como múltiplo al mismo número)

El segundo enunciado es falso: ya que no es cierto que haya un entero mayor que 1 que sea divisor de cualquier otro (por ejemplo cualquier entero mayor que 1 : , no es divisor de ).

b.

Partiendo del hecho de que toda álgebra de Boole tiene al menos dos elementos (los neutros aditivo y multiplicativo: 0 y 1) y que el agregado de un elemento obligará al agregado de su complemento, los elementos se darán de a pares, con lo cual el conjunto subyacente a un álgebra de Boole finita será necesariamente de la forma:

A =

c.

Efectivamente el conjunto P (conjunto de rectas paralelas de pendiente 1 con ordenada al origen recorriendo ℝ) con gráfica:

  Para ver el gráfico seleccione la opción "Descargar" del menú superior

 cumple con la definición de partición, es decir:

1. " r Î P: r Í R2.
2. r, s Î P: r = s o bien r Ç s = f
3. 

= R2.

2.

a. Teniendo en cuenta las condiciones de existencia de camino euleriano no cerrado en digrafos:

Un digrafo admite camino euleriano no cerrado de v a w sii:

• es conexo
• g- (v) = g+(v) + 1
• g+(w) = g-(w) + 1 y
• " u ¹ v, w: g+(u) = g-(u)

El dígrafo en cuestión admite tres caminos eulerianos de A a F:

• (A, B, C, D, B, F, D, E, F)
• (A, B, C, D, E, F, D, B, F)
• (A, B, F, D, B, C, D, E, F)

los cuales pueden mostrarse a través de un árbol con raíz en Ay hojas en F :

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

 b.

La interpretación dada permite asegurar que el esquema de razonamiento indicado es inválido debido a que bajo dicha interpretación resulta:

• v(

= V

(tanto antecedente como consecuentes son falsos)

• v(

= V

(por ejemplo ‘4’ es un número par y múltiplo de 4 al mismo tiempo)

• V(

= F

(por ejemplo ‘6’ es un número par y sin embargo no es múltiplo de 4)

c.

A lo sumo tendrá que premiar a personas

(tener en cuenta que una vez elegidas ocho de las nueve cifras disponibles, el orden, de acuerdo a la condición planteada será único.

3.

a. Teniendo en cuenta el enunciado:

En N: ∀ a: ∀ b: ( a, b, a + b: números primos → a = 2 ⊻ b = 2 )

Si se demostrara en forma directa, dado que por hipótesis a + b es primo: necesariamente a + b será un número impar

(a + b = 2 carece de solución con las condiciones fijadas y a + b = 2. q con q natural > 1 no es primo dado que admite como divisor a 2), con lo cual a es un natural par y b natural impar o la inversa.

En cualquiera de las dos situaciones uno de los dos sumandos y sólo uno será igual a 2 dado que el único primo par es 2.

b. Teniendo en cuenta el enunciado:

En un conjunto ordenado :

∀ a: ∀ b: ( a, b: maximales ∧ a ≠ b → a ⋠ b ∧ b ⋠ a), si se demostrara por absurdo, habrá que partir de la negación de esta afirmación, es decir:

∃ a: ∃ b: ( a, b: maximales ∧ a ≠ b ∧ (a ≼ b ∨ b ≼ a ) ) lo que resulta ser un absurdo dado que:

• si a ≼ b , a no sería maximal (tiene por encima a b).
• si b ≼ a, b no sería maximal (tiene por encima a a).

Nadia Soledad Cavalleri

cibernetica_nc[arroba]hotmail.com