Practico 10 Logica de primer orden

Vista previa del material en texto

Matemática para Informática
Primer Cuatrimestre 2016
Trabajo Práctico N� 10: Lógica de Primer Orden
Objetivos
El estudiante debe ser capaz de:
� Iniciarse en el manejo de herramientas de la Lógica de Primer orden.
� Demostrar teoremas basados en los axiomas.
� Reconocer la utililidad de la formalización de la Lógica Matemática.
Duración: Seis (6) horas
1. (a) Da un ejemplo de un símbolo de una operación de dos lugares.
(b) Da un ejemplo de un símbolo de predicado de tres lugares.
2. (a) De�ne fórmula.
(b) Da un ejemplo de una fórmula donde una variable esté acotada y la otra sea libre.
3. (a) Dada la siguiente fórmula reescribir sin usar puntos y usando las otras convenciones:
P ! Q:! :P :!: P ! Q:! :Q
(b) Realiza una prueba formal de la fórmula dada en (a).
4. Usando las de�niciones de _ , ^ y $ en término de los símbolos s, !, ( y ), expresa las fórmulas
siguientes sin usar _ e ^ :
(a) P ^Q! P (b) P ^Q$ Q ^ P
(c) P_ s P (d) P ^Q! P
5. Prueba que la siguiente fórmula es un teorema del cálculo proposicional:
P ! :Q! R :!: Q! :P ! R,
primero realizando una deducción línea a línea, luego repita la demostración usando el Teorema de
la Completitud del Cálculo Proposicional y el hecho de que es una tautología.
6. (a) Escribe en forma simbólica las siguientes espresiones:
Existe al menos una u tal que P (u) Existe a lo sumo una u tal que P (u)
Existe exactamente una u tal que P (u) Existe u tal que P (u)
(b) Repite el item anterior reemplazando una por dos.
1