Edición de «Práctica 7 (LyC Verano)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
==Ejercicio 01== | ==Ejercicio 01== | ||
==Ejercicio 02== | ==Ejercicio 02== | ||
Línea 23: | Línea 21: | ||
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. | 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)=== | ===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 | <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 | ||
<br>Sea un modelo M = {a,b,c} | <br>Sea un modelo M = {a,b,c} | ||
<br>Sea Rm = {(a,b), (b,c)} | <br>Sea Rm = {(a,b), (b,c)} | ||
<br>R(x,y) sii <math>(x==a \wedge y==b) | <br>R(x,y) sii <math>(x==a \wedge y==b) O (x==b \wedge y==c)</math> | ||
<br>Sea <math> | <br>Sea Fi = <math>(\forall x)(\forall y)(( R(x,y) \wedge R(y,z)) \rightarrow R(x,z))</math> | ||
<br>q.v.q. <math>M \neg\vDash | <br>q.v.q. <math>M \neg\vDash Fi</math>, o sea, <math>(\forall v) M \neg\vDash Fi[v]</math> | ||
<br>Supongamos que no, luego <math>(\exists v) tq M \vDash fi[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>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>\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 M \neg\vDash R(x,y) \wedge R(y,z)[v'] o M \vDash R(x,z)[v']</math> | ||
<br>sii | |||
<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 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> | <br>Pero <math>A \neg\vDash R(x,z)[v']</math> | ||
==Ejercicio == | ==Ejercicio 05== | ||
Si definimos la funcion la suma como f(x,y) = x + y + 1. <br> | 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. | Esto cumple los axiomas dados, pero sin embargo es evidente que no cumple con la suma en los naturales. | ||
==Ejercicio | ==Ejercicio 06== | ||
===a)=== | ===a)=== | ||
Si tomamos φi = "El modelo tiene al menos i elementos", un posible conjunto es Γ={φ1,φ2,φ3,..} | Si tomamos φi = "El modelo tiene al menos i elementos", un posible conjunto es Γ={φ1,φ2,φ3,..} | ||
===b)=== | ===b)=== | ||
Sup. que es posible. | 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== | ==Ejercicio 08== | ||
Si extendemos nuestro modelo con un c y un d que representan numeros/nodos arbitrarios y tomamos<br> | Si extendemos nuestro modelo con un c y un d que representan numeros/nodos arbitrarios y tomamos<br> | ||
Línea 66: | Línea 61: | ||
==Ejercicio 09== | ==Ejercicio 09== | ||
===a)=== | ===a)=== | ||
===b)=== | ===b)=== | ||
===c)=== | ===c)=== | ||
==Ejercicio 10== | ==Ejercicio 10== | ||
Línea 135: | Línea 111: | ||
<br>(13) <math> x \vee x </math> | <br>(13) <math> x \vee x </math> | ||
[[Category: | [[Category:Lógica y Computabilidad]] |