Edición de «Parcial Lógica 13/10/06 (Lógica y Computabilidad)»
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: | ||
*'''1. Demostraciones por Induccion y Conectivos Adecuados''' | |||
a. Sea <math>\alpha</math> perteneciente a ''Form'', tal que los conectivos de <math>\alpha</math> no aparece el conectivo unario ¬. | a. Sea <math>\alpha</math> perteneciente a ''Form'', tal que los conectivos de <math>\alpha</math> no aparece el conectivo unario ¬. | ||
Línea 10: | Línea 8: | ||
2. Si además en la fórmula no aparece el conectivo binario <math>\to</math>, mostrar que para toda valuación vale <math>v(\alpha) \equiv v(\alpha_R)</math>. Dar un ejemplo que muestre que esta afirmaci'on no es v'alida cuando <math>\to</math> es un conectivo de <math>\alpha</math> | 2. Si además en la fórmula no aparece el conectivo binario <math>\to</math>, mostrar que para toda valuación vale <math>v(\alpha) \equiv v(\alpha_R)</math>. Dar un ejemplo que muestre que esta afirmaci'on no es v'alida cuando <math>\to</math> es un conectivo de <math>\alpha</math> | ||
* '''Consecuencia Lógica y Álgebras de Boole''' | |||
a. Dado Γ ⊂ ''Form'' definimos ¬Γ = {¬α|α ∈ Γ}. Determinar, justificando adecuadamente, la verdad o falsedad de la siguiente afirmación. Para todo Γ ⊂ ''Form'' vale Con(Γ) ∩ Con(¬Γ) = ''Form'' ó Con(Γ) ∩ Con(¬Γ) = ''Taut'' | a. Dado Γ ⊂ ''Form'' definimos ¬Γ = {¬α|α ∈ Γ}. Determinar, justificando adecuadamente, la verdad o falsedad de la siguiente afirmación. Para todo Γ ⊂ ''Form'' vale Con(Γ) ∩ Con(¬Γ) = ''Form'' ó Con(Γ) ∩ Con(¬Γ) = ''Taut'' | ||
* '''Teoremas de Compacidad''' | |||
a. Sea <math>\Gamma = \{\alpha_1, \alpha_2, ...\}</math> un conjunto infinito de fórmulas satisfacibles del cálculo proposicional con la propiedad siguiente: para todo ''i'' y para todo ''j'', si ''i'' divide a ''j'' entonces la fórmula <math>\alpha_j \to \alpha_i</math> es una tautología. Probar que Γ es satisfacible. | a. Sea <math>\Gamma = \{\alpha_1, \alpha_2, ...\}</math> un conjunto infinito de fórmulas satisfacibles del cálculo proposicional con la propiedad siguiente: para todo ''i'' y para todo ''j'', si ''i'' divide a ''j'' entonces la fórmula <math>\alpha_j \to \alpha_i</math> es una tautología. Probar que Γ es satisfacible. | ||
* '''Elementos Distinguibles''' | |||
a. Sea V = {D, =} un vocabulario con dos símbolos de relación binarios y consideremos la interpretación I dada por:<math> U^I</math> = {n ∈ N | n divide a 12} y la igualdad se interpreta como la igualdad. Observar: #U^I = 6. Para cada elemento n ∈ <math>U^I</math> distinguible, dar una formula <math>\phi_n</math> que lo distinga. | a. Sea V = {D, =} un vocabulario con dos símbolos de relación binarios y consideremos la interpretación I dada por:<math> U^I</math> = {n ∈ N | n divide a 12} y la igualdad se interpreta como la igualdad. Observar: #U^I = 6. Para cada elemento n ∈ <math>U^I</math> distinguible, dar una formula <math>\phi_n</math> que lo distinga. | ||
Línea 27: | Línea 26: | ||
ψ = ∃x∃y(¬(x = y) ^ f(x) = f(y)). | ψ = ∃x∃y(¬(x = y) ^ f(x) = f(y)). | ||