Edición de «Parcial 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 ==

Sean <math>\Gamma_1, \Gamma_2 \subseteq \mathbf{Form}</math> 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.''' <math>\Gamma_1 \subseteq \mathbf{Con}(\Gamma_1 \cap \Gamma_2)</math>.

'''b.''' <math>\mathbf{Con}(\Gamma_1 \cup \{\alpha \rightarrow \beta \mid \alpha \in \Gamma_1, \beta \in \Gamma_2\}) = \mathbf{Con}(\Gamma_1 \cup \Gamma_2)</math>.

'''c.''' Si <math>\mathbf{Con}(\Gamma_1) \subseteq \mathbf{Con}(\Gamma_2)</math> entonces <math>\Gamma_1 \subseteq \Gamma_2</math>.

'''d.''' <math>\mathbf{Con}(\{ \alpha \wedge \beta \mid \alpha \in \Gamma_1, \beta \in \Gamma_2\}) \subseteq \mathbf{Con}(\Gamma_1)</math>.

== Ejercicio 2 ==

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

== Ejercicio 3 ==

Una función <math>f</math> se dice ''casi sobreyectiva'' si <math>\{y \mid (\forall x)  f(x) \neq y\}</math> 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 “<math>f</math> es una función casi sobreyectiva”.

== Ejercicio 4 ==

Sea <math>\mathcal{L}</math> un lenguaje de primer orden y sean <math>\mathcal{C}_1</math> y <math>\mathcal{C}_2</math> dos clases de <math>\mathcal{L}</math>-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 <math>\Gamma</math> un conjunto de axiomas correcto y completo respecto a <math>\mathcal{C}_1</math>. Si <math>\mathcal{C}_2 \neq \mathcal{C}_1</math>,  entonces <math>\Gamma</math> no es completa respecto a <math>\mathcal{C}_2</math>.

'''b.''' Sean <math>\Gamma_1 = \lbrace \varphi \mid \mathcal{C}_1 \models \varphi \rbrace</math> y <math>\Gamma_2 = \lbrace \varphi \mid \mathcal{C}_2 \models \varphi \rbrace</math>. Si <math>\mathcal{C}_1 \subseteq \mathcal{C}_2</math> entonces <math>\Gamma_1 \supseteq \Gamma_2</math>.

''Nota:'' Decimos que <math>\mathcal{C} \models \varphi</math> sii para toda <math>\mathcal{L}</math>-estructura <math>\mathcal{A} \in \mathcal{C}</math>
sucede que <math>\mathcal{A} \models \varphi</math>.