Recuperatorio de Lógica Verano 2017 (LyC)

El examen es a libro abierto y se puede suponer demostrado lo dado en las clases y los ejercicios de las guías colocando referencias claras. Entregar cada ejercicio en hojas separadas. En cada hoja debe figurar nombre y apellido.

Ejercicio 1

Se definen las $*$-fórmulas de la siguiente forma:

• Toda variable proposicional $p_{i}$ es una $*$-fórmula.
• Si $\psi$ y $\phi$ son $*$-fórmulas, entonces $\psi *\phi$ es una $*$-fórmula.
• Nada más es una $*$-fórmula.

Para una valuación $v$ y una $*$-fórmula $\phi *\psi$, se define que $v\models \phi *\psi$ si y solo si $v\nvDash \phi$ y $v\nvDash \psi$.

Demuestre que para toda fórmula $\phi$ de la lógica proposicional usual, existe una $*$-fórmula $\psi$ tal que para toda valuación $v$, $v\vDash \phi$ si y solo si $v\vDash \psi$.

Ejercicio 2

Sean $\Gamma _{1},\Gamma _{2}\subseteq \mathbf {Form}$ dos conjuntos maximales consistentes de fórmulas de la lógica proposicional.

a. Demuestre que $\Gamma _{1}=\Gamma _{2}$ si y solo si $\Gamma _{1}\vartriangle \Gamma _{2}$ es satisfacible.

b. Sean $\alpha ,\beta \in \Gamma _{1}\vartriangle \Gamma _{2}$. Demuestre que, si $\Gamma _{1}\cup \lbrace \alpha \rbrace \vdash \beta$, entonces $\Gamma _{2}\vdash \beta \rightarrow \alpha$.

Aclaración: La notación $A\vartriangle B$ hace referencia a la diferencia simétrica entre los conjuntos $A$ y $B$, es decir, al conjunto $(A\cup B)\backslash (A\cap B)$.

Ejercicio 3

Sea ${\mathcal {L}}$ un lenguaje de primer orden con igualdad y con dos funciones unarias $suc(x)$ y $f(x)$. La función $f$ se dice periódica si existe un número $n\in \mathbb {N}$ tal que para todo $x$ vale que $f(suc^{n}(x))=f(x)$. Demuestre que no es expresable la propiedad “$f$ es una función periódica”.

Ejercicio 4

Vamos a llamar ${\mathcal {N}}=\langle \mathbb {N} ;0;*_{2}\rangle$ al modelo usual de los números naturales con cero y la función que multiplica un natural por $2$. Considerar un lenguaje de primer orden con igualdad ${\mathcal {L}}$ con un símbolo de constante $0$ y un símbolo unario de función $*_{2}$. Sea la siguiente axiomatización $SQ_{N}$, que extiende a $SQ$ con los axiomas:

S1: $(\forall x)(*_{2}(x)=x\rightarrow x=0)$

S2: $(\forall x)(\forall y)(x\not =y\rightarrow *_{2}(x)\not =*_{2}(y))$

a. Demostrar que S2 es verdadero en ${\mathcal {N}}$.

b. Demostrar que $SQ_{N}$ no es completa con respecto a ${\mathcal {N}}$. Esto significa encontrar una fórmula $\varphi \in {\mathcal {L}}$ y un modelo ${\mathcal {M}}$ tal que ${\mathcal {N}}\models \varphi$, ${\mathcal {M}}\models SQ_{N}$, pero ${\mathcal {M}}\not \models \varphi$.