Recuperatorio de Lógica Verano 2017 (LyC)

De Cuba-Wiki
Saltar a: navegación, buscar

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[editar]

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[editar]

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[editar]

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[editar]

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 .