Edición de «Parcial de Lógica Verano 2016 (LyC)»

{{Back|Lógica y Computabilidad}}

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 <math>\clubsuit</math> un conectivo binario tal que para toda <math>v</math> valuación,

<math>
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))
</math>

Demostrar que el conjunto <math>\lbrace \rightarrow, \clubsuit \rbrace</math> '''no''' es adecuado.

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

# Sean <math>\Gamma</math> y <math>\Gamma'</math> dos conjuntos consistentes de fórmulas de la lógica proposicional. Si <math>\Gamma \cap \Gamma'</math> es maximal consistente entonces <math>\Gamma</math> y <math>\Gamma'</math> son iguales.
# Sean <math>\Gamma</math> y <math>\Gamma'</math> dos conjuntos inconsistentes de fórmulas de la lógica proposicional. Entonces <math>\Gamma \cap \Gamma'</math> 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 <math>\mathcal{L} = \lbrace\mathcal{R}\rbrace</math>, un lenguaje de primer orden con un símbolo de predicado binario <math>/mathcal{R}</math> y sea <math>SQ</math> la axiomatización correcta y completa respecto a la clase de todos los modelos vista en clase.

# Proponer una axiomatización <math>SQ_{equiv}</math> que extienda a <math>SQ</math> 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.
# 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 <math>\mathcal{L} = \lbrace =, \mathcal{R} \rbrace</math> un lenguaje de primer orden con igualdad y un símbolo de predicado binario <math>\mathcal{R}</math>. Decimos que una relación <math>R</math> tiene sus ciclos bajo control si para todo elemento <math>x</math> del dominio existe <math>k \in \mathbb{N}</math> tal que para todo ciclo con origen en <math>x</math> de la forma <math>R(x,y_1), R(y_1,y_2), \dots, R(y_{n-1},y_n), R(y_n,x)</math> con <math>todosDistintos(x, y_1, \dots, y_n)</math>, se tiene que <math>n \leq k</math>.

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