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

Demostraciones por Inducción y Conectivos Adecuados

a. Sea Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha} perteneciente a Form, tal que los conectivos de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \alpha} no aparece el conectivo unario ¬.

1. Definir inductivamente $\alpha _{R}$, la fórmula 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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle v(\alpha) \equiv v(\alpha_R)} . Dar un ejemplo que muestre que esta afirmaci'on no es v'alida cuando Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \to} es un conectivo de Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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:Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U^I} = {n ∈ N | n divide a 12} y la igualdad se interpreta como la igualdad. Observar: #U^I = 6. Para cada elemento n ∈ Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle U^I} distinguible, dar una formula Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \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 Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \varphi \land \psi} en el que todo elemento sea distinguible.

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\displaystyle \varphi} = ∀y∃x(f(x) = y),

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