Diferencia entre revisiones de «Práctica 6 (LyC Verano)»
| (No se muestran 24 ediciones intermedias de 5 usuarios) | |||
| Línea 1: | Línea 1: | ||
{{Back|Lógica y Computabilidad}} | |||
==Ejercicio 01== | ==Ejercicio 01== | ||
<br> | <br>El b) es Termino y los demas son Formulas | ||
==Ejercicio 02== | ==Ejercicio 02== | ||
| Línea 15: | Línea 12: | ||
==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)=== | ===a)=== | ||
| Línea 27: | Línea 28: | ||
*1: Hay una persona x que quiere a todas las personas | *1: Hay una persona x que quiere a todas las personas | ||
*2: Toda persona y es querida al menos por una persona x | *2: Toda persona y es querida al menos por una persona x | ||
*3: Hay 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 | *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>a)<math> \neg(\exists x) Politico(x) \wedge Honesto(x) </math> | ||
<br>b)<math> \neg(\forall x) Ave(x) \rightarrow Vuela(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>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>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> | <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 | ==Ejercicio 05== | ||
<br>a)<math> (\exists x)(\exists y) (x \neq y) </math> | <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>b)<math> (\exists x)((\exists y) (x \neq y) \wedge (\forall z)(x = z \vee y = z)) </math> | ||
| Línea 44: | Línea 45: | ||
<br>e)<math> (\exists x)(P(x) \rightarrow (\forall y) (x = y)) </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> | <br>f)<math> (\exists x)(P(x) \wedge (\forall y) (x = y)) </math> | ||
==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== | ||
Recordemos que un elemento de una interpretacion es distinguible si existe un predicado unario que se verifica solo para ese elemento. | Recordemos que un elemento de una interpretacion es distinguible si existe un predicado unario que se verifica solo para ese elemento. | ||
| Línea 58: | Línea 63: | ||
<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> | <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 | ==Ejercicio 9== | ||
(El unico predicado binario sera notado con <math>\leq</math>) | (El unico predicado binario sera notado con <math>\leq</math>) | ||
===a)=== | ===a)=== | ||
| Línea 92: | Línea 97: | ||
*El maximo: Tomo la conjuncion de las negaciones de todos los predicados anteriores. Hay un solo elemento que la cumple, y es este. | *El maximo: Tomo la conjuncion de las negaciones de todos los predicados anteriores. Hay un solo elemento que la cumple, y es este. | ||
==Ejercicio | ==Ejercicio 10== | ||
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. | 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. | ||
| Línea 103: | Línea 108: | ||
[[Category: | [[Category:Prácticas]] | ||
Revisión actual - 17:52 24 nov 2009
Ejercicio 01
El b) es Termino y los demas son Formulas
Ejercicio 02
Entre corchetes las ligadas:
a)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall x \exists y P([x],[x]) }
b)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists x P(y,y) \rightarrow \exists y P([y],z) }
c)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists x ( \exists y P([x],[x]) \wedge P([x],y) ) }
d)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall z ( \forall x P([z],[x]) ) \vee P(x,z) }
Ejercicio 03
a) No, ya que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle f_I(n) = \sqrt n }
no es siempre natural
b) Si
c) No, por que Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle g_I(n,n) }
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
a)
Esta propiedad equivale a: Para todo x,y en R tq x<y, existe un z en Q tq x<z<y
Esto significa que los racionales son densos en los reales, es decir, siempre hay un racional entre dos reales cualesquiera.
b)
Esta propiedad significa: Todos los dias nace un esclavo
c)
Esta propiedad significa: La suma de pares es impar (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
a)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg(\exists x) Politico(x) \wedge Honesto(x) }
b)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg(\forall x) Ave(x) \rightarrow Vuela(x) }
c)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\forall x) ((Trasc(x) \rightarrow Irrac(x)) \wedge (Irrac(x) \rightarrow Trasc(x))) }
d)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\exists x) ( Ivanoff(x) \wedge (\forall y) \neg Odia(y,y) \rightarrow Odia(x,y) )}
e)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle ((\forall x)(\exists y)Ama(x,y) \wedge \neg(\exists x)(\forall y)Ama(x,y)) \vee (\exists x)(\forall y)Ama(x,y) }
Ejercicio 05
a)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\exists x)(\exists y) (x \neq y) }
b)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\exists x)((\exists y) (x \neq y) \wedge (\forall z)(x = z \vee y = z)) }
c)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \neg(\exists x)(x = x) \vee (\exists x)(\forall y) (x = y) \vee }
Punto b)
d)Punto c) Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \wedge (\exists x)P(x) }
e)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\exists x)(P(x) \rightarrow (\forall y) (x = y)) }
f)Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle (\exists x)(P(x) \wedge (\forall y) (x = y)) }
Ejercicio 06
Podemos tomar φ = Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle ( (\forall x)(\forall y)f_A(x)=f_A(y) \rightarrow x=y ) \wedge ( (\exists x)(\forall y)x \neq f_A(y) )}
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
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
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: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall y (y.x = y)}
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: Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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)))}
Ejercicio 9
(El unico predicado binario sera notado con Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \leq} )
a)
Los siguientes seis predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.
- El minimo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall y(x \leq y). }
- El que esta a la derecha del minimo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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))) }
Tiene por lo menos uno abajo, y exactamente dos arriba.
- El que esta a la izquierda del minimo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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))). }
Hay uno abajo, y exactamente tres arriba.
- El que esta a la izquierda del maximo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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))). }
- El que esta a la derecha del maximo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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))). }
- El maximo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall y(y \leq x). }
b)
Los siguientes cinco predicados se verifican en un solo elemento del diagrama, y cada elemento verifica uno solo de ellos.
- El minimo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \forall y(x \leq y).}
- El que esta arriba del minimo:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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) }
Tiene exactamente uno abajo y dos arriba.
- El que sobresale:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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))}
Tiene exactamente dos abajo y ninguno arriba.
- El de abajo del “maximo”:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \exists y(y \neq x \wedge x \leq y \wedge \forall z(x \leq z \rightarrow (z = y \vee x = z))).}
Tiene exactamente uno arriba.
- 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
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.
Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi _i} 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi _1, \phi _2, ... \phi _n} .
Entonces la funcion que distingue al ultimo elemento, que es la que falta para que todos sean distinguibles, es:
Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \phi _{n+1} = \neg \phi _1 \wedge \neg \phi _2 \wedge ... \wedge \neg \phi _n}
