====== 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 A un conjunto y R una relación de orden en A que tiene la siguiente propiedad: "Para todo par de elementos a,b \in A siempre existen: sup\{a,b\} y inf\{a,b\}" \\ Probar que son equivalentes: \\ a) a_{0} = max(A) \\ b) Para todo x \in A se tiene sup\{x,a_{0}\} = a_{0} \\ c) Para todo y \in A se tiene inf\{y,a_{0}\} = y \\ \\ **2** Se define en N X \{ k \in Z: \mid k\mid\leq 7\} la siguiente relación R:(a,b)R(c,d) \leftrightarrow ((a-c) es múltiplo de 5) \wedge (\mid b\mid =\mid d\mid) \\ a) Probar que R es una relación de equivalencia. \\ b) Hallar: cl((4,0)) y cl((3,-3)) \\ c) ¿Cuantos elementos tiene el conjunto cociente? \\ \\ **3** Sea B un algebra de Boole. \\ a) Pruebe que: x\bar y = 0 \leftrightarrow xy = x \\ b) Enunciar y probar la propiedad dual de la del item a.\\ c) Demostrar que para todo x \in B se tiene x\neq \bar x. \\ \\ **4** Dada la función booleana: f(x,y,z) = x+(\bar y +(x\bar y + x\bar z)) \\ 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: x\bar y = 0 \leftrightarrow xy = x \\ Primero pruebo que x\bar y = 0 \rightarrow xy = x \\ Entonces x\bar y = 0 es mi hipótesis , y xy = x es mi tesis.\\ x\bar y = xy\bar y = x(y\bar y) = x\cdot0 = 0 y queda demostrado que x\bar y = 0 \\ \\ Ahora debo probar que x\bar y = 0 \rightarrow xy = x \\ xy = xy + (x\bar x ) = \overline{ \overline{ xy + (x\bar x ) } } = \overline{ \overline{xy}\cdot \overline{x\bar x} } = \overline{ (\bar x + \bar y ) \cdot (\bar x + x) } = \overline{ \bar x\cdot (\bar x + \bar y) + x\cdot (\bar x + \bar y) } = \\ \overline { (\bar x + \bar y \cdot \bar x) + x\bar y } por hip. x\cdot \bar y = 0 y por ley de absorción (\bar x + \bar y \cdot \bar x) = \bar x entonces: \\ \overline { \bar x + 0} = \overline { \overline {x}} = x \\ Entonces queda demostrado x\bar y = 0 \leftrightarrow xy = x \\ \\ \\ b) La propiedad dual se obtiene reemplazado los +/. por ./+ y los 0 por 1, con lo que nos quedaría:\\ x + \bar y = 1 \leftrightarrow x + y = x \\ Al ogual que antes debemos probar ambos sentidos de la condición. \\ Considero como hipótesis x + \bar y = 1 y trato de probar mi tesis x + y = x\\ x+y = (x+y)\cdot (x+\bar x ) = x\cdot (x+y) + \bar x \cdot (x+y) , por ley de absorción x + xy = x entonces:\\ x+y\bar x = \overline { \overline {x+y\bar x}} = \overline { \bar x \cdot \overline {y\bar x} } = \\ \overline {\bar x \cdot (\bar y + x) } , por hip. x + \bar y = 1, entonces: \\ \overline {\bar x \cdot 1} = \overline { \overline {x}} = x , queda demostrado x + \bar y = 1 \rightarrow x + y = x \\ \\ Ahora pruebo x +y = x \rightarrow x + \bar y = 1 \\ x+ \bar y = x+y+\bar y , por ley de inversos y+ \bar y = 1, entonces: \\ x + 1 =1 y demostre que x +y = x \rightarrow x + \bar y = 1 .\\ Queda así demostrado: x + \bar y = 1 \leftrightarrow x + y = x \\ \\ ===== 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 [[http://www.foros-fiuba.com.ar/privmsg.php?mode=post&u=3259|envíame un PM]].