Diferencia entre revisiones de «Parcial Lógica 13/10/06 (Lógica y Computabilidad)»
Sin resumen de edición |
Sin resumen de edición |
||
(No se muestran 7 ediciones intermedias del mismo usuario) | |||
Línea 1: | Línea 1: | ||
{{Back|Lógica y Computabilidad}} | |||
===Demostraciones por Inducción y Conectivos Adecuados=== | |||
a. Sea <math>\alpha</math> perteneciente a ''Form'', tal que los conectivos de \alpha no aparece el conectivo unario ¬. | a. Sea <math>\alpha</math> perteneciente a ''Form'', tal que los conectivos de \alpha no aparece el conectivo unario ¬. | ||
Línea 8: | Línea 10: | ||
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 26: | Línea 27: | ||
ψ = ∃x∃y(¬(x = y) ^ f(x) = f(y)). | ψ = ∃x∃y(¬(x = y) ^ f(x) = f(y)). | ||
[[Category:Parciales]] |
Revisión del 17:07 19 may 2010
Demostraciones por Inducción y Conectivos Adecuados
a. Sea perteneciente a Form, tal que los conectivos de \alpha no aparece el conectivo unario ¬.
1. Definir inductivamente , la f'ormula asociada a que se obtiene leyendo los s'imbolos de en orden inverso, cambiando el sentido de los par'entesis cuando corresponda. Por ejemplo, si , entonces
2. Si además en la fórmula no aparece el conectivo binario , mostrar que para toda valuación vale . Dar un ejemplo que muestre que esta afirmaci'on no es v'alida cuando es un conectivo de
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
Teoremas de Compacidad
a. Sea 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 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: = {n ∈ N | n divide a 12} y la igualdad se interpreta como la igualdad. Observar: #U^I = 6. Para cada elemento n ∈ distinguible, dar una formula que lo distinga.
b. Consideramos un vocabulario con igualdad y un símbolo de función unario, f. Determine, justificando adecuadamente, un modelo de en el que todo elemento sea distinguible.
= ∀y∃x(f(x) = y),
ψ = ∃x∃y(¬(x = y) ^ f(x) = f(y)).