tppsflógica proposicional - 1 1. asistentes de pruebas para lógicos y matemáticos i. lógica...
TRANSCRIPT
![Page 1: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/1.jpg)
TPPSF Lógica Proposicional - 1
1. Asistentes de Pruebas
para Lógicos y Matemáticos
I. Lógica Proposicional
![Page 2: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/2.jpg)
TPPSF Lógica Proposicional - 2
1. Ejemplo: División
Sean a y b N, b0.
Calculamos a div b y a mod b simultáneamente haciendo recursión en a:
• 0 divmod b = <0,0>• (n+1) divmod b = let <q,r> = n divmod b
in if r < b-1then <q,r+1>else <q+1,0>
![Page 3: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/3.jpg)
TPPSF Lógica Proposicional - 3
División: especificación
• Especificación: Para todos a,b N tq. b0 existen q y r tq. a=b.q+r y r < b.
• Prueba de que el programa es correcto: por inducción en a:
• 0 divmod b = <0,0> • (n+1) divmod b =
let <q,r> = n divmod b
in if r < b-1then <q,r+1>else <q+1,0>
supongamos n=b.q+r y r < b.
luego, si r < b - 1
entonces n+1 = b.q+(r+1) y r+1<b
sino n+1 = b.(q+1)+0 y 0<b
0 = b.0 + 0 y 0 < b
![Page 4: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/4.jpg)
TPPSF Lógica Proposicional - 4
2. Lógica proposicional
Lógica como herramienta para especificar y probar corrección de programas.
Cálculo proposicional
Sintaxis– variables de proposición: A,B,C,....– conectivos: , , , , ~,
Semántica– noción de verdad: existencia de prueba
![Page 5: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/5.jpg)
TPPSF Lógica Proposicional - 5
Lógica proposicional en Coq
• Prop es la familia de proposiciones
• Declaración de variables de proposición:
Variable A,B,C: Prop
• Conectivos: , , son primitivos
– ~ := ( )
:= ( ) ( )
se escribe False
![Page 6: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/6.jpg)
TPPSF Lógica Proposicional - 6
Construcción de pruebas en Coq
Para comenzar:
– queremos probar cierta fórmula objetivo (goal)
– para ello, utilizaremos diferentes tácticas que transforman al objetivo original e introducen hipótesis adicionales
![Page 7: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/7.jpg)
TPPSF Lógica Proposicional - 7
Desarrollo de pruebas lógicas
Situación general:– existen varios objetivos a probar, cada uno a partir
de ciertas hipótesis: 1
1
2
2
n
n
...
donde:
– cada i es un conjunto de fórmulas (hipótesis) de la forma:
H0: 0, H1: 1,... Hk: k.– i es una fórmula
– cada i debe ser probada a partir de i
![Page 8: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/8.jpg)
TPPSF Lógica Proposicional - 8
Tácticas = Reglas de inferencia
Una táctica transforma un secuente de la forma:
en cero o más secuentes:
tales que probar los últimos es suficiente para construir una prueba del secuente original
i
i
i1 i1
i2 i2
in
in
...
![Page 9: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/9.jpg)
TPPSF Lógica Proposicional - 9
Tácticas
Assumption
H:
Probado!caso trivial
![Page 10: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/10.jpg)
TPPSF Lógica Proposicional - 10
Tácticas (II) Reglas de introducción
Intro H
H:
• el identificador H es opcional
• variantes: Intros, Intros H1,...Hn
introducción
![Page 11: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/11.jpg)
TPPSF Lógica Proposicional - 11
Tácticas (III) Reglas de introducción (cont.)
introducción (Izq.)
Left
introducción (Der.)
Right
![Page 12: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/12.jpg)
TPPSF Lógica Proposicional - 12
Tácticas (IV) Reglas de introducción (cont.)
Absurd
False
“introducción”
Split
introducción
![Page 13: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/13.jpg)
TPPSF Lógica Proposicional - 13
Tácticas (V)Reglas de eliminación
Apply H
H:
H:
Apply H
H: 12...
H: ...
H: ...
...
en general:
eliminación
![Page 14: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/14.jpg)
TPPSF Lógica Proposicional - 14
Tácticas (VI) Reglas de eliminación (cont.)
eliminación
Elim HH:
H:
eliminación
Elim HH:
H:
H:
![Page 15: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/15.jpg)
TPPSF Lógica Proposicional - 15
Tácticas (VII) Reglas de eliminación (cont.)
eliminación
Elim HH: False
Probado!
![Page 16: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/16.jpg)
TPPSF Lógica Proposicional - 16
Tácticas (VIII)Otras tácticas
Utilización de lema intermediario
Cut
Explicitación de la prueba:
Exact t
Probado!
condición: t debe ser una prueba de (que figura
en las hipótesis o es un lema ya probado)
![Page 17: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/17.jpg)
TPPSF Lógica Proposicional - 17
Tácticas (IX)Eliminación de definiciones
Eliminación de definición
Unfold not
False
Eliminación de definición
Unfold iff
( ) ( )
variante: Unfold nom in h
![Page 18: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/18.jpg)
TPPSF Lógica Proposicional - 18
Observaciones
• En general:
si term es una prueba de una proposición , Elim term, aplica la regla de eliminación del conectivo principal de .
• Apply no se aplica solamente a una hipótesis H sino también a un lema previamente demostrados.
![Page 19: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/19.jpg)
TPPSF Lógica Proposicional - 19
Esquemas de proposición
Si demostramos
Variable A:Prop. Lemma L1 : A A. Proof. … Qed.La prueba es análoga para cualquier proposición.
Un esquema de proposición se expresa como:
Para toda proposición A, se cumple A A.
En Coq este esquema se expresa: (A:Prop) A A
![Page 20: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/20.jpg)
TPPSF Lógica Proposicional - 20
Esquemas de proposición Instanciación
Ejemplo:
Si ya demostramos en Coq
Lemma L2 : (A:Prop) A A Proof. … Qed.
Para demostrar ~False ~False
podemos hacer Exact (L2 ~False).
![Page 21: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/21.jpg)
TPPSF Lógica Proposicional - 21
3. Lógica proposicional clásicaAxioma del tercero excluído:
Para toda proposición P, se cumple P ~P
En lógica constructiva, una proposición es verdadera si y sólo si podemos exhibir una prueba.
Sabemos probar instancias de este axioma, pero no sabemos probar el esquema pues para cada proposición deberíamos exhibir una prueba de ella o de su negación (¿como haríamos con las conjeturas y resultados indecidibles?).
Ejemplo: sabemos probar 1=0 ~1=0 no sabemos (hoy) probar P=NP ~P=NP
![Page 22: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/22.jpg)
TPPSF Lógica Proposicional - 22
Lógica proposicional clásica
El axioma del tercero excluído no se demuestra en lógica constructiva.
En Coq este axioma está declarado en el módulo Classical y se llama classic.
Require Classical....
Check (classic A).(classic A) : (A \/ ~A)
![Page 23: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/23.jpg)
TPPSF Lógica Proposicional - 23
4. Razonamiento automatizado
Tauto
Probado!
Tautologías constructivas
Tauto implementa una estrategia de construcción de pruebas de tautologías constructivas.Esta estrategia tiene éxito cuando es una tautología cuya prueba no usa el tercero excluído.No es un procedimiento de decisión, pues construyeuna prueba. [Muñoz94]
![Page 24: TPPSFLógica Proposicional - 1 1. Asistentes de Pruebas para Lógicos y Matemáticos I. Lógica Proposicional](https://reader035.vdocumento.com/reader035/viewer/2022070416/5665b4971a28abb57c927660/html5/thumbnails/24.jpg)
TPPSF Lógica Proposicional - 24
Táctica (Semi)Automática
Auto
Probado!
Aplicación (hacia atrás) de lemas e hipótesis
Auto implementa una estrategia de construcción de pruebas similar a la de Prolog (razonamiento hacia atrás) aplicando lemas e hipótesis. Considera únicamente aquellos lemas declarados como Hint. No es un procedimiento de decisión pues construye una prueba.
O bien
Auto