Edición de «Práctica 7 (LyC Verano)»

{{Back|Lógica y Computabilidad}}

==Ejercicio 01==
==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==
===a)===
===b)===
===c)===

==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)===
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)===
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)===
<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==
===a)===
Si tomamos φi = "El modelo tiene al menos i elementos", un posible conjunto es Γ={φ1,φ2,φ3,..}

===b)===
Sup. que es posible. Si tomamos Γ={φ1,φ2,φ3,..}, por compacidad, existe un subconjunto finito satisfacible. Sea φ' = "El dominio es finito". Entonces si tomamos por ej. {φ1,φ2}U{φ'}, es satisfacible ya que hay modelos que lo hacen valido. Pero si tomamos ΓU{φ'}, estamos diciendo que el dominio es finito, pero al ser Γ infinito, es satisfacible si tiene infinitos elementos. Por lo tanto llegamos a un ABS



==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==
===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)===
<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)===
<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==
===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) </math>
<br><math>\neg \exists y \forall x P(x, y) </math>
<br><math>\exists y P(a1, y) </math>
<br><math>P(a1, b) </math>
<br><math>\neg\forall x P(x, b) </math>
<br><math>\neg P(a2, b)</math>
<br><math>\exists y P(a2, y) </math>
<br>...

Con lo cual la rama queda saturada, por lo que la negacion es satisfacible

===b)===
<br><math>( \exists y \forall x P(x, y)) \wedge \neg(\forall x \exists y P(x, y)) </math>
<br><math>\exists y \forall x P(x, y) </math>
<br><math>\neg\forall x \exists y P(x, y) </math>
<br><math>\forall x P(x, a) </math>
<br><math>\neg \exists y P(b, y) </math>
<br><math>P(b, a) </math>
<br><math>\neg P(b, a) </math>
<br>×

==Ejercicio 11==
==Ejercicio 12==
===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)===
Si

==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:

<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]]
@@ Línea 45: / Línea 45: @@
 ===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.
+Sup. que es posible. Si tomamos Γ={φ1,φ2,φ3,..}, por compacidad, existe un subconjunto finito satisfacible. Sea φ' = "El dominio es finito". Entonces si tomamos por ej. {φ1,φ2}U{φ'}, es satisfacible ya que hay modelos que lo hacen valido. Pero si tomamos ΓU{φ'}, estamos diciendo que el dominio es finito, pero al ser Γ infinito, es satisfacible si tiene infinitos elementos. Por lo tanto llegamos a un ABS
-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 08==