Edición de «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 <math>*</math>-fórmulas de la siguiente forma:
* Toda variable proposicional <math>p_i</math> es una <math>*</math>-fórmula.
* Si <math>\psi</math> y <math>\phi</math> son <math>*</math>-fórmulas, entonces <math>\psi*\phi</math> es una <math>*</math>-fórmula.
* Nada más es una <math>*</math>-fórmula.
Para una valuación <math>v</math> y una <math>*</math>-fórmula <math>\phi*\psi</math>, se define que <math>v\models \phi*\psi</math> si y solo si <math>v\nvDash \phi</math> y <math>v\nvDash \psi</math>.


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

== Ejercicio 2 ==

Sean <math>\Gamma_1, \Gamma_2 \subseteq \mathbf{Form}</math> dos conjuntos maximales consistentes de fórmulas de la lógica proposicional.

'''a.''' Demuestre que <math>\Gamma_1 = \Gamma_2</math> si y solo si <math>\Gamma_1 \vartriangle \Gamma_2</math> es satisfacible.

'''b.''' Sean <math>\alpha, \beta \in \Gamma_1 \vartriangle \Gamma_2</math>. Demuestre que, si <math>\Gamma_1 \cup \lbrace \alpha \rbrace \vdash \beta</math>, entonces <math>\Gamma_2 \vdash \beta \rightarrow \alpha</math>.

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

== Ejercicio 3 ==

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

== Ejercicio 4 ==

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

'''S1''': <math>(\forall x) (*_2(x) = x \rightarrow x = 0)</math>

'''S2''': <math>(\forall x)(\forall y) (x \not= y \rightarrow *_2(x) \not= *_2(y))</math>


'''a.''' Demostrar que <math>S2</math> es verdadero en <math>\mathcal{N}</math>.

'''b.''' Demostrar que <math>SQ_N</math> no es completa con respecto a <math>\mathcal{N}</math>. Esto significa encontrar una fórmula <math>\varphi \in \mathcal{L}</math> y un modelo <math>\mathcal{M}</math> tal que <math>\mathcal{N} \models \varphi</math>, <math>\mathcal{M} \models SQ_N</math>, pero <math>\mathcal{M} \not\models \varphi</math>.
Revisión actual		Tu texto
Línea 35:		Línea 35:


	'''a.''' Demostrar que S2 es verdadero en <math>\mathcal{N}</math>.		'''a.''' Demostrar que <math>S2</math> es verdadero en <math>\mathcal{N}</math>.

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