Práctica 7 (LyC Verano)

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:
¬(Existe 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)

Si
$\neg (\forall x\exists y\forall z\exists w(P(x,y)\lor \neg P(z,w)))$
$\neg (\exists y\forall z\exists w(P(a,y)\lor \neg P(z,w)))$
$\neg (\forall z\exists w(P(a,b)\lor \neg P(z,w)))$
$\neg (\exists w(P(a,b)\lor \neg P(a,w)))$
$\neg (P(a,b)\lor \neg P(a,b))$
$\neg P(a,b)$
$\neg \neg P(a,b)$
$P(a,b)$
$x$

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 5)$\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$