Tabla de Contenidos

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.