Edición de «Parcial Lógica 13/10/06 (Lógica y Computabilidad)»

{{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 ¬.

1. Definir inductivamente <math>\alpha_R</math>, la f'ormula asociada a <math>\alpha</math> que se obtiene leyendo los s'imbolos de <math>\alpha</math> en orden inverso, cambiando el sentido de los par'entesis cuando corresponda. Por ejemplo, si <math>\alpha = ((p_1 \lor p_2) \to (p_4 \lor p_3))</math>,
entonces <math>\alpha_R = ((p_3 \lor p_4) \to (p_2 \lor p_1)).</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''

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

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

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

<math>\varphi</math> = ∀y∃x(''f''(x) = y),

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

[[Category:Parciales]]