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