02-08-2018, 22:55
Hola, traigo el final de Discreta que se tomó en la última fecha de invierno (01/08/2018)
[attachment=16716]
Resolución: [attachment=16748]
Si alguien me puede ayudar con lo que no pude hacer les agradezco.
[attachment=16716]
Resolución: [attachment=16748]
Spoiler: Mostrar
Ejercicio 1:
1.1) Existe más de un isomorfismo entre ambos ya que existen infinitas formas de representar un grafo 3-regular como G1 y G2.
1.2) Acá hay que considerar cada una de las funciones como preposiciones.
Acá la clave es decir que estás usando particularización, sino te lo consideran inválido. Entonces si usamos la equivalencia del condicional nos queda
\[(p \vee q ) \wedge (q \Rightarrow r) \wedge (\sim r)\Leftrightarrow (p \vee q) \wedge (\sim q \vee r) \wedge (\sim r)\]
Luego, si consideramos cada una de las preposiciones como verdaderas nos queda que
\[V(\sim r) = V \Rightarrow V®=F\]
\[V(\sim q \vee r) = V \Rightarrow V(\sim q)=V \Rightarrow V(q)=F\]
\[V(p \vee q) = V \Rightarrow V(p)=V\]
Entonces, tanto C1 como C2 son verdaderas.
Ejercicio 2:
2.1)
El autómata finito es determinístico porque tiene como máximo un cambio de estado por cada letra del alfabeto
2.2) Recuerden que cada lenguaje tiene una sola expresión regular. Como se puede ir por el bucle de q2 o ir y volver de q1 a q2, la expresión regular correcta es 0*11(1 + 01)*
Ejercicio 3:
3.1) Lo hice todo mal
3.2) Acá el truco está en pensar a la suma como supremo y el producto como ínfimo. Entonces queda como
\[(A, \vee, \wedge) : a \wedge \overline{b} \preceq c , a\vee c=1_A\]
Luego, por definición de Álgebra de Boole,
\[c= \overline{a} \wedge a= \overline{c}\]
Ejercicio 4: No me acordaba como era el producto de matrices, FUFUFU!!!
Ejercicio 5:
5.1) Vamos a simplificar la ecuación
\[112 x \equiv 392(91) \]
\[\Leftrightarrow 21 x \equiv 28 (91)\; (porque \; 112 \equiv 21 (91) \; y \; 392 \equiv 28 (91)) \]
\[\Leftrightarrow 3.7 x \equiv 4.7 (7.13) \]
\[\Leftrightarrow 3 x \equiv 4 (13)\]
Bueno, ya está simplificada. Ahora, ¿tiene solución? Si, porque cumple con la condición necesaria y suficiente, que es (3:13)= 1 y 1|4.
El tema es que esto es para la ecuación simplificada. Si volvemos a la ecuación original, (112:91)= 7 y 7|392 porque 392 = 2^3 . 7^2.
Entonces, la ecuación tiene 7 soluciones, que siguen la forma
\[X= 10+ 91.k ,\; 0 \leq k < 7 \Rightarrow X = 10,\; 101,\;192,\;283,\;374,\;465,\;556\]
5.2) Tenemos que calcular el resto de dividir 1564628 por 23, es decir, a qué es congruente 1564628 módulo 23.
Primero, 23 es número primo. Entonces, podemos aplicar el Pequeño Teorema de Fermat, que dice que
\[\forall x \epsilon Z, \; x^{23-1} = x^{22} \equiv 1 (23)\]
Además, 1564628 = 22 . 71119 + 10.
Entonces,
\[5^{1564628 }= 5 ^{22\;. 71119 +10} \]
\[ = (5^{22})^{71119} . 5^{10} \]
\[ \equiv 1^{71119} . 5^{10} (23) \]
\[ = 1.\; (5^{2})^{5} \]
\[ \equiv 1.2^5 (23) \]
\[ \equiv 1.9(23) \]
\[ 5^{1564628 } \equiv 9 (23)\]
Entonces, por definición de congruencia, el resto de dividir 1564628 por 23 es 9.
5.3) Hay que demostrar por inducción
\[\forall n \epsilon N, n \geq 4, \; 2^n< n!\]
demostración:
n=4
\[2^4 < 4! \Rightarrow 16 < 24\]
n=5
\[2^5 < 5! \Rightarrow 32 < 120\]
caso inductivo:
\[\forall n \epsilon N, n \geq 4, \; 2^n< n! \Rightarrow 2^{(n+1)} < (n+1)! \]
\[ 2^{(n+1)} = 2^n.\;2 \]
\[< n! \; . \; 2 \; (hip\acute{o}tesis \; inductiva) \]
\[ < n! \; . \; (n+1) \; (n \geq 4) \]
\[ = (n+1)! \; (definici\acute{o}n \; de \; factorial) \]
\[ \Rightarrow 2^{(n+1)} < (n+1)!\]
1.1) Existe más de un isomorfismo entre ambos ya que existen infinitas formas de representar un grafo 3-regular como G1 y G2.
1.2) Acá hay que considerar cada una de las funciones como preposiciones.
Acá la clave es decir que estás usando particularización, sino te lo consideran inválido. Entonces si usamos la equivalencia del condicional nos queda
\[(p \vee q ) \wedge (q \Rightarrow r) \wedge (\sim r)\Leftrightarrow (p \vee q) \wedge (\sim q \vee r) \wedge (\sim r)\]
Luego, si consideramos cada una de las preposiciones como verdaderas nos queda que
\[V(\sim r) = V \Rightarrow V®=F\]
\[V(\sim q \vee r) = V \Rightarrow V(\sim q)=V \Rightarrow V(q)=F\]
\[V(p \vee q) = V \Rightarrow V(p)=V\]
Entonces, tanto C1 como C2 son verdaderas.
Ejercicio 2:
2.1)
El autómata finito es determinístico porque tiene como máximo un cambio de estado por cada letra del alfabeto
2.2) Recuerden que cada lenguaje tiene una sola expresión regular. Como se puede ir por el bucle de q2 o ir y volver de q1 a q2, la expresión regular correcta es 0*11(1 + 01)*
Ejercicio 3:
3.1) Lo hice todo mal
3.2) Acá el truco está en pensar a la suma como supremo y el producto como ínfimo. Entonces queda como
\[(A, \vee, \wedge) : a \wedge \overline{b} \preceq c , a\vee c=1_A\]
Luego, por definición de Álgebra de Boole,
\[c= \overline{a} \wedge a= \overline{c}\]
Ejercicio 4: No me acordaba como era el producto de matrices, FUFUFU!!!
Ejercicio 5:
5.1) Vamos a simplificar la ecuación
\[112 x \equiv 392(91) \]
\[\Leftrightarrow 21 x \equiv 28 (91)\; (porque \; 112 \equiv 21 (91) \; y \; 392 \equiv 28 (91)) \]
\[\Leftrightarrow 3.7 x \equiv 4.7 (7.13) \]
\[\Leftrightarrow 3 x \equiv 4 (13)\]
Bueno, ya está simplificada. Ahora, ¿tiene solución? Si, porque cumple con la condición necesaria y suficiente, que es (3:13)= 1 y 1|4.
El tema es que esto es para la ecuación simplificada. Si volvemos a la ecuación original, (112:91)= 7 y 7|392 porque 392 = 2^3 . 7^2.
Entonces, la ecuación tiene 7 soluciones, que siguen la forma
\[X= 10+ 91.k ,\; 0 \leq k < 7 \Rightarrow X = 10,\; 101,\;192,\;283,\;374,\;465,\;556\]
5.2) Tenemos que calcular el resto de dividir 1564628 por 23, es decir, a qué es congruente 1564628 módulo 23.
Primero, 23 es número primo. Entonces, podemos aplicar el Pequeño Teorema de Fermat, que dice que
\[\forall x \epsilon Z, \; x^{23-1} = x^{22} \equiv 1 (23)\]
Además, 1564628 = 22 . 71119 + 10.
Entonces,
\[5^{1564628 }= 5 ^{22\;. 71119 +10} \]
\[ = (5^{22})^{71119} . 5^{10} \]
\[ \equiv 1^{71119} . 5^{10} (23) \]
\[ = 1.\; (5^{2})^{5} \]
\[ \equiv 1.2^5 (23) \]
\[ \equiv 1.9(23) \]
\[ 5^{1564628 } \equiv 9 (23)\]
Entonces, por definición de congruencia, el resto de dividir 1564628 por 23 es 9.
5.3) Hay que demostrar por inducción
\[\forall n \epsilon N, n \geq 4, \; 2^n< n!\]
demostración:
n=4
\[2^4 < 4! \Rightarrow 16 < 24\]
n=5
\[2^5 < 5! \Rightarrow 32 < 120\]
caso inductivo:
\[\forall n \epsilon N, n \geq 4, \; 2^n< n! \Rightarrow 2^{(n+1)} < (n+1)! \]
\[ 2^{(n+1)} = 2^n.\;2 \]
\[< n! \; . \; 2 \; (hip\acute{o}tesis \; inductiva) \]
\[ < n! \; . \; (n+1) \; (n \geq 4) \]
\[ = (n+1)! \; (definici\acute{o}n \; de \; factorial) \]
\[ \Rightarrow 2^{(n+1)} < (n+1)!\]
Si alguien me puede ayudar con lo que no pude hacer les agradezco.