Download Lógica Proposicional 2

Lógica Proposicional 2:!
Deducción Sintáctica!
rafael ramirez
rafael.ramirez@upf.edu
55.316 (Tanger)
Deducción Sintáctica en LP
Previamente teníamos la notacion (para implicacion semántica)
Cuyo significado es “siempre que las premisas
verdad, la conclusion es vedad”.
sean
Definimos una relación nueva (para deducción sintáctica)
Cuyo significado es “de las premisas
podemos concluir
“
2
Deducción Natural
Objetivo:
Inferir fórmulas a partir de otras fórmulas usando un conjunto de reglas
de inferencia.
Esto se denota
Donde la parte izquierda son las premisas y la parte derecha es la
conclusión.
Esta expression es válida si existe una prueba usando las reglas de
inferencia.
3
Deducción Natural: Reglas
Básicas
4
Deducción Natural: Algunas
reglas derivadas
5
Reglas para Conjunción
6
Reglas para Doble Negación
7
Reglas para Eliminar la
Implicación
8
Eliminar la Implicación…
9
Introducir la Implicación…
10
Introducir la Implicación…
11
Introducir la Implicación…
12
Introducir la Implicación…
El ejemplo anterior muestra que se puede transformar la pueba
En la prueba
13
Consistencia
Teorema (Consistencia)
14
Consistencia
Teorema (Consistencia)
Prueba:
15
Consistencia
Prueba…
16
Completitud
Las reglas de Deducción Natural también son completas.
Teorema (Completitud)
Utilidad: dados los teoremas de consistencia y completitud
si y solo si
Así que cualquiera de los dos métodos puede ser usado
Ambos, verificación por tablas de verdad y la búsqueda de pruebas
son métodos en general intractables*.
* Problemas que pueden ser solucionados pero no lo suficientemente rápido para que la solución sea útil (2n, n=100, 1012OPS, 4x1010years)
17
Completitud
Teorema (Completitud)
Prueba:
La prueba consiste en tres pasos:
18
Completitud
19
Completitud
El corazón de la prueba de completitud es el paso 2 (Step 2) que
requiere probar lo siguiente:
La idea de la prueba es la siguiente:
- Supón
es verdad
- Si
tiene n letras proposicionales p1,…,pn entonces
en todas las 2n lineas de su tabla de verdad.
evalua a T
- Entonces “codificamos” cada línea de la tabla de verdad como una prueba
y las ensamblamos en una prueba para usando las reglas de disyunción.
20
Equivalencia Semántica, Validez
21
Forma Normal Conjuntiva (FNC)
22
Validez de una Disyunción de Literales
23
De Tablas de Verdad a FNC
24
Cláusulas de Horn
25