[Carlos Ivorra]

Como es habitual en este tipo de hilos, para facilitar el seguimiento del texto los comentarios que puedan surgir deben dirigirse a este hilo auxiliar de comentarios.


¿Qué es la lógica? Para formarnos una primera idea de cómo hay que entender la palabra "lógica" en el contexto de este artículo, creo que será ilustrativo considerar el silogismo siguiente:

Toda palabra properispómena es barítona,
\( \delta\tilde\omega\rho\omicron\nu \) es una palabra properispómena,
luego \( \delta\tilde\omega\rho\omicron\nu \) es una palabra barítona.

Tenemos ahí tres afirmaciones, y cualquiera que sepa algo de gramática griega podrá asegurarnos que las tres son verdaderas. Ahora bien, lo interesante desde el punto de vista lógico es que, sin saber absolutamente nada de gramática griega, podemos afirmar sin riesgo a equivocarnos que si las dos primeras afirmaciones son verdaderas, entonces la tercera también lo es.

Más detalladamente: Si toda palabra properispómena (signifique esto lo que signifique) es barítona (signifique esto lo que signifique) y \( \delta\tilde\omega\rho\omicron\nu \) (sea esto lo que sea) es una palabra properispómena (sea esto lo que sea), podemos afirmar sin riesgo a equivocarnos que \( \delta\tilde\omega\rho\omicron\nu \) (aunque no sepamos lo que es eso) es una palabra barítona (aunque no sepamos lo que es eso).

¡Pues esto es la lógica formal! ¡Esto es razonar formalmente! Consiste en concluir que determinadas afirmaciones son necesariamente ciertas bajo el supuesto de que otras lo sean, y llegar a tal conclusión sin atender en ningún momento al posible significado de las afirmaciones, sino meramente a su "forma". El razonamiento anterior tiene la forma siguiente:

Todo P es Q,
X es P,
luego X es Q.

y sólo por tener esa forma, podemos asegurar que es lógicamente válido, es decir, que si las dos primeras afirmaciones son verdaderas, entonces la tercera también tiene que serlo, y da igual que P signifique "palabra properispómena" o "bailarina de ballet".

La lógica formal determina qué razonamientos son válidos en este sentido (de que llevan necesariamente de afirmaciones verdaderas a afirmaciones verdaderas) atendiendo únicamente a la "forma", a la sintaxis, de las afirmaciones involucradas, y nunca a su posible significado. Esto no significa que no vayamos a estudiar y tener en cuenta los posibles significados de las afirmaciones que consideremos, sino únicamente que nuestro objetivo es tener en cuenta tales significados posibles sólo para acabar confirmando que hemos logrado nuestro propósito, es decir, que tenemos ciertamente la garantía de que nuestras conclusiones serán válidas independientemente cuáles sean tales significados posibles.

Para lograr este objetivo necesitamos sustituir el castellano por un lenguaje alternativo lo suficientemente simple como para ser estudiado teóricamente, pero a la vez lo suficientemente potente como para que pueda expresar cualquier razonamiento en el que podamos estar interesados.

El problema es que el castellano (como cualquier otra lengua natural) presenta ambigüedades que sólo pueden ser resueltas por el contexto, lo cual a menudo significa tener en cuenta el significado de las afirmaciones que estamos haciendo. Por ejemplo, recordemos lo que un desdichado amante le decía a su amada:

¿Cómo quieres que venga a verte, si el perro de tu padre sale a morderme?

Ésta es una frase que respeta totalmente la sintaxis castellana y, sin embargo, es inevitablemente ambigua. Podemos leerla una y mil veces y nada nos permitirá concluir con seguridad si quien afirmó esto estaba diciendo que su suegro tenía un perro o más bien que su suegro era un perro. Más concretamente, la expresión castellana "el perro de tu padre", puede significar "el perro que tiene tu padre" y también "el perro que es tu padre" (y, paralelamente, "morderme" puede tener un sentido literal o figurado).

Para estar en condiciones de estudiar la lógica con precisión necesitamos un lenguaje en el que estas cosas no puedan suceder, en el que cada afirmación tenga, no un significado, pero sí una forma precisa e inequívoca. El problema de la frase anterior no es que no sepamos el significado exacto de "te" en "verte" (no importa si la amada es fulana o mengana), ni que no sepamos quién es su padre (quién sea en concreto sería irrelevante para entender la lógica de la frase). Lo que hace que la frase no tenga una "lógica", una "forma" definida es que no sabemos si "perro" y "padre" se refieren al mismo objeto o a objetos distintos.

Sin embargo, sería injusto decir, por culpa de ejemplos como éste, que el castellano es un lenguaje inapropiado para razonar con precisión. Tal prejuicio lleva necesariamente a absurdos epistemológicos. La realidad es que en castellano se puede razonar con absoluta precisión (y cualquier ambigüedad que surja siempre se puede resolver en cuanto sea detectada) siempre y cuando hablemos de objetos cuyo significado sea totalmente preciso, hasta el punto de que no tengamos dificultades en determinar objetivamente el significado exacto de cada afirmación que consideremos.

La necesidad de la lógica formal, es decir, de la posibilidad de razonar mediante un lenguaje libre de ambigüedades sin tener en cuenta el significado posible de las palabras que empleemos, surge desde el momento en que pretendemos razonar con objetos a los que no somos capaces de dar un significado preciso. El caso más representativo es el concepto de "conjunto". Aunque todos tengamos una idea más o menos vaga de qué entendemos por "conjunto", lo cierto es que no es posible precisar su significado hasta el punto de poder hablar con seguridad sobre conjuntos controlando lo que decimos en función del significado de nuestras afirmaciones. La única forma conocida de razonar con rigor sobre conjuntos arbitrarios, como hacen los matemáticos, es manejar la palabra "conjunto" como alguien que no sepa griego puede manejar la palabra "properispómeno" para convencerse de que el silogismo anterior era correcto. Se trata de decir: si los "conjuntos" (sean lo que sean) cumplen tales axiomas, entonces los conjuntos "sean lo que sean" cumplen tales teoremas.

Así pues, nuestro propósito es, por una parte, diseñar lenguajes (no uno solo, sino que podemos considerar lenguajes distintos adaptados a cada contexto que queramos describir) con una gramática precisa y libre de ambigüedades (que impida que algunas expresiones como "el perro de tu padre" se puedan entender de formas lógicamente distintas), por otra parte estudiar la relación entre dichos lenguajes y los significados posibles de sus palabras (o, más precisamente, de sus signos) y finalmente mostrar que es posible manipular tales lenguajes sin atender para nada a los significados posibles de sus signos, pero con la garantía de que si, de acuerdo con un significado establecido, partimos de afirmaciones verdaderas, las conclusiones formales que obtendremos serán también verdaderas.

Este proyecto nos lleva inevitablemente a la necesidad de distinguir con sumo cuidado los signos y sus posibles significados. Nuevamente el castellano deja estas distinciones a cargo del contexto de una forma demasiado vaga para nuestras necesidades. Consideremos por ejemplo las dos frases siguientes:

España está en Europa                España tiene tres sílabas.

Cualquiera que las lea las entiende correctamente y reconoce que ambas son verdaderas, pero para ello ha tenido que interpretar la palabra "España" de dos formas completamente distintas, sin que nada en las frases advierta explícitamente de la necesidad de hacer tal distinción. En la primera frase "España" se interpreta como un país, mientras que en la segunda frase "España" se interpreta como una palabra.

El país España es un objeto completamente distinto de la palabra España. Para distinguir ambos conceptos (cosa que el castellano no obliga a hacer) adoptaremos el convenio de poner una palabra entre comillas cuando no queramos referirnos a su significado, sino a la palabra en sí. Con este criterio deberíamos escribir:

España está en Europa                "España" tiene tres sílabas.

Así, por ejemplo, entre los signos de los lenguajes que vamos a definir, llamaremos constantes a los que pretenden nombrar objetos (los equivalentes de los sustantivos en castellano), de modo que si diseñamos un lenguaje formal en el que hay una constante \( N \) que pretendemos usar para nombrar a Napoleón, entonces \( N \) será el equivalente en nuestro lenguaje a la palabra "Napoleón" en castellano, mientras que usaremos una barra \( \overline N \) para referirnos al significado de la constante \( N \) (en este caso, Napoleón, sin comillas, o, más precisamente, el emperador Napoleón I de Francia).

La diferencia entre \( N \) y \( \overline N \) es exactamente la misma que hay entre "Napoleón" y Napoleón. Y confundir \( N \) con \( \overline N \) resultaría tan catastrófico como creer que una palabra ha sido emperador de Francia o que un emperador de Francia estuvo formado por ocho letras, en lugar de por carne, huesos, fluidos corporales, etc.)

Más concretamente, \( N \) es una palabra (un signo) de nuestro lenguaje formal, de mismo modo en que "Napoleón" es una palabra castellana, mientras que \( \overline N \) no es una palabra de nuestro lenguaje formal, sino un hombre que lleva mucho tiempo muerto.

Más vueltas sobre lo mismo

Un lector malicioso puede objetar que, al fin y al cabo, "\( \overline N \)" no es un emperador, sino una letra con un palito encima. En efecto, si alguien pregunta ¿qué es "\( \overline N \)"? la respuesta es que "\( \overline N \)" es un signo que empleamos para nombrar a Napoleón, pero un signo que no pertenece al lenguaje formal del que estamos hablando, sino que es una extensión del castellano.

Hay muchas formas de referirnos a Napoleón en castellano. Algunas de ellas son: Napoleón, el primer emperador de Francia, el significado de la palabra "Napoleón", o también el significado de la constante \( N \) de nuestro lenguaje formal. Todas estas expresiones castellanas nombran a una misma persona, a saber, a Napoleón Bonaparte. Pues bien, "\( \overline N \)" es simplemente una abreviatura por "el significado de la constante \( N \)", es una expresión castellana como "el primer emperador de Francia". Es cierto que en los diccionarios de castellano no viene reflejado que una barrita encima de una letra debe leerse como "el significado de", pero se trata de un convenio que estamos introduciendo aquí y ahora. No es más que una abreviatura taquigráfica. Podemos decir que "vengo xq tengo q trabajar" es una frase castellana escrita taquigráficamente y, en ese mismo sentido, "\( \overline N \) es un emperador francés" es una frase castellana escrita taquigráficamente. Si desarrollamos la primera tenemos "vengo porque tengo que trabajar", y si desarrollamos la segunda tenemos "El significado de \( N \) es un emperador francés".

[cerrar]

Como decimos, la distinción cuidadosa entre \( N \) y \( \overline N \) va a marcar la diferencia entre entender qué estamos haciendo o no entender nada de nada. En particular hay que tener presente que definir un lenguaje formal que contenga una constante \( N \) convierte a \( N \) en un signo fijo e inamovible de dicho lenguaje, pero esto no nos obliga a fijarle de forma inamovible un significado \( \overline N \). Por el contrario, podemos trabajar con un lenguaje formal sin atribuir ningún significado concreto a sus signos, o bien podemos establecer en un momento dado que la constante \( N \) significa Napoleón, pero también podemos más tarde considerar el mismo lenguaje formal pero interpretando \( N \) de otra forma, digamos como Nabucodonosor, o como Beethoven. En resumen, nos va a interesar fijar lenguajes con unos signos específicos, como pueda ser una constante \( N \), y luego comparar distintas interpretaciones de dichos signos, de modo que  \( \overline N \) pueda ser Napoleón en un caso o Nabucodonosor en otro. De hecho, lo que nos interesará es poder decir cosas del estilo de "esto va a ser cierto sea lo que sea \( \overline N \) ".

La idea subyacente en todo lo que vamos a exponer es la siguiente:

1) Tenemos diversas realidades de las que podemos hablar en buen castellano

2) Podemos diseñar lenguajes formales para hablar de dichas realidades de forma "controlada".

3) Los lenguajes que vamos a diseñar pueden ser manipulados con total precisión sin hacer referencia a ninguna realidad concreta (incluso si no somos capaces de precisar una realidad concreta que se ajuste a lo que afirmamos), pero con la garantía de que si partimos de afirmaciones verdaderas en una realidad cualquiera, las conclusiones a las que llegaremos serán verdaderas en esa misma realidad.

En el mensaje siguiente empezaremos a precisar debidamente estas ideas.

[Carlos Ivorra]

En este mensaje presentaremos sin ánimo de ser rigurosos los conceptos básicos que vamos a manejar. Presentaremos "mezclados" los conceptos sintácticos (relativos a los signos) y los semánticos (relativos a los significados de los signos) porque resulta más natural. Luego, en el mensaje siguiente los separaremos cuidadosamente y precisaremos todo lo que aquí haya podido quedar "en el aire".


El universo de una interpretación Como hemos dicho en el mensaje anterior, cada lenguaje formal se diseña para describir una realidad. También hemos señalado que al final no será obligatorio explicar cuál es esa realidad de la que queremos hablar, sino que los lenguajes formales terminarán siendo "autónomos" y podremos razonar con ellos sin necesidad de especificar qué son los objetos de los que presuntamente estamos hablando. Ahora bien, si, pese a no estar obligados a ello, queremos especificar cuál es la "realidad" de la que estamos hablando con un lenguaje dado, lo primero que tendremos que especificar es la colección de objetos que integran dicha realidad. Dicha colección de objetos será lo que llamaremos el universo de la interpretación.

Por ejemplo, vamos a construir un lenguaje formal y le vamos a asignar a la vez una interpretación, y establecemos aquí que el universo de dicha interpretación será la colección \( U \) de todos los seres humanos que han vivido o viven en la Tierra desde el año 1 hasta el año 2012.

Colecciones

Usamos aquí la palabra "colección" en el mismo sentido en que normalmente se emplea la palabra "conjunto", pero preferimos evitar el término "conjunto" para no confundirlo con el término técnico de la teoría de conjuntos. Observemos que "la colección de todos los seres humanos que han vivido o viven en la Tierra desde el año 1 hasta el año 2012" es una colección de objetos bien definida, en el sentido de que no hay ninguna duda de qué objetos pertenecen a ella. Si alguien encuentra cualquier ambigüedad, puede concretarla a su gusto sin que altere nada de lo que vamos a decir. Por ejemplo, podemos concretar que si alguien ha nacido en 2012 y ha muerto en 2013 está contenido en \( U \) por definición, al igual que alguien que haya nacido antes del año 1 pero haya muerto en dicho año o después.

En general, hemos determinado una colección siempre que hayamos dado un criterio claro e inequívoco de qué objetos pertenecen a la colección y cuáles no. Napoleón está en \( U \), el caballo de Napoleón no está en \( U \), el faraón Keops no está en \( U \), etc. En general, está perfectamente definido qué es estar en \( U \) (sin perjuicio de que pueda haber un individuo del que no sepamos si está o no en \( U \) porque no sabemos si murió antes o después del año 1, pero eso sólo significa que no sabemos si tal persona está o no en \( U \), no que no esté bien definida su pertenencia (o no) a \( U \).

[cerrar]

Constantes Definir un lenguaje formal supone especificar unos signos. No vamos a poner restricciones sobre la forma que puedan adoptar los signos de un lenguaje formal. Cada signo podrá ser una letra (latina, griega, hebrea, etc.), una combinación de letras o cualquier "garabatito" con el único requisito de que podamos diferenciar clara e inequívocamente un signo de otro.

Pero, al establecer que un signo forma parte de un determinado lenguaje formal, estamos obligados a especificar su "función sintáctica" (el equivalente en castellano a ser un sustantivo, un adjetivo, un verbo, un pronombre, una conjunción, etc). Por ejemplo, en el mensaje precedente ya hemos hablado de las constantes. Son los nombres propios de los lenguajes formales. Una constante es un signo al que, en caso de que decidamos especificarle un significado, éste será un objeto concreto (perteneciente a un universo prefijado).

Por ejemplo, podemos empezar a construir un lenguaje formal estableciendo que va a tener tres constantes, \( N \), \( J \) y \( n \). Y además podemos atribuirles un significado. Por ejemplo, considerando el universo \( U \) especificado anteriormente, podemos establecer que \( \overline N \) (el significado de la constante \( N \)) sea el emperador Napoleón I, mientras que \( \overline J \) (el significado de \( J \)) sea la emperatriz Josefina Beauharnais y que \( \overline n \) sea Napoleón II, el hijo de ambos.

Aquí es crucial recordar que \( N \) es un signo de un lenguaje formal y \( \overline N \) es un emperador de Francia.


Relatores Fijado un universo, entre sus objetos podemos seleccionar las relaciones que nos interesen. En general, una relación \( n \)-ádica \( R \) en un universo \( U \) es cualquier criterio que, a cada \( n \) objetos \( x_1,\ldots, x_n \) de \( U \), repetidos o no y en un cierto orden, les asigna un "verdadero" o "falso". Cuando la relación \( R \) es verdadera sobre \( x_1,\ldots, x_n \) escribimos (a modo de taquigrafía) \( R(x_1,\ldots, x_n) \).

Por ejemplo, en nuestro universo \( U \) tenemos la relación monádica "ser un hombre", que es verdadera sobre los objetos de \( U \) que son hombres y es falsa sobre los que son mujeres (donde podemos definir "hombre" como "tener al menos un cromosoma Y").

Un ejemplo de relación diádica en \( U \) sería por ejemplo "estar casados".

Los relatores son los signos de un lenguaje formal que, en caso de ser interpretados, su significado es una relación. Un relator monádico es un relator que debe ser interpretado por una relación monádica, un relator diádico es un relator que debe ser interpretado por una relación diádica, etc.

Por ejemplo, en nuestro lenguaje formal podemos incluir dos relatores monádicos \( H \) y \( M \) y asignarles como significado las relaciones \( \overline H \) y \( \overline M \) en \( U \) dadas por "ser un hombre" y "ser una mujer", respectivamente.

En estos términos las cadenas de signos \( HN, MJ, Hn \) serían verdaderas, pues significan que Napoleón I es un hombre, que Josefina es una mujer y que Napoleón II es un hombre. En cambio \( HJ \) sería una afirmación falsa.

También podemos introducir un relator diádico \( C \) y asignarle como significado la relación diádica \( \overline C \) tal que \( \overline C(x,y) \) se cumple cuando \( x \) e \( y \) están casados (para cualesquiera objetos \( x \), \( y \) del universo \( U \).

En estos términos, \( CNJ \) es una afirmación verdadera en nuestro lenguaje formal, de acuerdo con la interpretación fijada. En cambio, \( CNn \) es falsa.

Podemos considerar también un relator triádico \( \rm Pd \) y asignarle como significado la relación \( \overline{\rm Pd} \) en \( U \) tal que \( \overline {\rm Pd}(x,y,z) \) se cumple si \( x \) e \( y \) son los padres de \( z \).

Así, \( {\rm Pd}NJn \) es una afirmación verdadera, y \( {\rm Pd}NnJ \) es falsa.

Cuando definimos un lenguaje formal, debemos especificar sus signos, así como a qué categoría pertenece cada signo (si es una constante, o un relator, o pertenece a cualquiera de las otras categorías que aún tenemos que introducir) y, en caso de que sea un relator, debemos especificar su rango, es decir, si se trata de un relator monádico, o diádico, o triádico, etc. No estamos obligados a asignarle un significado a un relator, pero si lo hacemos, la relación asignada a un relator monádico debe ser monádica (es decir, debe requerir un complemento), la asignada a un relator diádico debe ser diádica (debe requerir dos complementos), etc.

Observaciones

En principio, podríamos admitir también relatores \( 0 \)-ádicos, es decir, relatores cuyas relaciones asociadas no necesitaran ningún complemento, sino que fueran directamente verdaderas o falsas. Por ejemplo, un relator \( 0 \)-ádico podría ser un signo \( p \) cuyo significado \( \overline p \) fuera, por ejemplo, "Llueve".

También podríamos considerar relatores sin rango definido, como un relator \( H \) cuyo significado fuera "ser hermanos", de modo que \( Hxy \) significara "x e y son hermanos", mientras que \( Hxyz \) significara "x, y, z, son hermanos", etc.

Sin embargo, no vamos a admitir ni lo uno ni lo otro. La razón es que podemos prohibir ambas posibilidades sin reducir por ello las capacidades expresivas de nuestros lenguajes, y no admitir estos casos simplifica considerablemente la sintaxis.

Por ejemplo, si definimos \( H \) como un relator diádico, para expresar que "x, y, z son hermanos" podemos escribir \( Hxy\land Hyz\land Hxz \), donde hemos usado un signo \( \land \) que todavía no hemos introducido).

Observemos ahora que tendríamos problemas si quisiéramos definir un lenguaje formal que constara de un relator monádico \( H \) (con el significado de "ser un hombre") y de unas constantes \( E \) y \( HE \), (con el significado de Elena y "Héctor"). Entonces, no estaría claro si \( HE \) es la constante que representa a Héctor o si es la afirmación (falsa) "Helena es un hombre".

Una forma de evitar estos problemas sería ser muy estrictos sobre qué signos se admiten como válidos. Por ejemplo, podríamos decretar que si un lenguaje va a tener dos constantes, éstas tengan que ser precisamente \( C_1, C_2 \), y que si va a tener un relator monádico, éste tenga que ser precisamente \( R_1^1 \) (el superíndice indica que es monádico y el subíndice que es el primero). Ahora bien, esto haría muy rígidos y molestos de usar los lenguajes formales. En la práctica es preferible dejar que los signos tomen nombres "sugerentes" y a la vez tener cuidado de no dar pie a dudas sobre dónde empieza y dónde termina cada signo.

[cerrar]

Cada lenguaje formal puede tener las constantes que queramos (incluso ninguna) y los relatores que queramos, pero exigiremos que todo lenguaje formal tenga al menos un relator diádico que representaremos por \( = \) (y que llamaremos igualador) y al que siempre asignaremos el mismo significado, a saber la relación diádica \( \equiv \) de identidad (de modo que \( x\equiv y \) se cumple si y sólo si \( x \) e \( y \) son el mismo objeto).


Funtores En un universo dado \( U \), además de relaciones, podemos considerar funciones \( n \)-ádicas, es decir, criterios \( f \) que a cada \( n \) objetos de \( U \) repetidos o no y en un cierto orden les asigne un nuevo objeto de \( U \) que representaremos por \( f(x_1,\ldots, x_n) \).

Los signos de un lenguaje formal que, en caso de ser interpretados, deben tener asignado como significado una función \( n \)-ádica se llaman funtores \( n \)-ádicos.

Por ejemplo, podemos añadir a nuestro lenguaje un funtor monádico \( P \) cuyo significado sea la función monádica \( \overline P \) dada por

\( \overline P(x)=\left\{\begin{array}{cl}\text{el padre de } x & \text{si el padre de } x \text{ está en } U\\ x&\text{en caso contrario.}\end{array}\right. \)

De este modo, \( N=Pn \) es una afirmación verdadera en nuestro lenguaje formal (siempre respecto de la interpretación fijada), pues significa que Napoleón I es el padre de Napoleón II.

Como en el caso de los relatores, exigiremos que cada funtor tenga un rango definido (no admitiremos funtores que admitan una cantidad indeterminada de argumentos). Notemos que los funtores \( 0 \)-ádicos serían simplemente las constantes.


Conectores lógicos Los conectores lógicos son signos de naturaleza diferente a las constantes, los relatores y los funtores, porque van a tener siempre la misma interpretación y no admitiremos que se modifique. Además, el significado de un conector lógico no será un objeto, una relación o una función, sino una tabla de verdad.

Por ejemplo, un conector lógico es el negador, al que le reservaremos siempre el signo \( \lnot \), y su significado es la tabla:

\( \begin{array}{|c|c|}
p&\lnot p\\
\hline
V&F\\
F&V
\end{array} \)

Esto significa que si \( p \) es una afirmación de nuestro lenguaje formal, entonces \( \lnot p \) es otra afirmación que es falsa cuando \( p \) es verdadera y viceversa. Esto se abrevia diciendo que el significado de \( \lnot \) es el mismo que el de la palabra castellana "no".

Por ejemplo, \( MN \) significa que Napoleón es una mujer, y es una afirmación falsa, mientras que \( \lnot MN \) significa que Napoleón no es una mujer, y es una afirmación verdadera.

Los restantes conectores lógicos requieren dos argumentos. Son \( \land, \lor, \rightarrow, \leftrightarrow \), se llaman conjuntor, disyuntor, implicador y coimplicador, y sus significados vienen dados por las tablas de verdad:

\( \begin{array}{|cc|c|c|c|c|}
p&q&p\land q&p\lor q&p\rightarrow q&p\leftrightarrow q\\
\hline
V&V&V&V&V&V\\
V&F&F&V&F&F\\
F&V&F&V&V&F\\
F&F&F&F&V&V
\end{array} \)

Estas tablas se resumen en que \( \land \) significa "y", \( \lor \) significa "o", \( \rightarrow \) significa "si... entonces" y \( \leftrightarrow \) significa "si y sólo si".

Por ejemplo, la afirmación \( HJ\rightarrow MN \) es verdadera, pues su significado es "Si Josefina es un hombre entonces Napoleón es una mujer", y esto es cierto, porque la tabla de verdad del implicador asigna el valor "verdadero" al caso en que ambas afirmaciones son falsas.


Variables y cuantificadores Las variables son signos similares a las constantes, pero a los que en ningún caso se asignará un significado fijo. Son el equivalente a los pronombres indefinidos en castellano, como "todo", "alguno", etc.

Así, por ejemplo, \( Hx \) significa que "x" es un hombre, y no podemos decir que sea una afirmación verdadera o falsa, pues no está especificado el significado de la variable \( x \). La afirmación \( x={\rm Pd}n \) significa que "x" es el padre de Napoleón II, y ahora podemos decir que será verdadera si la variable \( x \) se interpreta como Napoleón I, y falsa en cualquier otro caso.

Las variables están pensadas para ser usadas en combinación con los cuantificadores, que son otros dos signos con un significado fijo. Les reservaremos los signos \( \forall \) y \( \exists \). El primero se llama cuantificador universal o generalizador y el segundo cuantificador existencial o particularizador.

Cada cuantificador debe ir seguido de una variable, e indica que para que la afirmación sea verdadera, debe serlo para toda interpretación posible de la variable (en el caso del generalizador) o al menos para alguna interpretación posible de la variable (en el caso del particularizador).

Por ejemplo, la afirmación \( \exists x\ Hx \) significa que existe al menos un hombre, y es una afirmación verdadera, mientras que \( \forall x(Hx\rightarrow \lnot Mx) \) significa que todo \( x \) que sea un hombre no puede ser una mujer, y también es una afirmación verdadera.


Los signos lógicos de un lenguaje formal serán aquellos cuya presencia es obligada y su significado es fijo, a saber, los conectores lógicos, el igualador y los cuantificadores. Además, también consideraremos a las variables como signos lógicos.  Los demás signos de un lenguaje formal serán sus signos opcionales, es decir, los signos que un lenguaje puede tener o no y que, en caso de existir, requieren que se les asigne una interpretación si queremos interpretar las afirmaciones en las que aparezcan, ya que no tienen ningún significado fijo asignado. Los signos opcionales son, pues, las constantes, los relatores distintos de igualador y los funtores. Las variables las consideraremos como signos lógicos pues, por una parte, son obligatorios (exigiremos que todo lenguaje formal tenga infinitas variables) y, por otra parte, no hay que fijarles ninguna interpretación.

Ejemplo Vamos a definir ahora otro lenguaje formal distinto del que acabamos de construir. Sus signos opcionales serán dos relatores monádicos \( P \) y \( B \) y una constante \( D \). En este lenguaje formal podemos considerar las afirmaciones siguientes:

\( \forall x(Px\rightarrow Bx) \)
\( PD \)
\( BD \)

Se trata de la formalización del silogismo del mensaje anterior. Mejor dicho, la formalización de dicho silogismo sería lo que más adelante expresaremos así:

\( \forall x(Px\rightarrow Bx), PD\vdash BD \)

Según veremos, aquí dice que la tercera afirmación es consecuencia lógica de las dos primeras. La lógica nos permitirá probar que esto es así sin necesidad de considerar ninguna interpretación de los signos opcionales. No obstante, hay muchas interpretaciones posibles. La que es fiel al significado en castellano del silogismo del mensaje anterior tiene por universo la colección \( U \) de todas las palabras griegas, la interpretación del relator \( P \) es la relación monádica \( \overline P \) en \( U \) que cumplen las palabras llamadas properispómenas (que son cierta clase de palabras griegas, como en castellano hay palabras agudas, llanas y esdrújulas), la interpretación del relator \( B \) es la relación monádica \( \overline B \) que cumplen las palabras barítonas (que son otra clase de palabras griegas) y la interpretación de la constante \( D \) es la palabra griega \( \overline D\equiv \delta\tilde\omega\rho\omicron\nu \).

Con esta interpretación, el \( \forall x \) de la primera afirmación se interpreta como "para toda palabra griega" (pues hemos fijado como universo la colección de las palabras griegas), y la afirmación significa "para toda palabra griega x, si x es properispómena, entonces x es barítona" o, lo que es lo mismo, "toda palabra (griega) properispómena es barítona".

Ahora bien, nada nos impide cambiar completamente la interpretación, tomar como universo la colección de las personas vivas en 2012, interpretar \( P \) como "ser español", interpretar \( B \) como "ser europeo" e interpretar \( D \) como "El rey Juan Carlos I". Entonces, exactamente las mismas afirmaciones del mismo lenguaje formal (que no hemos modificado en nada) se interpretan como el silogismo:

Todo español (vivo en 2012) es europeo,
El rey Juan Carlos I es español (vivo en 2012),
luego el rey Juan Carlos I es europeo.

Este silogismo tiene exactamente la misma forma lógica que el considerado en el mensaje anterior. Esto significa que ambos silogismos son interpretaciones particulares de las mismas fórmulas de un mismo lenguaje formal.

Como hemos dicho al principio de este mensaje, nuestro objetivo aquí era únicamente el de presentar los conceptos principales que vamos a manejar. En los mensajes sucesivos precisaremos todos los conceptos que aquí hemos empleado sin más explicaciones, como el de "afirmación", el de "verdadero", etc.

[Carlos Ivorra]

En este mensaje empezaremos a precisar y separar por completo los conceptos sintácticos y semánticos que en el mensaje anterior hemos presentado conjuntamente. Empezamos dando una definición de lenguaje formal que no haga absolutamente ninguna referencia al posible significado de los signos que lo componen:

Definición Un lenguaje formal es una colección de signos arbitrarios divididos arbitrariamente en las categorías que especificamos a continuación:

Variables: Un lenguaje formal debe tener infinitas variables, y cada una de ellas debe tener asociado un único número natural al que llamaremos su índice. Recíprocamente, todo número natural es el índice de una única variable.

Notas

Lo más simple es tomar como variables, por ejemplo, los signos \( x_0, x_1, x_2, x_3, \ldots \) de modo que \( x_i \) es la variable de índice \( i \). En la práctica, no obstante, es útil dar nombres alternativos a las variables. Por ejemplo, en lugar de escribir \( \forall x_0x_1(x_0=x_1\rightarrow x_1=x_0) \) es más cómodo escribir \( \forall xy(x=y\rightarrow y=x) \). Si hacemos esto, simplemente estamos adoptando el convenio taquigráfico de escribir \( x \) cuando deberíamos escribir \( x_0 \) e \( y \) cuando deberíamos escribir \( x_1 \). Si sabemos lo que estamos haciendo no hay confusión posible.

En la práctica iremos más lejos y usaremos letras cualesquiera para representar variables sin especificar qué variable es concretamente cada letra (si \( x_0 \) o \( x_1 \) o cuál de todas). La explicación es que nunca será relevante si una variable \( x \) que consideremos en un momento dado es en realidad \( x_0 \) o \( x_{213} \).

[cerrar]

Constantes: Un lenguaje formal puede tener cualquier cantidad de constantes, desde ninguna hasta infinitas. Si hay un número finito \( n \) de ellas, a cada una le corresponderá un número natural (un índice) de \( 0 \) a \( n-1 \), mientras que si hay infinitas entonces habrá una para cada índice natural.

Relatores: Cada signo clasificado como relator debe tener asociado un número natural no nulo llamado su rango. Los relatores de rango \( n \) se llaman relatores \( n \)-ádicos. Un lenguaje formal puede tener cualquier cantidad de relatores \( n \)-ádicos, desde ninguno hasta infinitos, pero si los hay cada uno de ellos debe estar identificado por un índice, que varíe entre los primeros números naturales (si hay un número finito de relatores \( n \)-ádicos) o en todos los números naturales, si hay infinitos.

La única excepción a lo dicho es que todo lenguaje formal debe tener el relator diádico de índice \( 0 \), al que llamaremos igualador y representaremos por \( = \).

Funtores: Todo lo dicho para los relatores vale igualmente para los funtores, salvo que no hay ningún funtor obligatorio.

Conectores lógicos: Todo lenguaje formal debe tener dos signos llamados conectores lógicos, a saber, el negador \( \lnot \) y el implicador \( \rightarrow \).

Nota

En contra de lo establecido en el mensaje anterior, no incluimos el conjuntor, el disyuntor ni el coimplicador porque estos tres signos podrán ser definidos más tarde en función del negador y el implicador. Lo mismo sucede con el cuantificador existencial, que no lo incluimos a continuación porque podrá ser definido a partir del cuantificador universal o generalizador.

[cerrar]

Generalizador: Todo lenguaje formal debe tener un signo llamado generalizador y que representaremos por \( \forall \).

Se entiende que cada signo de un lenguaje formal debe estar clasificado en una única de estas categorías y cumplir los requisitos indicados.

Observemos que en la definición anterior no hay la menor alusión al significado posible de los signos de un lenguaje formal. Por ejemplo, no decimos que \( \forall \) significa "para todo". Simplemente especificamos que \( \forall \) es un signo obligatorio en todo lenguaje formal.

Ejemplo: Para definir un lenguaje formal basta especificar sus signos opcionales (sus constantes, relatores y funtores) Por ejemplo, podemos llamar \( \mathcal L_0 \) al lenguaje formal cuyos signos opcionales son una constante \( D \) (que tendrá índice \( 0 \)) y dos relatores monádicos \( P \) y \( B \) (de índices \( 0 \) y \( 1 \) respectivamente).

Con esto \( \mathcal L_0 \) queda completamente determinado. Sus signos son los indicados además de las variables \( x_0, x_1, x_2, \ldots \) y los signos lógicos \( =, \lnot, \rightarrow, \forall \).


Una vez definido el concepto de lenguaje formal sin hacer referencia a los posibles significados de los signos, podemos definir el concepto de modelo de un lenguaje formal, que es una asignación de significados:

Definición: Un modelo \( M \) de un lenguaje formal \( \mathcal L \) está determinado por:

Un universo \( U \), es decir, una colección no vacía bien definida de objetos cualesquiera.

Un criterio que a cada constante \( c \) de \( \mathcal L \) le asigna un objeto \( \overline c \) de \( U \), al que llamaremos objeto denotado por \( c \) respecto a \( M \) o, simplemente, el significado de la constante \( c \) (en el modelo \( M \)).

Un criterio que a cada relator \( n \)-ádico \( R \) de \( \mathcal L \) le asigne una relación \( n \)-ádica \( \overline R \) en el universo \( U \), que será el significado del relator \( R \) en el modelo \( M \). La relación asociada al igualador \( = \) será obligatoriamente la relación \( \equiv \) de identidad en \( U \), es decir, la relación tal que \( a\equiv b \) se cumple exactamente cuando \( a \) y \( b \) son el mismo objeto.

Un criterio que a cada funtor \( n \)-ádico \( f \) de \( \mathcal L \) le asigne una función \( n \)-ádica \( \overline f \) en el universo \( U \), que será el significado del funtor \( f \) en el modelo \( M \).

Ejemplo: Un modelo para el lenguaje formal \( \mathcal L_0 \) que hemos definido antes puede ser el especificado como sigue: el universo del modelo es el conjunto de personas vivas en el año 2012, el objeto denotado por la constante \( D \) es el rey de España, la relación \( \overline P \) asociada al relator \( P \) es la relación "ser español" y la relación \( \overline B \) asociada al relator \( B \) es la relación "ser europeo".

Nota

Al especificar un modelo de un lenguaje formal, toda afirmación de dicho lenguaje pasa a tener un significado que la hace verdadera o falsa. Por ejemplo, la afirmación \( \forall x(Px\rightarrow x = D) \) significa "Para toda persona \( x \) (viva en 2012), si \( x \) es español entonces \( x \) es el rey de España" o, equivalentemente, el único español es a lo sumo el rey de España. Obviamente es una afirmación falsa (aunque podría ser verdadera en otro modelo definido adecuadamente).

Sin embargo, esta observación no está debidamente justificada de momento, pues para poder afirmar esto con precisión necesitamos definir primero qué es una "afirmación" de un lenguaje formal y qué significa que una afirmación sea verdadera o falsa.

[cerrar]

Términos y fórmulas Cuando escribimos consecutivamente un número finito de signos de un lenguaje formal \( \mathcal L \) tenemos lo que se llama una cadena de signos de \( \mathcal L \). Por ejemplo, una cadena de signos del lenguaje que hemos definido más arriba es:

\( ==\forall\lnot BBP\rightarrow \)

Concretamente, se trata de una cadena de longitud 8 (la longitud de una cadena de signos es simplemente el número de signos que contiene, contando varias veces los signos repetidos).

De entre todas las cadenas de signos posibles, vamos a especificar las que llamaremos términos y fórmulas. En términos imprecisos, un término es una cadena de signos que nombra a un objeto, mientras que una fórmula es una cadena de signos que afirma algo, pero estas "definiciones" aparte de que no son suficientemente específicas, hacen referencia al posible significado de las cadenas de signos, y eso las vuelve completamente inaceptables. Queremos una definición de "término" y "fórmula" que no use más que los conceptos que aparecen en la definición de lenguaje formal, sin hacer referencia para nada a los significados que aporta un modelo dado.

Definición Diremos que una cadena de signos \( t \) de un lenguaje formal \( \mathcal L \) es un término si existe una sucesión de cadenas de signos \( t_1,\ldots, t_m \) tal que \( t\equiv t_m \) y cada \( t_i \) es una variable, una constante, o bien se obtiene yuxtaponiendo un funtor \( n \)-ádico \( f \) de \( \mathcal L \) con \( n \) elementos anteriores de la sucesión.

De este modo: toda variable y toda constante de \( \mathcal L \) es un término, y si \( t_1,\ldots, t_n \) son términos de \( \mathcal L \) y \( f \) es un funtor \( n \)-ádico, se cumple que \( ft_1\cdots t_n \) también es un término de \( \mathcal L \) (pues podemos construirlo encadenando las sucesiones de términos que definen a cada \( t_i \) y luego añadiendo \( ft_1\cdots t_n \). La sucesión así obtenida satisface la definición precedente).

Ejemplo: Llamaremos lenguaje de la aritmética al lenguaje \( \mathcal L_a \) cuyos signos opcionales son una constante \( 0 \), un funtor monádico \( S \) y dos funtores diádicos \( f_+ \) y \( f_\times \).

Adoptamos el convenio de notación consistente en que, en lugar de escribir \( f_+t_1t_2 \) o \( f_\times t_1t_2 \), como exige la definición de término, escribiremos \( (t_1+t_2) \) y \( (t_1\cdot t_2) \) respectivamente.

Entonces, algunos ejemplos de términos de \( \mathcal L_a \) son las cadenas de signos siguientes:

\( 0,\quad S0, \quad SS0,\quad (S0+SS0),\quad (SS0\cdot(S0+SS0)) \).

Por ejemplo, la primera de estas cadenas es un término porque es una constante, la segunda es un término porque consta del funtor monádico \( S \) seguido del término \( 0 \), la tercera es un término porque consta del funtor monádico \( S \) seguido del término \( S0 \), la cuarta es un término porque consta del funtor diádico \( f_+ \) seguido de los términos \( S0 \) y \( SS0 \). (Sólo que, según hemos acordado, en lugar de escribir \( f_+S0SS0 \) escribimos \( (S0+SS0) \)) y la última cadena es un término porque consta del funtor diádico \( f_\times \) seguido de los términos \( SS0 \) y \( (S0+SS0) \).

Definición: Una cadena de signos \( \alpha \) de un lenguaje formal \( \mathcal L \) es una fórmula si existe una sucesión de cadenas de signos \( \alpha_1,\ldots, \alpha_m \) tal que \( \alpha\equiv \alpha_m \) y cada cadena de la sucesión es de una de estas formas:

a) \( Rt_1,\ldots, t_n \), donde \( R \) es un relator \( n \)-ádico de \( \mathcal L \) y \( t_1,\ldots, t_n \) son términos de \( \mathcal L \). (En la práctica escribiremos \( (t_1=t_2) \) en lugar de \( =t_1t_2 \).)

b) \( \lnot \beta \), donde \( \beta \) es una cadena anterior en la sucesión. (En la práctica escribiremos \( (t_1\neq t_2) \) en lugar de \( \lnot(t_1=t_2) \).)

c) \( \rightarrow \beta\gamma \), donde \( \beta \) y \( \gamma \) son cadenas anteriores de la sucesión. (En la práctica escribiremos \( (\beta \rightarrow \gamma) \) en lugar de \( \rightarrow \beta\gamma \).)

d) \( \forall x\beta \), donde \( x \) es una variable y \( \beta \) es una cadena anterior de la sucesión.

Nota técnica

La razón por la que, en principio, definimos las implicaciones en la forma \( \rightarrow \beta\gamma \), aunque en la práctica escribiremos, por supuesto, \( \beta\rightarrow\gamma \), es que de este modo los paréntesis son absolutamente innecesarios desde un punto de vista teórico. Poniendo en medio los implicadores es ambiguo escribir \( \alpha\rightarrow\beta\rightarrow\gamma \), pues no está claro si debe ser entendido como \( (\alpha\rightarrow\beta)\rightarrow\gamma \) o como \( \alpha\rightarrow (\beta\rightarrow\gamma) \). Ahora bien, si escribimos estas fórmulas como lo indica estrictamente la definición, la primera es \( \rightarrow\rightarrow\alpha\beta\gamma \), es decir, una implicación cuya primera fórmula es la implicación de \( \alpha \) y \( \beta \) y la segunda es \( \gamma \), mientras que la otra fórmula es \( \rightarrow\alpha\rightarrow\beta\gamma \), una implicación cuya primera fórmula es \( \alpha \) y su segunda fórmula es la implicación de \( \beta \) y \( \gamma \). De este modo los paréntesis quedan relegados a meros signos taquigráficos, usados para aclarar las ambigüedades que se pueden general al escribir las fórmulas de la forma que nos resulta familiar.

Más aún, si entendemos que "oficialmente" (es decir, sin abusos de lenguaje) las fórmulas son como indica la definición, tenemos que toda fórmula es de una de las formas indicadas en los apartados a), b), c) o d). Concretamente, si el primer signo de una fórmula es un relator, entonces es del tipo a), si el primer signo es un negador, es de tipo b), si el primer signo es un implicador es de tipo c) y si el primer signo es un generalizador es de tipo d).

[cerrar]

Por lo tanto:

Al escribir un relator \( n \)-ádico seguido de \( n \) términos obtenemos una fórmula (aunque cuando el relator sea el igualador lo escribiremos en medio de los términos, y no delante).

Si \( \beta \) es una fórmula, \( \lnot \beta \) también es una fórmula (porque si prolongamos con \( \lnot\beta \) la sucesión que justifica que \( \beta \) es una fórmula obtenemos una justificación de que \( \lnot\beta \) es una fórmula).

Si \( \beta \) y \( \gamma \) son fórmulas, también lo es \( \rightarrow\beta\gamma \) (aunque en la práctica escribiremos \( (\beta\rightarrow \gamma) \). Esto es porque si encadenamos las sucesiones que justifican que \( \beta \) y \( \gamma \) son fórmulas y luego escribimos  \( (\beta\rightarrow \gamma) \) tenemos una sucesión que justifica que  \( (\beta\rightarrow \gamma) \) es una fórmula.

Si \( \beta \) es una fórmula y \( x \) es una variable, entonces \( \forall x\beta \) es una fórmula, pues si prolongamos con \( \forall x\beta \)  la sucesión que justifica que \( \beta \) es una fórmula obtenemos una sucesión que justifica que \( \forall x\beta \) también lo es.

Ejemplo: La sucesión siguiente de cadenas de signos justifica que la última de ellas (y, de hecho, también todas las anteriores) es una fórmula del lenguaje \( \mathcal L_a \):

\( x=Sy \) (un relator diádico actuando sobre dos términos).

\( x=0 \) (ídem)

\( x\neq 0 \) (negación de la fórmula precedente)

\( (x=Sy\rightarrow x\neq 0) \) (implicación de dos fórmulas precedentes)

\( \forall y(x=Sy\rightarrow x\neq 0) \) (generalización de una fórmula precedente)

\( \forall x\forall y(x=Sy\rightarrow x\neq 0) \) (generalización de una fórmula precedente).

En la práctica, cuando haya varios cuantificadores seguidos, como en la última fórmula, los abreviaremos escribiendo \( \forall xy(x=Sy\rightarrow x\neq 0) \).


Hemos definido el lenguaje de la aritmética \( \mathcal L_a \), pero no le hemos asociado ningún modelo. El modelo natural de \( \mathcal L_a \) es el modelo que tiene por universo el conjunto de los números naturales, en el que el significado de la constante \( 0 \) es el número natural cero, el significado del relator \( S \) es la función que a cada número natural le asigna el número siguiente, y los significados de los funtores diádicos \( f_+ \) y \( f_\times \) son las funciones de suma y producto de números naturales, respectivamente.

En este modelo "está claro" que la fórmula \( \forall xy(x=Sy\rightarrow x\neq 0) \) significa que si un número natural es el siguiente de otro, entonces no puede ser el número natural cero. En el mensaje siguiente explicitaremos este "hecho claro", es decir, veremos cómo asociar un significado a cada término y a cada fórmula de un lenguaje formal respecto a un modelo prefijado. Sin embargo, es un hecho fundamental que aquí hemos definido los conceptos de "término" y "fórmula" sin hacer referencia en ningún momento a posibles modelos de un lenguaje formal.

[Carlos Ivorra]

Antes de seguir adelante hagamos un resumen de lo que tenemos hasta ahora. Cualquiera que vea estas dos cadenas de signos:

\( \forall\forall \lnot\rightarrow xy= \),    \( \forall xy(x=Sy\rightarrow x\neq 0) \)

se da cuenta de forma inmediata que la primera es un galimatías, mientras que la segunda tiene sentido.

Lo que hemos visto en el mensaje anterior es que

1) Esa distinción que sabemos hacer a simple vista, incluso sin saber explicar en qué notamos la diferencia, puede describirse mediante unas reglas muy simples, que pueden ser fácilmente programadas para que un ordenador distinga entre cadenas con y sin sentido (es decir, entre términos y fórmulas y galimatías).

2) La distinción entre cadenas con y sin sentido puede hacerse sin hacer referencia para nada al sentido (el significado posible) de las cadenas de signos, atendiendo únicamente a la forma en que están ordenados los distintos signos (es decir, formalmente, atendiendo a la forma y no al significado).

En particular hemos descrito la estructura formal de los términos y las fórmulas, que se resume en lo siguiente:

1) Cada término de un lenguaje formal es una variable, una constante o un funtor n-ádico seguido de n términos.

2) Cada fórmula de un lenguaje formal es un relator n-ádico seguido de n términos, o bien un negador seguido de una fórmula, o bien un implicador seguido de dos fórmulas (aunque en la práctica escribimos el implicador en medio de ambas) o bien un generalizador seguido de una variable y una fórmula (aunque en la práctica simplifiquemos a veces la escritura, como al escribir \( \forall xy \) en lugar de \( \forall x\forall y \)).

Para acabar de sentar las bases más elementales de la lógica nos falta ver que otra acción que sabemos hacer instintivamente puede ser descrita también de forma "entendible para ordenadores". Me refiero a "leer", "entender el significado". Por ejemplo, cuando vemos la fórmula escrita más arriba, si suponemos una interpretación de su lenguaje formal cuyo universo sea el conjunto de los números naturales y en la que el objeto denotado por la constante \( 0 \) sea el número cero y la función denotada por el funtor \( S \) sea la operación sucesor, inmediatamente "entendemos" que la fórmula dice que el sucesor de un número natural no puede ser el cero. Más precisamente, ¿qué relación hay entre estas dos afirmaciones?:

\( \color{blue} \forall xy(x=Sy\rightarrow x\neq 0) \)

El sucesor de un número natural no puede ser el cero.

La respuesta es que la relación entre la primera y la segunda es la misma que entre la segunda y ésta otra:

The successor of a natural number cannot be zero.

Las tres son versiones de la misma afirmación en tres idiomas diferentes: un cierto lenguaje formal, el castellano y el inglés. Las tres tienen perfecto sentido en su propio lenguaje, y las tres tienen el mismo significado, pasar de una a otra cualquiera es lo que se conoce como "traducir". Ahora bien, así como traducir del castellano al inglés es un arte que los ordenadores distan mucho de dominar, traducir de un lenguaje formal al castellano es una labor puramente mecánica que ahora vamos a describir.

Cabe señalar que no toda afirmación castellana puede traducirse a un determinado lenguaje formal, pues un lenguaje formal puede tener únicamente signos específicos para hablar de conceptos muy concretos, mientras que toda afirmación de un lenguaje formal puede traducirse al castellano (supuesto que se haya fijado un modelo del lenguaje formal). Cuando una afirmación castellana puede traducirse a un lenguaje formal decimos que es formalizable en dicho lenguaje, y formalizar afirmaciones castellanas es el primer paso para poder estudiarlas desde el punto de vista de la lógica.

En definitiva, lo que nos preguntamos ahora es ¿qué es exactamente el significado de un término o de una fórmula (respecto de un modelo)?

Para responder a esta pregunta necesitamos asignar un significado provisional a las variables de un lenguaje formal, que, precisamente por ser "variables" no tienen asignado en principio ningún significado fijo:

Definición: Sea \( \mathcal L \) un lenguaje formal y sea \( M \) un modelo de \( \mathcal L \). Una valoración de \( \mathcal L \) en \( M \) es cualquier criterio \( v \) que a cada variable \( x \) de \( \mathcal L \) le asigne un objeto \( v(x) \) del universo de \( M \).

En definitiva, una valoración asigna a cada variable un "significado provisional", como hemos dicho.

Si \( v \) es una valoración, \( x \) es una variable y \( a \) es un objeto del universo de \( M \), representaremos por \( v_x^a \) la valoración que coincide con \( v \) salvo que \( v_x^a(x)\equiv a \), independientemente de lo que valga \( v(x) \).

Ahora ya podemos definir el objeto denotado por (es decir, el significado de) un término:

Definición: Sea \( \mathcal L \) un lenguaje formal, sea \( M \) un modelo de \( \mathcal L \) y sea \( v \) una valoración en \( M \). Cada término \( t \) de \( \mathcal L \) tiene asignado un objeto \( \overline t \) del universo de \( M \) (al que llamaremos objeto denotado por \( t \), respecto de \( M \) y \( v \)) mediante las reglas siguientes:

Si \( x \) es una variable, entonces el objeto que denota es \( \bar x = v(x) \).

Si \( c \) es una constante, entonces el objeto \( \overline c \) que denota es el fijado por el modelo \( M \).

Si \( t = ft_1\ldots t_n \) es un término compuesto por un funtor \( n \)-ádico seguido de \( n \) términos, entonces su objeto denotado es \( \overline t = \overline f(\overline{t_1},\ldots, \overline{t_n}) \), es decir, es el objeto que resulta de aplicar la función denotada por \( f \) (dada por el modelo) sobre los objetos denotados por los términos \( t_1,\ldots, t_n \).

Cuando queramos indicar que \( \overline t \) depende de \( M \) y \( v \) escribiremos \( \overline t = M(t)[v] \).

Notemos que el cálculo de el objeto denotado por un término requiere calcular previamente los objetos denotados por los términos menores que contenga, pero como éstos son necesariamente un número finito, es claro que el proceso para calcular dicho objeto denotado es siempre finito.

Ejemplo: Consideremos el término \( SS0+S0 \) del lenguaje \( \mathcal L_a \) de la aritmética y vamos a calcular el objeto que denota respecto de su modelo natural.

Para ello observamos que \( \overline 0 \) es el número natural cero, pues el objeto denotado por una constante es el que le asigna el modelo, y el modelo natural de \( \mathcal L_a \) establece que la constante \( 0 \) denota al cero.

A continuación calculamos \( \overline{S0} = \overline S(\overline 0) \). Como la función \( \overline S \) es la función sucesor (por la definición del modelo) y ya sabemos que \( \overline 0 \) es el cero, concluimos que \( \overline{S0} \) es el sucesor del número cero, es decir, el número uno.

Igualmente concluimos que \( \overline{SS0} \) es el número dos.

Por último, el término \( SS0+S0 \) es lo que, sin el abuso de notación de poner el funtor en medio, sería \( f_+SS0S0 \), es decir, el funtor diádico \( f_+ \) (que denota en el modelo a la función suma de números naturales) seguido de los términos \( SS0 \) y \( S0 \). Por lo tanto \( \overline{SS0+S0} \) es el número que resulta de aplicar la función suma \( \overline{f_+} \) a los números \( \overline{SS0} \) y \( \overline{S0} \), es decir, la suma de dos más uno, o sea, tres. Concluimos que  \( \overline{SS0+S0} \) es el número natural tres.

Ahora pasamos a definir el significado de una fórmula o, equivalentemente, qué significa exactamente que una fórmula dada sea verdadera o falsa (respecto de un modelo). La presencia de valoraciones hace que evitemos de momento las palabras "verdadero" y "falso" y hablemos más bien de si una fórmula es satisfecha o no por una valoración en un modelo.

Definición:  Sea \( \mathcal L \) un lenguaje formal, sea \( M \) un modelo de \( \mathcal L \) y sea \( v \) una valoración en \( M \). Diremos que una fórmula \( \alpha \) de \( \mathcal L \) es satisfecha en \( M \) por la valoración \( v \) (y lo representaremos \( M\vDash \alpha[v] \)) si se cumple lo siguiente, según la estructura de \( \alpha \):

1) \( M\vDash Rt_1\cdots t_n[v] \) si y sólo si \( \overline R(\overline{t_1},\ldots, \overline{t_n}) \), es decir, una fórmula del tipo "relator seguido de términos" es satisfecha si la relación asociada al relator por el modelo se cumple sobre los objetos denotados por los términos. En particular, \( M\vDash (t_1=t_2)[v] \) equivale a que los objetos denotados por \( t_1 \) y \( t_2 \) sean el mismo (porque la relación denotada por \( = \) es la identidad).

2) \( M\vDash \lnot \alpha [v] \) si y sólo si no \( M\vDash \alpha[v] \), es decir, una fórmula de tipo \( \lnot \alpha \) es satisfecha si y sólo si la fórmula \( \alpha \) no es satisfecha.

3) \( M\vDash (\alpha\rightarrow \beta) [v] \) si y sólo si no \( M\vDash \alpha[v] \) o bien \( M\vDash \beta[v] \) o, equivalentemente, \( \alpha\rightarrow \beta \) es satisfecha salvo si \( \alpha \) es satisfecha y \( \beta \) no lo es.

4) \( M\vDash \forall x\alpha[v] \) si y sólo si para todo objeto \( a \) del universo de \( M \) se cumple que \( M\vDash \alpha[v_x^a] \), es decir, si la fórmula \( \alpha \) es satisfecha, no sólo por la valoración \( v \), sino también por cualquier valoración en la que la variable \( x \) denote cualquier objeto \( a \) posible. En otras palabras, \( \forall x\alpha \) es satisfecha si y sólo si \( \alpha \) es satisfecha cualquiera que sea la interpretación de la variable \( x \).

Nota

Por definición, un modelo asigna un significado a cada constante, a cada relator y a cada funtor de un lenguaje formal, pero no asigna ningún significado a los signos lógicos \( \lnot, \rightarrow, \forall \). La razón es que queríamos que estos signos tuvieran siempre el mismo significado, y es ahora cuando acabamos de asignarles el significado fijo que queremos que tengan.

Los puntos 2) y 3) de la definición anterior vienen a decir que \( \lnot \) y \( \rightarrow \) tienen el significado dado por las tablas de verdad

\( \begin{array}{|c|c|}
\alpha&\lnot \alpha\\
\hline
V&F\\
F&V
\end{array}\qquad \begin{array}{|cc|c|}
\alpha&\beta&\alpha\rightarrow \beta\\
\hline
V&V&V\\
V&F&F\\
F&V&V\\
F&F&V
\end{array} \)

mientras que el punto 4) viene a decir que \( \forall x \) debe interpretarse siempre como "para todo valor posible de la variable \( x \)".

[cerrar]

Ejemplo: Considerando el modelo natural de \( \mathcal L_a \) y una valoración cualquiera \( v \), nos preguntamos a qué equivale exactamente

\( M\vDash \forall xy(x=Sy\rightarrow x\neq 0)[v] \)

Ya sabemos la respuesta: equivale a que un número natural que sea el sucesor de otro no puede ser cero, pero vamos a comprobar que esto es precisamente lo que obtenemos cuando aplicamos la definición precedente.

Por el punto 4) sabemos que \( M\vDash \forall xy(x=Sy\rightarrow x\neq 0)[v] \) equivale a que, para todo objeto \( a \) del universo de \( M \), es decir, para todo número natural \( a \), se cumpla

\( M\vDash \forall y(x=Sy\rightarrow x\neq 0)[v_x^a] \).

De nuevo por 4) sabemos que esto equivale a que para todo número natural \( b \) se cumpla que

\( M\vDash (x=Sy\rightarrow x\neq 0)[v_{xy}^{ab}] \).

Por 3) esto equivale a que para todos los números naturales \( a \) y \( b \), o bien no se cumple \( M\vDash(x=Sy)[v_{xy}^{ab}] \), o bien \( M\vDash (x\neq 0)[v_{xy}^{ab}] \). Equivalentemente, esto es tanto como afirmar que si se cumple \( M\vDash(x=Sy)[v_{xy}^{ab}] \), también se ha de cumplir \( M\vDash (x\neq 0)[v_{xy}^{ab}] \).

Por 1) y 2) esto equivale a que, para todo par de números naturales \( a \) y \( b \), supuesto que cumplan \( M(x)[v_{xy}^{ab}]\equiv M(Sy)[v_{xy}^{ab}] \), también deben cumplir que no \( M\vDash (x=0)[v_{xy}^{ab}] \).

Ahora tenemos en cuenta que el objeto denotado por \( x \) respecto a la valoración \( v_{xy}^{ab} \) es \( v_{xy}^{ab}(x)\equiv a \), mientras que el objeto denotado por \( Sy \) es el siguiente del número denotado por \( y \), que es \( v_{xy}^{ab}(y)\equiv b \). Por lo tanto tenemos:

Para todo par de números naturales \( a \) y \( b \), si \( a \) es el siguiente de \( b \), entonces no se cumple que \( M(x)[v_{xy}^{ab}]\equiv M(0)[v_{xy}^{ab}] \). En definitiva:

Para todo par de números naturales \( \color{blue} a \) y \( \color{blue} b \), si \( \color{blue} a \) es el siguiente de \( \color{blue} b \), entonces \( \color{blue} a \) no es cero.

Así pues, lo que obtenemos después de morirnos de asco aplicando metódicamente la definición de satisfacción es lo que cualquiera capta de un golpe de vista al mirar la fórmula de partida. Obviamente, en la práctica es absurdo seguir todo este camino para llegar a lo evidente. El interés de la definición de satisfacción es que nos permite estudiar el concepto teóricamente con la garantía de que estamos hablando de lo mismo que hacemos en la práctica cuando "entendemos" el significado de una fórmula.

[Carlos Ivorra]

Nuestra descripción básica de los lenguajes formales no puede estar completa si no introducimos de algún modo los "signos perdidos" que hemos omitido en la definición bajo la promesa de recuperarlos más tarde, a saber, el conjuntor, el disyuntor, el coimplicador y el cuantificador existencial.

Si tenemos dos fórmulas \( \alpha \) y \( \beta \), definimos

\( \alpha\lor \beta\equiv \lnot\alpha\rightarrow \beta \)

Aquí hay que destacar que esta definición no es "caprichosa" o arbitraria. Por el contrario, esta definición es la que tiene que ser para que el conjuntor \( \lor \) que acabamos de definir tenga por tabla de verdad la correspondiente a la disyunción, es decir, a la conjunción "o" (no exclusiva) castellana.

En efecto, Si fijamos un modelo \( M \) de un lenguaje formal y una valoración \( v \), tenemos que

\( M\vDash(\alpha\lor \beta)[v] \) es lo mismo que \( M\vDash(\lnot\alpha\rightarrow \beta)[v] \), lo cual sucede si y sólo si no \( M\vDash \lnot\alpha[v] \) o \( M\vDash \beta[v] \), lo cual sucede si y sólo si \( M\vDash \alpha[v] \) o \( M\vDash \beta[v] \).

Puesto que los conectores \( \lnot \) y \( \rightarrow \) tienen siempre la misma interpretación en todos los modelos (la dada por sus respectivas tablas de verdad) acabamos de probar que \( \lor \) tiene siempre la misma interpretación en todos los modelos, de modo que una fórmula \( \alpha\lor\beta \) es satisfecha cuando y sólo cuando lo es al menos una de las dos fórmulas \( \alpha \) y \( \beta \).

Si hubiéramos optado por introducir el disyuntor \( \lor \) como un signo lógico obligatorio más de todo lenguaje formal (en igualdad de condiciones que el negador y el implicador), en la definición de satisfacción habríamos tenido que añadir que una fórmula \( \alpha\lor \beta \) es satisfecha si y sólo si al menos una de las dos \( \alpha \) o \( \beta \) lo es. Y en tal caso las fórmulas \( \alpha\lor \beta \) y \( \lnot\alpha\rightarrow \beta \) no serían la misma fórmula (como lo son según el convenio que hemos adoptado), sino que serían un ejemplo de un par de fórmulas lógicamente equivalentes, es decir, dos fórmulas tales que una es satisfecha por una valoración en un modelo si y sólo si lo es la otra.

Análogamente podemos definir el conjuntor mediante:

\( \alpha\land \beta\equiv \lnot(\lnot\alpha\lor\lnot\beta) \).

Si ahora analizamos cuándo sucede \( M\vDash (\alpha\land\beta)[v] \), según la definición de satisfacción y el resultado que acabamos de probar para la satisfacción del disyuntor, concluiremos fácilmente que \( M\vDash (\alpha\land\beta)[v] \) se cumple cuando y sólo cuando \( M\vDash \alpha[v] \) y \( M\vDash \beta[v] \), lo que demuestra que la tabla de verdad asociada al conjuntor es precisamente la que corresponde a la conjunción castellana "y".

Igualmente podemos (o, mejor, debemos) definir el coimplicador como

\( \alpha\leftrightarrow \beta \equiv (\alpha\rightarrow\beta)\land (\beta\rightarrow \alpha) \).

Nuevamente, esta definición no es "caprichosa", sino que es la necesaria para que la tabla de verdad del coimplicador sea la esperada.

Consideremos por último el caso del cuantificador existencial o particularizador:

\( \exists x\alpha\equiv\lnot \forall x\lnot \alpha \).

Veamos con detalle su interpretación. Si fijamos un modelo \( M \) y una valoración \( v \) tenemos que \( M\vDash \exists x\alpha[v] \) es lo mismo que \( M\vDash \lnot \forall x\lnot \alpha[v] \), lo cual, por definición de satisfacción, equivale a que no \( M\vDash \forall x\lnot \alpha[v] \). Esto, a su vez equivale a que no se cumpla para todo \( a \) en el universo del modelo,  \( M\vDash \lnot\alpha[v_x^a]  \).

Decir que esto no se ha de cumplir para todo \( a \) es lo mismo que decir que existe un \( a \) en el universo del modelo que no cumple \( M\vDash \lnot\alpha[v_x^a]  \), o también que existe un \( a \) en el universo del modelo que cumple \( M\vDash \alpha[v_x^a]  \).

Ésta es la interpretación del cuantificador existencial: se cumple \( M\vDash \exists x\alpha[v] \) si y sólo si existe un objeto \( a \) en el universo del modelo tal que \( \alpha \) es satisfecha si modificamos la valoración para que la variable \( x \) se interprete como \( a \).

Dicho más laxamente, \( \exists x\alpha \) es satisfecha si existe una posible interpretación para la variable \( x \) que hace que \( \alpha \) sea satisfecha.

Así, la definición de \( \exists \) no es caprichosa, sino que es la necesaria para que \( \exists x \) signifique "existe un \( x \)". Si hubiéramos introducido el cuantificador existencial como un signo más de los lenguajes formales (en lugar de definirlo luego a partir del cuantificador universal), entonces habría que haber añadido a la definición de satisfacción que \( M\vDash \exists x\alpha[v] \) equivale a lo que acabamos de probar, y entonces las fórmulas \( \exists x\alpha \) y \( \lnot\forall x\lnot\alpha \) no serían la una una abreviatura de la otra, sino que serían dos fórmulas distintas, pero lógicamente equivalentes.

Para terminar destacamos que las definiciones

\( \alpha\lor \beta\equiv \lnot\alpha\rightarrow \beta \), \( \alpha\land \beta\equiv \lnot(\lnot\alpha\lor\lnot\beta) \), \( \alpha\leftrightarrow \beta \equiv (\alpha\rightarrow\beta)\land (\beta\rightarrow \alpha) \) y \( \exists x\alpha\equiv\lnot \forall x\lnot \alpha \)

son puramente sintácticas, es decir, que no dependen para nada de ningún posible modelo del lenguaje formal. Una vez dadas podemos determinar (como hemos hecho) el significado de los nuevos signos lógicos en cualquier modelo, pero todos ellos están definidos sin hacer referencia a modelos (ni, por lo tanto, a su posible significado).

[Carlos Ivorra]

Consideremos una fórmula como

\( \exists y\ x = Sy \).

En esta fórmula la variable \( x \) está libre, mientras que la variable \( y \) está ligada. En general, se dice que una variable está libre en una fórmula cuando aparece en ella, pero no está afectada por ningún cuantificador, mientras que en caso contrario se dice que está ligada. Hay que tener en cuenta que una misma variable puede estar a la vez libre y ligada en una fórmula. Es el caso, por ejemplo, de la variable \( x \) en

\( x= 0\land \exists x\ x = S0 \)

Aquí la primera \( x \) está libre, mientras que la segunda está ligada. Estas indicaciones bastan para que cualquiera sepa distinguir qué variables están libres o ligadas en una fórmula cualquiera. No obstante, a efectos de hacer demostraciones conviene observar que estos conceptos satisfacen las relaciones recurrentes siguientes:

1) Las variables libres de un término son exactamente las que aparecen en él. Un término no tiene variables ligadas.

2) Las variables libres de una fórmula de tipo \( Rt_1\ldots t_n \) son exactamente las que aparecen en ella, y no tiene variables ligadas.

3) Las variables libres/ligadas de una fórmula de tipo \( \lnot \alpha \) son las mismas que las de \( \alpha \).

4) Las variables libres/ligadas de una fórmula de tipo  \( \alpha\rightarrow \beta \)  son las que están libres/ligadas en \( \alpha \) o en \( \beta \).

5) Las variables libres en una fórmula de tipo \( \forall x\,\alpha \) son las variables libres de \( \alpha \) distintas de \( x \); las variables ligadas son las variables ligadas de \( \alpha \) y además \( x \).

Teniendo en cuenta las definiciones introducidas en el mensaje anterior, de estas reglas se deduce que las variables libres/ligadas en una fórmula de tipo \( \alpha\lor\beta \), \( \alpha\land \beta \) o \( \alpha\leftrightarrow \beta \) son las que están libres/ligadas en \( \alpha \) o en \( \beta \), así como que la regla 5) es válida si cambiamos \( \forall x \) por \( \exists x \).

La interpretación semántica del concepto de variable libre es que las variables libres de un término o fórmula son las únicas (a lo sumo) a las que necesitamos asignar una interpretación para determinar el objeto denotado por el término o si la fórmula es o no satisfecha en un modelo. Éste es el contenido de los dos teoremas siguientes:

Teorema: Sea \( M \) un modelo de un lenguaje formal \( \mathcal L \), sean \( v \) y \( w \) dos valoraciones en \( M \) y sea \( t \) un término de \( \mathcal L \). Si \( v \) y \( w \) coinciden sobre las variables libres en \( t \), entonces \( M(t)[v]\equiv M(t)[w] \).

En otras palabras, que para calcular el objeto denotado \( M(t)[v] \) sólo necesitamos saber cómo actúa \( v \) sobre las variables libres en \( t \). Su actuación sobre las variables que no aparezcan en \( t \) es irrelevante.

Demostración

Por inducción sobre la longitud de \( t \).

Si \( t\equiv x \) es una variable, entonces \( x \) está libre en \( t \), luego por hipótesis, \( M(t)[v] \equiv v(x)\equiv w(x)\equiv M(t)[w] \).

Si \( t\equiv c \) es una constante, entonces el objeto que denota es \( M(c) \), que depende únicamente del modelo \( M \) y no de las valoraciones.

Supongamos que \( t\equiv ft_1\cdots t_n \), para cierto funtor \( n \)-ádico \( f \). Los términos \( t_i \) tienen longitud menor que \( t \), luego por hipótesis de inducción denotan un mismo objeto \( \overline{t_i} \) respecto de ambas valoraciones. El objeto denotado por \( t \) es

\( M(t)[v] \equiv M(f)(\overline{t_1},\ldots, \overline{t_n}) = M(t)[w] \).

Notemos el argumento subyacente al razonamiento inductivo: si el teorema no fuera cierto, habría un termino \( t \) que denotaría dos objetos distintos respecto de dos valoraciones que coinciden sobre sus variables libres. De entre todos los términos así, podríamos tomar uno de la longitud mínima posible. El razonamiento anterior prueba que dicho término de longitud mínima no podría ser ni una variable, ni una constante, ni un funtor con términos, pero todo término ha de ser de uno de estos tipos, luego tenemos una contradicción.

[cerrar]

Teorema: Sea \( M \) un modelo de un lenguaje formal \( \mathcal L \), sean \( v \) y \( w \) dos valoraciones en \( M \) y sea \( \alpha \) una fórmula de \( \mathcal L \). Si \( v \) y \( w \) coinciden sobre las variables libres en \( \alpha \), entonces \( M\vDash \alpha[v] \) es equivalente a \( M\vDash \alpha[w] \).

Demostración

Por inducción sobre la longitud de \( \alpha \).

Si \( \alpha\equiv Rt_1\ldots t_n \) las variables libres de cada término \( t_i \) están entre las de \( \alpha \), luego \( v \) y \( w \) coinciden en dichas variables libres y, por el teorema anterior, \( t_i \) denota un mismo objeto \( \overline{t_i} \) respecto de ambas valoraciones. Entonces

\( M\vDash Rt_1\cdots t_n[v] \) equivale a \( M(R)(\overline{t_1},\ldots, \overline{t_n}) \), que a su vez equivale a \( M\vDash Rt_1\cdots t_n[w] \).

Si \( \alpha\equiv \lnot \beta \), entonces las variables libres de \( \beta \) son las mismas que las de \( \alpha \), por lo que, por hipótesis de inducción \( M\vDash \beta[v] \) equivale a \( M\vDash \beta[w] \). Por lo tanto, no \( M\vDash \beta[v] \) equivale a no \( M\vDash \beta[w] \), es decir, que \( M\vDash \lnot\beta[v] \) equivale a \( M\vDash \lnot\beta[w] \).

El argumento si \( \alpha\equiv\beta\rightarrow\gamma \) es similar.

Si \( \alpha\equiv \forall x\beta \), entonces las variables libres de \( \alpha \) son las de \( \beta \) menos \( x \). Tenemos que \( M\vDash \forall x\beta[v] \) si y sólo si para todo \( a \) en el universo del modelo se cumple que \( M\vDash \beta[v_x^a] \). Las valoraciones \( v_x^a \) y \( w_x^a \) coinciden sobre todas las variables libres en \( \beta \) (pues coinciden sobre \( x \), ya que ambas toman el valor \( a \), y cualquier otra variable libre en \( \beta \) está libre en \( \alpha \), luego las valoraciones coinciden por hipótesis). Por lo tanto, por hipótesis de inducción tenemos que \( M\vDash \forall x\beta[v] \) si y sólo si para todo \( a \) en el universo del modelo \( M\vDash \beta[w_x^a] \), lo cual equivale a que \( M\vDash \forall x\beta[w] \).

[cerrar]

Es útil usar la notación \( \alpha(x_1,\ldots, x_n) \) para indicar que las variables libres de \( \alpha \) están entre \( x_1,\ldots, x_n \) y, en tal caso, escribir \( M\vDash \alpha[a_1,\ldots, a_n] \) para indicar que se cumple \( M\vDash \alpha[v] \), donde \( v \) es cualquier valoración que cumpla \( v(x_i)\equiv a_i \), es decir, que la fórmula \( \alpha \) es satisfecha por cualquier valoración que interprete la variable \( x_i \) como \( a_i \). Según el teorema anterior, las posibles interpretaciones que dé la valoración a las demás variables es irrelevante.

Definición: Se dice que un término es abierto si tiene variables libres. En caso contrario se dice que es cerrado, o que es un designador. Se dice que una fórmula es \( abierta \) si tiene variables libres. En caso contrario se dice que es \( cerrada \) o que es una sentencia.

Los dos teoremas anteriores se traducen en que un designador designa a un mismo objeto en cada modelo, que no depende de la valoración que se considere, e igualmente una sentencia es satisfecha o no en un modelo, sin que importe la valoración que se considere.

El tratamiento de las variables libres nos plantea un problema técnico, y es que los matemáticos, en su uso cotidiano, tratan a veces las variables libres como que representan a objetos arbitrarios (y sus conclusiones valen entonces para todo valor de las variables) y a veces como que representan a objetos particulares (y sus conclusiones valen entonces para un cierto valor de las variables). La diferencia depende del contexto. Si un matemático ha empezado un razonamiento diciendo "tomemos un número real arbitrario \( x \)", entonces la variable \( x \) es genérica, mientras que si la introduce en la forma "podemos asegurar que esta ecuación tiene al menos una solución \( x \)", en lo sucesivo "recuerda" que la variable \( x \) es particular.

De momento no estamos en condiciones de tener en cuenta estos contextos, así que vamos a adoptar una interpretación "por defecto" de las variables libres (la genérica), pero teniendo en cuenta que más adelante nos las ingeniaremos para considerar variables particulares sin contradecir estrictamente nada de lo que vamos a decir ahora.

Definición: Diremos que una fórmula \( \alpha \) es verdadera en un modelo \( M \), y lo representaremos por \( M\vDash \alpha \), si \( M\vDash \alpha[v] \) para toda valoración \( v \) en el modelo. Diremos que es falsa si no  \( M\vDash \alpha[v] \) para toda valoración \( v \) en el modelo.

En otras palabras, una fórmula \( \alpha \) es verdadera si es satisfecha con cualquier valoración o, equivalentemente, con cualquier asignación de significados para sus variables libres, y es falsa si no es satisfecha con ninguna valoración (con cualquier asignación de significados a sus variables libres). Con esta definición se cumple:

Teorema: Si \( \alpha \) es una fórmula de un lenguaje formal y \( M \) es un modelo de dicho lenguaje, entonces \( M\vDash \alpha \) si y sólo si \( M\vDash \forall x\alpha \).

Demostración

Supongamos que \( M\vDash \alpha \). Tomemos una valoración \( v \) en \( M \) y tomemos un \( a \) arbitrario en el universo de \( M \). Entonces \( M\vDash \alpha[v_x^a] \), pues por la definición anterior esto vale para toda valoración, en particular para \( v_x^a \). Pero el hecho de que esto valga para todo \( a \) en el universo de \( M \) equivale a que \( M\vDash \forall x\alpha[v] \), y como esto vale para toda valoración \( v \) concluimos que \( M\vDash \forall x\alpha \).

Recíprocamente, si \( M\vDash \forall x\alpha \), fijamos una valoración \( v \), de modo que \( M\vDash \forall x\alpha [v] \). Esto significa que para todo \( a \) en el universo de \( M \) se cumple \( M\vDash \alpha[v_x^a] \). En particular, si \( a\equiv v(x) \), tenemos que \( M\vDash \alpha[v] \), y como esto vale para toda \( v \) concluimos que \( M\vDash \alpha[v] \).

[cerrar]

Por ejemplo, la fórmula \( x+y=y+x \) del lenguaje de la aritmética es verdadera en su modelo natural, pues es satisfecha sean cuales sean los números naturales con los que se interpreten las variables \( x \) e \( y \), y esto es equivalente a que sea verdadera la sentencia \( \forall xy(x+y=y+x) \). Por el contrario, la fórmula \( x=Sy \) no es ni verdadera ni falsa, pues es satisfecha con ciertas valoraciones (las que asignan a la variable \( x \) el número siguiente al que asignan a la variable \( y \)) y no es satisfecha por otras.

Insistimos en que la equivalencia entre

\( M\vDash x+y=y+x \) y \( M\vDash \forall xy(x+y=y+x) \)

sólo expresa un convenio arbitrario que acabamos de adoptar: que, a efectos de que una fórmula se considere verdadera, debe ser satisfecha con cualquier valoración o, lo que es lo mismo, las variables libres se deben considerar cuantificadas universalmente.

Observemos que si \( \alpha \) es una sentencia, entonces, o bien es satisfecha en un modelo por todas las valoraciones o bien no lo es por ninguna, pues hemos demostrado que de la valoración considerada solo influye su actuación sobre las variables libres, y en este caso no las hay. Por lo tanto:

Teorema: Toda sentencia es verdadera o falsa en un modelo dado.

Está claro que las fórmulas:

\( \alpha_1\equiv \exists x\ y = Sx \),   \( \alpha_2\equiv \exists z\ y = Sz \),   

son equivalentes, en el sentido de que, fijado un modelo y una valoración, \( M\vDash \alpha_1[v] \) es equivalente a \( M\vDash \alpha_2[v] \)

Observemos en general que si en una fórmula cambiamos sistemáticamente una variable ligada (y no libre) por otra nueva (es decir, por otra que no esté presente en la fórmula) esto no altera su significado, es decir, que la formula inicial y la final serán ambas satisfechas o no por una valoración dada en un modelo.  La razón es que al interpretar una fórmula no tenemos en cuenta la interpretación que asigna la valoración a una variable ligada, sino que consideramos todas sus interpretaciones posibles (para ver si todas cumplen lo requerido, en el caso de un cuantificador universal, o si alguna lo cumple, en el caso existencial). Esto debería bastar para que uno se convenza de lo dicho, de manera que la demostración tediosa siguiente no debería aportar gran cosa a nadie.

Demostración tediosa

En primer lugar probamos que si \( t \) es un término y \( t' \) es el término que resulta de cambiar toda aparición de la variable \( x \) por una nueva variable \( y \), entonces, fijado un modelo \( M \) y una valoración \( v \), se cumple que

\( M(t)[v] \equiv M(t')[v_y^{v(x)}] \).

En efecto, razonamos por inducción sobre la longitud de \( t \). Si \( t\equiv z \) es una variable distinta de \( x \) (luego de \( y \)), entonces \( t'\equiv z \), y entonces
\( M(t)[v] \equiv v(x)\equiv  M(t')[v_y^{v(x)}] \).

Si \( t\equiv x \), entonces \( t'\equiv y \), luego \( M(t)[v] \equiv v(x)\equiv v_y^{v(x)}(y)\equiv  M(t')[v_y^{v(x)}] \).

Si \( t \) es una constante es trivial, pues el objeto que denota no depende de la valoración.

Si \( t\equiv ft_1\cdots t_n \), entonces \( t'\equiv ft'_1\cdots t'_n \) y por hipótesis de inducción todos los términos \( t_i \) y \( t'_i \) denotan los mismos objetos \( \overline{t_i}=\overline{t'_i} \) respecto de las dos valoraciones \( v \) y \( v_y^{v(x)} \) respectivamente, luego también

\( M(t)[v] \equiv M(f)(\overline{t_1},\ldots, \overline{t_n}) \equiv M(f)(\overline{t'_1},\ldots, \overline{t'_n})\equiv M(t')[v_y^{v(x)}] \).

Seguidamente probamos que si \( \alpha \) una fórmula y \( \alpha' \) es la fórmula que resulta de cambiar todas sus variables \( x \) por una nueva variable \( y \). Entonces, fijado un modelo \( M \) y una valoración \( v \):

\( M\vDash \alpha[v] \) si y sólo si \( M\vDash \alpha'[v_y^{v(x)}] \).

En efecto, si \( \alpha\equiv Rt_1\cdots t_n \), entonces \( \alpha'\equiv Rt'_1\cdots t'_n \) y hemos probado que los términos \( t_i \) y \( t'_i \) denotan un mismo objeto \( \overline{t_i}=\overline{t'_i} \) con las dos valoraciones, luego

\( M\vDash \alpha[v] \) si y sólo si \( M(R)(\overline{t_1},\ldots, \overline{t_n}) \) si y sólo si \( M(R)(\overline{t'_1},\ldots, \overline{t'_n}) \) si y sólo si \( M\vDash \alpha'[v_y^{v(x)}] \).

Los casos \( \alpha\equiv \lnot\beta \) y \( \alpha\equiv \beta\rightarrow \gamma \) son inmediatos.

Si \( \alpha\equiv \forall z\beta \), donde \( z \) no es \( x \), entonces \( \alpha'\equiv \forall z\beta' \), de modo que

\( M\vDash \forall z\beta \) si y sólo si para todo \( a \) en el universo del modelo \( M\vDash \beta[v_z^a] \), si y sólo si \( M\vDash \beta'[v_{zy}^{av(x)}] \) si y sólo si \( M\vDash \beta'[v_{yz}^{v(x a)}] \) si y sólo si \( M\vDash \forall z\beta'[v_y^{v(x)}] \).

Si \( \alpha\equiv \forall x\beta \), entonces \( \alpha'\equiv \forall y\beta' \) y entonces

\( M\vDash \forall x\beta[v] \) si y sólo si para todo \( a \) en el universo del modelo \( M\vDash \beta [v_x^a] \), si y sólo si \( M\vDash \beta'[v_{xy}^{av_x^a(x)}] \) si y sólo si (siempre para todo \( a \)) \( M\vDash \beta'[v_{xy}^{aa}] \) si y sólo si \( M\vDash \beta'[v_{y}^{a}] \) (porque \( x \) no aparece en \( \beta' \), ni libre ni ligada) si y sólo si \( M\vDash \forall y\beta'[v] \)

En particular, si \( x \) está ligada y no libre en \( \alpha \), entonces \( y \) no está libre en \( \alpha' \), luego lo que hemos probado se reduce a

\( M\vDash \alpha[v] \) si y sólo si \( M\vDash \alpha'[v] \),

como queríamos probar.

[cerrar]

Esto hace que en cualquier momento podemos cambiar una variable ligada por otra (nueva) sin cambiar el significado de una fórmula. Por ello, se considera "de mal gusto" escribir fórmulas como

\( x= 0\land \exists x\ x = S0 \)

En su lugar, es preferible escribir

\( x= 0\land \exists y\ y = S0 \),

para evitar que la variable \( x \) deba ser interpretada de dos formas distintas (primero como una variable libre que requiere, para que la fórmula sea satisfecha, una valoración que le asigne como interpretación el cero, y luego como una variable ligada que puede ajustarse como haga falta para que se cumpla la segunda parte, de modo que la interpretación "correcta" en la segunda parte no tiene nada que ver con la interpretación de la variable en la primera parte). Decimos "de mal gusto" porque no hay nada de incorrecto en ella, pero los matemáticos prefieren que (en un mismo contexto) objetos que no son necesariamente el mismo estén representados por variables distintas. Fórmulas como \( x= 0\land \exists x\ x = S0 \) son técnicamente correctas y su uso no genera ningún problema, pero siempre es posible sustituirlas por fórmulas como \( x= 0\land \exists y\ y = S0 \), que significan lo mismo y son "más claras". De hecho, si uno no lo piensa mucho puede creer que la fórmula \( x= 0\land \exists x\ x = S0 \) no puede ser satisfecha en el modelo usual de la aritmética (parece que diga que \( x \) tiene que ser cero y uno a la vez), y no es así. Es satisfecha por cualquier valoración para la que \( v(x) \) sea el número cero.

[Carlos Ivorra]

Nos falta discutir un último aspecto sobre los lenguajes formales antes de poder usarlos para formalizar razonamientos. Se trata del concepto de sustitución. Es un concepto que los matemáticos usan cotidiana e instintivamente. Por ejemplo, cuando un matemático escribe

\( A = \{x\in \mathbb R\mid \alpha(x)\} \)

y luego tiene que \( 3\in A \), de ahí deduce \( \alpha(3) \). Al escribir esto ha sustituido la variable \( x \) por el término \( 3 \) en la fórmula \( \alpha \). Parece una operación trivial que apenas requiere un comentario para ser definida, pero no es exactamente así, como vamos a ver ahora. En esencia es ciertamente trivial, pero hay una cuestión técnica que debemos tener presente a la hora de tratar con sustituciones.

Para empezar, a la hora de tratar teóricamente con la sustitución, es preferible usar una notación más explícita, en la que se vean todos los elementos involucrados. En lugar de escribir \( \alpha(x) \) y \( \alpha(3) \), escribiremos \( \alpha \) (porque una fórmula puede tener varias variables libres, y cualquiera de ellas puede ser sustituida en cualquier momento por un término) y escribiremos \( S_x^3\alpha \) para la sustitución (de modo que se indica claramente que estamos sustituyendo la variable \( x \) por el término \( 3 \) en la fórmula \( \alpha \)). El objetivo de este mensaje es dar una definición precisa de \( S_x^t\theta \), donde \( \theta \) es un término o una fórmula, \( x \) es una variable y \( t \) es un término.

Como siempre en estos contextos, la idea subyacente al concepto que queremos definir se expresa de forma natural en términos semánticos, es decir, en términos de lo que pretendemos que signifique lo que queremos definir, supuesto que hayamos fijado un modelo para el lenguaje formal considerado, pero al final daremos una definición puramente sintáctica (formal) que no haga referencia a ningún modelo posible, pero de tal modo que cuando se fije un modelo se corresponda con lo que pretendíamos.

En términos semánticos, el propósito de la sustitución es el siguiente:

Si \( \color{blue} T \) es un término, una sustitución \( \color{blue} S_x^tT \) debe ser otro término con la propiedad de que el objeto que denote en un modelo dado sea el objeto que denota el término \( \color{blue} T \) cuando la variable \( \color{blue} x \) se interpreta como el objeto denotado por el término \( \color{blue} t \)

Si \( \color{blue} \alpha \) es una fórmula, una sustitución \( \color{blue} S_x^t\alpha \) debe ser otra fórmula que sea satisfecha en un modelo si \( \color{blue} \alpha \) es satisfecha interpretando la variable \( \color{blue} x \) como el objeto denotado por \( \color{blue} t \).

Veamos algún ejemplo concreto con el lenguaje de la aritmética (y su modelo natural):

Si \( T= Sx \), se trata de un término que significa "el siguiente del número natural \( x \)". El objeto que denota en el modelo natural depende de la valoración \( v \) que consideremos, pues será el siguiente del número natural \( v(x) \).

¿Qué queremos que sea \( S_x^{SS0}Sx \)? Queremos que sea un término que signifique lo mismo que \( T \), es decir, "el siguiente de \( x \)", pero cuando la variable \( x \) se interpreta concretamente como el objeto denotado por \( SS0 \), es decir, como el número natural dos. Así pues, \( S_x^{SS0}Sx \) debe denotar al siguiente del número natural dos, es decir, el tres. Por lo tanto, lo natural es tomar \( S_x^{SS0}Sx\equiv SSS0 \), que es simplemente lo que resulta de quitar la variable \( x \) y poner en su lugar el término \( SS0 \), es decir, lo que vulgarmente se entiende por "sustituir".

Veamos ahora un ejemplo con una fórmula: tomemos

\( \alpha\equiv \forall y(\exists z\ x=y\cdot z\land y\neq S0\rightarrow \exists w\ y=w\cdot SS0) \)

Esta fórmula dice que todo divisor de \( x \) distinto de \( 1 \) es par. Más precisamente, esta fórmula es satisfecha en el modelo natural del lenguaje de la aritmética si y sólo si el objeto denotado por \( x \), es decir, \( v(x) \), tiene todos sus divisores no triviales pares o, equivalentemente, si y sólo si \( v(x) \) es potencia de dos.

¿Qué queremos que sea \( S_x^{SSSx}\alpha \)? Tiene que ser una fórmula que ya no sea satisfecha cuando \( v(x) \) sea potencia de dos, sino cuando el objeto denotado por \( SSSx \) sea potencia de dos, es decir, cuando \( v(x)+3 \) sea potencia de dos. La fórmula obvia que cumple esto es:

\( S_x^{SSSx}\alpha\equiv \forall y(\exists z\ SSSx=y\cdot z\land y\neq S0\rightarrow \exists w\ y=w\cdot SS0) \).

Una vez más, se trata de la fórmula que se obtiene quitando \( x \) y poniendo en su lugar \( SSSx \), es decir, "sustituyendo", en el sentido usual de la palabra.

Esto podría llevarnos a pensar que una definición puramente sintática de \( S_x^t\theta \) (sin hacer referencia a modelos) es definirlo como la expresión (término o fórmula, según lo sea \( \theta \)) que resulta de cambiar cada \( x \) que aparezca en \( \theta \) por el término \( t \). Sin embargo, dar esa definición no sería una buena idea, al menos sin tener presentes un par de cuestiones técnicas.

1) En primer lugar tenemos las "fórmulas de mal gusto" en las que una misma variable puede aparecer a la vez libre y ligada. La fórmula siguiente es lógicamente equivalente a la que hemos puesto como ejemplo, en el sentido de que será satisfecha en cualquier modelo y con cualquier valoración si y sólo si lo es la que hemos dado:

\( \alpha^*\equiv \forall y(\exists z\ x=y\cdot z\land y\neq S0\rightarrow \exists x\ y=x\cdot SS0) \)

Cuando interpretamos esta fórmula en un modelo con una valoración, la primera \( x \) que aparece se interpretará como \( v(x) \), mientras que la segunda \( x \), al estar ligada por el cuantificador \( \exists x \), se interpretará como convenga (si es posible) para que se cumpla la fómrula que sigue al cuantificador, y no será necesario asignarle precisamente el valor \( v(x) \).

Según explicábamos en otro mensaje, los matemáticos evitan este tipo de fórmulas, y en lugar de expresar así la propiedad "tener sólo divisores pares", la expresan con la fórmula inicial, donde la variable \( x \) no representa dos papeles distintos. Pero lo cierto es que estas fórmulas existen, y nuestra definición debe dar cuenta de ellas, y si seguimos al pie de la letra nuestra propuesta de definición de sustitución obtendríamos este "engendro" que ni siquiera es una fórmula:

\( S_x^{SSSx}\alpha^*\equiv \forall y(\exists z\ SSSx=y\cdot z\land y\neq S0\rightarrow \exists SSSx\ y=SSSx\cdot SS0) \)

Observemos que esto no es una fórmula porque las reglas sintácticas no permiten escribir \( \exists SSSx \), sino que detrás de un cuantificador sólo puede ir una variable. Pero aunque corrigiéramos nuestra definición para no tocar las variables que siguen a los cuantificadores y calculáramos esto:

\( S_x^{SSSx}\alpha^*\equiv \forall y(\exists z\ SSSx=y\cdot z\land y\neq S0\rightarrow \exists x\ y=SSSx\cdot SS0) \)

seguiríamos sin acertar, porque esta fórmula no significa que el objeto denotado por \( x \) más tres es potencia de dos. Aquí dice que todo divisor de \( x \) más tres distinto de \( 1 \) es un número par mayor o igual que \( 6 \), cosa que no cumple, por ejemplo, el \( 1 \), a pesar de que \( 1+3=4 \) es potencia de dos.

La sustitución correcta es:

\( S_x^{SSSx}\alpha^*\equiv \forall y(\exists z\ SSSx=y\cdot z\land y\neq S0\rightarrow \exists x\ y=x\cdot SS0) \)

y la moraleja que extraemos de este ejemplo es que la sustitución \( S_x^t\alpha \) debe definirse de modo que las apariciones ligadas de \( x \) no se alteren en absoluto. Sustituir una variable por un término es sustituir únicamente las apariciones libres de la variable.

Sin embargo, esta precisión era la menor de las dos consideraciones que nos vemos obligados a hacer si queremos llegar a un concepto de "sustitución" que se corresponda realmente con nuestro objetivo en todos los casos.

2) Volvamos a nuestra fórmula \( \alpha \) original, sin el doble papel "de mal gusto" que la \( x \) tenía en la fórmula \( \alpha^* \), pero supongamos ahora que queremos calcular \( S_x^{y+z}\alpha \).

Puesto que \( \alpha \) significa "\( x \) es potencia de dos", queremos que \( S_x^{y+z}\alpha \) signifique "\( y+z \) es potencia de dos", pero si nos limitamos a sustituir cada \( x \) (libre) que aparece en \( \alpha \) por \( y+z \) lo que nos sale es:

\( S_x^{y+z}\alpha\equiv \forall y(\exists z\ y+z=y\cdot z\land y\neq S0\rightarrow \exists w\ y=w\cdot SS0) \)

y esto es un "enredo" que nada tiene que ver con que los divisores de \( y+z \) sean pares. Ahí dice algo que es cierto, algo así como que, para todo número \( y \), si existe un \( z \) que cumple la ecuación \( y+z=yz \) e \( y \) no es uno, entonces \( y \) es par (y es cierto porque la condición sólo se da cuando \( y=2,z=2 \)). ¿Qué ha fallado? Que las variables \( y, z \) estaban libre en \( y+z \), pero al meter este término en el lugar de \( x \), han quedado en el radio de alcance de los cuantificadores \( \forall y\ \exists z \), y se han mezclado con otras \( y, z \) que ya estaban en la fórmula \( \alpha \), y el resultado ha sido completamente imprevisible.

Los libros de lógica evitan estas sustituciones incontroladas de dos formas distintas:

A) Quizá la solución más aceptada sea prohibir que se realice la sustitución en este caso. Para ello definen que una variable \( x \) es sustituible por un término \( t \) en una fórmula \( \alpha \) si ninguna variable que está (libre) en \( t \) aparece ligada en \( \alpha \), y sólo consideran definida la sustitución \( S_x^t\alpha \) cuando se cumple esta condición.

En nuestro ejemplo, la variable \( x \) no es sustituible por el término \( y+z \) en la fórmula \( \alpha \) porque las variables \( y, z \) están en \( y+z \) y están ligada en \( \alpha \).

La solución A), con ser, como decimos, la más habitual y totalmente operativa, tiene dos defectos. Uno es que obliga a poner como hipótesis en todos los teoremas que involucren una sustitución que tal o cual variable debe ser sustituible por tal o cual término en tal o cual fórmula, lo cual supone mantener en un constante primer plano lo que es una mera anécdota que nunca se encuentra uno en la práctica.

El segundo inconveniente es que esto de que ciertas variables no puedan ser sustituidas por ciertos términos es algo totalmente ajeno a la práctica habitual del matemático que razona competentemente sin conocer los tecnicismos de la lógica. Si un matemático ve \( \alpha(x) \) y tiene un \( t \) a mano y le interesa decir que \( t \) cumple \( \phi(x) \), no concibe que no pueda escribir \( \phi(t) \). ¿Qué hace en la práctica un matemático? La realidad es que lo que hace es evitar que se le den casos como el que nos ocupa eligiendo prudentemente las variables, pero imaginemos que, por un descuido, un matemático ha escrito la fórmula \( \alpha \) como nosostros lo hemos hecho y, en el curso de un razonamiento está trabajando con una \( y \) y una \( z \) y se ve en la necesidad de decir que \( y+z \) cumple la propiedad \( \alpha \). ¿Qué haría?

El matemático vería \( \alpha \):

\( \forall y(\exists z\ x=y\cdot z\land y\neq S0\rightarrow \exists w\ y=w\cdot SS0) \),

se daría cuenta de que no puede meter ahí \( y+z \) sin hacer un estropicio y, en lugar de detenerse, corregiría la fórmula \( \alpha \), cambiándola por

\( \forall u(\exists v\ x=u\cdot v\land u\neq S0\rightarrow \exists w\ u=w\cdot SS0) \),

pues sabe que las \( y, z \) que aparecen ligadas en la fórmula no tienen nada que ver con las \( y,z \) concretas que está manejando y que le aparecen en su término \( y+z \), y sabe que si en la fórmula cambia las \( y, z \) ligadas por unas \( u,v \) ligadas pasa a otra fórmula que significa lo mismo, que le vale igual, y ahora puede sustituir con tranquilidad y escribir que

\( S_x^{y+z}\alpha\equiv \forall u(\exists v\ y+z=u\cdot v\land u\neq S0\rightarrow \exists w\ u=w\cdot SS0) \)

Así obtiene una fórmula que realmente significa "\( y+z \) es potencia de dos".

En definitiva, la solución B) al problema consiste en definir la sustitución incluyendo instrucciones para sustituir variables ligadas cuando éstas entran en conflicto con variables del término que queremos sustituir. Con esto complicamos la definición de sustitución, pero eso afecta únicamente a los tres o cuatro resultados que hay que demostrar basándose en la definición de sustitución y, a partir de ahí, como las sustituciones se tratarán apelando a esos tres o cuatro resultados ya demostrados, en la práctica usual este caso patológico no deja rastro alguno. Ni hace falta añadir hipótesis a los teoremas recordando siempre lo que no es más que un caso extraño, ni hace falta contradecir la idea natural de que cualquier variable es sustituible en cualquier fórmula por cualquier término si uno tiene dos dedos de frente a la hora de hacerlo.

Naturalmente, adoptaremos la solución B), y tras esta discusión ya estamos en condiciones de dar una definición sintáctica no ingenua de sustitución de una variable por un término. En el próximo mensaje daremos dicha definición y demostraremos que cumple lo requerido.

[Carlos Ivorra]

Ahora estamos en condiciones de definir el concepto de sustitución, teniendo en cuenta los requisitos apuntados por la discusión del hilo precedente.

La sustitución de una variable por un término en otro término no tiene ninguna complicación. Simplemente \( S_x^tT \) es el término que resulta de cambiar cada \( x \) por una \( T \). Una definición recurrente es esta:

\( S_x^t y\equiv \left\{\begin{array}{lll} t & \mbox{si}& y\equiv x\\ y & \mbox{si}& y\not\equiv x\end{array}\right. \)

Observación

Aquí hay que entender que \( x \), \( y \) son variables de un sistema formal. Por ejemplo, podría ser \( x\equiv x_5 \), \( y\equiv x_7 \), pero también podría ser \( x\equiv y\equiv x_5 \), y ésos son los dos casos que distinguimos. Normalmente, cuando en una fórmula escribimos, por ejemplo, \( \forall xy \), sobrentendemos que \( x \) e \( y \) representan dos variables distintas, aunque no se especifique, pero en la definición de sustitución de una variable por un término en una variable necesitamos considerar el caso en que la variable sea la variable a sustituir o que sea otra distinta, y por ello (puntualmente) hemos incumplido el convenio tácito de que letras distintas hacen referencia a variables distintas.

[cerrar]

Si \( c \) es una constante, \( S_x^tc \equiv c \).

\( S_x^t ft_1\cdots t_n\equiv fS_x^tt_1\cdots S_x^tt_n \).

La última relación indica que para sustituir \( x \) por \( t \) en un término de la forma \( ft_1\cdots t_n \) basta dejar el funtor como está y sustituir la variable en cada uno de los términos que le siguen.

Estas reglas permiten calcular en la práctica cualquier sustitución en un término en un número finito de pasos. Más aún, nos muestran (por si alguien no lo consideraba evidente) que al sustituir una variable por un término en un término, lo que sale sigue siendo un término, pues vemos que es siempre una variable, el término sustituido, una constante o una cadena de la forma funtor n-ádico seguido de n términos.

Observación

El último argumento es en realidad un argumento por inducción sobre la longitud de un término. Más explícitamente puede razonarse así: supongamos que existiera un término \( T \) tal que al calcular la sustitución \( S_x^tT \) el resultado no fuera un término. Si hay un término así, podemos tomar uno \( T \) que tenga la longitud mínima posible. Ahora bien, dicho \( T \) no puede ser una variable, pues la definición de sustitución en una variable implica que el resultado es una variable o \( t \), ni puede ser una constante, pues el resultado sería una constante, ni puede ser \( T\equiv ft_1\cdots t_n \), ya que entonces los términos \( t_i \) tendrían longitud menor que \( T \), luego por la elección de \( T \) se cumpliría que cada \( S_x^tt_i \) es un término, y entonces \( S_x^t T \) también lo sería. Como \( T \) tendría que ser de una de estas formas por definición de término, concluimos que \( T \) no puede existir.

[cerrar]

Es en la definición de una variable por un término en una fórmula donde las consideraciones del hilo anterior nos llevan a dar una definición algo más sofisticada de lo que uno podría esperar:

\( S_x^tRt_1\cdots t_n\equiv RS_x^tt_1\cdots S_x^tt_n \)

(es decir, la sustitución de \( x \) por \( t \) en una fórmula atómica se define dejando el relator como está y sustituyendo \( x \) por \( t \) en cada uno de los términos.

\( S_x^t\lnot\alpha\equiv \lnot S_x^t\alpha \)

\( S_x^t(\alpha\rightarrow \beta)\equiv S_x^t\alpha\rightarrow S_x^t\beta \)

(Estas dos condiciones implican a su vez que \( S_x^t(\alpha\lor \beta)\equiv S_x^t\alpha\lor S_x^t\beta \), \( S_x^t(\alpha\land \beta)\equiv S_x^t\alpha\land S_x^t\beta \), \( S_x^t(\alpha\leftrightarrow \beta)\equiv S_x^t\alpha\leftrightarrow S_x^t\beta \). Basta sustituir cada conector por su definición y aplicar las reglas que acabamos de dar.)

\( S_x^t\forall y\alpha\equiv \left\{\begin{array}{lll} \forall y\alpha & \mbox{ si } x \text{ no está libre en } \forall y\alpha\\ \forall yS_x^t\alpha & \mbox{si }  x \text{ está libre en }\forall y\alpha \text{ e } y \text{ no está libre en } t\\
\forall z S_x^tS_y^z\alpha&\mbox{si } x \text{ está libre en } \forall x\alpha,\ y \text{ está libre en } t.\end{array}\right. \)

En el tercer caso, \( z \) es la variable de menor índice que no está ni en \( \forall y\alpha \) ni en \( t \). De la definición del cuantificador existencial se sigue fácilmente que la misma regla vale cambiando \( \forall \) por \( \exists \).

Nota conceptual importante

La última condición de la definición de sustitución no es evidente. Si uno lee las observaciones del hilo anterior puede convencerse de que es "razonable", pues lo que dice la primera condición es que si la variable \( x \) no está libre no se realiza sustitución alguna, y que si la variable \( y \) (que está ligada en \( \forall y\alpha \) está libre en \( t \), antes de hacer la sustitución cambiamos \( y \) por una variable nueva \( z \), de modo que la \( y \) siga quedando libre en el resultado de la sustitución.

Pero es importante comprender que nada de esto es suficiente. En el hilo anterior hemos visto que hay que tomar ciertas precauciones si queremos que la sustitución se comporte correctamente, pero ¿hemos tenido en cuenta todo lo que hacía falta tener en cuenta? ¿No puede ocurrir que, aparte de los problemas señalados en el hilo anterior pudiera haber otros que no hemos tenido en cuenta y que vuelvan "defectuosa" la definición que acabamos de dar? La respuesta es negativa, pero lo que garantiza que nuestra definición es correcta es el teorema siguiente, que demuestra que la sustitución se comporta exactamente como pretendíamos que se comportara.

Esto está relacionado con una discusión desarrollada en el hilo de comentarios: si uno toma un libro de lógica, se encuentra con esta definición de sustitución u otra distinta y la acepta porque sí, y uno o dos temas más adelante se encuentra con el teorema siguiente, y lo toma simplemente como "una propiedad que tiene la sustitución", sin darse cuenta de que no es "una propiedad más", sino la justificación de que la sustitución está bien definida, entonces está adquiriendo una visión deformada de la lógica, pues no está siendo consciente de que las definiciones "porque sí" son inadmisibles, que hay que demostrar que las definiciones que se dan cumplen la función que se espera de ellas y, sí, el libro lo demostrará, pero no basta con que esté demostrado, hace falta comprender que esa demostración no es gratuita, sino que es un requisito indispensable para justificar que lo que estamos haciendo no es un juego en el que se fijan las reglas por capricho o conveniencia, sino que son pasos en un programa concreto con un objetivo concreto cuya consecución debe ser justificada: formalizar el razonamiento (aunque de momento estamos en el paso previo de formalizar el lenguaje que se usa en los razonamientos). Formalizar no es inventar, es cerciorarse de que las definiciones formales describen fielmente los conceptos no formalizados que deseamos capturar mediante definiciones formales.

Es como si tengo un problema que involucra unas ciudades y unas carreteras que las unen, y quiero tratarlo formalmente, y para ello decido representar los datos como un grafo. Si tengo siete ciudades (objetos no matemáticos, no son conjuntos de la teoría de conjuntos), no puedo "formalizar" el problema tomando un grafo de cinco vértices. No puedo decir que "mis ciudades" son por definición los vértices de un grafo de cinco vértices. La formalización debe reflejar las características relevantes de la situación no formalizada que se quiere capturar para estudiarla matemáticamente, no soy libre de definir como quiera un grafo que debe representar a las ciudades (no formalizadas) de mi problema. Debo justificar que la formalización se ajusta a la realidad a formalizar. Nuestro caso es idéntico.

[cerrar]

Teorema: Consideremos un lenguaje formal,  un modelo \( M \) y una valoración \( v \). Sean \( x, t, T y \alpha \) una variable, dos términos y una fórmula del lenguaje. Entonces:

\( M(S_x^tT)[v]\equiv M(T)[v_x^{M(t)[v]}] \)

\( M\vDash (S_x^t\alpha)[v] \) se cumple si y sólo si  \( M\vDash \alpha[v_x^{M(t)[v]}] \)

La primera parte dice que el objeto denotado por \( S_x^tT \) es el objeto denotado por \( T \) cuando la variable \( x \) se interpreta como el objeto denotado por \( t \). La segunda parte dice que \( S_x^t\alpha \) es satisfecha si y sólo si \( \alpha \) es satisfecha cuando la variable \( x \) se interpreta como el objeto denotado por \( t \). Son estos hechos los que nos permiten decir que la sustitución está "bien definida" en el sentido de que es una expresión definida "como haga falta" para que al final signifique lo que tiene que significar.

Demostración

Probamos primero la parte de los términos. Razonamos por inducción sobre la longitud de \( T \). Esto supone considerar un \( T \) de longitud mínima que incumpliera el resultado para llegar a una contradicción. En la práctica, basta ver que el teorema se cumple para variables y constantes, y demostrar que se cumple para términos \( ft_1\cdots t_n \) supuesto que se cumpla para \( t_1\cdots t_n \).

En efecto:

Si \( T\equiv x \) tenemos:

\( M(S_x^tx)[v] \equiv M(t)[v] \equiv M(x)[v_x^{M(t)[v]}] \)

Si \( T\equiv y \) es una variable distinta de \( x \) entonces

\( M(S_x^ty)[v]\equiv M(y)[v] \equiv v(y)\equiv M(y)[v_x^{M(t)[v]}] \), porque la últma valoración asigna a \( y \) el valor \( v(y) \).

Si \( T\equiv c \) entonces

\( M(S_x^tc)[v]\equiv M(c)[v]\equiv M(c)\equiv M(c)[v_x^{M(t)[v]}] \).

Si \( T\equiv ft_1\cdots t_n \) y el resultado vale para los \( t_i \), entonces

\( M(S_x^tft_1\cdots t_n)[v]\equiv M(fS_x^tt_1\cdots S_x^tt_n)[v]\equiv \bar f(M(S_x^tt_1)[v],\ldots, M(S_x^tt_n)[v])\equiv \bar f(M(t_1)[v_x^{M(t)[v]}],\ldots, M(t_n)[v_x^{M(t)[v]}]) \)

\( \equiv M(ft_1\cdots t_n)[v_x^{M(t)[v]}] \),

donde hemos representado por \( \bar f \) la función asociada a \( f \) por el modelo \( M \). Ahora vamos a probar la propiedad para las fórmulas. Razonamos de nuevo por inducción sobre la longitud de \( \alpha \). En el primer caso usamos la parte ya probada:

Si \( \alpha\equiv Rt_1\cdots t_n \) y llamamos \( \overline R \) a la relación asociada a \( R \) por el modelo, entonces

\( M\vDash  S_x^tRt_1\cdots t_n[v] \) equivale a \( M\vDash  RS_x^tt_1\cdots S_x^tt_n[v] \), que a su vez equivale a \( \overline R(M(S_x^tt_1)[v],\cdots, M(S_x^tt_n)[v]) \), que por la parte ya probada equivale a \( \overline R(M(t_1)[v_x^{M(t)[v]}],\cdots, M(t_n)[v_x^{M(t)[v]}]) \), pero esto es lo mismo que \( M\vDash Rt_1\cdots t_n[v_x^{M(t)[v]}] \).

Si vale para \( \alpha \), entonces

\( M\vDash S_x^t\lnot\alpha[v] \) equivale a \( M\vdash \lnot S_x^t\alpha[v] \), que equivale a que no se cumpla \( M\vdash  S_x^t\alpha[v] \), que, por hipótesis de inducción equivale a que no se cumpla \( M\vDash \alpha[v_x^{M(t)[v]}] \), que a su vez equivale a que \( M\vDash \lnot \alpha[v_t^{M(t)[v]}] \).

El razonamiento para \( \alpha\rightarrow \beta \) es análogo y lo dejamos al lector.

Consideremos ahora una fórmula \( \forall y\alpha \) y suponemos que el resultado vale para \( \alpha \). Distinguimos los tres casos que se distinguen en la definición de sustitución:

Si \( x \) no está libre en \( \forall y\alpha \), entonces

\( M\vDash (S_x^t\forall y\alpha)[v] \) es lo mismo que \( M\vDash \forall y\alpha[v] \), que es lo mismo que \( M\vDash \forall y\alpha[v_x^{M(t)[v]}] \), donde hemos usado que la satisfacción sólo depende de cómo actúa la valoración sobre las variables libres en la fórmula, y como \( x \) no está libre en la fórmula considerada, podemos cambiar \( v \) por \( v_x^{M(t)[v]} \) sin que ello influya en nada.

Si \( x \) está libre en \( \forall y\alpha \) pero \( y \) no está libre en \( t \), entonces

\( M\vDash (S_x^t\forall y \alpha)[v] \) equivale a \( M\vDash (\forall yS_x^t\alpha)[v] \), que a su vez equivale a que para todo \( a \) del universo del modelo se cumpla \( M\vDash (S_x^t\alpha)[v_y^a] \). Por hipótesis de inducción esto equivale a que, para todo \( a \), se cumpla \( M\vDash \alpha[v_{yx}^{aM(t)[v_y^a]}] \).

Ahora usamos que, como \( y \) no está libre en \( t \), se cumple que \( M(t)[v_y^a]\equiv M(t)[v] \) y que, como \( x \) y \( y \) son variables distintas (porque una está libre en \( \forall y\alpha \) y la otra no), la valoración  \( v_{yx}^{aM(t)[v]} \) es la misma que \( v_{xy}^{M(t)[v]a} \). Por lo tanto, la última condición que hemos obtenido es equivalente a que para todo \( a \) del universo del modelo se cumpla \( M\vDash \alpha[v_{xy}^{M(t)[v]a}] \), lo cual equivale a que \( M\vDash \forall y\alpha[v_x^{M(t)[v]}] \).

Por último, supongamos que \( x \) está libre en \( \forall y\alpha \), que \( y \) está libre en \( t \) y sea \( z \) la menor variable que no está ni en \( \forall y\alpha \) ni en \( t \). (En particular \( z \) es distinta de \( x \) y de \( y \).)

\( M\vDash S_x^t\forall y\alpha[v] \) equivale a que \( M\vDash \forall z S_x^tS_y^z\alpha [v] \). Por definición de satisfacción esto equivale a que para todo \( a \) en el universo del modelo se cumpla \( M\vDash S_x^t S_y^z\alpha [v_z^a] \).

Ahora aplicamos la hipótesis de inducción a la fórmula \( S_y^z\alpha \), que tiene longitud igual a \( \alpha \) (porque cambiar una variable por otra no altera la longitud), luego menor que \( \forall y\alpha \). Así, lo anterior equivale a que para todo \( a \) en el universo del modelo \( M\vDash S_y^z\alpha[v_{zx}^{aM(t)[v_z^a]}] \).

Notemos que \( M(t)[v_z^a] \) es lo mismo que \( M(t)[v] \), porque la variable \( z \) no está libre en \( t \), luego no importa el valor que le asigne \( v \). Usando la hipótesis de inducción para \( \alpha \) esto equivale a que (siempre para todo \( a \)) \( M\vDash \alpha[v_{zxy}^{aM(t)[v]M(z)[v_{zx}^{aM(t)[v]}]}] \).

Aquí observamos que \( M(z)[v_{zx}^{aM(t)[v]}]\equiv a \), luego \( v_{zxy}^{aM(t)[v]M(z)[v_{zx}^{aM(t)[v]}]} \) es lo mismo que \( v_{zxy}^{aM(t)[v]a} \). Por lo tanto la condición equivale a que (para todo \( a \)) \( M\vDash \alpha[v_{zxy}^{aM(t)[v]a}] \). Pero \( z \) no está libre en \( \alpha \), luego el valor que la valoración asigna a \( z \) es irrelevante, luego esto equivale a \( M\vDash \alpha[v_{xy}^{M(t)[v]a}] \).

Por definición de satisfacción esto equivale a que \( M\vDash \forall y\alpha[v_{x}^{M(t)[v]}] \), como queríamos probar.

[cerrar]

En la prueba anterior se ve la utilidad de haber introducido los signos \( \lor, \land, \leftrightarrow, \exists \) como signos definidos y no primitivos. Si fueran signos primitivos tendríamos que haber añadido a la prueba un caso más para cada uno de ellos. Ahora sabemos (con la prueba tal como la hemos presentado) que el resultado es cierto para toda fórmula, luego en particular para las que contienen los signos definidos.

Como explicábamos en el mensaje anterior, los matemáticos no usan la notación \( S_x^t\alpha \), sino que en su lugar prefieren escribir \( \alpha(x) \) sin que esto indique nada en especial (la variable \( x \) puede estar o no libre en \( \alpha \) y aparte puede haber otras variables libres), pero cuando luego escriben \( \alpha(t) \) eso es una forma de escribir \( S_x^t\alpha \).

Un ejemplo de sustitución aparece en la definición de existencia con unicidad. Definimos:

\( \exists! x\alpha(x)\equiv \exists x\alpha(x)\land \forall xy(\alpha(x)\land \alpha(y)\rightarrow x=y) \),

donde \( y \) es la variable de menor índice que no está en \( \exists x\alpha \).

Escrito con la notación \( S \) para la sustitución sería:

\( \exists! x\alpha \equiv \exists x\alpha \land \forall xy(\alpha \land S_x^y\alpha\rightarrow x=y) \).

El teorema que justifica que esta definición no es caprichosa, sino que realmente formaliza la existencia con unicidad es el siguiente:

Teorema: Dado un lenguaje formal y fijado un modelo \( M \) y una valoración \( v \), se cumple \( M\vDash \exists!x\alpha[v] \) si y sólo si existe un único \( a \) en el universo del modelo tal que \( M\vDash \alpha[v_x^a] \).

Demostración

\( M\vDash \exists!x\alpha[v] \) equivale a que \( M\vDash \exists x\alpha[v] \) y \( M\vDash  \forall xy(\alpha \land S_x^y\alpha\rightarrow x=y)[v] \).

La primera parte equivale a que existe un \( a \) en el universo del modelo tal que \( M\vDash \alpha[v_x^a] \).

La segunda parte (aplicando dos veces la definición de satisfacción de un cuantificador) equivale a que para todo par de objetos \( a \) y \( b \) en el universo del modelo se cumple

\( M\vDash (\alpha \land S_x^y\alpha\rightarrow x=y)[v_{xy}^{ab}] \).

Esto equivale a que, \( a \) y \( b \) cumplen \( M\vDash \alpha[v_{xy}^{ab}] \) y \( M\vDash S_x^y\alpha[v_{xy}^{ab}] \), entonces \( a\equiv b \).

Como \( y \) no está en \( \alpha \), la primera condición equivale a \( M\vDash \alpha[v_{x}^{a}] \) y por el teorema anterior la segunda equivale a \( M\vDash \alpha[v_{xyx}^{abM(y)[v_{xy}^{ab}]}] \), que se simplifica obviamente a \( M\vDash \alpha[v_x^b] \), pues podemos eliminar la modificación de la valoración en \( y \) (que no está en \( \alpha \)) y de las dos modificaciones de \( x \) prevalece la última.

En resumen, la fórmula que hemos definido se satisface si y sólo si:

Existe un \( a \) en el universo del modelo tal que \( M\vDash \alpha[v_x^a] \) y si dos elementos \( a,b \) en dicho universo cumplen \( M\vDash \alpha[v_x^a] \) y \( M\vDash \alpha[v_x^b] \), necesariamente \( a\equiv b \).

Pero esto es lo mismo que decir que sólo hay un \( a \) que cumpla \( M\vDash \alpha[v_x^a] \).

[cerrar]

Dejamos como ejercicio probar que el teorema anterior se cumple también con esta definición alternativa de la existencia con unicidad (que no involucra el concepto de sustitución)

\( \exists! x\alpha\equiv \exists y\forall x(\alpha\leftrightarrow x=y) \),

donde \( y \) es la menor variable que no está en \( \exists x\alpha \).

Las dos definiciones posibles que hemos dado son ejemplos de fórmulas lógicamente equivalentes, es decir, de fórmulas tales que una es satisfecha en un modelo cualquiera si y sólo si lo es la otra.

Con esto ya tenemos suficientes resultados sobre lenguajes formales para empezar (a partir del hilo siguiente) a utilizarlos en nuestro proyecto de formalizar el razonamiento.

[Carlos Ivorra]

Definición: Usaremos la notación \( \alpha_1,\ldots, \alpha_n\vDash \alpha \) para indicar que \( \alpha_1,\ldots, \alpha_n, \alpha \) son fórmulas de un lenguaje formal \( \mathcal L \) tales que es posible demostrar que cuando \( M \) es un modelo de \( \mathcal L \) y se cumple \( M\vDash \alpha_1,\ldots, \alpha_n \) necesariamente se cumple también  \( M\vDash \alpha \).

En palabras: el hecho de que \( \alpha_1,\ldots, \alpha_n, \alpha \) sean verdaderas en un modelo hace que necesariamente \( \alpha \) también lo sea.

Ejemplo: Si \( \alpha \) y \( \beta \) son fórmulas arbitrarias de un lenguaje formal, se cumple

\( \alpha\rightarrow\beta,\ \alpha\vDash \beta \).

Demostración

Vamos a dar dos demostraciones de este hecho:

1) Supongamos que \( M \) es un modelo del lenguaje considerado y que se cumple \( M\vDash \alpha \) y \( M\vDash (\alpha\rightarrow \beta) \), esto significa que, para toda valoración \( v \) en el modelo, se cumple \( M\vDash \alpha[v] \) y \( M\vDash (\alpha\rightarrow \beta)[v] \). Por definición de satisfacción, lo segundo significa que o bien no \( M\vDash \alpha[v] \), o bien \( M\vDash \beta[v] \), pero la primera posibilidad no puede darse, pues tenemos que  \( M\vDash \alpha[v] \). Así pues, tiene que ser \( M\vDash \beta[v] \). Como esto vale para toda valoración \( v \), concluimos que \( M\vDash \beta \), como queríamos probar.

2) Cuando no hay cuantificadores involucrados podemos usar tablas de verdad. En este caso tenemos:

\( \begin{array}{c|c|c}
\alpha&\beta&\alpha\rightarrow \beta\\
\hline
\color{blue}V&V&\color{blue}V\\
V&F&F\\
F&V&V\\
F&F&V
\end{array} \)

Observamos que en el único caso en que tanto \( \alpha \) como \( \alpha\rightarrow\beta \) son verdaderas, sucede que \( \beta \) también lo es. Como la tabla contempla todas las posibilidades para las tres fórmulas, queda claro que es imposible que  \( \alpha \) y \( \alpha\rightarrow\beta \) sean verdaderas en un modelo sin que \( \beta \) lo sea.

[cerrar]

Se dice que una expresión de la forma \( \alpha\rightarrow\beta,\ \alpha\vDash \beta \) es una regla de inferencia semántica, es decir, un criterio que nos garantiza que si sabemos que unas fórmulas son verdaderas (en un modelo cualquiera) otra tiene que serlo necesariamente. También se dice que \( \beta \) es una consecuencia lógica de \( \alpha \) y \( \alpha\rightarrow\beta \).

Es costumbre dar nombre a las reglas de inferencia. La del ejemplo anterior se llama modus ponendo ponens (en latín, la regla que afirmando (\( \alpha \)) afirma (\( \beta \))), aunque se suele abreviar en modus ponens.

Otro ejemplo es el modus tollendo ponens (la regla que negando (\( \alpha \)) afirma \( (\beta) \)):

\( \alpha\lor\beta,\lnot\alpha\vDash\beta \)

Demostración

Basta considerar la tabla de verdad:

\( \begin{array}{c|c|c|c}
\alpha&\beta&\lnot\alpha&\alpha\lor\beta\\
\hline
V&V&F&V\\
V&F&F&V\\
F&V&\color{blue} V&\color{blue} V\\
F&F&V&F
\end{array} \)

Vemos que en el único caso (a priori podría haber habido más) en que tanto \( \lnot\alpha \) como \( \alpha\lor\beta \) son verdaderas sucede que \( \beta \) también es verdadera.

Es claro entonces que si tomamos un modelo en el que tanto \( \lnot\alpha \) como \( \alpha\lor\beta \) sean verdaderas también lo será \( \beta \), como queríamos probar.

[cerrar]

El modus tollendo tollens (la regla que niega negando) es

\( \alpha\rightarrow\beta,\ \lnot\beta\vDash \lnot\alpha \).

Dejamos la comprobación al lector.

Definición: Una clase particular de reglas de inferencia semánticas son las de la forma \( \vDash \alpha \). Esto significa que podemos razonar que la fórmula \( \alpha \) es verdadera en cualquier modelo. Entonces se dice también que \( \alpha \) es una fórmula lógicamente válida.

Por ejemplo, es fácil comprobar que \( \vDash \alpha\lor\lnot \alpha \). Esta regla recibe el nombre de tercio excluido o, en latín, tertium non datur. Demostrarla equivale a comprobar que en su tabla de verdad sólo puede tomar el valor V, cosa que se comprueba trivialmente.

Veamos ahora alguna regla de inferencia que no puede demostrarse mediante tablas de verdad. Por ejemplo la de transitividad de la igualdad:

\( t_1=t_2,\ t_2=t_3\vDash t_1=t_3 \),

donde \( t_1,t_2,t_3 \) son términos cualesquiera.

Demostración

Supongamos que \( M \) es un modelo en el que \( M\vDash (t_1=t_2) \) y \( M\vDash (t_2=t_3) \). Esto significa que, para cualquier valoración \( v \), se cumple que \( M\vDash (t_1=t_2)[v] \) y \( M\vDash (t_2=t_3)[v] \). A su vez, esto equivale a que \( M(t_1)[v]\equiv M(t_2)[v] \) y \( M(t_2)[v]\equiv M(t_3)[v] \), es decir, a que \( M(t_1)[v] \), \( M(t_2)[v] \) y \( M(t_3)[v] \) son el mismo objeto, luego en particular  \( M(t_1)[v]\equiv M(t_3)[v] \), lo cual equivale a \( M\vDash (t_1=t_3)[v] \). Como vale para toda valoración, \( M\vDash (t_1=t_3) \).

[cerrar]

Tampoco podemos usar tablas de verdad cuando hay cuantificadores involucrados. Por ejemplo en la regla de eliminación del generalizador:

\( \forall x\alpha\vDash S_x^t\alpha \),

donde \( x, t, \alpha \) son una variable, un término y una fórmula arbitrarios de un lenguaje formal dado.

Demostración

Supongamos que \( M \) es un modelo en el que \( M\vDash\forall x\alpha \). Esto significa que, para toda valoración \( v \), se cumple \( M\vDash (\forall x\alpha)[v] \). Esto significa que, para todo \( a \) en el universo del modelo, se cumple \( M\vDash \alpha[v_x^a] \). Aplicamos esto concretamente para \( a\equiv M(t)[v] \). Entonces \( M\vDash \alpha[v_x^{M(t)[v]}] \), pero por el teorema fundamental que hemos probado para la sustitución, esto equivale a \( M\vDash S_x^t\alpha[v] \). Como vale para toda valoración, concluimos que \( M\vDash S_x^t\alpha \).

[cerrar]

Veamos un ejemplo más sofisticado que involucra al igualador y a un cuantificador. Si la variable \( x \) no está libre en el término \( t \), entonces:

\( \vDash (\forall x(x=t\rightarrow \alpha)\leftrightarrow S_x^t\alpha) \).

Observemos que los dos miembros de la fórmula afirman (cada cual a su manera) que \( t \) cumple lo que dice \( \alpha \).

Demostración

Tomamos un modelo \( M \) del lenguaje formal considerado y hemos de probar que la fórmula indicada es verdadera en \( M \). Esto equivale a que para toda valoración \( v \) se tiene que cumplir

\( M\vDash (\forall x(x=t\rightarrow \alpha)\leftrightarrow S_x^t\alpha)[v] \)

Por la tabla de verdad del coimplicador, esto equivale a que se cumple \( M\vDash \forall x(x=t\rightarrow \alpha)[v] \) si y sólo si se cumple \( M\vDash(S_x^t\alpha)[v] \).

Supongamos en primer lugar que \( M\vDash \forall x(x=t\rightarrow \alpha)[v] \). Esto quiere decir que, para todo \( a \) en el universo del modelo (y tomamos concretamente \( a\equiv M(t)[v] \)) se cumple \( M\vDash (x=t\rightarrow \alpha)[v_x^{M(t)[v]}] \).

Esto significa que, o bien no se cumple \( M\vDash (x=t)[v_x^{M(t)[v]}] \), o bien \( M\vDash \alpha[v_x^{M(t)[v]}] \).

Ahora bien, \( M\vDash (x=t)[v_x^{M(t)[v]}] \) equivale a \( v_x^{M(t)[v]}(x)\equiv M(t)[v] \), y esto sí que se cumple, luego tenemos \( M\vDash \alpha[v_x^{M(t)[v]}] \). El teorema sobre la sustitución nos da que esto equivale a \( M\vDash S_x^t\alpha[v] \).

Recíprocamente, si se cumple \( M\vDash S_x^t\alpha[v] \), para probar que también se tiene \( M\vDash \forall x(x=t\rightarrow \alpha)[v] \) hemos de probar que para todo \( a \) en el universo del modelo, se cumple \( M\vDash(x=t\rightarrow \alpha)[v_x^a] \). Para que esto suceda, hemos de ver que si \( M\vDash (x=t)[v_x^a] \), entonces \( M\vDash\alpha[v_x^a] \).

Suponemos, pues, que \( M\vDash (x=t)[v_x^a] \), es decir, que \( a\equiv M(t)[v_x^a] \). En este punto usamos que \( x \) no está libre en \( t \), lo que nos permite afirmar que \( a\equiv M(t)[v_x^a]\equiv M(t)[v] \).

Ahora usamos que \( M\vDash S_x^t\alpha \), que por el teorema de sustituciones es lo mismo que \( M\vDash \alpha[v_x^{M(t)[v]}] \), o también que \( M\vDash\alpha[v_x^a] \), que es justo lo que queríamos probar.

[cerrar]

Hay una regla de inferencia que involucra el cuantificador universal que requiere especial atención. Es la de introducción del generalizador:

\( \alpha\vDash \forall x\alpha \)

Demostración

Si se cumple \( M\vDash \alpha \), esto significa que se cumple \( M\vDash \alpha[v] \), para toda valoración \( v \). En particular, para cualquier \( a \) en el universo del modelo, lo anterior se cumple para la valoración \( v_x^a \), es decir, \( M\vDash \alpha[v_x^a] \), y esto es justo lo que significa que \( M\vDash \forall x\alpha[v] \). Como vale para toda valoración, tenemos que \( M\vDash \forall x\alpha \).

[cerrar]

Su peculiaridad es que se cumple en virtud del convenio que hemos adoptado de considerar que una fórmula es verdadera cuando es satisfecha por cualquier valoración, lo cual equivale a que se cumple si y sólo si se cumple para toda posible interpretación de sus variables libres, y en particular si y sólo si se cumple "para todo x". Ahora bien, ya hemos comentado que los matemáticos no siempre entienden que lo que dice una fórmula hay que entenderlo como que vale para cualquier interpretación de sus variables, sino que distinguen (según el contexto) variables que representan objetos generales y variables que representan objetos particulares. Al adoptar el convenio sobre interpretación de las variables libres nos hemos apartado ligeramente de los hábitos matemáticos y la regla de introducción del generalizador pone de manifiesto esa divergencia. Más adelante veremos cómo podemos "congraciarnos" de nuevo con la práctica usual de los matemáticos sin desdecirnos de lo dicho.

Las reglas de inferencia nos permiten desglosar los razonamientos complejos en razonamientos más simples y reducirlos a "piezas" ya chequeadas y que no es necesario volver a chequear. Por ejemplo, consideremos de nuevo el silogismo que pusimos de ejemplo al inicio del hilo (el de las palabras properispómenas y barítonas). Su formalización es:

\( \forall x(Px\rightarrow Bx),\ PD\vDash BD \)

Ya comentamos que estas fórmulas pueden interpretarse en un modelo cuyo universo sean todas las palabras griegas, en el que los relatores \( P \) y \( B \) se interpretan como dos propiedades de las palabras griegas que los gramáticos griegos sabrán qué demonios significan, y donde la constante \( D \) se interpreta como una cierta palabra griega. Pero el hecho de que el silogismo sea lógicamente válido significa que todo eso es irrelevante, que se cumple lo que acabamos de escribir ahora, es decir, que si las dos premisas son verdaderas en un modelo cualquiera (no importa si su universo son palabras griegas o animales microscópicos) entonces la conclusión también tiene que serlo. Podríamos razonar esto con la misma clase de razonamientos que hemos venido usando en este mensaje, pero, en su lugar, podemos encadenar reglas de inferencia ya demostradas, así:

\( \begin{array}{lll}
1)&\forall x(Px\rightarrow Bx)&\mbox{Premisa}\\
2)&PD&\mbox{Premisa}\\
3)& PD\rightarrow BD&\mbox{Eliminación del generalizador 1}\\
4)&BD&\mbox{Modus Ponens 2,3}
\end{array} \)

¿Cómo hay que entender esto? Supongamos que las dos premisas son verdaderas en un modelo \( M \). Entonces podemos asegurar que la fórmula 3) también será verdadera en \( M \), porque resulta de aplicar la regla de inferencia de eliminación del generalizador, que ya hemos demostrado (notemos que la fórmula 3 resulta de calcular \( S_x^{D} \) sobre la fórmula tras \( \forall x \) en 1). A su vez 4) tiene que ser verdadera en \( M \) porque se obtiene de 2 y 3 por la regla Modus Ponens, que también está demostrada.

Así hemos reducido un razonamiento que podríamos haber improvisado directamente a la aplicación de unas reglas de inferencia, que no son sino razonamientos ya comprobados y que no hace falta comprobar cada vez. Más aún, para construir la sucesión de fórmulas precedente no ha hecho falta considerar para nada ningún modelo. Sólo ha sido un problema de encajar las reglas oportunas adecuadamente, como un puzzle.

Ahora estamos en condiciones de precisar nuestro objetivo inmediato: ¿es posible seleccionar un número finito de reglas de inferencia semánticas (lo cual supone demostrarlas) de modo que siempre que queramos probar una afirmación del tipo \( \alpha_1,\ldots, \alpha_n\vDash \alpha \) (es decir, que el hecho de que unas premisas sean verdaderas en un modelo obliga a que también lo sea la conclusión) podamos hacerlo aplicando oportunamente a las premisas las reglas de inferencia seleccionadas, de modo que no sea necesario mencionar modelos para nada?

La respuesta es afirmativa (pero no es nada trivial que así sea, y esto es una de las joyas que nos regala la lógica), y eso es formalizar el razonamiento, es decir, reducir cualquier razonamiento (que, en su versión no formalizada, significa justificar racionalmente que la verdad de unas premisas en un modelo fuerza a la verdad de la conclusión) a una concatenación de un número finito (fijo) de reglas de inferencia semánticas previamente demostradas, de modo que el razonamiento se reduce a una sucesión de fórmulas enlazadas por unas reglas fijas (que han sido verificadas razonando con modelos, pero que ya no necesitan volver a ser verificadas y, por consiguiente, en la demostración formal no queda referencia alguna a modelos).

En el mensaje siguiente empezaremos a desarrollar este programa de formalización. De momento terminamos con una observación sobre el concepto de regla de inferencia semántica.

Observación: Si en lugar de trabajar metamatemáticamente estuviéramos trabajando en una teoría formal, habríamos dado una definición de regla de inferencia ligeramente distinta, a saber:

\( \alpha_1,\ldots, \alpha_n\vDash \alpha \) significa que para todo modelo \( M \) del lenguaje formal considerado, si \( M\vDash \alpha_1,\ldots, \alpha_n \) entonces \( M\vDash \alpha \).

¿Cuál es la diferencia? Que aquí decimos "si las premisas son verdaderas, la conclusión también lo es", mientras que en la definición al principio del hilo hemos dicho "se puede demostrar que si las premisas son verdaderas..."

No es lo mismo. ¿No podría suceder que tuviéramos unas premisas y una presunta conclusión pero, por una parte no se nos ocurriera (o, peor aún, no hubiera) ningún razonamiento que justificara que la conclusión tiene que ser verdadera cuando lo son las premisas y, al mismo tiempo, no se nos ocurriera cómo construir (o, peor aún, no hubiera forma de construir) un modelo \( M \) en el que las premisas fueran verdaderas pero la conclusión falsa?

Si se diera ese caso, ¿tendría sentido decir que la regla de inferencia es válida o no lo es, aunque no sepamos cuál es el caso? Si no hubiera forma de razonar que la regla es válida ni de construir un modelo que sirva de contraejemplo, ¿tendría sentido decir que hay tal modelo pero no podemos encontrarlo? ¿o habría que decir que no hay tal modelo y la regla es válida pero no hay un razonamiento que lo justifique?

Volveremos sobre estas preguntas más adelante, pero de momento, para evitar esa situación embarazosa, recordemos que hemos definido \( \alpha_1,\ldots, \alpha_n\vDash \alpha \) como que existe un razonamiento que justifica la regla.

[Carlos Ivorra]

En este mensaje empezamos a materializar el proyecto esbozado al final del mensaje anterior. Se trata de seleccionar un número finito de reglas de inferencia semánticas para considerar todas las deducciones que pueden realizarse únicamente con ellas, donde una deducción es una sucesión de fórmulas en la que sólo admitimos las premisas que se quieran considerar y las consecuencias lógicas de esas premisas que se obtienen por aplicación de alguna de las reglas de inferencia seleccionadas. Las deducciones obtenidas de esta forma serán lógicamente válidas en el sentido de que tendremos la garantía de que todas las consecuencias a las que lleguemos de este modo serán verdaderas en todo modelo en el que las premisas sean verdaderas. Lo realmente interesante es que, según veremos, eligiendo adecuadamente las reglas de inferencia, todo razonamiento podrá obtenerse a partir de ellas, es decir, siempre que podamos razonar (por cualquier medio) que se cumple \( \alpha_1,\ldots, \alpha_n\vDash \alpha \), podremos obtener \( \alpha \) a partir de las premisas dadas aplicando oportunamente las reglas de inferencia seleccionadas a las premisas.

Concretamente, vamos a necesitar ocho reglas de inferencia, seis de las cuales serán de la forma \( \vDash \alpha \), para fórmulas \( \alpha \) con cierta estructura prefijada. En tal caso, en lugar de decir que \( \vDash \alpha \) es una regla de inferencia (o, equivalentemente, que \( \alpha \) es una fórmula lógicamente válida) diremos que \( \alpha \) es un axioma lógico, es decir, una fórmula que puede escribirse en cualquier momento en una deducción independientemente de lo que hayamos escrito hasta el momento.

Introducimos primero los seis axiomas lógicos que vamos a considerar. Con más precisión debemos decir que hay infinitos axiomas lógicos, pero que son de seis tipos concretos, fácilmente reconocibles, que constituyen lo que se llama seis esquemas axiomáticos:

Definición: Dado un lenguaje formal \( \mathcal L \), llamaremos axiomas lógicos en \( \mathcal L \) a las fórmulas de \( \mathcal L \) que sean de uno de los seis tipos siguientes (donde \( \alpha,\beta,\gamma \) representan fórmulas arbitrarias, \( t \) representa un término arbitrario y \( x \) representa una variable arbitraria):

K1) \( \alpha\rightarrow (\beta\rightarrow\alpha) \)

K2) \( (\alpha\rightarrow (\beta\rightarrow\gamma))\rightarrow ((\alpha\rightarrow\beta)\rightarrow (\alpha\rightarrow\gamma)) \)

K3) \( (\lnot\alpha\rightarrow\lnot\beta)\rightarrow (\beta\rightarrow\alpha) \)

K4) \( \forall x\alpha\rightarrow S_x^t\alpha \)

K5) \( \forall x(\alpha\rightarrow\beta)\rightarrow (\alpha\rightarrow \forall x\beta) \)     si \( x \) no está libre en \( \alpha \).

K6) \( \forall x(x=t\rightarrow \alpha)\leftrightarrow S_x^t\alpha \)     si \( x \) no está libre en \( t \).

Las condiciones en K5) y K6) significan que si una fórmula tiene la forma indicada pero no cumple esas condiciones adicionales no se considera (por definición) un axioma lógico.

Estos axiomas se eligen con ciertos grados de libertad, pero no de forma arbitraria. Para que lo que hacemos tenga sentido es necesario, por una parte, que todos ellos sean fórmulas lógicamente válidas, es decir, que sean verdaderas en cualquier modelo (para que \( \vDash \alpha \) sea realmente una regla de inferencia semántica) y por otra parte se eligen para que (junto con las dos reglas de inferencia que nos falta por introducir) sean suficientes para formalizar cualquier razonamiento.

Empecemos comprobando que en efecto se cumple una parte de estos requisitos:

Teorema: Todos los axiomas lógicos son fórmulas lógicamente válidas.

Demostración

La comprobación de que los axiomas de tipo K1, K2 y K3 son lógicamente válidos se reduce a calcular sus tablas de verdad y comprobar que ninguno de ellos puede ser falso sean cuales sean los valores de verdad de las fórmulas \( \alpha,\beta,\gamma \) que en ellos aparecen.

El caso de K4 está casi comprobado en el mensaje anterior, donde vimos que \( \forall x \alpha\vDash S_x^t\alpha \) es una regla de inferencia semántica. En efecto, sabiendo esto, si \( M \) es un modelo cualquiera del lenguaje formal considerado, para que un axioma de tipo K4 sea verdadero en \( M \) tiene que suceder que, para toda valoración \( v \), se cumpla \( M\vDash (\forall x\alpha\rightarrow S_x^t\alpha)[v] \), lo cual equivale a que, si \( M\vDash \forall x\alpha[v] \), entonces también se cumpla \( M\vDash S_x^t\alpha[v] \), pero eso es justo lo que comprobamos en el mensaje anterior para demostrar la regla de inferencia citada.

El caso de K6 lo vimos con detalle en el mensaje anterior, luego sólo falta comprobar K5. Queremos probar que, en cualquier modelo \( M \) y con cualquier valoración \( v \) se cumple

\( M\vDash \forall x(\alpha\rightarrow\beta)\rightarrow (\alpha\rightarrow \forall x\beta)[v] \),

bajo el supuesto de que \( x \) no está libre en \( \alpha \). Esto equivale a que si el modelo cumple \( M\vDash  \forall x(\alpha\rightarrow\beta)[v] \) también tiene que cumplir \( M\vDash (\alpha\rightarrow \forall x\beta)[v] \).

Para que se cumpla esto último lo que tiene que suceder es que si \( M\vDash \alpha[v] \), también se tiene que cumplir \( M\vDash \forall x\beta [v] \).

En definitiva, suponemos que \( M\vDash  \forall x(\alpha\rightarrow\beta)[v] \) y \( M\vDash \alpha[v] \), y queremos probar que \( M\vDash \forall x\beta [v] \).

Para ello consideramos un \( a \) arbitrario en el universo del modelo y sabemos que \( M\vDash (\alpha\rightarrow \beta)[v_x^a] \). Como \( x \) no está libre en \( \alpha \), sabemos que \( M\vDash \alpha[v] \) es equivalente a \( M\vDash \alpha[v_x^a] \), pues sólo importan los valores asignados a las variables libres.

De \( M\vDash (\alpha\rightarrow \beta)[v_x^a] \) y \( M\vDash \alpha[v_x^a] \) se deduce \( M\vDash \beta[v_x^a] \), y como tenemos esto para todo \( a \), podemos afirmar que \( M\vDash \forall x\beta \), como había que probar.

[cerrar]

Ahora introducimos el concepto de deducción lógica junto con las dos reglas de inferencia que nos falta seleccionar:

Definición: Una deducción lógica en un lenguaje formal a partir de unas premisas \( \alpha_1,\ldots, \alpha_n \) es una sucesión finita de fórmulas del lenguaje tal que cada fórmula de la sucesión es una premisa, un axioma lógico o bien es consecuencia inmediata de fórmulas anteriores de la sucesión, donde consecuencia inmediata significa que puede obtenerse por la aplicación de una de las dos reglas de inferencia primitivas siguientes:

Modus Ponens: De \( \alpha \) y \( \alpha\rightarrow\beta \) es consecuencia inmediata \( \beta \).

Introducción del generalizador De \( \alpha \) es consecuencia inmediata \( \forall x\alpha \).

Escribiremos \( \alpha_1,\ldots, \alpha_n\vdash \alpha \) para indicar que existe una deducción con premisas \( \alpha_1,\ldots, \alpha_n \) cuya última fórmula es \( \alpha \).

De este modo, tenemos dos conceptos distintos que hemos expresado mediante las notaciones

\( \alpha_1,\ldots, \alpha_n\vDash \alpha,\qquad \alpha_1,\ldots, \alpha_n\vdash \alpha \)

El primero significa que \( \alpha \) tiene que ser verdadera en todos los modelos en los que las premisas sean verdaderas, mientras que el segundo significa que \( \alpha \) puede obtenerse en un número finito de pasos a partir de las premisas y de axiomas lógicos aplicando oportunamente las dos reglas de inferencia a las que hemos llamado primitivas. El primer concepto tiene un sentido muy claro, mientras que el segundo no es en principio más que un cúmulo de arbitrariedades ¿por qué esos axiomas lógicos y no otros? ¿por qué esas reglas de inferencia y no otras? Lo que da sentido al segundo concepto de deducción es que es equivalente al primero, aunque la prueba dista mucho de ser inmediata.

Queda, pues, claro que los axiomas y las reglas de inferencia no se eligen arbitrariamente, pero no es menos cierto que tenemos un margen para elegir los axiomas y las reglas. Hay otras elecciones posibles distintas de las que hemos hecho que dan lugar a un concepto de deducción formal igualmente equivalente al de consecuencia lógica en el sentido semántico. Para recoger estas distintas posibilidades igualmente válidas conviene introducir un concepto general de sistema deductivo formal:

Definición: Dado un lenguaje formal \( \mathcal L \), un sistema deductivo formal \( F \) sobre \( \mathcal L \) está determinado por una colección de fórmulas de \( \mathcal L \) a las que se llama axiomas de \( F \) y un conjunto finito de reglas primitivas de inferencia, que son criterios que especifican cuándo una fórmula se considera consecuencia inmediata en \( F \) de otra u otras fórmulas de \( \mathcal L \).

Una deducción en \( F \) a partir de unas premisas \( \alpha_1,\ldots, \alpha_n \) es cualquier sucesión finita de fórmulas de \( \mathcal L \) de modo que cada una de ellas sea una premisa, un axioma de \( F \) o sea consecuencia inmediata en \( F \) de fórmulas anteriores de la sucesión (es decir, que resulte de aplicar una de las reglas de inferencia de \( F \)).

Escribiremos \( \alpha_1,\ldots, \alpha_n\vdash_F\alpha \) para indicar que \( \alpha \) es la última línea una deducción en \( F \) con premisas \( \alpha_1,\ldots, \alpha_n \).

En estos términos, hemos asociado un sistema deductivo formal a cada lenguaje formal \( \mathcal L \) al que llamaremos \( K_{\mathcal L} \), aunque escribiremos \( \vdash \) en lugar de \( \vdash_{K_{\mathcal L}} \), porque es el único que vamos a usar.

En principio, cualquiera puede tomar las fórmulas más pintorescas y diseñar reglas de inferencia estrafalarias y decir que ha definido un sistema deductivo formal, pero que sus elecciones arbitrarias satisfagan la definición de sistema deductivo formal no ponen al engendro en pie de igualdad con nuestro \( K_{\mathcal L} \), pues éste ha sido diseñado teniendo en cuenta unos requisitos muy específicos:

Definición: Un sistema deductivo formal es correcto si sus axiomas son lógicamente válidos y sus reglas de inferencia son reglas de inferencia semánticas.

Sabemos que \( K_{\mathcal L} \) es correcto, pues hemos demostrado que sus axiomas son lógicamente válidos y en el mensaje anterior vimos que sus dos reglas de inferencia primitivas son reglas de inferencia semánticas. Esto tiene una consecuencia importante:

Teorema: Si \( F \) es un sistema deductivo formal correcto y \( \alpha_1,\ldots, \alpha_n\vdash_F\alpha \), entonces \( \alpha_1,\ldots, \alpha_n\vDash \alpha \).

Demostración

Supongamos que  \( \alpha_1,\ldots, \alpha_n\vdash_F\alpha \). Esto significa que existe una sucesión \( \beta_1,\ldots, \beta_m \) de fórmulas del lenguaje formal considerado tales que \( \beta_m\equiv\alpha \) y cada fórmula es una premisa, un axioma de \( F \) o bien una consecuencia inmediata en \( F \) de fórmulas anteriores de la sucesión.

Queremos probar que \( \alpha_1,\ldots, \alpha_n\vDash \alpha \), es decir, que tenemos un razonamiento que nos asegura que si las premisas son verdaderas en un modelo \( M \) entonces \( \alpha \) también tiene que ser verdadera en \( M \). Veamos cuál es ese razonamiento:

Consideramos \( \beta_1 \). Como no tiene fórmulas anteriores, tiene que ser un axioma o una premisa. Si es un axioma de \( F \), como los axiomas de \( F \) son lógicamente válidos existe un razonamiento que garantiza que \( \beta_1 \) tiene que ser verdadera en \( M \). Si es una premisa no hay nada que razonar, sino que el hecho de que \( \beta_1 \) es verdadera en \( M \) es una de las premisas (en el sentido informal del término) de nuestro razonamiento.

Ahora pasamos a \( \beta_2 \). Si es un axioma, podemos razonar que es verdadero en \( M \), porque es lógicamente válido, y si es una premisa, no hay nada que justificar. Por último, si \( \beta_2 \) se deduce de \( \beta_1 \) por una regla de inferencia de \( F \), como dicha regla es una regla de inferencia semántica, esto significa que existe un razonamiento que nos asegura que \( \beta_2 \) es verdadera en \( M \) partiendo de que \( \beta_1 \) lo es.

De este modo, encadenando los razonamientos que prueban que los axiomas lógicos que intervienen en la deducción son verdaderos en cualquier modelo con los que prueban que las reglas de inferencia de \( F \) llevan siempre de premisas verdaderas a conclusiones verdaderas, vamos construyendo un razonamiento que va justificando que cada fórmula \( \beta_i \) es verdadera en \( M \) apoyándonos en que lo tenemos ya garantizado (sea por ser una premisa o por haberlo demostrado a partir de las premisas) para las fórmulas anteriores. Procediendo de esta forma, tras un número finito de pasos llegamos a un razonamiento que prueba que \( \beta_m\equiv \alpha \) es verdadera en \( M \).

En resumen, una deducción formal en un sistema deductivo formal correcto contiene toda la información necesaria para construir un razonamiento que pruebe que la verdad de la conclusión se sigue de la verdad de las premisas enlazando adecuadamente los razonamientos que justifican que los axiomas del sistema son lógicamente válidos y las reglas de inferencia son reglas de inferencia semánticas. Las deducciones formales no son razonamientos, sino que codifican razonamientos, igual que una fórmula no es una afirmación, sino que codifica una información. La información, al igual que los razonamientos, está hecha de pensamiento, no de signos. Los signos sólo la codifican.

[cerrar]

Diseñar sistemas deductivos formales correctos es muy fácil. Sólo hay que tener cuidado de elegir axiomas y reglas de inferencia correctas, y hay muchos donde elegir y es fácil verificar que en efecto lo son. Lo que ya requiere cierto arte es elegir esos axiomas y esas reglas de inferencia para que el sistema sea semánticamente completo, en el sentido siguiente:

Definición: Un sistema deductivo formal \( F \) sobre un lenguaje formal \( \mathcal L \) es semánticamente completo si para todas las fórmulas \( \alpha_1,\ldots, \alpha_n, \alpha \) de \( \mathcal L \) se cumple que

\( \alpha_1,\ldots, \alpha_n\vdash_F\alpha \)      si y sólo si      \( \alpha_1,\ldots, \alpha_n\vDash\alpha \)

Veremos que \( K_{\mathcal L} \) es semánticamente completo y, desde el momento en que existen sistemas deductivos formales semánticamente completos, sería absurdo trabajar con uno que no lo fuera. Se pueden tomar otros axiomas y otras reglas de inferencia, pero dichas alternativas estarán bien elegidas si al final dan lugar a un sistema completo. Notemos que si \( F \) y \( G \) son dos sistemas deductivos semánticamente completos sobre un mismo lenguaje formal, por muy diferentes que sean sus axiomas y sus reglas de inferencia, al final se tiene que

\( \alpha_1,\ldots, \alpha_n\vdash_F\alpha \)      si y sólo si     \( \alpha_1,\ldots, \alpha_n\vdash_G\alpha \)

para fórmulas cualesquiera de su lenguaje, ya que ambas afirmaciones equivalen a \( \alpha_1,\ldots, \alpha_n\vDash\alpha \), y esta afirmación es independiente de cualquier convenio arbitrario. Ser una consecuencia lógica de unas premisas significa simplemente que si las premisas son verdaderas en un modelo la consecuencia también tiene que serlo, y esto es así o no es así, pero no depende de si hemos elegido definir "razonar" de esta o de aquella manera. Podemos definir sistemas deductivos formales con unos criterios u otros, pero no se define "razonar", lo que está bien razonado está bien razonado y lo que no está bien razonado no lo está. O bien un sistema deductivo formal formaliza sólo razonamientos correctos (es decir, es correcto) o no lo es, y o bien puede formalizar todos los razonamientos correctos (es decir, es completo) o no lo es.

Nota filosófica

Alguien podrá objetar que lo anterior es falso, porque sí que existen distintas nociones de lo que es razonar. Por ejemplo, uno puede aceptar que toda afirmación es verdadera o falsa, mientras que otro puede sostener que hay afirmaciones que no son verdaderas ni falsas, sino "indeterminadas". Alguien así no admitirá que se afirmen cosas como que, dado un modelo, una valoración y una fórmula, se tiene que cumplir \( M\vDash \alpha[v] \) o no se tiene que cumplir (en cuyo caso se cumple \( M\vDash \lnot\alpha[v] \)). Esto es cierto, pero cuando yo hablo de "razonar", me refiero a una forma concreta de razonar (lo que se conoce como lógica clásica, que la humanidad viene empleando desde que el mundo es mundo y, desde luego, mucho antes de que se inventara la lógica formal) que todos tenemos la capacidad de emplear (incluso los que tienen objeciones de conciencia hacia ella) y que es una realidad anterior a cualquier sistema formal, una realidad que se pretende capturar con el concepto de sistema deductivo formal y que, de hecho, se captura con éxito, en virtud del teorema de completitud semántica.

Si consideramos lógicas "informales" alternativas, como la lógica intuicionista, nos encontramos con la misma situación: tenemos una lógica informal y tenemos la posibilidad de formalizarla. Naturalmente, un sistema deductivo formal que formalice la lógica intuicionista será distinto de \( K_{\mathcal L} \), pero igualmente podremos decir que un sistema deductivo formal intuicionista estará diseñado para capturar las formas de razonamiento aceptadas por los intuicionistas, y no dejará de ser cierto que no es el sistema formal el que define el razonamiento, sino el razonamiento el que condiciona la definición de un sistema deductivo que lo capture adecuadamente.

Otro hecho que no tiene nada que ver con lo anterior es que cuando hablo de "razonamiento" me refiero a la restricción de nuestra capacidad de razonamiento a lo que se puede razonar sobre modelos de un lenguaje formal de primer orden. Esto es un contexto muy específico, y nuestra capacidad de razonar va mucho más allá, pero simplemente nuestras posibilidades de razonar, por ejemplo, con realidades que varían con el tiempo, o en situaciones de incertidumbre, simplemente no son aplicables a nuestro contexto, donde estudiamos únicamente realidades (modelos) estáticas en el tiempo, y con propiedades libres de toda posible imprecisión o ambigüedad. Este contexto, aparentemente muy restrictivo, es el único necesario para razonar en teoría de conjuntos, en la cual es posible a su vez formalizar cualquier realidad dinámica, incierta, con lógicas multivaluadas, etc., de tal modo que cualquier lógica alternativa se reduce a la lógica clásica gracias a que puede ser formalizada en la teoría de conjuntos, cuya lógica es la clásica.

[cerrar]

El interés de formalizar el razonamiento es evidente (dejando de lado las necesidades técnicas de fundamentar una teoría de conjuntos). En principio, afirmar que \( \alpha_1,\ldots, \alpha_n\vDash\alpha \) tiene un significado muy concreto, pero es algo muy amplio. Razonar es razonar. No se puede acotar a priori qué argumentos son correctos y cuales son falaces. Si uno argumenta que \( \alpha \) tiene que ser verdadera si lo son las premisas, su razonamiento puede estar bien o puede estar mal, y distinguir los razonamientos correctos de los falaces es precisamente la característica que se llama "racionalidad". Si uno ve un razonamiento de otro y considera que está mal, tendrá que advertirle su error y, o bien el otro reconoce el error, o a su vez considerará que es erróneo el razonamiento que afirma que hay un error. Y no hay unas reglas a priori por las que se pueda decir quién tiene razón. Si un tercero hace de árbitro, podrán convencerle los argumentos de uno o los del otro o los de nadie, pero lo único objetivo es el hecho empírico de que los seres racionales suelen llegar a consensos en las discusiones racionales (las disensiones se producen cuando hay premisas dudosas o implícitas, no por razonamientos dudosos a partir de las premisas).

En cambio, si todos los seres racionales llegan a aceptar que los razonamientos que justifican que \( K_{\mathcal L} \) es semánticamente completo son correctos, a partir de ese momento desaparece cualquier posibilidad de discrepancia sobre lo que es un razonamiento correcto (en el contexto de la lógica de primer orden, es decir, sobre cualquier problema que pueda expresarse como si una determinada afirmación de un lenguaje de primer orden es verdadera o falsa en un modelo). Sencillamente, si un razonamiento puede reducirse a una deducción en \( K_{\mathcal L} \), entonces es correcto, y si no se puede, no es correcto. De este modo, la razón se concreta a sí misma. (Al menos en el contexto de los razonamientos matemáticos) no es necesario confiar en que dos seres racionales que discutan sobre si un razonamiento es válido o no lo es lleguen a un consenso sin saber a qué atenerse más que a su capacidad de raciocinio, sino que si los dos llegan a consensuar que el razonamiento que prueba que \( K_{\mathcal L} \) es semánticamente completo, a partir de ahí tienen garantizado que pueden consensuar cualquier otra discrepancia: si estamos de acuerdo en esto, estamos de acuerdo en todo (en el sentido de que podemos dilucidar sistemáticamente cualquier futura discrepancia estableciendo que sólo tendrá razón quien pueda formalizar su razonamiento en \( K_{\mathcal L} \)). Por supuesto, uno puede equivocarse al formalizar un argumento igual que puede equivocarse al razonar "en el aire", pero la diferencia es que la corrección de una demostración en \( K_{\mathcal L} \) es algo que puede ser comprobado mecánicamente, incluso por un ordenador que no entienda nada, pero sepa distinguir qué es un axioma y qué es una regla de inferencia bien aplicada.

Hay que advertir que esto tiene un poco de utópico, porque trabajar en \( K_{\mathcal L} \) "a bajo nivel" sería muy tedioso y nadie lo hace en la práctica, sino que las demostraciones matemáticas se dejan normalmente a un nivel "semiformalizado", en el sentido de un nivel que no tiene el detalle suficiente como para que uno pueda decir que aquí se aplica MP y allá se aplica IG, pero sí lo suficientemente detallado como para que pasar de ahí a una prueba completamente detallada sea una mera rutina sin interés y que cualquiera podría hacer sin dificultad si tuviera un par de eras geológicas libres, pero en la práctica surgen inconvenientes técnicos, como que unos teoremas se basan en otros, y es fácil que en un enunciado falte una pequeña hipótesis que se ha asumido tácitamente en la prueba pero que haga inválidas referencias posteriores en las que no se tiene tal hipótesis, etc.

Pese a todo, resulta indiscutible que poder "enlatar" toda la capacidad de razonamiento matemático en seis esquemas de axioma y dos reglas de inferencia tiene un gran valor tanto teórico (para estudiar el alcance y las limitaciones del razonamiento matemático) como práctico (para concretar lo que es un razonamiento válido y resolver discrepancias entre seres con uso de razón).

Para terminar, una reflexión: La idea de que uno puede definir un sistema deductivo formal como \( K_{\mathcal L} \) con el propósito de "definir" el razonamiento lógico y limitarse a presentar unos axiomas y reglas de inferencia considerando que no está obligado a justificar nada es esencialmente perversa. Los axiomas y las reglas deben ser demostrados (cosa que nosotros ya hemos hecho) y aún demostrándolos nos quedamos cortos, pues todavía falta justificar que no nos falta ningún axioma o regla por añadir, sino que los que hemos dado son suficientes para extraer todas las consecuencias lógicas posibles de unas premisas dada (cosa que aún tenemos pendiente, y que es lo que se conoce como teorema de completitud semántica).