Examen (Parcial) - 61.07. Matemática Discreta

Examen (Parcial) - 61.07. Matemática Discreta

Cátedra: todas
Fecha: 1er Oportunidad - (1er Cuatrimestre) 2008
Día: 31/05/2008

Esta página está incompleta; podés ayudar completando el material.

Enunciado

1 Sea $<tex>A</tex>$ un conjunto y $<tex>R</tex>$ una relación de orden en $<tex>A</tex>$ que tiene la siguiente propiedad: “Para todo par de elementos $<tex>a,b \in A</tex>$ siempre existen: $<tex>sup\{a,b\}</tex>$ y $<tex>inf\{a,b\}</tex>$ ”
Probar que son equivalentes:
a) $<tex>a_{0} = max(A)</tex>$
b) Para todo $<tex>x \in A</tex>$ se tiene $<tex>sup\{x,a_{0}\} = a_{0}</tex>$
c) Para todo $<tex>y \in A</tex>$ se tiene $<tex>inf\{y,a_{0}\} = y</tex>$

2 Se define en $<tex> N X \{ k \in Z: \mid k\mid\leq 7\}</tex>$ la siguiente relación $<tex>R</tex>$ : $<tex>(a,b)R(c,d) \leftrightarrow ((a-c)</tex>$ es múltiplo de $<tex>5) \wedge (\mid b\mid =\mid d\mid)</tex>$
a) Probar que $<tex>R</tex>$ es una relación de equivalencia.
b) Hallar: $<tex>cl((4,0))</tex>$ y $<tex>cl((3,-3))</tex>$
c) ¿Cuantos elementos tiene el conjunto cociente?

3 Sea $<tex>B</tex>$ un algebra de Boole.
a) Pruebe que: $<tex> x\bar y = 0 \leftrightarrow xy = x</tex>$
b) Enunciar y probar la propiedad dual de la del item a.
c) Demostrar que para todo $<tex>x \in B</tex>$ se tiene $<tex>x\neq \bar x</tex>$ .

4 Dada la función booleana: $<tex>f(x,y,z) = x+(\bar y +(x\bar y + x\bar z))</tex>$
a) Encontrar su forma normal disyuntiva.
b) Simplificarla algebraicamente.
c) Hallar un circuito que la represente utilizando solo compuertas NAND.

5 a) Enunciar el principio de inducción.
b) Probar, usando el principio de induccion, que en toda fila de dos o más personas, si la primera es una mujer y la última un varón, en algún lugar de la fila hay una mujer y un varón consecutivos.

Resolución

Punto III

a) Pruebe que: $<tex> x\bar y = 0 \leftrightarrow xy = x</tex>$
Primero pruebo que $<tex> x\bar y = 0 \rightarrow xy = x</tex>$
Entonces $<tex> x\bar y = 0 </tex>$ es mi hipótesis , y $<tex> xy = x </tex>$ es mi tesis.
$<tex> x\bar y = xy\bar y = x(y\bar y) = x\cdot0 = 0 </tex>$ y queda demostrado que $<tex> x\bar y = 0</tex>$

Ahora debo probar que $<tex> x\bar y = 0 \rightarrow xy = x</tex>$
$<tex> xy = xy + (x\bar x ) = \overline{ \overline{ xy + (x\bar x ) } } </tex>$ $<tex> = \overline{ \overline{xy}\cdot \overline{x\bar x} } = </tex>$ $<tex> \overline{ (\bar x + \bar y ) \cdot (\bar x + x) } = \overline{ \bar x\cdot (\bar x + \bar y) + x\cdot (\bar x + \bar y) } = </tex>$
$<tex> \overline { (\bar x + \bar y \cdot \bar x) + x\bar y } </tex>$ por hip. $<tex> x\cdot \bar y = 0</tex>$ y por ley de absorción $<tex> (\bar x + \bar y \cdot \bar x) = \bar x </tex>$ entonces:
$<tex> \overline { \bar x + 0} = \overline { \overline {x}} = x </tex>$
Entonces queda demostrado $<tex> x\bar y = 0 \leftrightarrow xy = x</tex>$

b) La propiedad dual se obtiene reemplazado los +/. por ./+ y los 0 por 1, con lo que nos quedaría:
$<tex> x + \bar y = 1 \leftrightarrow x + y = x</tex>$
Al ogual que antes debemos probar ambos sentidos de la condición.
Considero como hipótesis $<tex> x + \bar y = 1 </tex>$ y trato de probar mi tesis $<tex>x + y = x</tex>$
$<tex> x+y = (x+y)\cdot (x+\bar x ) = x\cdot (x+y) + \bar x \cdot (x+y) </tex>$ , por ley de absorción $<tex>x + xy = x</tex>$ entonces:
$<tex> x+y\bar x = \overline { \overline {x+y\bar x}} = \overline { \bar x \cdot \overline {y\bar x} } = </tex>$
$<tex> \overline {\bar x \cdot (\bar y + x) } </tex>$ , por hip. $<tex>x + \bar y = 1</tex>$ , entonces:
$<tex> \overline {\bar x \cdot 1} = \overline { \overline {x}} = x </tex>$ , queda demostrado $<tex>x + \bar y = 1 \rightarrow x + y = x</tex>$

Ahora pruebo $<tex> x +y = x \rightarrow x + \bar y = 1 </tex>$
$<tex> x+ \bar y = x+y+\bar y </tex>$ , por ley de inversos $<tex>y+ \bar y = 1</tex>$ , entonces:
$<tex> x + 1 =1 </tex>$ y demostre que $<tex> x +y = x \rightarrow x + \bar y = 1 </tex>$ .
Queda así demostrado: $<tex> x + \bar y = 1 \leftrightarrow x + y = x</tex>$

Discusión

Si ves algo que te parece incorrecto en la resolución y no te animás a cambiarlo, dejá tu comentario acá o envíame un PM.