Diferencia entre revisiones de «Parcial Lógica 13/10/06 (Lógica y Computabilidad)»
Sin resumen de edición |
|||
(No se muestran 9 ediciones intermedias de 2 usuarios) | |||
Línea 1: | Línea 1: | ||
{{Back|Lógica y Computabilidad}} | |||
===Demostraciones por Inducción y Conectivos Adecuados=== | |||
1. Definir inductivamente <math>\alpha_R</math>, la | a. Sea <math>\alpha</math> perteneciente a ''Form'', tal que los conectivos de <math>\alpha</math> no aparece el conectivo unario ¬. | ||
1. Definir inductivamente <math>\alpha_R</math>, la fórmula 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> | entonces <math>\alpha_R = ((p_3 \lor p_4) \to (p_2 \lor p_1)).</math> | ||
2. Si | 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]] |
Revisión actual - 22:38 19 may 2010
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)).