Teoría de la demostración · Definición

Demostración formal

lógicademostración

Antes de empezar necesitas conocer

Una demostración formal es una sucesión de pasos verificables que lleva de las premisas a la conclusión.

Definición

Una demostración formal de \(\varphi_n\) es una sucesión \(\varphi_1,\ldots,\varphi_n\) en la que cada término es un axioma, una hipótesis admitida o el resultado de una regla aplicada a términos anteriores.

\[\varphi_1,\varphi_2,\ldots,\varphi_n\vdash\varphi_n\]

Cada línea de una prueba formal debe ser un axioma, una hipótesis permitida o el resultado de aplicar una regla a líneas anteriores, de modo que cualquiera pueda verificarla paso a paso.

Ejemplo guía: de las hipótesis \(P\) y \(P\to Q\) se obtiene \(Q\). La prueba tiene tres líneas: \(P\), \(P\to Q\) y \(Q\), esta última justificada por modus ponens sobre las dos anteriores.

Error típico: escribir una línea sin justificarla porque parece evidente. Un salto de \(P\) a \(Q\) sin regla deja una laguna y la prueba deja de ser formal.

Para pensar

¿Puede una conclusión correcta formar parte de una demostración si no se justifica?

No. Una demostración formal exige justificar también los pasos que llevan a una conclusión verdadera.

Ejercicios 10

  1. Una demostración formal es una...
  2. Cada línea de una demostración formal debe ser...
  3. La última línea de una demostración suele ser...
  4. Una demostración formal depende de...
  5. ¿Cuál paso no pertenece a una demostración formal?
  6. Una demostración formal es una secuencia de...
  7. El primer paso de una demostración puede ser...
  8. Una línea de una prueba debe poder justificarse por...
  9. Una prueba formal tiene las líneas \(P\to Q\) y \(P\), ambas hipótesis permitidas. ¿Qué línea puede añadirse legítimamente?
  10. Si una prueba salta de P a Q sin una regla que lo permita, entonces...

Referencias

  • Frederic P. Schuller, Lectures on the Geometrical Anatomy of Theoretical Physics · Lecture 1, Introduction / Logic of Propositions and Predicates, YouTube, 2015.