| Revisión actual |
Tu texto |
| Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| |
|
| |
| ==Ejercicio 01== | | ==Ejercicio 01== |
| ==Ejercicio 02== | | ==Ejercicio 02== |
| Es satifacible, y por lo tanto tambien consistente.
| |
| Sea la propiedad P: P(x) = (x>1)
| |
| No pasa que para todo x se cumple x, es decir, existe uno para el cual no se cumple. (De hecho el numero 1 o 0 no cumplen dicha propiedad)
| |
| Luego podemos instanciar x2,x3,x4 ,.... en los naturales mayores que 1, cualesquiera sean. Eso nos dara una valuacion satisfacible
| |
|
| |
| ==Ejercicio 03== | | ==Ejercicio 03== |
| ===a)=== | | ===a)=== |
| Línea 14: |
Línea 7: |
|
| |
|
| ==Ejercicio 04== | | ==Ejercicio 04== |
| La extension es el esquema axiomatico que representa la transitividad:
| |
| <math>(\forall x)(\forall y)(( R(x,y) \wedge R(y,z)) \rightarrow R(x,z))</math>
| |
| ===a)=== | | ===a)=== |
| Esto se supone es explicable sin formalidades rigurosas...si alguien lo puede hacer mejor que lo haga.
| |
| Es correcta si todo lo demostrable en nuestro sistema axiomatico es realmente una verdad de nuestro modelo, es decir, es una consecuencia de nuestro modelo.
| |
| Si agarramos un modelo transitivo cualquiera, podemos probar todas las cosas anteriores a agregar a nuestro modelo, y ademas la transitividad, que es justamente la particularidad que tendra nuestro modelo.
| |
| ===b)=== | | ===b)=== |
| Si era completo sin el axioma de transitividad, luego tambien lo sera con el, ya que podremos probar las mismas cosas como si nos olvidaramos de que agregamos un axioma.
| |
| ===c)=== | | ===c)=== |
| <br>Debemos ver que hay cosas que podemos probar que no son ciertas para cualquier modelo. Es evidente que la transitividad no sera cierta en un modelo no transitivo y sin embargo la podremos demostrar debido a nuestro axioma. Entonces:
| |
| <br>Sea un modelo M = {a,b,c}
| |
| <br>Sea Rm = {(a,b), (b,c)}
| |
| <br>R(x,y) sii <math>(x==a \wedge y==b) \vee (x==b \wedge y==c)</math>
| |
| <br>Sea <math>\phi = (\forall x)(\forall y)(( R(x,y) \wedge R(y,z)) \rightarrow R(x,z))</math>
| |
| <br>q.v.q. <math>M \neg\vDash \phi</math>, o sea, <math>(\forall v) M \neg\vDash \phi[v]</math>
| |
| <br>Supongamos que no, luego <math>(\exists v) tq M \vDash fi[v]</math>
| |
| <br>o sea <math>A \vDash (\forall x)(\forall y)(( R(x,y) \wedge R(y,z)) \rightarrow R(x,z)) </math>
| |
| <br>sii <math>\forall k1,k2,k3 / v' = v( (x=k1)(y=k2)(z=k3)) \in M, M \vDash R(x,y) Y R(y,z) \rightarrow R(x,z)[v']</math>
| |
| <br>sii <math>M \neg\vDash R(x,y) \wedge R(y,z)[v'] \vee M \vDash R(x,z)[v']</math>
| |
| <br>Pero si pasa que k1=a, k2=b, k3=c. En ese caso <math>M \vDash R(x,y) \wedge R(y,z)[v']</math> porque <math>(a,b) \in Rm \wedge (b,c) \in Rm</math>
| |
| <br>Pero <math>A \neg\vDash R(x,z)[v']</math>
| |
|
| |
| ==Ejercicio ==
| |
| Si definimos la funcion la suma como f(x,y) = x + y + 1. <br>
| |
| Esto cumple los axiomas dados, pero sin embargo es evidente que no cumple con la suma en los naturales.
| |
|
| |
|
| ==Ejercicio 07== | | ==Ejercicio 05== |
| | ==Ejercicio 06== |
| ===a)=== | | ===a)=== |
| Si tomamos φi = "El modelo tiene al menos i elementos", un posible conjunto es Γ={φ1,φ2,φ3,..}
| |
|
| |
| ===b)=== | | ===b)=== |
| Sup. que es posible. Tomemos Γ={φ1,φ2,φ3,..}. Sea φ' = "El dominio es finito". Entonces si tomamos por ej. {φ1,φ2}U{φ'}, es satisfacible ya que hay modelos que lo hacen valido.
| |
| Esto ocurre para todo subconjunto finito de Γ (por ejemplo, con un subconjunto de los naturales tal que tenga al menos la cantidad minima de elementos distintos necesarios).
| |
| Por compacidad, si todo subconjunto finito es satisfacible, entonces el producto de la union de todos estos subconjuntos : ΓU{φ'}, también es satisfacible.
| |
| Para los modelos M que lo satisfacen, estamos diciendo que el dominio de M es finito, pero al ser Γ infinito, que M lo satisfaga --> M tiene infinitos elementos. Por lo tanto llegamos a un ABS
| |
|
| |
|
| | ==Ejercicio 07== |
| ==Ejercicio 08== | | ==Ejercicio 08== |
| Si extendemos nuestro modelo con un c y un d que representan numeros/nodos arbitrarios y tomamos<br>
| |
| φi = "No hay un camino de longitud i entre c y d".<br>
| |
| longitud dos en primer orden se escribiria:<br>
| |
| ¬(<math>\exists</math> x)(R(c,x) Y R(x,d))<br>
| |
| Y se puede generalizar facilmente para mostrar que es posible escribirlo en primer orden.<br>
| |
| Luego definimos lo que queremos probar que no es expresable.<br>
| |
| Sea<br>
| |
| ψ = "Entro todo par de nodos hay un camino de longitud finita"
| |
| Sea Γ = {φ1,φ2,φ3,..} U {ψ} un conjunto infinito.
| |
| Sabemos que cualquier subconjunto finito que eligamos de Γ es satisfacible. (Ya que si bien podria no haber camino de longitud Maximo entre todos los φi elegidos, podria haber uno de longitud i+1.
| |
| Entonces por compacidad Γ es satisfacible. Absurdo porque si no tienen camino de ninguna longitud los nodos c y d , luego no podemos decir que entre todo par d nodos hay un camino de longitud finita.
| |
| Absurdo que provino d pensar que ψ era expresable.
| |
|
| |
| ==Ejercicio 09== | | ==Ejercicio 09== |
| | <font color=white>code0602</font> |
| ===a)=== | | ===a)=== |
| <br><math>\neg( \exists y P(y) \rightarrow \forall x \exists y P(y) )</math>
| |
| <br><math>\exists y P(y)</math>
| |
| <br><math>\neg( \forall x \exists y P(y) )</math>
| |
| <br><math>\neg( \exists y P(y) )</math>
| |
| <br>X
| |
|
| |
| ===b)=== | | ===b)=== |
| <br><math>\neg( \exists y P(y) \rightarrow \exists y \exists x P(y) )</math>
| |
| <br><math>(1)\exists y P(y)</math>
| |
| <br><math>(2)\neg( \exists y \exists x P(y) )</math>
| |
| <br><math>(3)P(c) (1)</math>
| |
| <br><math>(4)\neg( \exists x P(c) ) (2)</math>
| |
| <br><math>(5)\neg P(c) (4) </math>
| |
| <br>X
| |
|
| |
| ===c)=== | | ===c)=== |
| <br><math>\neg( \forall x P(x) \rightarrow P(t) )</math>
| |
| <br><math>\forall x P(x)</math>
| |
| <br><math>\neg( P(t) )</math>
| |
| <br><math>P(t)</math>
| |
| <br>X
| |
|
| |
|
| ==Ejercicio 10== | | ==Ejercicio 10== |
| ===a)=== | | ===a)=== |
| <br><math>\neg (\forall x \exists y P(x, y) \rightarrow \exists y \forall xP(x, y)) </math> | | <br><math>(\forall x \exists y P(x, y)) \wedge \neg( \exists y \forall xP(x, y)) </math> |
| <br><math>\forall x \exists y P(x, y) </math> | | <br><math>\forall x \exists y P(x, y) </math> |
| <br><math>\neg \exists y \forall x P(x, y) </math> | | <br><math>\neg \exists y \forall x P(x, y) </math> |
| <br><math>\exists y P(a1, y) </math> | | <br><math>\exists y P(a, y) </math> |
| <br><math>P(a1, b) </math> | | <br><math>P(a, b) </math> |
| <br><math>\neg\forall x P(x, b) </math> | | <br><math>\neg\forall x P(x, b) </math> |
| <br><math>\neg P(a2, b)</math> | | <br><math>\neg P(c, b)</math> |
| <br><math>\exists y P(a2, y) </math> | | <br>Contraejemplo: I =< {a, b}, {(a, b), (b, a)} > |
| <br>...
| | |
|
| |
|
| Con lo cual la rama queda saturada, por lo que la negacion es satisfacible
| | Bueno esto no se quien lo hizo pero creo que se equivoco. El contraejemplo no lo entendi pero estoy seguro que c puede ser a por lo tanto nos quedaria cerrado el arbol. Fijense.... |
|
| |
|
| ===b)=== | | ===b)=== |
| Línea 113: |
Línea 49: |
|
| |
|
| ==Ejercicio 11== | | ==Ejercicio 11== |
| | <font color=white>code0605</font> |
| ==Ejercicio 12== | | ==Ejercicio 12== |
| | <font color=white>code0608</font> |
| ===a)=== | | ===a)=== |
| Se puede ver que <math> \forall x \exists y \forall z \exists w ( P(x,y) \vee \neg P(z,w) ) </math> no es tautologia, ya que si tomamos P(x,y) = x=0 ٨ y=0 se hace falsa la formula
| |
|
| |
| ===b)=== | | ===b)=== |
| Si
| |
|
| |
|
| ==Ejercicio 13== | | ==Ejercicio 13== |
| <br>Antes podemos reescribir la formula de la siguiente forma: P٨Q→Z <=> ¬(P٨Q)٧Z <=> ¬P٧¬Q٧Z . Con lo cual la negacion queda P٨Q٨¬Z. Entonces: | | <font color=white>code0610</font> |
| | |
| <br><math>(1)[ \forall x \forall y \forall z P(x,y,z) \rightarrow P(y,x,z) ] \wedge (2)[ \exists x \forall y \exists z P(y,z,x) ] \wedge (3)\neg [ \exists x \forall y \exists z P(z,y,x) ] </math>
| |
| <br>(4)(Usando 2)<math> \forall y \exists z P(y,z,t) </math>
| |
| <br>(5)(Usando 3)<math> \neg \forall y \exists z P(z,y,t) </math>
| |
| <br>(6)(Usando 5)<math> \neg \exists z P(z,t1,t) </math>
| |
| <br>(7)(Usando 4)<math> \exists z P(t1,z,t) </math>
| |
| <br>(8)(Usando 7)<math> P(t1,t2,t) </math>
| |
| <br>(9)(Usando 6)<math> \neg P(t2,t1,t) </math>
| |
| <br>(10)(Usando 1)<math> P(t1,t2,t) \rightarrow P(t2,t1,t) </math>
| |
| <br>(11)<math> \neg P(t1,t2,t) \vee P(t2,t1,t) </math>
| |
| <br>(12)(Usando 8,9)<math> P(t1,t2,t) \vee \neg P(t2,t1,t) </math>
| |
| <br>(13) <math> x \vee x </math>
| |
|
| |
|
| [[Category:Prácticas]] | | [[Category:Lógica y Computabilidad]] |
