Práctica 7 (LyC Verano)

De Cuba-Wiki
Revisión del 01:17 10 mar 2007 de 201.235.208.37 (discusión) (→‎Ejercicio 13)
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

Ejercicio 01

Ejercicio 02

Ejercicio 03

a)

b)

c)

Ejercicio 04

a)

b)

c)

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 07

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 09

a)

b)

c)

Ejercicio 10

a)










...

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

b)









×

Ejercicio 11

Ejercicio 12

a)

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:



(4)(Usando 2)
(5)(Usando 3)
(6)(Usando 5)
(7)(Usando 4)
(8)(Usando 7)
(9)(Usando 6)
(10)(Usando 1)
(11)
(12)(Usando 8,9)
(13)