Diferencia entre revisiones de «Práctica 7 (LyC Verano)»

De Cuba-Wiki
Línea 74: Línea 74:
==Ejercicio 12==
==Ejercicio 12==
===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 implicacion


===b)===
===b)===

Revisión del 02:07 10 mar 2007

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

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

Se puede ver que 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:



(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)