next up previous contents
Next: Calculabilidad Up: La formalización como cálculo. Previous: Lenguajes formales   Contents

Sistemas formales

La pretensión de formalización del pensamiento, que se inició con la osadía de Boole al pretender haber encontrado ``las leyes del pensamiento", dió origen a un interés renovado por la lógica y a la aparición de la lógica matemática 21 (Morgan 22 , Frege 23, Russell 24, Hilbert25), que se inicia en la segunda mitad del siglo XIX, y que incide de forma determinante en la moderna fundamentación de la matemática, y en el desarrollo de la teoría de conjuntos (Peano, Cantor).

La idea de formalización de una teoría es la que brevemente exponemos a continuación.

Definimos a un sistema formal, como una cuádrupla:

\begin{displaymath}S = ( \Sigma , F , A , R )\end{displaymath}

donde sus elementos los interpretamos como sigue:

$\Sigma$ :
es un alfabeto.
$F$ :
es un subconjunto recursivo de $\Sigma^*$, llamado conjunto de fórmulas ( $F \subseteq \Sigma $*).
$A$:
es un subconjunto recursivo de $F$, cuyos elementos reciben el nombre de axiomas. $(A \subseteq F)$.
$R$:
es un conjunto finito de reglas de inferencia, de la forma $R_i ( x_1 , x_2 , ... x_m ; y)$, cuyas variables tomarán valores en $F$. En estas reglas se dice que la fórmula $y$ se obtiene a partir de las $x_1 , x_2 , ... x_m$ mediante $R_i$ , o que $y$ es consecuencia de $x_1 , x_2 , ... x_m$.

Dado un sistema formal $S$, decimos que $d$ es una demostración en $S$, si $d$ es una secuencia finita de fórmulas


\begin{displaymath}x_1 , x_2 , x_3 , . . . . x_n \end{displaymath}

que comienza con un axioma $( x_1 \in A )$, y en la que cualquier elemento posterior o es un axioma o se puede deducir a partir de otros elementos que ya están en la demostración.

Decimos que una formula $x_n$ es un teorema de $S$ , si y sólo si existe una demostración


\begin{displaymath}d \equiv x_1 , x_2 ,. . . . x_n\end{displaymath}

.

Un ejemplo de sistema formal para la lógica proposicional, es el que damos en la nota 26, en donde tambien se da un ejemplo de demostracion formal.

Con el desarrollo de los sistemas formales se abrió la espectativa de poder reducir la demostración a cálculo, y con ello se produjo una gran esperanza que llevó a la búsqueda de la pretendida demostración automática, es decir de procedimientos para la definición de algoritmos capaces de construir la secuencias de fórmulas que formen una demostración. Pero pese a que esta búsqueda hizo avanzar la lógica matemática con algunos éxitos 27 estos no lograron el intento de alcanzar la demostración automática, imposibilidad que dejaron patentes los limitadores teoremas de Godel 28que básicamente dicen que, en general, los sistemas formales o son incompletos, o son inconsistentes; es decir, en el primer caso se trataría de sistemas que contienen fórmulas para las que no existe una demostración (en el sentido formal), y en el segundo, que contienen fórmulas para las que existe una demostración y también para su negación. Con este planteo renacen y vuelven a aparecer los fantasmas que llevan consigo los dilemas y las aporías lógicas. (Desde las antiguas del mentiroso, del barbero, la del puente y la horca, y las mas recientes como las vinculadas con la teoría de conjuntos como la de Russell, de la que ya hemos subrayado su importancia mas arriba.)

Estos avances pusieron cota a la ilusión de que todo sea calculable. Y si no todo es calculable surgen las preguntas, qué se puede calcular? dónde están los límites de la calculabilidad?.


next up previous contents
Next: Calculabilidad Up: La formalización como cálculo. Previous: Lenguajes formales   Contents
Miquel 2001-03-13