Título: PPA – Un asistente de demostración para lógica de primer orden con extracción de testigos usando la traducción de Friedman
Director: Pablo Barenbaum
Jurado:
– Verónica Becher
– Miguel Pagano (FaMAF, UNC)

Transmision: https://youtube.com/live/9uIHpGT4EnI

Resumen:
Los asistentes de demostración son programas que simplifican la escritura de demostraciones matemáticas, permitiendo la colaboración masiva o la verificación formal de programas.
Existen muchos asistentes como Mizar, Coq e Isabelle, basados en distintas teorías. Un criterio deseable que pueden cumplir es el de De Bruijn: a partir de demostraciones en un lenguaje de alto nivel se pueden extraer demostraciones en un lenguaje núcleo fácilmente verificable. Esto elimina la necesidad de tener que confiar en la implementación del asistente, ya que las demostraciones pueden ser verificadas por un programa independiente.
En esta tesis se presenta PPA, un asistente de demostración para lógica clásica de primer orden. Cumple con el criterio de De Bruijn, generando demostraciones en el sistema lógico de deducción natural a partir de programas escritos en un lenguaje de alto nivel, cuyo objetivo es ser similar a cómo serían en lenguaje natural. Tiene un mecanismo principal de demostración, el by, que por debajo cuenta con un solver heurístico para lógica de primer orden que facilita la escritura de demostraciones. Está inspirado en el mecanismo análogo en Mizar.
Algunos asistentes implementan la extracción de testigos de existencial. Dada una demostración de ∃x.p(x), se extrae un testigo t tal que cumpla p(t). Es sencillo hacerlo sobre lógica intuicionista por su naturaleza constructiva, pero un desafío sobre lógica clásica, que no lo es. Para ello hay dos grandes categorías: directas (mediante técnicas semánticas como realizabilidad clásica) o indirectas (mediante traducciones a otra lógica, como intuicionista).
El aporte principal del trabajo es una implementación práctica de la extracción de testigos. PPA la implementa de forma indirecta usando la traducción de Friedman, que permite convertir demostraciones clásicas de fórmulas Π2 de la forma ∀y0…∀yn.∃x.φ, con φ sin cuantificadores, a demostraciones intuicionistas. Se describe cómo una vez traducidas pueden ser normalizadas usando reglas de reducción bien conocidas, que se corresponden con las reglas de reducción del cálculo-lambda vistas desde el isomorfismo Curry–Howard. Finalmente, de una demostración normalizada se podrá extraer un testigo. Identificamos algunos detalles en la implementación práctica de la traducción, que limitan las fórmulas para las cuales se puede usar (más allá de la limitación teórica de Π2) y también limitan las axiomatizaciones de las teorías que se pueden procesar.