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== | ||
==Ejercicio 03== | ==Ejercicio 03== | ||
===a)=== | ===a)=== | ||
Línea 14: | Línea 7: | ||
==Ejercicio 04== | ==Ejercicio 04== | ||
===a)=== | ===a)=== | ||
===b)=== | ===b)=== | ||
===c)=== | ===c)=== | ||
==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> | ||
φi = "No hay un camino de longitud i entre c y d".<br> | φi = "No hay un camino de longitud i entre c y d".<br> | ||
longitud dos en primer orden se escribiria:<br> | longitud dos en primer orden se escribiria:<br> | ||
¬( | ¬(Existe x)(R(c,x) Y R(x,d))<br> | ||
Y se puede generalizar facilmente para mostrar que es posible escribirlo en primer orden.<br> | Y se puede generalizar facilmente para mostrar que es posible escribirlo en primer orden.<br> | ||
Luego definimos lo que queremos probar que no es expresable.<br> | Luego definimos lo que queremos probar que no es expresable.<br> | ||
Línea 66: | Línea 39: | ||
==Ejercicio 09== | ==Ejercicio 09== | ||
===a)=== | ===a)=== | ||
===b)=== | ===b)=== | ||
===c)=== | ===c)=== | ||
==Ejercicio 10== | ==Ejercicio 10== | ||
Línea 115: | Línea 69: | ||
==Ejercicio 12== | ==Ejercicio 12== | ||
===a)=== | ===a)=== | ||
Si | |||
<br> <math> \neg ( \forall x \exists y \forall z \exists w ( P(x,y) \or \neg P(z,w) ) )</math> <br> <math> \neg ( \exists y \forall z \exists w ( P(a,y) \or \neg P(z,w)) ) </math> | |||
<br> <math> \neg ( \forall z \exists w ( P(a,b) \or \neg P(z,w)) ) </math> | |||
<br> <math> \neg ( \exists w ( P(a,b) \or \neg P(a,w)) ) </math> | |||
<br> <math> \neg ( P(a,b) \or \neg P(a,b) ) </math> | |||
<br> <math> \neg P(a,b) </math> | |||
<br> <math> \neg \neg P(a,b) </math> | |||
<br> <math> P(a,b)</math> | |||
<br> <math> x </math> | |||
===b)=== | ===b)=== | ||
Línea 129: | Línea 91: | ||
<br>(7)(Usando 4)<math> \exists z P(t1,z,t) </math> | <br>(7)(Usando 4)<math> \exists z P(t1,z,t) </math> | ||
<br>(8)(Usando 7)<math> P(t1,t2,t) </math> | <br>(8)(Usando 7)<math> P(t1,t2,t) </math> | ||
<br>(9)(Usando | <br>(9)(Usando 5)<math> \neg P(t2,t1,t) </math> | ||
<br>(10)(Usando 1)<math> P(t1,t2,t) \rightarrow P(t2,t1,t) </math> | <br>(10)(Usando 1)<math> P(t1,t2,t) \rightarrow P(t2,t1,t) </math> | ||
<br>(11)<math> \neg P(t1,t2,t) \vee P(t2,t1,t) </math> | <br>(11)<math> \neg P(t1,t2,t) \vee P(t2,t1,t) </math> | ||
Línea 135: | Línea 97: | ||
<br>(13) <math> x \vee x </math> | <br>(13) <math> x \vee x </math> | ||
[[Category: | [[Category:Lógica y Computabilidad]] |