Parcial Lógica 13/10/06 (Lógica y Computabilidad)

De Cuba-Wiki

Plantilla:Back

Demostraciones por Inducción y Conectivos Adecuados[editar]

a. Sea perteneciente a Form, tal que los conectivos de no aparece el conectivo unario ¬.

1. Definir inductivamente , la fórmula 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[editar]

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[editar]

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[editar]

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)).