Parcial de Lógica Verano 2017 (LyC)

Ejercicio 1

Sean $\Gamma _{1},\Gamma _{2}\subseteq \mathbf {Form}$ dos conjuntos de fórmulas de la lógica proposicional. Decidir en cada caso si la afirmación es verdadera o falsa y justificar apropiadamente (i.e., demostrar o dar un contraejemplo).

a. $\Gamma _{1}\subseteq \mathbf {Con} (\Gamma _{1}\cap \Gamma _{2})$.

b. $\mathbf {Con} (\Gamma _{1}\cup \{\alpha \rightarrow \beta \mid \alpha \in \Gamma _{1},\beta \in \Gamma _{2}\})=\mathbf {Con} (\Gamma _{1}\cup \Gamma _{2})$.

c. Si $\mathbf {Con} (\Gamma _{1})\subseteq \mathbf {Con} (\Gamma _{2})$ entonces $\Gamma _{1}\subseteq \Gamma _{2}$.

d. $\mathbf {Con} (\{\alpha \wedge \beta \mid \alpha \in \Gamma _{1},\beta \in \Gamma _{2}\})\subseteq \mathbf {Con} (\Gamma _{1})$.

Ejercicio 2

Sea $\Gamma \subseteq \mathbf {Form}$ un conjunto de fórmulas de la lógica proposicional. Demostrar que $\mathbf {Con} (\Gamma )$ es maximal consistente si y solo si existe una única valuación $v$ tal que $v\vDash \Gamma$.

Ejercicio 3

Una función $f$ se dice casi sobreyectiva si $\{y\mid (\forall x)f(x)\neq y\}$ es finito y no vacío. Demostrar que, dado un lenguaje de primer orden con igualdad y un símbolo de función unario, no es expresable la propiedad “$f$ es una función casi sobreyectiva”.

Ejercicio 4

Sea ${\mathcal {L}}$ un lenguaje de primer orden y sean ${\mathcal {C}}_{1}$ y ${\mathcal {C}}_{2}$ dos clases de ${\mathcal {L}}$-estructuras. Decidir en cada caso si la afirmación es verdadera o falsa y justificar apropiadamente (i.e., demostrar o dar un contraejemplo).

a. Sea $\Gamma$ un conjunto de axiomas correcto y completo respecto a ${\mathcal {C}}_{1}$. Si ${\mathcal {C}}_{2}\neq {\mathcal {C}}_{1}$, entonces $\Gamma$ no es completa respecto a ${\mathcal {C}}_{2}$.

b. Sean $\Gamma _{1}=\lbrace \varphi \mid {\mathcal {C}}_{1}\models \varphi \rbrace$ y $\Gamma _{2}=\lbrace \varphi \mid {\mathcal {C}}_{2}\models \varphi \rbrace$. Si ${\mathcal {C}}_{1}\subseteq {\mathcal {C}}_{2}$ entonces $\Gamma _{1}\subseteq \Gamma _{2}$.

Nota: Decimos que ${\mathcal {C}}\models \varphi$ sii para toda ${\mathcal {L}}$-estructura ${\mathcal {A}}\in {\mathcal {C}}$ sucede que ${\mathcal {A}}\models \varphi$.