Revisión actual |
Tu texto |
Línea 1: |
Línea 1: |
| {{Back|Lógica y Computabilidad}}
| | *'''1. Demostraciones por Induccion y Conectivos Adecuados''' |
|
| |
|
| ===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 <math>\alpha</math> 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>, |
| | |
| 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 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'as en la f'ormula no aparece el conectivo binario <math>\to</math>, mostrar que para toda valuaci'on 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)).
| | * '''Consecuencia L'ogica y 'Algebras de Boole''' |
|
| |
|
| [[Category:Parciales]]
| | a. Dado Γ ⊂ ''Form'' definimos |