| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| |
|
| |
| ==Ejercicio 01== | | ==Ejercicio 01== |
| <br>El b) es Termino y los demas son Formulas
| |
|
| |
| ==Ejercicio 02== | | ==Ejercicio 02== |
| Entre corchetes las ligadas:
| |
| <br>a)<math> \forall x \exists y P([x],[x]) </math>
| |
| <br>b)<math> \exists x P(y,y) \rightarrow \exists y P([y],z) </math>
| |
| <br>c)<math> \exists x ( \exists y P([x],[x]) \wedge P([x],y) ) </math>
| |
| <br>d)<math> \forall z ( \forall x P([z],[x]) ) \vee P(x,z) </math>
| |
|
| |
| ==Ejercicio 03== | | ==Ejercicio 03== |
| <br>a) No, ya que <math> f_I(n) = \sqrt n </math> no es siempre natural
| |
| <br>b) Si
| |
| <br>c) No, por que <math> g_I(n,n) </math> no es total, es decir, no esta definida para todo par n,m como lo es g en el lenguaje, sino que esta definida solamente para n = m.
| |
|
| |
| ==Ejercicio 04== | | ==Ejercicio 04== |
| ===a)===
| |
| <br>Esta propiedad equivale a: <i>Para todo x,y en R tq x<y, existe un z en Q tq x<z<y</i>
| |
| <br>Esto significa que los racionales son densos en los reales, es decir, siempre hay un racional entre dos reales cualesquiera.
| |
| ===b)===
| |
| <br>Esta propiedad significa: <i>Todos los dias nace un esclavo</i>
| |
| ===c)===
| |
| <br>Esta propiedad significa: <i>La suma de pares es impar</i> (No habran querido poner al reves?)
| |
|
| |
| ===d)===
| |
| *1: Hay una persona x que quiere a todas las personas
| |
| *2: Toda persona y es querida al menos por una persona x
| |
| *3: Hay una persona x, que si y quiere a todas las personas entonces x quiere a y
| |
| *4: Hay una persona x que no quiere a ninguna persona
| |
|
| |
| ==No está en la práctica 6 del 2° cuat 2009==
| |
| <br>a)<math> \neg(\exists x) Politico(x) \wedge Honesto(x) </math>
| |
| <br>b)<math> \neg(\forall x) Ave(x) \rightarrow Vuela(x) </math>
| |
| <br>c)<math> (\forall x) ((Trasc(x) \rightarrow Irrac(x)) \wedge (Irrac(x) \rightarrow Trasc(x))) </math>
| |
| <br>d)<math> (\exists x) ( Ivanoff(x) \wedge (\forall y) \neg Odia(y,y) \rightarrow Odia(x,y) )</math>
| |
| <br>e)<math> ((\forall x)(\exists y)Ama(x,y) \wedge \neg(\exists x)(\forall y)Ama(x,y)) \vee (\exists x)(\forall y)Ama(x,y) </math>
| |
|
| |
| ==Ejercicio 05== | | ==Ejercicio 05== |
| <br>a)<math> (\exists x)(\exists y) (x \neq y) </math>
| |
| <br>b)<math> (\exists x)((\exists y) (x \neq y) \wedge (\forall z)(x = z \vee y = z)) </math>
| |
| <br>c)<math> \neg(\exists x)(x = x) \vee (\exists x)(\forall y) (x = y) \vee </math> Punto b)
| |
| <br>d)Punto c) <math> \wedge (\exists x)P(x) </math>
| |
| <br>e)<math> (\exists x)(P(x) \rightarrow (\forall y) (x = y)) </math>
| |
| <br>f)<math> (\exists x)(P(x) \wedge (\forall y) (x = y)) </math>
| |
|
| |
| ==Ejercicio 06== | | ==Ejercicio 06== |
| Podemos tomar φ = <math>( (\forall x)(\forall y)f_A(x)=f_A(y) \rightarrow x=y ) \wedge ( (\exists x)(\forall y)x \neq f_A(y) )</math>
| |
| <br>Tal formula es satisfacible, por ej. fA(x)=2^x lo cumple. Para los modelos finitos no cumple, ya que en este caso una funcion inyectiva debe ser tambien sobreyectiva
| |
|
| |
| ==Ejercicio 07== | | ==Ejercicio 07== |
| Un lenguaje podria ser A=<N,<,0>, dado que puede construirse un predicado para cada elemento tal que satisfaga unicamente a ese mismo elemento
| |
|
| |
| ==Ejercicio 08== | | ==Ejercicio 08== |
| | | ==Ejercicio 09== |
| Recordemos que un elemento de una interpretacion es distinguible si existe un predicado unario que se verifica solo para ese elemento.
| |
| | |
| En el caso de (N, ·), el uno es el unico elemento neutro:
| |
| <math>\forall y (y.x = y)</math>
| |
| | |
| En el caso de (N, +), el uno es el unico elemento que verifica que si dos numeros sumados dan 1, uno es cero y el otro no:
| |
| <math>\forall y \forall z (y+z = x \rightarrow (\forall w(w+y = w) \wedge \exists w(w+z \neq w)) \vee (\forall w(w+z = w) \wedge \exists w(w+y \neq w)))</math>
| |
| | |
| ==Ejercicio 9== | |
| (El unico predicado binario sera notado con <math>\leq</math>)
| |
| ===a)===
| |
| <br>Los siguientes seis predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.
| |
| *El minimo:
| |
| <math>\forall y(x \leq y). </math>
| |
| *El que esta a la derecha del minimo:
| |
| <math>\exists y\forall z(z \leq x \rightarrow y = z) \wedge \exists z\exists y(z \neq y \wedge z \neq x \wedge y \neq z \wedge \forall w(x \leq w \rightarrow (w = y \vee w = z \vee w = x))) </math>
| |
| <br><i>Tiene por lo menos uno abajo, y exactamente dos arriba.</i>
| |
| *El que esta a la izquierda del minimo:
| |
| <math>\exists y\forall z(z \leq x \rightarrow z = y) \wedge \exists y\exists z\exists w(x \leq w \wedge x \leq z \wedge x \leq y \wedge z \neq y \wedge z \neq w \wedge z \neq x \wedge y \neq w \wedge y \neq x \wedge w \neq x \wedge \forall v(x \leq v \rightarrow (v = w \vee v = y \vee v = z))). </math>
| |
| <br><i>Hay uno abajo, y exactamente tres arriba.</i>
| |
| *El que esta a la izquierda del maximo:
| |
| <math>\exists y\forall z(x \leq z \rightarrow y = z) \wedge \exists z\exists y(z \neq y \wedge z \neq x \wedge y \neq z \wedge \forall w(w \leq x \rightarrow (w = y \vee w = z \vee w = x))). </math>
| |
| *El que esta a la derecha del maximo:
| |
| <math>\exists y\forall z(x \leq z \rightarrow z = y) \wedge \exists y\exists z\exists w(w \leq x \wedge z \leq x \wedge y \leq x \wedge y \neq z \wedge w \neq z \wedge z \neq x \wedge y \neq w \wedge y \neq x \wedge w \neq x \wedge \forall v(v \leq x \rightarrow (v = w \vee v = y \vee v = z))). </math>
| |
| *El maximo:
| |
| <math> \forall y(y \leq x). </math>
| |
| | |
| ===b)===
| |
| Los siguientes cinco predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.
| |
| *El minimo:
| |
| <math>\forall y(x \leq y).</math>
| |
| *El que esta arriba del minimo:
| |
| <math> \exists y(y \neq x \wedge y \leq x \wedge \forall z(z \leq x \rightarrow z = y)) \wedge \exists y\exists z(z \neq y \wedge z \neq x \wedge y \neq x \wedge x \leq z \wedge x \leq y) </math>
| |
| <br><i>Tiene exactamente uno abajo y dos arriba.</i>
| |
| *El que sobresale:
| |
| <math> \exists y\exists z(y \neq x \wedge z \neq y \wedge z \neq x \wedge y \leq x \wedge z \leq x \wedge \forall w(w \leq x \rightarrow (w = y \vee w = z \vee w = x)) \wedge \neg\exists y(y \neq x \wedge x \leq y))</math>
| |
| <br><i>Tiene exactamente dos abajo y ninguno arriba.</i>
| |
| *El de abajo del “maximo”:
| |
| <math>\exists y(y \neq x \wedge x \leq y \wedge \forall z(x \leq z \rightarrow (z = y \vee x = z))).</math>
| |
| <br><i>Tiene exactamente uno arriba. </i>
| |
| *El maximo: Tomo la conjuncion de las negaciones de todos los predicados anteriores. Hay un solo elemento que la cumple, y es este.
| |
| | |
| ==Ejercicio 10== | | ==Ejercicio 10== |
| | ==Ejercicio 11== |
|
| |
|
| Probar que si el universo de una interpretacion es finito con n+1 elementos, y tiene la propiedad que n elementos del universo son distinguibles, entonces todos los elementos son distinguibles.
| | [[Category:Lógica y Computabilidad]] |
| | |
| Sea <math>\phi _i</math> la funcion que es valida solo al ser evaluada en el elemento i, es decir, la funcion que distingue al elemento i del conjunto. Por hipotesis, existen las funciones <math>\phi _1, \phi _2, ... \phi _n</math>.
| |
| | |
| Entonces la funcion que distingue al ultimo elemento, que es la que falta para que todos sean distinguibles, es:
| |
| | |
| <math>\phi _{n+1} = \neg \phi _1 \wedge \neg \phi _2 \wedge ... \wedge \neg \phi _n</math>
| |
| | |
| | |
| [[Category:Prácticas]] | |
