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

Partes: 1, 2, 3

FINAL DE MATEMÁTICA DISCRETA.
U.T.N.F.R.B.A. 07 / 03 / 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.Un grafo posee 60 vértices y 310
aristas, 59 vértices con grado 10. El grado del
vértice restante es:

a.10 b.15 c.20 d.
30

2. En el grafo indicado entre A y B se da lo
indicado:

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

a.
Hay exactamente 3 caminos mínimos de long. 10
b. Hay exactamente 2 caminos mínimos de long.
9

c. Hay exactamente 3 caminos mínimos de
long. 9 d. Hay exactamente 2 caminos mínimos de
long. 10

3. El grafo indicado en el ejercicio anterior
:

a. Admite camino euleriano no cerrado b.
Es regular

c. Admite sólo un árbol generador
mínimo que no contenga las aristas AC y CB

d. Es fuertemente conexo y admite subgrafo
bipartido completo

4. En una cierta residencia de
estudiantes, la oficina de
alojamientos ha decidido nombrar, para cada piso, un consejero
residente masculino y uno femenino. La cantidad de pares
diferentes de consejeros que pueden seleccionarse para un
edificio de 7 pisos, de 12 candidatos del sexo masculino
y 15 del sexo femenino y siempre que Chiche y Eduardo no
estén juntos es de :

a. C154, 7 b. V179,
7 c. V178, 7 d. V154, 7

5. La cantidad de números de 4
dígitos que pueden formarse utilizando únicamente
los dígitos 3, 4, 5, 6 y 7 y de modo tal que tengan
al menos dos dígitos repetidos es de:

a. 85 b.505 c.300 d.
17

(485).Poner 60 como opción

6. La suma : resulta ser igual a:

a. b. c.
d.

7. Dado el entero "a", si resto (a : 7 ) = 6
entonces resto ((a + 10): 7) es igual a:

a.10 b. 0 c. 2
d. 16

8. La ecuación -525 º 18. x (módulo 24)
admite exactamente (en término de clases):

a. 0 soluciones
b. 1 solución c. 3 soluciones d. 6
soluciones

9. Dados los enteros no nulos a, b y c, de a | b
y a | c se infiere que necesariamente:

a. 2.a | b + c b. a | b 2 + 3.
c c. 2.a | b. c d. a. c | a. b

10. En un álgebra de
Boole : "
x: " y:
ínfimo{x, y} es igual a:

a. x +y b. x c. x. y
d. y

11. En un álgebra de Boole se
verifica (cualquiera sea x e y): es igual a:

a. b. c. d.

12. Un estudiante recibirá
una calificación de aprobado en un curso si se
reúne una o mas de las condiciones
siguientes :

i) Obtuvo 7 puntos o más en el examen de mitad de
período (X) y 7 puntos o más en el examen final
(Y).

ii) Obtuvo 7 puntos o más en al menos uno de los
dos exámenes (de mitad de período o final) y tiene
una beca de atletismo
(Z).

iii) Su padre es el instructor del curso (I)

Una expresión booleana que de1 en caso de que
apruebe y 0 en caso contrario resulta ser:

a. X + Z + Y+ I b. c. d. X. Y. Z

13. Dadas las proposiciones:

i) Es necesario que José no vaya al
cine para que
termine su tarea

ii) No es cierto que: José termine su
tarea o vaya al cine

iii) José no termina su tarea y no
irá al cine.

Son equivalentes entre sí:

a. Sólo i) y ii) b. ninguna
c. Sólo ii) y iii) d. i), ii) y
iii)

14. De las premisas

se concluye en forma válida (cualquiera sea
el universo de
definición y los esquemas indicados):

a. b. c. d.

15. La proposición indicada en A , resulta
ser verdadera:

a.
b.

c. d.

16. Dada en la relación definida por: :

a. R es una relación de orden pero no de
equivalencia.

b. R es una relación de equivalencia pero
no de orden.

c. R es una relación de orden y de
equivalencia.

d. R no es una relación ni de orden ni de
equivalencia.

17. El conjunto ordenado (N2, R) con
(a, b) R (c, d) sii a | c y b ≤ d cumple lo
indicado:

a Está parcialmente ordenado y carece de
mínimo

b. Está totalmente ordenado y carece de
máximo

c. Está bien ordenado y tiene un solo
minimal

d. No está bien ordenado pero admite
subconjunto totalmente ordenado

18. En todo conjunto ordenado se cumple lo
indicado " x, y,
z::

a. (sup{x,y} ≼ sup{y,z} )
® x ≼ z
b. (x ≼ y Ù z ≼ y) ® ínf{x, z} ≼ y

c. (x ≼ y Ù x ≼ z) ® x ≼ ínf{y, z} d.
x ≼ sup{y,z} ® (x ≼ y Ù x ≼ z

19. Dada la relación de equivalencia
definida en R: x S y sii x.(x +4) = y.(y +4)

a. 0 y 4 están en la misma clase de
equivalencia b. Cl (0) = {0} c. cl (4)
Ç cl(-4)
= f d.
cl(4) = cl(-4)

20.Dada una relación de equivalencia
definida en un conjunto no vacío A,
necesariamente:

a.$
a: cl( a) = f
b. $
a: $ b:
(a ¹
b Ù
cl( a) Ç
cl( b) ¹
f ) c.
" a:
" b : cl( a)
Ç cl( b)
¹ f

d. " a: cl( a) ¹ f

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

1. Los 15 vértices de un grafo simple
pueden tener:

a. valencia 3 b. valencia 5 c.
valencia 4 d. valencia 7

2. Se quiere duplicar los tramos de un red de comunicación que en caso de deteriorarse
imposibilitaría la
comunicación entre ciertos puntos.

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

Los tramos que deben duplicarse son los
indicados.

a. AB y DF b. BD y FE c. BD y FG
d. DE y FE

3. El grafo indicado

Euleriano y acíclico
Bipartido y conexo
Isomorfo al grafo o k –
regular
Euleriano y con más de tres árboles generadores

4. La cantidad de números enteros
positivos del 1 al 1000 no divisibles ni por 3, ni por 7 , ni por
11 a la vez es de:

a. 667 b. 858 c. 997 d.
910

5. El número de soluciones enteras de la
ecuación x1 +x2 + x3 +
x4 = 32 con xi > 0 , 1 < i < 4 es
de:

a. 6545 b. 4495 c. 58.905 d.
35.960

6. La sumatoria resulta ser igual a:

a. 4105 + 524 b.
4105 c. – 4105 + 524 d.
–4105

7. La ecuación 5.x º 15 (módulo 25)
admite exactamente (en término de clases):

a. 0 soluciones b. 1 solución
c. 5 soluciones d. 15 soluciones

8. El máximo común divisor y el
mínimo común múltiplo entre n + 3 y n + 4
(cualquiera sea el natural n) son respectivamente:

a. 3 y 4 b. 1 y n2 + 7.n + 12
c. 1 y n + 4 d. n + 3 y n + 4

9. Sea S = { (1,1,0,0); (1,1,1,1); (1,0,1,1);
(1,0,0,0)} con S Í {0, 1}4 .

La expresión reducida, en término de suma
de productos, de
la función
booleana que toma el valor 1 en el
conjunto S y 0 en el resto resulta ser:

a. b. c. d.

10. Es posible que el conjunto subyacente a un
álgebra de Boole finita tenga exactamente:

a. 10 elementos b. 5 elementos c. 6
elementos d. 16 elementos

11. Es posible determinar (cualquiera sean a, b y
c)un álgebra de Boole en el cual:

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

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

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

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

12. El doble condicional indicado es verdadero
(cualquiera sea el universo de
definición y los esquemas p(x) y q(x):

13. De las premisas se concluye en forma válida
(cualquiera sea el universo de definición y los esquemas
indicados):

a. b. c. d.

14. La proposición indicada en R , resulta
ser verdadera:

a. b.

c. d.

15. El conjunto cociente correspondiente a la
relación de equivalencia definida en R2
:

(a,b) R (c,d) sii b2 =
d2 resulta ser:

a. {cl ((1, y))/ y < 0} b. {cl (y)/ y
≥ 0} c. {cl ((0, y))/ y ≥ 0} d. {cl ( y) / y
< 0}

16. Dada una relación de equivalencia
definida en un conjunto A y dos clases de equivalencia
cualesquiera cl(a) y cl(b) podría ocurrir lo
indicado:

a. cl(a) Í cl(b) y cl(b) ⊈ cl(a) b.
cl(a) = cl(b) o bien cl(b) Ç cl(a) = Ø

c. cl(a) = Ø o bien cl(b) = Ø
d. cl(a) Ì cl(b) o bien cl(b) Ì cl(a)

17. Es posible ordenar el conjunto A =
{a,b,c,d,e,f} de modo tal que:

a. Esté bien ordenado y admita elementos
incomparables

b. Esté bien ordenado y admita exactamente
dos maximales

c. Esté bien ordenado y no admita
elementos incomparables

d. Esté bien ordenado y admita al menos
dos minimales

18. Dada un álgebra de Boole (A, +, . ,
¯ , 0, 1) y un subconjunto S de A no
vacío, para que S resulte ser también un
álgebra de Boole es suficiente que:

a. 0 ɛ S b. 1 ɛ S c. 1
ɛ S y (" a,
b: a, b ɛ S®
a + b ɛ S) d. 1 ɛ S y (" a, b: a, b ɛ
S® a
. ɛ
S

19. La altura de un árbol binario completo
con 2047 nodos es:

a. 9 b. 10 c. 11
d. 12

20. La suma
resulta ser igual a :

a. n2 b. c. d.

FINAL DE MATEMÁTICA DISCRETA.
28 / 05/ 03

Ejercicio 1:

a) Dadas las funciones
proposicionales .
Probar que:

v []=V

v.[]=F

b) Analizar la validez del siguiente razonamiento sin
utilizar tablas de verdad:

"Si un monte se quema, algo suyo se quema. Algo
suyo se quema si y sólo si es usted descuidado. Si usted
no es descuidado, es acreedor a una felicitación.
Por lo tanto, si un monte se quema, usted no es acreedor a una
felicitación"

Ejercicio 2:

Probar que en un álgebra de Boole:
Se desea diseñar un dispositivo para una
máquina expendedora de golosinas. La misma cuenta con 3
ranuras una para introducir monedas de 10 centavos, otra para
monedas de 5 centavos y la última para monedas de 25
centavos. A lo sumo una moneda por ranura . Si la golosina que
entrega la máquina vale 30 centavos, el dispositivo debe
indicar con un 1 en la salida si las monedas depositadas son suficientes
para realizar la operación y con un 1 en la salida
si en caso de
realizar la operación, se debe entregar vuelto. Efectuar
las tablas, simplificar y

, y dibujar ambos circuitos.

Ejercicio 3: a) Demostrar la verdad o
falsedad de las siguientes proposiciones:

b) En las elecciones a intendente de una localidad, con
un padrón electoral de 180 ciudadanos. Se presentan 3
partidos
políticos. Se sabe que votó el 80 % de los
empadronados, que cada candidato votó por sí mismo
y que hubo votos en blanco. Cuántos resultados distintos
pueden obtenerse.

Ejercicio 4:

Si es
una relación de equivalencia definida en el conjunto
. Definir clase
de equivalencia y probar que
En se
define la siguiente relación :. Probar que es una relación de
orden. ¿Es un orden total?.Realizar el diagrama de
Hasse y hallar las cotas superiores del conjunto

Ejercicio 5: a) Probar que si
es un
árbol entonces es conexo y si se le quita una arista deja
de serlo

Dado el grafo cuya matriz de
adyacencia es:

RESOLUCIÓN:

RESOLUCIÓN FINAL
MATEMÁTICA DISCRETA 28 / 05 / 03

CÁTEDRA LIC. MARÍA
HORTENSIA ARRIOLA

Ejercicio 1:

Demostración de la Falsedad de la segunda
proposición:
Considerar:
Como es verdadero y es verdadero entonces
también lo es
o sea el antecedente de la proposición es
VERDADERO
Pero es falso ,
o sea el consecuente de la proposición es
FALSO
Demostración formal de la primera
proposición:
m: un monte se quema

q: algo suyo se quema

d: Ud. es descuidado

f: Ud. es acreedor a una
felicitación

Supongo premisas verdaderas y conclusión
falsa.

Si la conclusión es Falsa entonces

En 1) como el antecedente es V y la implicación
también se obtiene que y con este resultado, pasando a 2) se obtiene que
.

Estos valores no
producen ninguna contradicción en 3) (F-à F) por lo tanto estos
valores obtenidos producen premisas verdaderas y
conclusión falsa por lo tanto se trata de un
RAZONAMIENTO INVÁLIDO

Ejercicio 2:

De multiplicando por se obtiene: (1)
De sumando se obtiene += de lo
que (2)
De (1) y (2) se deduce la igualdad
pedida.
b)

X (de
10)
Y( de
25)
Z( de
5)
f
g
0
0
0
0
0
0
1
0
0
1
0
0
2
0
1
0
0
0
3
0
1
1
1
0
4
1
0
0
0
0
5
1
0
1
0
0
6
1
1
0
1
1
7
1
1
1
1
1
Para ver el gráfico
seleccione la opción "Descargar" del menú
superior
Ejercicio 3:
La primera proposición es VERDADERA:
Como 7 es un número primo se tiene que
(7, )=1 entonces multiplico por entonces y como por hipótesis 7/ entonces entonces 7/
La segunda proposición es FALSA: tomar
por ejemplo
Una demostración puede ser:
votaron el 80% de 180= 144. Estos votos deben
repartirse en 4 casilleros(partido 1, partido 2, partido 3,
Blancos) pero hay 3 que va cada uno a cada uno de los tres
primeros casilleros.. Es decir quedan por ubicar 141 en 4
casilleros, o sea

Ejercicio 4:

a) Demostración de

sea y
por transitividad osea (1)

sea y
por transitividad o sea (2).
De (1) y (2) se prueba la tesis

Demostración de

Como entonces y
por lo tanto

Reflexiva: (a,b) R (a,b) porque aa y b

Antisimetría: Si (a,b)R (c,d) y
(c,d)R(a,b) entonces a=c y b=d

(ac y
bd ) y (
ca y db)

a=c b=d

Transitividad: (a,b) R (c,d) y (c, d)R (e,f)
entonces (a,b) R (e,f)

(ac y
bd ) y (
ce y df)

a
e y bf entonces
(a,b)R(e,f)

En el diagrama de Hasse se advierte que no es orden
total ya que (1,1) no se relaciona con (0,0)

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

COTAS SUPERIORES:

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

Ejercicio 5:

Supongo que le quito una
arista y sigue siendo conexo. Esa arista tiene dos
vértices por extremos. Si el grafo sigue siendo conexo
existe un camino (por ende camino simple) que une dichos
vértices y que no utiliza dicha arista. Pero este
más el que saqué ( la arista sacada es un
camino de longitud 1 entre dichos vértices) hace que
originariamente entre estos dos vértices existan 2
caminos simples diferentes. Lo que niega el hecho que G es un
árbol.
Si G es un árbol para cualquier par de
vértices existe un único un camino simple que los
une. Es por lo tanto obviamente conexo. ( se usó la
existencia del camino )
grado (v1)=4

grado (v2)=4

grado (v3)=3

grado (v4)=3

grado (v5)=3

grado (v6) =3

No es grafo de Euler porque tiene 4 vértices de
grado impar.

Hay que eliminar un vértice tratando que los que
quedan tengan los mismos grados que el otro grafo, estos son:
2 de grado 3, 1 de grado 4 y 2 de grado 2.

Por ejemplo si elimino el v1 la matriz
queda:

y
quedan 3 vértices de grado 2 y 2 de grado 3 NO
SIRVE

Por ejemplo si elimino v4 la matriz
queda:

al eliminar v4 quedan 1 de grado 4
(v1), 2 de grado 3 (v2 y v6) y 2
de grado 2.(v3 y v5 )

Esta matriz de adyacencia coincide con la del
grafo

según la ordenación de
vértices:

a, c, e, b, d, por lo que resulta ser grafos
isomorfos

ESTE EXAMEN LO PODRÁN BAJAR DEL
FORO DE CONSULTA:

EN ARCHIVO. FINALES
UTN 2003

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

1. Responder en forma justificada a los siguientes
interrogantes:

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

con x, y, z Î {0, 1}:

1. ¿bajo qué condiciones la
relación es reflexiva?

2. ¿bajo qué condiciones la
relación es simétrica?

3. ¿bajo qué condiciones la
relación es antisimétrica?

4. ¿bajo qué condiciones la
relación es transitiva?

b. ¿Necesariamente en cualquier grafo
simple con "n " vértices hay al menos dos vértices
con la misma valencia?

c. ¿Cuál es el menor número
de tres cifras que al ser dividido por 5 y 7 en cada caso da
residuo 3?

2. Realizar las acciones
indicadas:

a. En una reunión celebrada entre 12
países de la Comunidad Europea
se acuerda aceptar las resoluciones aprobadas por la
mayoría de los miembros. España,
Italia, Portugal
y Grecia votan
en bloque. Situación similar es la de Francia y
Alemania.
También hacen lo mismo Reino Unido e Irlanda por un lado y
Bélgica, Holanda y Luxemburgo por otro. Dinamarca siempre
vota lo contrario que Alemania y los tres países
Bélgica, Holanda y Luxemburgo lo contrario que Irlanda.
Encontrar los países que tienen mayor poder de
decisión.(justificar la respuesta)

b. Demostrar que si T es un árbol y
v una hoja de T entonces T – v es un
árbol.

c. Indicar en caso de ser posible dos
clases de equivalencia disjuntas entre sí,
correspondientes a la relación de equivalencia definida en
R2:

(a, b) R (c, d) sii 4.a – b = 4.c –
d

3. Recuadrar en cada caso la única respuesta
correcta.

a. Si se sabe que algunos mamíferos son acuáticos y algunos
animales
acuáticos son carnívoros y se indican las
afirmaciones:

i. Algunos mamíferos son
carnívoros.

ii. Ningún mamíferos es
carnívoro

iii. Todos los animales acuáticos son
mamíferos.

¿Cuál de las opciones indicadas se
da?

1.Exactamente una se infiere necesariamente
(recuadrarla)

2. Ninguna se infiere necesariamente.

3. Más de una se infiere necesariamente
(recuadrarlas).

b. La cantidad de maneras diferentes en que se
pueden sentar 10 personas en una mesa redonda
de 6 asientos y con 4 en espera es la indicada:

1. 151.200

2. 210

3. 25.200

RESOLUCIÓN FINAL DE
MATEMÁTICA DISCRETA.

U.T.N.F.R.B.A 28 / 02 /
02.

Nueva dirección para consulta vía
mail:

1. Si se tiene en cuenta que dada A =
[aij] = M ( R ) = y:

R es reflexiva sii aii = 1
" i
R es simétrica sii aii = a
ji "
i, j (A simétrica)
R es antisimétrica sii " i, j:( (i ≠j
Ù
aij = 1)Þ aji = 0)
R es transitiva sii A.A ≼ A (considerando la
suma y producto
booleanos) y la relación de orden definida en la forma:
C ≼ D sii cij £ dij
" i, j

1. La relación es reflexiva sii y = 1

2. La relación es simétrica sii z =
0

3. Para ningún valor de x – y- z la
relación es antisimétrica

4. La relación es transitiva sii

.=
≼
sii

sii ≼ sii
x = z = 0

b. Lo planteado ocurre necesariamente

Efectivamente , si un grafo simple (sin lazos ni
aristas paralelas) tiene "n " vértices entonces
existen al menos dos vértices con la misma
valencia.

Si lo probamos por absurdo partiríamos de la
siguiente consideración:

"
v: " w:
g(v) ≠ g(w)

con lo cual y dado que " x Î VG : 0 £ g(x) £ n-1

(recordar que no hay lazos ni aristas
paralelas)

se daría las siguientes asignaciones entre
vértices y valencias (o grados):

y entonces se produciría una
contradicción entre la primera y la última
afirmación la cual proviene de suponer que la
afirmación dada es falsa.

c. De acuerdo al enunciado el número
buscado deberá ser de la forma:

y como [5, 7] = 35, el número buscado
tendrá la forma:

con lo cual y dado que N debe tener tres cifras, N = 35.
3 + 3 = 108

a. De acuerdo a las alianzas establecidas entre los
países mencionados se los puede agrupar del siguiente
modo:

B1 = {España, Italia, Portugal,
Grecia}

B2 = {Francia, Alemania}

B3 = {Reino Unido, Irlanda}

B4 = {Bélgica, Holanda,
Luxemburgo}

B5 = {Dinamarca}

Si se armara una tabla booleana considerando:

1 : voto por la afirmativa para tomar cierta
resolución

0 : voto por la negativa para tomar cierta
resolución

y el hecho de que:

Dinamarca siempre vota lo mismo que
Alemania
Los tres países Bélgica, Holanda y
Luxemburgo lo contrario que Irlanda

Bastará considerar para el
análisis una tabla con 8 filas (la tabla
completa tendría 16 filas) en donde se expliciten los
votos efectuados (por bloques) y la resolución tomada en
cada caso:

B1	B2	B3	B4	B5	Resultado general (por mayoría)
0	0	0	1	1	0
0	0	1	0	1	0
0	1	0	1	0	0
0	1	1	0	0	0
1	0	0	1	1	1
1	0	1	0	1	1
1	1	0	1	0	1
1	1	1	0	0	1

Restará buscar cuál es el
bloque con más coincidencias entre votación por
bloque – votación general tomada y los países
integrantes de cada bloque para determinar los países con
mayor poder de decisión.

De este análisis
resulta:

B1 ® 8
coincidencias

B2 ® 4
coincidencias

B3 ® 4
coincidencias

B4 ® 4
coincidencias

B5 ® 4 coincidencias

Con lo cual los países con mayor
poder de decisión (al menos en esta reunión) son
los integrantes del bloque 1: España, Italia, Portugal,
Grecia

H) T es un árbol y v una hoja de T
T) T – v es un árbol

D / Por absurdo

Si se parte del supuesto que : T
es un árbol , v es una hoja de T y T –
v no es un árbol, podría darse de acuerdo a
la última afirmación dos casos:

Si esto se diera T también
admitiría ciclo con lo cual T no sería
árbol. Absurdo pues contradice el primer
supuesto.
T – v admite ciclo
T – v no es conexo

Si esto se diera querrá decir que
entre dos vértices distintos s y t (s, t ≠ v) no
habrá camino que no contenga a v. Ahora bien como T es
conexo, entre s y t habrá camino que contiene
necesariamente a v (puede considerarse camino simple): (s,….u,
v, k…..,t), con lo cual v no sería hoja debido a g(v)
> 1 (se muestra
aquí que es adyacente al vértice u y k).
Absurdo pues contradice el segundo supuesto.

c. Es posible

Si se tiene en cuenta que para cada valor
de a y b:

cl((a, b)) = { (x, y) Î R2 / 4.a
–b = 4.x – y} =

= { (x, y) Î R2 / y = 4.x + (b –
4.a)}

(rectas con pendiente 4 (paralelas) y
ordenada al origen ( b – 4.a))

para determinar dos clases disjuntas
entre sí, bastará con elegir dos pares ordenados
que pertenezcan a dos rectas diferentes. Por ejemplo:

cl ((0, 1)) ® y = 4.x + 1 y cl ((1,
0)) ® y
= 4.x – 4

a. La opción correcta es la
2

Si se considera los conjuntos

M = { x / x es mamífero}

A = {x / x es animal acuático}

C = {x / x es carnívor}

La afirmación i. no se infiere
necesariamente .Podría ocurrir lo planteado en el
diagrama de Venn indicado a continuación
La afirmación ii. no se infiere
necesariamente .Podría ocurrir lo planteado en el
diagrama de Venn indicado a continuación
Teniendo en cuenta cualquiera de las consideraciones
anteriores la afirmación iii. no se infiere
necesariamente

b. La opción correcta es
3.

Dado que sólo hay 6 asientos se podrán
sentar personas y
como la disposición es circular, a su vez cada grupo de
personas (interesan las posiciones relativas) se podrá
ubicar de (6 –1)! = 5! =120 formas diferentes.

Por ende el número total de ubicaciones
será: 210.120 = 25.200

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

1. ¿De cuántas maneras diferentes
se podrán ubicar "todas" las cifras desde el 1 hasta el 7
en el siguiente esquema:

a. 823,543

b. 5040

c. 840

d. 35.280

2. El número de soluciones enteras de la
ecuación a + b + c + d + e = 45 con a, b, c, d, e > 0
es :

a. b.
c. d.

3. En un torneo se jugaron (parejas) en total 524
partidos y se sabe además que hubieron 2 ruedas. En la
primera jugaron todos contra todos y en la segunda jugarán
los 8 mejores. ¿Cuántos
participarán?

a. 22 b. 516 c. 32 d.
254

4. El razonamiento: Todos los Ingenieros en
Sistemas son
especialistas en programación . Los escritores son bohemios.
Joaquín es Ingeniero en Sistemas. Ningún bohemio es
especialista en programación.

Por lo tanto Joaquín no es escritor.

a. Válido b. Inválido
c. A veces válido d. A veces
inválido

5. Indicar la proposición equivalente a :
"No es el caso que: el peso se devalúe y no se de un
proceso
inflacionario".

a. El peso se devalúa o no se da un
proceso inflacionario.

b. No se devalúa el peso o se da un
proceso inflacionario.

c. No se devalúa el peso o no se da un
proceso inflacionario.

d. El peso se devalúa y no se da un
proceso inflacionario.

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

a.
b.

c. d.

7. con x + y = [x, y], x ● y = (x, y) y = n : x para el valor de n
indicado :

a. n = 50 b. n = 348 c.
99 d. 1155

8. Sea S = { (1,0,1,0); (0,0,0,0); (1,0,1,1);
(1,0,0,0)} con S Í {0, 1}4 .

La expresión reducida, en término de suma
de productos, de la función booleana que toma el valor 1
en el conjunto S y 0 en el resto resulta ser:

a. b. c. d.

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

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

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

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

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

10. La ecuación 66.x º 48 (módulo 248)
admite exactamente (en término de clases):

a. 0 soluciones b. 1 solución
c. 2 soluciones d. 3 soluciones

11. El máximo común divisor y el
mínimo común múltiplo entre 2.n + 1 y 2. n +
2 (cualquiera sea el natural n) son respectivamente:

a. 1 y 2 b. n + 1 y n + 2 c. 1 y 4.
n2 + 6.n + 2 d. n + 1 y n + 2

12. El menor número que al ser dividido
por 7, 11 y 13 en cada caso genera un residuo máximo
resulta ser igual a :

a. 1001 b. 1000 c. 91 d.
90

13. El conjunto cociente correspondiente a la
relación de equivalencia definida en R2
:

(a, b) R (c, d) sii a + 3.b = c + 3.d
resulta ser:

a. {cl ((0, x))/ x ≦ 0} b. {cl (x)/
x ≥ 0} c. {cl (( x, 0))/ x ∈ R} d. {cl ((x,
0)) / x ≥ 0}

14. Dada una relación de equivalencia R y
una relación de orden S definidas en un conjunto A,
resulta lo indicado:

a R ⋂ S es antisimétrica bR
⋃ S es simétrica c. R ⋂ S es
simétrica d. R ⋃ S es transitiva

15. Es posible ordenar el conjunto A = {a, b, c,
d, e, f} de modo tal que:

a. Admita un subconjunto bien ordenado con al
menos dos pares de elementos incomparables .

b. Esté totalmente ordenado y admita
exactamente dos maximales

c. Esté bien ordenado y admita elementos
incomparables

d. Esté totalmente ordenado y admita al
menos dos minimales

16. El conjunto ordenado (N2, R) con
(a, b) R (c, d) sii a | c y b | d satisface lo
indicado:

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

c. No está bien ordenado d.
Carece de cotas inferiores

17. La relación S definida en Z : x S y
sii x + y es un número par, resulta ser:

a. de orden pero no de equivalencia b. de
equivalencia pero no de orden

c. ni de orden ni de equivalencia d. de
orden y de equivalencia

18. El conjunto P resulta ser partición de
A:

a. P = , A = Z

b. P ={A1, A2
} A1 = { (x, y) / x > 0}, A2
= { (x, y) / x < 0}, A = R2

c. P ={A1, A2
,A3 }, A1 = {3.x + 1 /
x ∈ Z}, A2 ={3.x + 2 / x ∈ Z} ,
A3 = ={3.x / x ∈ Z}, A =Z

d. P ={A1, A2 }
A1 = { (x, y) / y > 0}, A2 = {
(x, y) / y < 0}, A = R2

19. Se quiere construir una red de ordenadores: a,
b, c, d, e, f, y g . En la tabla se indica el coste de construcción de las líneas de
transmisión para conectar algunos pares de
ellos.

Para minimizar los costos se
habilitarán las líneas indicadas

	a	b	c	d	e	f	g
a	–	5	4	–	5	5	–
b		–	3	3	–	–	–
c			–	1	2	–	–
d				–	3	–	2
e					–	6	2
f						–	7
g							–

20. El digrafo indicado

Euleriano y acíclico
Euleriano y k – regular
Isomorfo al dígrafo

d. Euleriano o fuertemente conexo

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

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
La cantidad de funciones booleanas distintas f :
{0,1}5 ® {0,1} formadas por más de un
minitérmino es:
La cantidad total (T) de formas de completar este
examen y la cantidad de formas con las que se aprueba (A)
son:

T = 415
A =

T = V ’4,15

A = ·
46

T = 415

A =

T = 15 · C4,1

A = 9 · C4,1

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 =

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.
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.
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.
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.
Sea A = {a,b,c,d} , (P(A), Í ) es un Algebra de Boole
isomorfa a (Dn, ½ ) siendo n:
En toda Algebra de Boole, " y: " x: " z se cumple lo indicado:

La respuesta correcta es la A

JUSTIFICACION:

Como x z Ù
x `
z Þ
x + z = z Ù x +` z = ` z Þ
Þ (
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.
en ( D30 , ½ ) siendo 0A = 1 tomando
x = 2 Ù
y = 3,
2 · 5 = 1 Ù 3 · 5 = 1 pero no se cumple el
consecuente.
también en ( D30 ,
½ ) tomando x
= 2 Ù y
= 3 Ù z
= 5, se cumple que x · z y · z ya que
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

Dadas dos relaciones R y S definidas en un conjunto
A, si R y S son de orden entonces también lo
es:
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
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 }
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:
Dadas las siguientes proposiciones:

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

Son verdaderas:

a) i y iii

b) i y ii

c) i, ii y iii

d) ii

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.

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)

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}

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.
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
En Z – {0} de a | r y a | s se desprende
necesariamente lo indicado:
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:

a) igual a 2

b) menor que 3

c) igual a 3

d) distinta de 1

e) ninguna

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).

Partes: 1, 2, 3

Página anterior

Volver al principio del trabajo

Página siguiente