Examen Parcial - 61.07. Matemática Discreta - 29/10/2011

Cátedra: Todas
Fecha: 1ra Oportunidad - (2do Cuatrimestre) 2011
Día: 29/10/2011

1. Sea la sentencia, definida en Z ”” . ¿Cuál es el valor de verdad de:
   1. 
   2. 
   3. 
   4. ?
2. Utilizando cuantificadores y predicados con una variable, exprese:
   1. Hay un estudiante de esta clase que no tiene teléfono celular.
   2. Todo estudiante de Ingeniería Informática necesita un curso de Matemática Discreta.

Si , se llama cadena ternaria de longitud , a una n-upla que sólo contiene los números 0,1 y 2.

1. Determinar la relación de recurrencia para una sucesión (). donde es la cantidad de cadenas ternarias de longitud que no poseen dos ceros consecutivos. Determine, también, los valores iniciales.
2. Resolver la dada en 1).
3. Calcular, utilizando lo obtenido en 2), .

Demostrar, utilizando el principio de inducción, que en un conjunto de elementos hay subconjuntos de exactamente dos elementos, si . Exprese claramente cual es la proposición que debe probar.

1. Probar, sin utilizar la noción de átomo, que no existe un álgebra de Boole que tenga exactamente tres elementos.
2. Hallar la forma normal disyuntiva de la función booleana dada por:
   

y representarla en un circuito que tenga solamente compuertas NAND (con sólo dos entradas).

Si , se define en las siguientes relaciones:

1. Determinar si son relaciones de orden o de equivalencia.
2. Para todas las que sean relación de equivalencia, hallar todas las clases y cuántos elementos tiene cada una.
3. Para todas las que sean relación de orden, hallar todos los elementos particulares de