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

• 1. Demostraciones por Induccion y Conectivos Adecuados

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

1. Definir inductivamente $\alpha _{R}$, la f'ormula asociada a $\alpha$ que se obtiene leyendo los s'imbolos de $\alpha$ en orden inverso, cambiando el sentido de los par'entesis cuando corresponda. Por ejemplo, si $\alpha =((p_{1}\lor p_{2})\to (p_{4}\lor p_{3}))$, entonces $\alpha _{R}=((p_{3}\lor p_{4})\to (p_{2}\lor p_{1})).$

2. Si además en la fórmula no aparece el conectivo binario $\to$, mostrar que para toda valuación vale $v(\alpha )\equiv v(\alpha _{R})$. Dar un ejemplo que muestre que esta afirmaci'on no es v'alida cuando $\to$ es un conectivo de $\alpha$

• 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 $\Gamma =\{\alpha _{1},\alpha _{2},...\}$ 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 $\alpha _{j}\to \alpha _{i}$ 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:$U^{I}$ = {n ∈ N | n divide a 12} y la igualdad se interpreta como la igualdad. Observar: #U^I = 6. Para cada elemento n ∈ $U^{I}$ distinguible, dar una formula $\phi _{n}$ que lo distinga.

b. Consideramos un vocabulario con igualdad y un símbolo de función unario, f. Determine, justificando adecuadamente, un modelo de $\varphi \land \psi$ en el que todo elemento sea distinguible.

$\varphi$ = ∀y∃x(f(x) = y),

ψ = ∃x∃y(¬(x = y) ^ f(x) = f(y)).