Lean 4 y verificación formal: primero derriba una fila de fichas de dominó
Una fila de fichas de dominó que se extiende hasta donde no alcanza la vista. ¿Cómo te aseguras de que todas caerán?
Esta fila de fichas de dominó se extiende hasta donde no se ve. ¿Cómo confirmar que todas caerán?
Revisarlas una por una: incluso al anochecer solo sabrás que "las revisadas están bien". Esto es testing.
Cambiemos de método: confirma solo dos cosas: que la primera cae, y que cada ficha derriba a la siguiente. Entonces, sin mirar más, todas caerán. Esto es demostración.
Con los programas pasa igual. Las pruebas solo pueden decir "las entradas probadas están bien"; una demostración puede decir "todas las entradas están bien". Este curso te enseña a escribir tales demostraciones y a dejar que una herramienta llamada Lean las verifique paso a paso: como cuando quitaste una ficha, si falta un eslabón, se detiene.
Prueba otro: demuestra una vez en lenguaje llano
Una demostración no tiene por qué usar símbolos. Dado que "llueve y hace viento", muestra que "hace viento y llueve".
Dado (lo que tienes)
Lo que hay que demostrar
Lo que hay que demostrar es "hace viento y llueve", que son dos cosas. No se puede explicar de una vez: primero sepáralas.
Lo mismo, escrito en Lean
example (p q : Prop) (h : p ∧ q) : q ∧ p := byDado h: p y q. Hay que demostrar: q y p. constructorDividirlo en dos subobjetivos exact h.rightUsando la mitad derecha conocida exact h.leftUsando la mitad izquierda conocidap Está lloviendo q Se levantó viento ∧ y h La frase conocida
Las cuatro líneas de la derecha son una verdadera demostración en Lean, que pasa la verificación de Lean:
example (p q : Prop) (h : p ∧ q) : q ∧ p := by
constructor
exact h.right
exact h.leftAhora no necesitas recordar estas palabras. Llévate solo una sensación: hay un objetivo que justificar, y cada paso debe tener su fundamento, hasta que no quede nada por justificar. Las lecciones siguientes solo añaden cosas sobre esa sensación.
- Derribé esa fila de dominó, y también probé quitar una ficha
- Terminé de demostrar en lenguaje llano que "hace viento y llueve"
Qué tendrás en las manos al terminar
Un mini compilador escrito por ti y demostrado correcto por Lean: traduce expresiones aritméticas a instrucciones, y además demostraste que, para cualquier expresión, las instrucciones resultantes calculan el mismo resultado que la expresión original.
No necesitas base matemática; basta con saber un poco de programación en cualquier lenguaje.
Ruta
| Etapa | Lección | Lograrás |
|---|---|---|
| Inicio | Qué es la verificación formal | Explicar en qué se diferencian las pruebas y las demostraciones |
| Instala Lean 4 | Lograr que Lean calcule 1 + 1 en tu propia computadora | |
| Primera demostración | Escribir y entender un teorema | |
| Lógica | Si… entonces… | Usar intro, apply, exact |
| Y y O | Descomponer y componer proposiciones compuestas | |
| Deja que Lean calcule por ti | Usar rw, simp, omega, decide | |
| Inducción | Inducción sobre los números naturales | Demostrar cosas que valen para todos los números naturales |
| Inducción sobre listas | Demostrar que "invertir dos veces equivale a no invertir" | |
| Verificación de programas | Demostrar que un compilador es correcto | Completar el proyecto final |
Cómo garantiza este curso que no haya errores
- Cada fragmento de código Lean del texto fue verificado realmente por Lean 4.35.0 antes de publicarse. Los ejemplos marcados como "dará error" también se confirmó que realmente dan error.
- Las salidas que siguen a "deberías ver" fueron cotejadas con la salida real de Lean.
- Los estados de objetivo y los errores de los ejercicios interactivos son generados por un script a partir de Lean.
Si tras una actualización de Lean lo que ves no coincide con el texto, dínoslo al final de esa sección.
Preguntas frecuentes
¿Qué lenguaje es Lean 4?
Lean es una herramienta que verifica tus demostraciones paso a paso, y Lean 4 es su versión actual. Este curso te enseña a escribir demostraciones y a dejar que Lean verifique cada paso: si falta un eslabón, se detiene. Cada fragmento de código Lean del texto fue verificado realmente por Lean 4.35.0 antes de publicarse.
¿Qué es la verificación formal? ¿Cómo entender este término?
La verificación formal consiste en sustituir las pruebas por demostraciones: las pruebas solo pueden decir "las entradas probadas están bien"; una demostración puede decir "todas las entradas están bien". Como al derribar fichas de dominó: basta confirmar que la primera cae y que cada ficha derriba a la siguiente para concluir que todas caerán, sin revisarlas una por una.
¿Hay ejemplos de Lean 4?
Sí. El fragmento siguiente es una verdadera demostración en Lean, que pasa la verificación de Lean:
example (p q : Prop) (h : p ∧ q) : q ∧ p := by
constructor
exact h.right
exact h.leftLo que muestra es: dado que "llueve y hace viento", se concluye "hace viento y llueve".
¿Qué hago si Lean 4 da un error?
La verificación de Lean es paso a paso: se detiene en el paso donde falta un fundamento, y el error te dice justo qué eslabón falta. Los ejemplos del curso marcados como "dará error" también se confirmó que realmente dan error antes de publicarse, y los estados de objetivo y errores de los ejercicios interactivos son generados por un script a partir de Lean. Si tras una actualización de Lean lo que ves no coincide con el texto, dínoslo al final de esa sección.
¿Qué base necesito para este curso?
No necesitas base matemática; basta con saber un poco de programación en cualquier lenguaje. Al terminar tendrás un mini compilador escrito por ti y demostrado correcto por Lean.
Siguiente paso
Empieza por Qué es la verificación formal. Si prefieres ir directo a la práctica, ve a Instala Lean 4.