Práctica 7 (LyC Verano)

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 05

Si definimos la funcion la suma como f(x,y) = x + y + 1.
Esto cumple los axiomas dados, pero sin embargo es evidente que no cumple con la suma en los naturales.

Ejercicio 06

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
φi = "No hay un camino de longitud i entre c y d".
longitud dos en primer orden se escribiria:
¬($\exists$ x)(R(c,x) Y R(x,d))
Y se puede generalizar facilmente para mostrar que es posible escribirlo en primer orden.
Luego definimos lo que queremos probar que no es expresable.
Sea
ψ = "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 10

a)

$\neg (\forall x\exists yP(x,y)\rightarrow \exists y\forall xP(x,y))$
$\forall x\exists yP(x,y)$
$\neg \exists y\forall xP(x,y)$
$\exists yP(a1,y)$
$P(a1,b)$
$\neg \forall xP(x,b)$
$\neg P(a2,b)$
$\exists yP(a2,y)$
...

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

b)

$(\exists y\forall xP(x,y))\wedge \neg (\forall x\exists yP(x,y))$
$\exists y\forall xP(x,y)$
$\neg \forall x\exists yP(x,y)$
$\forall xP(x,a)$
$\neg \exists yP(b,y)$
$P(b,a)$
$\neg P(b,a)$
×

Ejercicio 12

a)

Se puede ver que $\forall x\exists y\forall z\exists w(P(x,y)\vee \neg P(z,w))$ no es tautologia, ya que si tomamos P(x,y) = x=0 ٨ y=0 se hace falsa la implicacion

b)

Si

Ejercicio 13

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:

$(1)[\forall x\forall y\forall zP(x,y,z)\rightarrow P(y,x,z)]\wedge (2)[\exists x\forall y\exists zP(y,z,x)]\wedge (3)\neg [\exists x\forall y\exists zP(z,y,x)]$
(4)(Usando 2)$\forall y\exists zP(y,z,t)$
(5)(Usando 3)$\neg \forall y\exists zP(z,y,t)$
(6)(Usando 5)$\neg \exists zP(z,t1,t)$
(7)(Usando 4)$\exists zP(t1,z,t)$
(8)(Usando 7)$P(t1,t2,t)$
(9)(Usando 6)$\neg P(t2,t1,t)$
(10)(Usando 1)$P(t1,t2,t)\rightarrow P(t2,t1,t)$
(11)$\neg P(t1,t2,t)\vee P(t2,t1,t)$
(12)(Usando 8,9)$P(t1,t2,t)\vee \neg P(t2,t1,t)$
(13) $x\vee x$