Diferencia entre revisiones de «Recuperatorio de Lógica Verano 2017 (LyC)»

De Cuba-Wiki
(Página creada con «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 hoj...»)
 
 
Línea 35: Línea 35:




'''a.''' Demostrar que <math>S2</math> es verdadero en <math>\mathcal{N}</math>.
'''a.''' Demostrar que S2 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>.

Revisión actual - 13:59 24 nov 2017

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 -fórmulas de la siguiente forma:

  • Toda variable proposicional es una -fórmula.
  • Si y son -fórmulas, entonces es una -fórmula.
  • Nada más es una -fórmula.

Para una valuación y una -fórmula , se define que si y solo si y .


Demuestre que para toda fórmula de la lógica proposicional usual, existe una -fórmula tal que para toda valuación , si y solo si .

Ejercicio 2

Sean dos conjuntos maximales consistentes de fórmulas de la lógica proposicional.

a. Demuestre que si y solo si es satisfacible.

b. Sean . Demuestre que, si , entonces .

Aclaración: La notación hace referencia a la diferencia simétrica entre los conjuntos y , es decir, al conjunto .

Ejercicio 3

Sea un lenguaje de primer orden con igualdad y con dos funciones unarias y . La función se dice periódica si existe un número tal que para todo vale que . Demuestre que no es expresable la propiedad “ es una función periódica”.

Ejercicio 4

Vamos a llamar al modelo usual de los números naturales con cero y la función que multiplica un natural por . Considerar un lenguaje de primer orden con igualdad con un símbolo de constante y un símbolo unario de función . Sea la siguiente axiomatización , que extiende a con los axiomas:

S1:

S2:


a. Demostrar que S2 es verdadero en .

b. Demostrar que no es completa con respecto a . Esto significa encontrar una fórmula y un modelo tal que , , pero .