Parciales de Matemática discreta

Primer parcial de Matemática discreta, abril de 2003, tema 1

1) Probar, usando inducción matemática que la siguiente propiedad relativa al conjunto de los números naturales:

2) Estudiar las propiedades de la relación  definida en el conjunto Q -{0} de la forma que se da a continuación: a b Û a· b<0. Si es de equivalencia, hallar las clases de equivalencia y el conjunto cociente, si es de orden, indicar su es total o parcial.

3) Demostrar que un Álgebra de Boole (B; Ù ;Ú ) se verifica: (x’ Ù y’)’= x Ú y (el elemento con prima es el complemento del correspondiente sin prima). Para la expresión booleana f(x;y) = x Ú y, se pide dar la normal disyuntiva completa.

4) En el conjunto A={1,2,5}se define la relación § por:

a§ b = "resto de la división de a por b", se pide indicar si es cerrada en el conjunto A, estudiar las propiedades e indicar los elementos notables.

Primer parcial de matemática discreta, abril de 2003, tema 2

1) Probar, usando inducción matemática, la siguiente propiedad relativa al conjunto de los números naturales:

2) En el subconjunto {0,1}³, estudiar la relación  :

" {a1; b1; c1} Î {0,1}³, " {a2; b2; c2} Î {0,1}³: {a1; b1; c1}Â {a2; b2; c2}Û c1 = c2

Si la relación de equivalencia, hallar clases y conjunto cociente, si es de orden indicar si el conjunto queda totalmente ordenado por  .

3) En el conjunto  de los números reales, se define la operación binaria ª , de la forma que se da a continuación:

Se pide:

1. Indicar si es cerrada en el conjunto dado
2. Estudiar las propiedades
3. Analizar si hay elemento neutro

   4) Analizar el valor de verdad de cada una de las siguientes proposiciones. Si son verdaderas probarlas, si son falsas dar un contraejemplo:

   1. Todo conjunto finito y acotado tiene un último elemento.
   2. Si K es cota superior de B Í A, A es un conjunto ordenado, entonces K siempre es un elemento de B.
4. Si corresponde, enumerar los elementos que tienen simétricos

Primer parcial de Matemática discreta, Septiembre de 2003, tema 1

1) Demostrar, usando inducción matemática, que para cualquier número natural:

2) Sabiendo que la operación © definida por la tabla que se da a continuación es asociativa en el conjunto A={1,2,3,4,5,6}, estudiar la conmutatividad, existencia de neutro e indicar los elementos que tienen simétrico.

3) En el conjunto  de los números reales, se define la siguiente relación:

a b Û a = b Ú a * b = -6. Indicar, justificando, si es de equivalencia o de orden. Si es de equivalencia hallar el conjunto cociente, si es de orden decir si es total.

4) Considerar el conjunto A={1,2,3,9,4,8,16,25,32,64,27,81}ordenado por a b Û "a es divisor de b". Hacer el diagrama de Hasse y hallar maximales y minimales. Considerar B={9,8} y hallar las cotas superiores e inferiores.

Primer parcial de Matemática discreta, octubre de 2003, tema 2

1) Si el máximo común divisor entre 2540 y b es 120, y el mínimo común divisor es 1.584.000, se pide dar el valor de b.

2) Estudiar las propiedades de la relación  definida en Z-{0} de la forma que se da a continuación: a b Û a|b Ù b|a. Si es de equivalencia hallar las clases de equivalencia, si es de orden indicar si es parcial o total.

3) Sea M la matriz booleana asociada a la relación R, y L la asociada a la relación S.

Se sabe que R Í S y que R es reflexiva, se pide calcular:

M Ù N; M Ú L; M Ú L; M Ù N; L Ú N; I Ú L

4) Sabiendo que la operación © definida por la tabla contigua es asociativa en el conjunto A={1,2,3,4,5,6} estudiar la conmutatividad, existencia de neutro e indicar

los elementos que tienen simétrico.

Primer parcial de Matemática discreta, octubre de 2003, tema 1

1) Para la siguiente relación de recurrencia, se pide hallar la solución general y una solución particular para las condiciones iniciales dadas.

2) Sean las relaciones  y ¦ definidas en A={xÎ Z / |x| < 5}

a b Û aº b(3); a¦ b Û (a|b Ù b|a) Ú (a=b=0), se pide:

1. Escribir ambas relaciones por extensión.
2. Indicar las propiedades; si son de equivalencia escribir el conjunto cociente.

   3) Sea la operación a§ b = (a+b)/2

   1. ¿Es una operación binaria cerrada en {enteros pares}?
   2. ¿Es una operación binaria cerrada en Q?
   3. En caso que la respuesta sea afirmativa, indicar si es asociativa, conmutativa, existencia de neutro, de simétrico, elementos idempotentes y elementos absorbentes.
3. Encontrar ¦ È Â y decir si es relación de equivalencia y hallar el conjunto cociente.

4) La siguiente tabla fue llenada parcialmente y corresponde a la operación Ù de una red. Se pide completarla, definir la operación Ú , hacer el diagrama de Hasse, indicar los átomos y, si es posible, complemento de cada elemento:

Primer parcial de Matemática discreta, octubre de 2003, tema 2

1) Probar, usando inducción matemática, la siguiente propiedad relativa al conjunto de los números naturales:

2) En el conjunto R de los números reales, se define la siguiente relación ¦ :

a¦ b Û a = b Ú a * b = 5. Estudiar sus propiedades, si es de equivalencia hallar las clases de equivalencia y el conjunto cociente, si es de orden indicar si es total o parcial.

3) Estudiar las propiedades de la operación © definida en el conjunto Z de los números enteros de la siguiente forma: a© b = a – 2ba. Indicar si hay neutro y si hay elementos que tengan simétrico.

4) Hallar la forma normal disyuntiva (forma canónica en minitérminos) de la función booleana f(x1,x2,x3) = {[(x1’Ù x2)Ú x3] Ù x2} donde el elemento con prima es el complemento del elemento sin prima.

Primer parcial de Matemática discreta, abril de 2004, tema 1

1)

Es la solución de una relación de recurrencia. Se pide reconstruir la relación, clasificarla, dar la ecuación característica y dar las condiciones iniciales. Asimismo definir otra relación de recurrencia cuya solución tenga la misma ecuación característica.

2) En el conjunto N de los números naturales, se define la relación  como se da a continuación: a b Û "p divide a (a² – b²)", pÎ Z.

Se pide probar que la relación es de equivalencia, dar las clases de equivalencia y la partición que determina en el conjunto donde está definida.

3) En el conjunto Z, de los números enteros, se define la siguiente operación binaria:

4) Para la función dada, simplificar y hallar el diagrama de compuertas correspondiente:

f(x1, x2, x3) = (x1 Ù x2 Ù x3) Ú (x1 Ù x2’ Ù x3’) Ú (x1 Ù x2 Ù x3’), el elemento con prima indica el complemento del correspondiente sin prima.

Primer parcial de Matemática discreta, abril de 2004, tema 2

1) Aplicando inducción matemática, demostrar la siguiente propiedad relativa al conjunto de los números naturales:

2) En el conjunto Z de los números enteros, se define la siguiente relación  :

Probar que es una relación de equivalencia, que no se cumple la propiedad antisimétrica y hallar la partición que determina Z.

3) Considerar el conjunto de los divisores positivos de 24, D24, definir la operación § por

a § b = "mínimo común múltiplo entre a y b", definir la tabla de la operación, sabiendo que es asociativa, estudiar si es conmutativa, si es idempotente, si tiene neutro y si hay elementos con simétrico.

4) Para el conjunto del ejercicio anterior, se pide ordenarlo por la relación de divisibilidad, hacer el diagrama de Hasse, indicar el primer y último elemento, la menor de las cotas superiores y la mayor de las cotas inferiores.

Primer parcial de Matemática discreta, febrero de 2005

1) Probar, usando inducción matemática, la siguiente propiedad relativa al conjunto de los números naturales:

2) En el conjunto de los números enteros se define la relación  tal que:

x y Û x²-y² = 4 (x-y)

1. Demostrar que es de equivalencia
2. Hallar la clase de equivalencia en un entero cualquiera p

   3) En el conjunto Q x Q-{0} considerar la operación &uml; definida por (x;y) ¨ (z;t) = (x+yz;yt)

   1. Indicar si se trata de una operación binaria cerrada

      4) Considere el conjunto A={1; 2; 3; 4; 5; 6; 7}ordenado por la relación R = {(1;5);(2;5); (3;5);(4;5);(6:5);(7;5);(1;2);(1;3);(1;4);(6;1);(1;7);(6;2);(6;4);(6;3);(6;7);(2;3);(4;3);(4;7)}

      1. Construya el diagrama de Hasse
      2. Encuentre elementos máximos, mínimos, elementos maximales, elementos minimales y átomos, según corresponda.
      3. ¿Está A totalmente ordenado? ¿Está bien ordenado?
      4. Para el subconjunto B={1;3;4;7}encuentre cotas inferiores y superiores, supremo e ínfimo.
      5. Indique los elementos maximales y minimales de B
      6. El conjunto A, ¿constituye una red? Justifique y en caso afirmativo construya la tabla de la operación "supremo" para dicha red
      7. Ídem para el subconjunto B
   2. Estudiar las propiedades y los elementos destacados.
3. Indicar el conjunto cociente

Examen final de Matemática discreta, febrero de 2005

1) Probar, usando inducción matemática, que

2) En el conjunto R de los Números Reales, se define la relación S de la forma que se da a continuación: xSy Û y – x Î Z, siendo Z el conjunto de los números enteros. Se pide estudiar las propiedades, si es de orden indicar si el conjunto queda totalmente ordenado, si es de equivalencia, dar las clases de equivalencia, el conjunto cociente y graficar.

3) Sea (G, *) un grupo con neutro e. Probar:

a) Si x * x = e, " nÎ G, entonces el grupo es abeliano.

b) Si H Í G, demostrar que H es subgrupo de G Û

b1) H ≠ Æ

b2) Si x,y Î H Þ x * y’ Î H

4) Sea G = (V;A;j ) un grafo no conexo con k componentes conexas. Si |V| = n, |A| = m.

Probar o refutar con un contraejemplo, n £ m + k

5) Demostrar o refutar cada una de las siguientes afirmaciones:

a) A = BÞ A D B = Æ

b) Para el conjunto A = {§ , ¨ , © }, la operación * según la tabla, es conmutativa, tiene neutro y cada elemento tiene simétrico.

c) El autómata finito AF = ({q0, q1, q2}; {D , o , ð }; d ; q0; {q2}) es determinístico e interpreta el lenguaje L = D o o (ð o )*