Download Ejercicio nº1 En el conjunto de los números naturales se define la

Ejercicio nº1 En el conjunto de los números naturales se define la siguiente
relación:
aRb  3 a+4 b= 7n, n entero. Probar que es una relación de equivalencia, dar
las clases de equivalencia y el conjunto cociente.
SOLUCIÓN
" a Î N : 3a + 4a = 7n Þ aRa, reflexiva
aRb Û 3a + 4b = 7n Þ 4b + 3a = 7n Þ bRa,simétrica
aRb Ù bRc Û 3a + 4b = 7nÙ 3b + 4c = 7m, (a, b, c son naturales, n, m son enteros
Es de equivalencia
Las clases:
ì
ü
7n - 3a
/ 4divida a bïý
[a ]= {b Î N / aRb}= ïí b =
4
ïï
îïï
þ
Conjunto cociente es el conjunto de las clases: N/R=U[a ]/ a Î N
Para entenderlo veamos algunas clases:
ì
7n - 3.1ü
ïý recorriendo los n,haciendo las cuentas y viendo cuando
[1]= ïí b =
ïîï
4 ïþ
ï
se consigue un múltiplo de 4, en este caso quedan ( algunos ejemplos):
[1]= {1,8,15....}, [2]= {2,9,16...}
Ejercicio nº2 Para el grupo aditivo (Z18; ) se pide: dar sus generadores;
considerar el conjunto INV Z18 y probar que es un grupo bajo la multiplicación ,
dar todos los subgrupos y el índice que cada uno determina en el grupo, dar su
red. Indicar si el grupo multiplicativo obtenido es isomorfo al grupo aditivo de
los restos módulo 6.
SOLUCIÓN
(Z
18
;+ )
Los generadores son los mismos que los inversibles para la multiplicación
de clases son {1,5, 7,11,13,17}
Sabemos que los inversibles de un semigrupo (Z18 ;.)es un grupo ((Z18 toma
la misma estructura que (Z;.) que es asociativa, tiene neutro pero no todos
tienen inverso). Todo eso por el teorema fundamental de compatibilidad
Si se hace la tabla de multiplicar en Z18 queda :
1
.
1
5
1
5
1
5
5
7 11 13 17
7 11 13 17
7 17
1 11 13
7 7 17 13 5 1 11
11 11 1 5 13 17 7
13 13 11 1 17 7 5
17 17 13 11
7
5
1
Se ve que
1¢= 1(es el neutro)
5¢= 11
7 ¢= 13
De ahí sabemos los simétricos de 11,13
Falta el de 17, pero como ese conjunto tiene un número par de
elementos el simétrico de 17debe ser 17
Veamos los subgrupos:
1 = {1}
5 = {7,17,13,11,1,5}
7 = {7,13,1}
17 = {17,1}
son todos los subgrupos, los simétricos generan lo mismo
No dibujo la red.
Veamos que pasa con Z6 ( con la +de clases), no hago la tabla pero si los subgrupos:
0 = {0}
1 = {0,1, 2,3, 4,5}
2 = {4, 2, 0}
3 = {3, 0}
En ambos casos tenemos: 1 subg. de orden 1, 1 subg. de orden 2, 1 subg. de orden 3,
1 subg. de orden 6
Los dos son cíclicos con 2 generadores, tiene la misma forma de red si hacemos una f
De la forma siguiente: F: Z6 INVZ18/
F(0) = 1
F(1)=5
F(5)=11
F(2)=7
2
F(3) = 17
F(4)=13
Eso es el isomorfismo pedido, por ejemplo:
F(1+2) = F(1).F(2)
F(3) = 5.7 es decir (35 e Z18 para la multiplicación es 17)
F(3)= 17
Ejercicio nº3 Para el grafo cuyo diagrama se da a continuación, se pide:
Se pide:
3.1Las matrices de adyacencia e incidencia
3.2 Indicar, justificando, si es bipartito. Si la respuesta es afirmativa exhibirlo y
justificar, en otro caso dar un subgrafo con el mayor número de vértices que lo
sea
3.3 Dar todos los puentes e istmos del grafo original
SOLUCIÓN
3.1 no tuvieron problemas
3.2 no es bipartito puede encontrarse un subgrafo que lo sea
3.3no hay istmos ni puentes
Ejercicio nº4
Si G =  V;A;φ es un bosque con V = n, k componentes, se dar ( justificando) el número de aristas.
SOLUCIÓN
La fácil es A= V- 1 en un árbol
Tengo k árboles, por lo tanto A= V- k . Eso por inducción
Ejercicio nº5 Dar el valor de verdad de las siguientes proposiciones, si son
verdaderas probarlas, en otro caso justificar
-
La solución general de la relación de recurrencia:
a n + a n-1 - 6a n-2 = 0 con a 0 = 1, a1 = 3 es:
6
1
n
a n = 2n +  -3
5
5
3
-
La red de los divisores positivos de 12 , ordenada por la divisibilidad es una
red distributiva y complementada
Una operación binaria y cerrada en un conjunto A asigna, por lo menos , un
elemento a cada par ordenado de AA
En un álgebra de Boole hay elementos que son su propio complemento
Si R y S son relaciones definidas en A tales que R  S  R -1  S-1
Si a, b = m ⇒ m a ∧ m b
Un conjunto A está totalmente ordenado por R si y solamente si está bien
ordenado por R
SOLUCIÓN
1. La solución que se da es una particular por lo tanto es FALSO que sea la
solución general
2. 12= 22.3, no es un producto de primos distintos y tiene 6 elementos, luego
no es complementada, no es álgebra de Boole
3. Una operación binaria y cerrada asigna sólo un elemento a cada par (a;
b)( es función no se cumpliría la unicidad)
4. FALSA se cumple la idempotencia , no puede ser NUNCA su propio
complemento
5. VERDADERA
(x;y)  R-1  (y;x)  R (y;x)  S (x;y)  S-1
Partimos de la primera parte de la tesis, usamos la definición de relación
inversa, usamos la hipótesis y nuevamente la definción de inversa
4