Edición de «Práctica 5 (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 47: | Línea 47: | ||
Luego nuestro axioma será una contradicción.<br> | Luego nuestro axioma será una contradicción.<br> | ||
==Ejercicio | ==Ejercicio 04== | ||
===a)=== | ===a)=== | ||
'''Inducción:'''<br> | '''Inducción:'''<br> | ||
Línea 165: | Línea 165: | ||
</pre> | </pre> | ||
==Ejercicio == | ==Ejercicio 07== | ||
===a)=== | ===a)=== | ||
{p},{p->q} | {p},{p->q} | ||
Línea 191: | Línea 191: | ||
* 3. Γ0 <math>\subseteq</math> Γ1U{¬α} insatisfacible -> Γ1|=α | * 3. Γ0 <math>\subseteq</math> Γ1U{¬α} insatisfacible -> Γ1|=α | ||
==Ejercicio | ==Ejercicio 10== | ||
Como Γ1 U Γ2 es insatisfacible, por compacidad existe Γ0 <math>\subseteq</math> Γ1 U Γ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1,..,αn a las formulas de Γ1 ∩ Γ0 y β1,..,βm a las de | Como Γ1 U Γ2 es insatisfacible, por compacidad existe Γ0 <math>\subseteq</math> Γ1 U Γ2 finito e insatisfacible. Este conjunto tiene que tener por lo menos una formula de Γ1 y una de Γ2. Si no, serıa satisfacible. Si llamamos α1,..,αn a las formulas de Γ1 ∩ Γ0 y β1,..,βm a las de Γ1 ∩ Γ0, podemos hacer α = α1 ٨..٨ αn y β = β1 ٨..٨ βm. Es claro que α ε C(Γ1) y que β ε C(Γ2). Ademas, α ٨ β es una contradiccion. Pero α ٨ β ≡ ¬(¬α ٧ ¬β) ≡ ¬(α → ¬β), de lo cual podemos concluir que (α → ¬β) es una tautologia | ||
==Ejercicio 11 | ==Ejercicio 11== | ||
<br>Sea Γ' <math>\subseteq</math> Γ finito. Veamos por induccion en su cantidad de elementos que es satisfacible. Si #Γ' = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo Γ' de menos de n elementos es satisfacible. Sea Γ' con n elementos. Entonces, Γ' = {α} U Γ" (con α <math>\notin</math> Γ"). Sea v una valuacion que satisface a Γ" (existe por HI). Sea w una valuacion que satisface a α. Construimos v' como sigue. En las variables de α, da lo mismo que w. En las demas variables, da lo mismo que v. Esta valuacion satisface a Γ'. Entonces, como todo subconjunto finito es satisfacible, Γ es satisfacible (por compacidad). | <br>Sea Γ' <math>\subseteq</math> Γ finito. Veamos por induccion en su cantidad de elementos que es satisfacible. Si #Γ' = 1, sabemos que es satisfacible pues consta de una sola contingencia. Supongamos que todo Γ' de menos de n elementos es satisfacible. Sea Γ' con n elementos. Entonces, Γ' = {α} U Γ" (con α <math>\notin</math> Γ"). Sea v una valuacion que satisface a Γ" (existe por HI). Sea w una valuacion que satisface a α. Construimos v' como sigue. En las variables de α, da lo mismo que w. En las demas variables, da lo mismo que v. Esta valuacion satisface a Γ'. Entonces, como todo subconjunto finito es satisfacible, Γ es satisfacible (por compacidad). | ||
<br>Si no queremos usar compacidad, vemos directamente que Γ es satisfacible. Para cada elemento αi hay una valuacion vi. Construimos la valuacion v que es igual a cada vi en las variables de αi, y 0 en las variables que no aparezcan en Γ. Esta bien definida por las intersecciones vacias. v satisface a Γ. | <br>Si no queremos usar compacidad, vemos directamente que Γ es satisfacible. Para cada elemento αi hay una valuacion vi. Construimos la valuacion v que es igual a cada vi en las variables de αi, y 0 en las variables que no aparezcan en Γ. Esta bien definida por las intersecciones vacias. v satisface a Γ. | ||
==Ejercicio | ==Ejercicio 12== | ||
Supongamos que ninguna formula de la forma α1 ٧...٧ αn sea tautologia. Esto es lo mismo que decir que ninguna formula de la forma ¬α1 ٨ ... ٨ ¬αn no es contradiccion. Pero esto ultimo es lo mismo que decir que todo subconjunto finito de negaciones de formulas de Γ es satisfacible. Entonces ¬Γ = {¬α, α ε Γ} es satisfacible. Entonces, existe v valuacion tal que v(¬α) = 1 para todo α en Γ. Esto contradice la hipotesis de que v satisface al menos una formula de Γ. Entonces, tienen que existir finitas formulas α1, ... , αn tales que su disyuncion es una tautologia. | Supongamos que ninguna formula de la forma α1 ٧...٧ αn sea tautologia. Esto es lo mismo que decir que ninguna formula de la forma ¬α1 ٨ ... ٨ ¬αn no es contradiccion. Pero esto ultimo es lo mismo que decir que todo subconjunto finito de negaciones de formulas de Γ es satisfacible. Entonces ¬Γ = {¬α, α ε Γ} es satisfacible. Entonces, existe v valuacion tal que v(¬α) = 1 para todo α en Γ. Esto contradice la hipotesis de que v satisface al menos una formula de Γ. Entonces, tienen que existir finitas formulas α1, ... , αn tales que su disyuncion es una tautologia. | ||
==Ejercicio | ==Ejercicio 13== | ||
Recordemos que {P} |= Q sii (P → Q) es una tautologia. Y esto tambien es equivalente a que [P] <= [Q]. Con esto en mente, supongamos que Γ |= γ. Entonces, por compacidad, existe un subconjunto finito Γ0 = {α1, ... , αn} de Γ tal que {α1, ... , αn} |= γ . Miremos el cociente finito Γ0/ ≡. La hipotesis de que α → β es tautologia o β → α es tautologia se puede traducir en que este cociente se puede ordenar totalmente. Sea [α] su primer elemento. Es claro que todos los elementos de [α] son consecuencia de α. Los elementos de clases mayores tambien, pues se tiene que α → β es tautologia para toda β que este en una clase [P] tal que [α] <= [P]. Entonces, todo Γ0 es consecuencia de α. Luego, {α} |= γ . | Recordemos que {P} |= Q sii (P → Q) es una tautologia. Y esto tambien es equivalente a que [P] <= [Q]. Con esto en mente, supongamos que Γ |= γ. Entonces, por compacidad, existe un subconjunto finito Γ0 = {α1, ... , αn} de Γ tal que {α1, ... , αn} |= γ . Miremos el cociente finito Γ0/ ≡. La hipotesis de que α → β es tautologia o β → α es tautologia se puede traducir en que este cociente se puede ordenar totalmente. Sea [α] su primer elemento. Es claro que todos los elementos de [α] son consecuencia de α. Los elementos de clases mayores tambien, pues se tiene que α → β es tautologia para toda β que este en una clase [P] tal que [α] <= [P]. Entonces, todo Γ0 es consecuencia de α. Luego, {α} |= γ . | ||
[[Category:Prácticas]] | [[Category:Prácticas]] |