Skip to content

¿Qué es la verificación formal ​

La verificación formal consiste en usar una demostración matemática para mostrar que un programa satisface los requisitos para todas las entradas, y hacer que la computadora compruebe cada paso de esa demostración. Solo se diferencia de las pruebas en una cosa: las pruebas verifican las entradas que has probado, la demostración cubre todas.

Esta sección parte de construir unos escalones para aterrizar esa frase. No hace falta instalar nada.

Qué sabrás hacer al terminar ​

  • Explicar qué garantiza cada cosa, las pruebas y las demostraciones
  • Entender qué dice un teorema de Lean
  • Saber qué significa y qué no significa que "Lean haya aceptado la comprobación"

Construyamos primero unos escalones ​

Construimos escalones con ladrillos: el primero con 1 ladrillo, el segundo con 2, el tercero con 3. ¿Cuántos ladrillos hacen falta en total para n escalones?

Pruébalo tú mismoConstruir uno 4 escalones, ¿cuántos ladrillos se necesitan?

Contar uno por uno (prueba)

1 + 2 + … + 4 = 10

n=4 ✓

Has probado 1 n. Mueve el control deslizante y prueba algunos más. Pero hay infinitos n, nunca terminarás de probarlos todos.

Unirlo (demostración)

Luego toma una copia idéntica de los escalones, al revés.

Hiciste dos cosas distintas:

  • Arrastrar el control deslizante para contar ladrillos: cada vez solo conoces la respuesta para un n. Por muchos que pruebes, solo sabes que "estos n están bien".
  • Formar un rectángulo: de una sola vez viste todos los n. Sin importar cuántos escalones haya, dos copias forman exactamente n filas y n + 1 columnas, así que dos copias de los escalones tienen en total n × (n + 1) ladrillos.

Lo primero son las pruebas, lo segundo es la demostración.

  • Arrastré el control deslizante y también formé el rectángulo

Escribir los escalones como un programa ​

Contar ladrillos, escrito como una función de Lean, queda así. No importa si no entiendes los detalles: dice que "los ladrillos de n escalones = los ladrillos de los primeros n − 1 escalones + los n ladrillos del escalón n":

lean
def sumTo : Nat → Nat
  | 0 => 0
  | n + 1 => sumTo n + (n + 1)

Una función, dos comprobaciones ​

El enfoque de las pruebas: elegir un número y calcular.

lean
#eval sumTo 100

Deberías ver:

text
5050

100 × 101 ÷ 2 también da 5050, coincide. Pero esto solo demuestra que es correcto para n = 100. ¿Y para n = 101? ¿Y para n = cien millones? Puedes probar más casos, pero nunca terminarás.

El enfoque de la demostración: escribir la conclusión obtenida al formar el rectángulo como una afirmación válida para todo n, y luego demostrarla.

lean
theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1) := by
  induction n with
  | zero =>
    rfl
  | succ k ih =>
    simp [sumTo]
    rw [Nat.mul_add, ih]
    simp [Nat.mul_add, Nat.add_mul]
    omega

No pasa nada si por ahora no entiendes lo que va después de by; eso es contenido de secciones posteriores. Mira solo la primera línea:

  • theorem sumTo_formula: un teorema, llamado sumTo_formula.
  • (n : Nat): para cualquier número natural n.
  • 2 * sumTo n = n * (n + 1): los ladrillos de dos copias de los escalones equivalen a n × (n + 1). Es justo el rectángulo que formaste.

Lean comprobó esta demostración con éxito. A partir de ahora, esa afirmación vale para todos los números naturales, sin necesidad de más pruebas.

  • Puedo explicar qué garantiza cada uno, #eval sumTo 100 y theorem sumTo_formula

¿Qué pasa si te equivocas? ​

Supón que recordaste mal la fórmula y crees que sumar de 1 hasta n da n × n:

lean
theorem wrong_formula (n : Nat) : sumTo n = n * n := by
  induction n with
  | zero => rfl
  | succ k ih => simp [sumTo, ih]; omega

Lean no lo acepta. Su respuesta empieza con esta frase:

text
omega could not prove the goal:

No puedes colarte con un "parece más o menos correcto". Una proposición falsa no se puede demostrar, no importa cómo la escribas. Esta es la razón por la que la verificación formal es digna de confianza: quien comprueba la demostración es un programa, no la paciencia de una persona.

Pon a prueba tus conocimientosEscribiste 200 pruebas para una función de ordenamiento y todas pasaron. ¿Qué demuestra esto?

Qué no garantiza ​

Lean garantiza que: la frase que escribiste quedó demostrada. No garantiza que esa frase sea lo que realmente querías.

El teorema de arriba dice que "el doble de sumTo n equivale a n × (n + 1)". Si lo que querías era otra propiedad pero escribiste esta frase, Lean no puede ayudarte. Por eso leer la primera línea del teorema es más importante que leer la demostración. La demostración la comprueba Lean; la proposición la tienes que leer tú.

  • Sé que "demostración aceptada" garantiza que la proposición es verdadera, no que la proposición refleje bien el requisito

Puntos de control ​

  • Puedo explicar la verificación formal en una frase: usar una demostración para mostrar que el programa es correcto para todas las entradas, y hacer que la computadora compruebe la demostración
  • Puedo explicar la diferencia entre pruebas y demostración: entradas probadas, todas las entradas
  • Puedo leer el significado de cada parte de theorem 名字 (n : Nat) : 命题
  • Sé que una proposición falsa no se puede demostrar en Lean

Malentendidos frecuentes ​

"La verificación formal es simplemente más pruebas." No. Las pruebas ejecutan el programa y observan el resultado; la demostración no ejecuta el programa, razona a partir de las definiciones y cubre todos los casos de una sola vez.

"Si la demostración fue aceptada, el programa no tiene ningún problema." La demostración solo se ocupa de la frase que escribiste. Las propiedades que no escribiste en la proposición no están cubiertas por la garantía.

Preguntas frecuentes ​

¿Qué significa verificación formal? ​

La verificación formal consiste en usar una demostración matemática para mostrar que un programa satisface los requisitos para todas las entradas, y hacer que la computadora compruebe cada paso de esa demostración. Solo se diferencia de las pruebas en una cosa: las pruebas verifican las entradas que has probado, la demostración cubre todas. La definición del inicio de esta página y la sección "Construyamos primero unos escalones" lo ilustran con el ejemplo de los ladrillos.

¿Qué significa Lean 4? ​

Lean 4 es una herramienta para escribir programas y demostraciones. En esta página la usaste para definir la función sumTo, y con theorem escribiste una proposición válida para todos los números naturales, cuya demostración comprueba Lean paso a paso. Quien comprueba la demostración es un programa, no la paciencia de una persona.

¿Cómo se escribe la verificación formal? ​

Primero escribe como proposición la propiedad que quieres demostrar, de modo que valga para todas las entradas, por ejemplo theorem sumTo_formula (n : Nat) : 2 * sumTo n = n * (n + 1), y luego da una demostración para que la computadora la compruebe. La demostración de esta página usa inducción; los detalles se desarrollan en secciones posteriores.

Si la demostración fue aceptada, ¿el programa no tiene ningún problema? ​

No. Lean garantiza que la frase que escribiste quedó demostrada, no que esa frase sea lo que realmente querías. Las propiedades que no escribiste en la proposición no están cubiertas por la garantía, así que leer la primera línea del teorema es más importante que leer la demostración; consulta la sección "Qué no garantiza".

Siguiente sección ​

Si quieres que Lean compruebe este código con tus propias manos, primero instala Lean 4.

gaodong.aiAboutPrivacyContact

Independent tutorials, not affiliated with any product mentioned. Product names and trademarks belong to their owners. Check official pages for prices and policies.