Parcial de Lógica Verano 2016 (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, apellido y número de orden. El examen consta de 4 ejercicios de igual valor. Cada ejercicio será calificado con A (aprobado), R (regular) o I (insuficiente), ocasionalmente con un signo - (menos). Para aprobar un parcial es necesario tener al menos dos ejercicios calificados con A o A-. Para promocionar es necesario tener al menos tres ejercicios calificados con A o A- en ambos parciales o sus correspondientes recuperatorios.

Ejercicio 1

Sea $\clubsuit$ un conectivo binario tal que para toda $v$ valuación,

$v\models a\clubsuit b\Longleftrightarrow ((v\models \alpha {\text{ y }}v\models \beta ){\text{ o }}(v\not \models \alpha {\text{ y }}v\not \models \beta ))$

Demostrar que el conjunto $\lbrace \rightarrow ,\clubsuit \rbrace$ no es adecuado.

Ejercicio 2

Decidir si son verdaderas o falsas las siguientes afirmaciones. Justificar la respuesta.

1. Sean $\Gamma$ y $\Gamma '$ dos conjuntos consistentes de fórmulas de la lógica proposicional. Si $\Gamma \cup \Gamma '$ es maximal consistente entonces $\Gamma$ y $\Gamma '$ son iguales.
2. Sean $\Gamma$ y $\Gamma '$ dos conjuntos inconsistentes de fórmulas de la lógica proposicional. Entonces $\Gamma \cup \Gamma '$ no es maximal consistente.

Ejercicio 3

Decimos que un modelo de primer orden es de equivalencia si todas sus relaciones binarias son de equivalencia. Sea ${\mathcal {L}}=\lbrace {\mathcal {R}}\rbrace$, un lenguaje de primer orden con un símbolo de predicado binario ${\mathcal {R}}$ y sea $SQ$ la axiomatización correcta y completa respecto a la clase de todos los modelos vista en clase.

1. Proponer una axiomatización $SQ_{equiv}$ que extienda a $SQ$ y que sea correcta y completa respecto a la clase de modelos que son de equivalencia. Justificar apropiadamente que la axiomatización propuesta cumple lo pedido.
2. Demostrar que la axiomatización dada en el ítem anterior es completa pero no es correcta respecto a la clase de todos los modelos.

Ejercicio 4

Sea ${\mathcal {L}}=\lbrace =,{\mathcal {R}}\rbrace$ un lenguaje de primer orden con igualdad y un símbolo de predicado binario ${\mathcal {R}}$. Decimos que una relación $R$ tiene sus ciclos bajo control si para todo elemento $x$ del dominio existe $k\in \mathbb {N}$ tal que para todo ciclo con origen en $x$ de la forma $R(x,y_{1}),R(y_{1},y_{2}),\dots ,R(y_{n-1},y_{n}),R(y_{n},x)$ con $todosDistintos(x,y_{1},\dots ,y_{n})$, se tiene que $n\leq k$.

Demostrar que no es posible expresar en primer orden que una relación tiene sus ciclos bajo control.