Teorema de la deducción y permutación de las hipótesis

El teorema de la deducción es el que afirma, por ejemplo, que de una demostración de p suponiendo q se puede concluir que q → p. Dicho teorema sirve para demostrar p → q →. p → q así: p → q, p ⊢ q luego p → q ⊢ p → q luego p → q →. p → q. Pero tal vez sea una forma más correcta de expresarse decir que lo que esto prueba es que existe la demostración de esta última fórmula, antes que ser la prueba de ella. De un modo bastante similar tenemos: p, p → q ⊢ q luego p ⊢ p → q → q luego p →. p → q → q. De nuevo, con esto probamos (en virtud de la prueba del teorema de la deducción) que tal prueba existe, pero no dijimos cual es en concreto (usando sólo el lenguaje objeto).

La prueba de Church proporciona en cierto sentido un modo de dar con una prueba. Veamos por ejemplo el primero de los dos ejemplos del post. El lector dirá probablemente que resulta más lógico probar primero p → p y luego sustituir p por p → q en dicho teorema. Eso se obtendría así:

ley de la reflexividad de la implicación material

1 [p →. p → p → p] →. [p →. p → p] →. p → p ; por sustitución en axioma 2.

2 p →. p → p → p ; sustitución en axioma 1

3 [p →. p → p] →. p → p ; modus ponens 1, 2

4 p →. p → p ;  sustitución en axioma 1

*5 p → p ; por modus ponens, 3, 4.

    

Luego, por sustitución en *5: p → q →. p → q

Pero a diferencia de p → q →. p → q, con p →. p  → q → q no podemos proceder así, apelando sencillamente a la reflexividad de →.

Primero tenemos que pasar de p, p → q ⊢ q a p  ⊢ p → q →. q. Aquí tenemos p → q en lugar de Aₙ y q de Bₘ (Cf. este post). Para cada B hay que probar Aₙ → B.

Como p es supuesto, sabemos como probar p ⊢ p → q → p. También sabemos probar p → q →. p → q. Tenemos que probar entonces p ⊢ p → q →. q. Y la parte derecha de dicha fórmula es nuestro Aₙ → Bₘ, con lo que usamos:

[Aₙ →. Bₖ → Bₘ] →. Aₙ → Bₖ →. Aₙ → Bₘ

 y sustiyendo:

[p → q →. Bₖ → q] →. [p → q] → Bₖ →. p → q. → q

y Bₖ es una las las líneas de la prueba de p, p → q ⊢ q. En este caso es una de las premisas: p. Así, nos queda

[p → q →. p → q] →. p → q → p →. p → q. → q

p → q →. p → q ya sabemos probarlo, obtenemos:

p → q → p →. p → q. → q 

Y como p es premisa, probamos también p ⊢ p → q → p. Una vez más modus ponens  y nos queda : 

p ⊢ p → q. → q

Ahora hacemos el paso que sigue. Sustituyendo en

[Aₙ →. Bₖ → Bₘ] →. Aₙ → Bₖ →. Aₙ → Bₘ

¿Cuál es Bₖ → Bₘ? Pues como vimos: 

** p → q → p →. p → q. → q

obtenemos pues:

[p →. [p → q → p] → [p → q. → q] ] →. p → [p → q → p] →. p → [p → q. → q] 

El antecedente se prueba por ** y lema 1. Obtenemos:

[p →. p → q → p] →. p →. p → q. → q

Y p →. p → q → p se obtiene en un paso del primer axioma, entonces:

p →. p → q. → q

Que es lo que queríamos probar.

Sin duda, ahora el lector querrá la prueba de algo un poco más general, a saber: [p →. q → r] → [q →. p → r], lo cual establece la posibilidad de permutación en general de las hipótesis en una deducción de modo que si de cualesquiera p y q se concluye r, se las puede suponer en cualquier orden, queda como ejercicio (o se lo encuentra acá).

El uso y el prestigio de la razón

En una conversación reciente sobre temas filosóficos escuché decir que la racionalidad se encontraba en algo así como su ocaso. Tal enunciado, claro, contiene propiedades que son extra lógicas. Además, salvo en el caso en que se parta de la noción de una historia, ya lineal o dialéctica, en la que sus momentos se suceden siguiendo el encadenamiento de un orden, justamente, racional; es evidente que no puede ser abordado en ninguna crítica que se se sirva de medios absolutamente apriorísticos.

Si alguien dijera que, en primer lugar, no puede decidirse por medios puramente lógicos si el devenir histórico otorgará tal o cual lugar a la racionalidad, y en segundo que de hacerlo sólo será sobre la base de algún elemento extraído de un conocimiento de ese mismo devenir de un modo intuitivo, sin duda habrá quien quiera responderle que ese enunciado no se reivindica racional, y por ende nada le afectará tal observación. Y como presumiblemente los argumentos meramente formales no serán muy persuasivos en un caso así, deberán esgrimirse otros.

Además, toda la discusión podría ser declarada de "abstracta" (según el uso que recibe el término en ciertas esferas jurídicas) por quien pretenda que la situación aseverada es un hecho presente.

Lo cual nos lleva a un punto de caracter más esencial, a saber, el sentido del enunciado en cuestión. Y, en particular, del termino racional.

Es costumbre en los debates retóricos la subsumsión como modo de reclamar razón. Así, se evoca una palabra como nombre de aquello que el interlocutor esgrime contra una determinada posición para desacreditarla, dejándola así a salvo.

Debates emprendidos en formas semejantes son a no dudarlo los más habituales. Y esto no es de hoy. ¿Qué pasa entonces con la racionalidad, moderna o no?

Es cierto que en la edad moderna la racionalidad ha logrado extender sus confines y abarcar para sí mayores porciones culturales. Pero debe diferenciarse este hecho, el de la extensión efectiva de la influencia de la razón y la lógica, del de la extensión de su prestigio.

La segunda cuestión es más bien política. Es obvio que el uso del prestigio de la razón como fundamento suficiente de alguna proposición no es para nada racional. Es, si se quiere, una forma del argumentum ad verecundiam.

Me imagino, entonces, que para quien la racionalidad se encuentre en algo así como su ocaso, se refiere sin duda a su prestigio. Asumamos esto en lo que sigue.

¿Es esto así? Bueno, ya seguir con esto sería aventurarse en un especulación extrema, con la enorme desventaja que no se trataría de una especulación pura, y así conllevaría sobrepasar los confines del uso recomendado de la misma. Se me ocurre que tales ámbitos del "saber" es el refugio de las especulaciones de deseo (o "elucubraciones de deseo"). Y como el deseo no es sólo de una instancia, el especulador dirá en tales casos lo que quiere que sea, o un deseo contrario a él, etc.

Desde tal punto de mira, parece claro que quienes no han dedicado un gran trabajo al uso racional de la facultad especulativa puedan aseverar la proximidad de un ocaso como el evocado en el post, mientras que quienes lo han hecho por años aseveraran enunciados divergentes. Entonces se vuelve un debate de exhortaciones.

La pregunta es ¿es un debate de tal naturaleza una pérdida de tiempo? Muchos lectores acordarán en que sí lo es. Pero también habrá quienes no consideren de ese modo al entretenimiento, y se entretengan con tales debates, ya sea que formen o no parte de los alocutores.

Pero existe un hecho (lo doy por asumido, pues supongo que todo lector estará de acuerdo, y de no ser así los comentarios permitirán ser ocasión para decir algo más al respecto) y es que tales debates existen, lo han hecho desde hace mucho y muy probablemente sigan haciéndolo. Pareciera haber pues en la razón cierta propensión al entretenimiento, que limita sin duda por lo demás su capacidad productiva.

Y ¿cuál es el lugar de la racionalidad en el entretenimiento de la razón? Antes de dejar lugar a los comentarios (los haya o no) quisiera indicar una cuestión ligada bastante, creo, a esta última pregunta.

En el supuesto avance de la razón durante la época moderna y contemporánea, se han visto desprestigiados distintos modos de argumentación no circunscriptos al conjunto de aquellos basados en al lógica. Ese desprestigio ha hecho, sin duda, que en determinados ámbitos dichos modos se hayan visto reducidos en cierta medida (digo cierta medida, pues no creo que lo haya sido en ningún caso de manera cabal, sea o no por razones de necesidad). Sea cual fuera el nivel de dicha merma, ésta se vuelve notoria al leer sus debates. Pero existen determinados ámbitos donde no se ha corroborado de ninguna manera dicha merma, y una retórica no racional parece regir el pensamiento. El de la oferta publicitaria es sin duda un lugar donde tal cosa se observa con claridad, o al menos que se vé en un análisis lógico se sus enunciados. Y esto es así, incluso, en aquellos casos en que se invoca el prestigio de la ciencia en favor de un producto (frecuente en medicamentos, determinados alimentos para niños, etc.).

Un prueba en la teoría Nicod-Lukasiewicz

Veamos la prueba de «p → p» en el sistema Nicod-Lukasiewicz.

Recordemos el axioma: p/qr | (s/ss) / (sq → ps)

Sustituyendo en él: 'p' por 'p/qr', 'q' por 's/ss', 'r' por 'sq → ps' y 's' por 't', obtememos:

[p/qr|(s/ss)/(sq → ps)] | t/tt / (t|s/ss → p/qr|t)

Nótese que la parte entre corchetes es el axioma mismo, por tanto podemos aplicar la regla, lo cual nos permite afirmar:

(I)  t|s/ss → p/qr|t


Sustituyendo, nuevamente en el axioma, 'p' por 't|s/ss', 'q' y 'r' por 'p/qr|t', 's' por 'w', obtenemos:


(t|(s/ss) → p/qr|t) | (w → w) / (w|(p/qr|t) → t/(s/ss)|w)

Y aplicando la regla (teniendo en cuenta I), obtenemos:

(II)   w|(p/qr|t) → t/(s/ss)|w


Ahora, realizamos en (II) la siguiente sustitución:

'w' por 'p/qr'; 'p', 'q' y 'r' por 's'; 't' por 'sq → ps', 's' por 't' y 't' por 'sq → ps'. Obtenemos el condicional:

p/qr|(s/ss)/(sq → ps) → (sq → ps)/(t/tt)|p/qr

Cuyo antecedente no es sino al axioma, y por ende:

(III)    (sq → ps)/(t/tt)|p/qr

Sustityendo en (I) 't' por '((st → ts)|t/tt)' y 's' por 't':

(st → ts)/(t/tt)| t/tt → p/qr | (st → ts)/(t/tt)

Y como reemplazando en (III) 'p', 'q' y 'r' por 't' nos da:

 (st → ts)/(t/tt)|t/tt

Luego:

(IV)     p/qr | (st → ts)/(t/tt)


Reemplazando en (IV) 'p' por 't|s/ss' y 'q' y 'r' por 'p/qr|t', obtenemos:

(t|s/ss → p/qr|t) | (st → ts) / (t/tt)

Aplicando la regla (teniendo en cuenta (I)), deducimos:

⊢ t/tt

Que es lo que se quería probar.

Más del axioma de Nicod

En el post anterior se hace rerefencia a un axioma que permite, usando la regla de sustitución y una regla de inferencia deducir toda fórmula proposicional. Lukasiwiecz menciona que Leśniewski fue quien notó que la prueba dada por Nicod de «p → p» incluía un error y que, por tanto, no era tal prueba. Esa deducción es publicada por Lukasiewicz en 1931¹. Asimismo, introduce también una modificación en el  axioma de Nicod por otro que es deductible a partir de él en un paso con una sustitución, y que es el presentado en el post citado. El de Nicod es:

p/qr | Ctt / (sq → ps)²

A partir del cual con la sustitución de t por s obtenemos el de Lukasiewicz. Otra prueba que da este autor es la que parte de esta segunda versión del axioma y concluye en la primera, permitiendo afirmar su equivalencia. Se menciona a su vez otro axioma, respecto del cual Wajsberg mostró que servía en lugar del de Nicod. Éste es:

p/qr | [(sr → ps) | p/pq]

Ejercicios:

Usando el axioma y las reglas del post citado, probar:

a. p → p
b. p/qr | Ctt / (sq → ps)



Nota:
1. Luakasiewicz, J. «Uwagi o aksjomacie Nicoda i 'dedukcji uogólniajacej'»
2. Para leer lafórmula téngase en cuenta que: dos letras minuculas una después de la otra, por ejemplo 'pq' representa «p|q»; la barra «/» tiene el mismo significado que «|», pero al momento de cerrar entre paréntesis prepondera la seguda, o sea que 'p|q/p' significa 'p|(q|p)'; 'Css' representa 's → s'.

Función Lisp para convertir fórmula en notación habitual en una de notación prefija

Habitualmente, las fórmulas de la lógica proposicional se escriben usando letras minúsculas como «p», «q», etc., para expresar proposiciones y los signos conectivos, como «→», «∧», etc. se sitúan «entre» ellas para expresar funciones veritativas en las que hagan de argumentos.

Por ejemplo: p → q, p ∧ (q → p), etc.

Se vé, en el segundo caso, que figuran dos paréntesis, lo cual resulta necesario debido a que sin ellos no resultaría claro si lo que se quiere expresar es la función escrita, a saber una conjunción cuyo segundo miembro es un condicional o (como se interpretaría sin los paréntesis) un condicional cuyo primer miembro es una conjunción.  Pero existe una manera, debida a Lukasiewicz, de expresar todas las fórmulas de la lógica proposicional (y aún con predicados y cuantificadores) sin recurrir paréntesis. Estos mismos ejemplos se escribirían así:

Cpq, KpCqp

En este post ya habíamos hecho mención de ello. Pero en el presente nos interesa mostrar una cierta función que sirve para, dada una fórmula expresada en la notación habitual, obtener una equivalente pero expresada en la de Lukasiewicz. A tal fin recurriremos al lenguaje Lisp para escribir la función.

La idea entones es partir de una fórmula tal como:

(p → q) → (p ∧ (q → p))

para obtener una como:

CCpqKpCqp

Para ello usaremos «replace-regexp-in-string». Utilizaremos los siguientes signos conectivos (en otro post, de seguir con el tema, incluiremos además los cuantificadores y los operadores modales):

→ (que en notación prefija es «C»)
∧ («K»)
∨ («A»)
↔ («E»)
|  («D»)

Lo que necesitamos hacer es que cualquier expresión "(x_*_y)" sea transformada en una expresión "*xy" donde el signo conectivo (que está representado por el asterisco, en en el que en cada caso representa un caracter diferente) pase a la primer posición izquierda, y se eliminen  los paréntesis y los espacios en blanco, representados con los guiones bajos. Para que sea más legible, procederemos a reemplazar todo paréntesis izquierdo por el número 0 y todo paréntesis derecho por el 1. Veamos, para empezar, el caso de la conjunción únicamente.

(defun conj (formula)
 (setq formula (replace-regexp-in-string " " "" formula))
 (while (string-match "∧" formula)
  (setq formula (replace-regexp-in-string "(" "0" formula)
        formula (replace-regexp-in-string ")" "1" formula)
        formula (replace-regexp-in-string "0\\([^10]*\\)∧\\([^01]*\\)1" "K\\1\\2" formula)
           )
  )
 (message "%s" formula)
 )

¿Qué hace esta función que llamamos conj?. Pues bien, primero elimina los espacios en blanco. Una vez hecho esto corrobora si en la cadena en cuestión hay algún signo conjuntivo en notación habitual. Si la prueba da t (true) esto significa que hay que aplicar los cambios que siguen. A saber, se cambian los paréntesis por 0 y 1 (como dije, para mayor claridad), luego se toma cualquier subcadena que figure entre paréntesis (0 y 1) y que tenga una signo conectivo ∧ y que no incluya otros paréntesis que los extremos y se reemplaza por otra cadena compuesta por:

Primero, la letra K, que es el signo de la conectiva sobre la que se aplica la función en la notación de Lukasiewicz
Segundo, la parte que se encontraba a izquierda del signo conectivo y
Tercero, la parte que se hallaba a la derecha.

Evidentemente, esto impone la condición de que la fórmula que sea tomada por argumento no debe tener conjunciones de más de dos miembros. Así, en lugar de

p ∧ q ∧ r

debemos escribir, por ejemplo, la fórmula equivalente:

((p ∧ q) ∧ r)

También debe notarse que la fórmula ingresada debe tener paréntesis extremos, aunque sería sencillo evitar esta condición agregándolos en la misma función.

Ahora tenemos que hacer una función que haga la tarea requerida, que llamaremos «nlukasiewicz»

(defun nlukasiewicz (formula)
 (setq formula (replace-regexp-in-string " " "" formula)
       formula (replace-regexp-in-string "¬" "N" formula))
 (while (or (string-match "∧" formula)
        (string-match "∨" formula)
        (string-match "→" formula)
        (string-match "↔" formula))
  (setq formula (replace-regexp-in-string "(" "0" formula)
        formula (replace-regexp-in-string ")" "1" formula)
        formula (replace-regexp-in-string "0\\([^10]*\\)∧\\([^01]*\\)1" "K\\1\\2" formula)
        formula (replace-regexp-in-string "0\\([^10]*\\)∨\\([^01]*\\)1" "A\\1\\2" formula)
        formula (replace-regexp-in-string "0\\([^10]*\\)→\\([^01]*\\)1" "C\\1\\2" formula)
        formula (replace-regexp-in-string "0\\([^10]*\\)↔\\([^01]*\\)1" "E\\1\\2" formula)
           )
  )
 (message "%s" formula)
 )

El lector puede probar en el programa "Emacs" el siguiente ejemplo (luego, claro, de haber evaluado la función):

(nlukasiewicz "((p ∧ (¬q ∨ (¬q → p))) ↔ (p ∧ (p ∨ (q → ¬p))))")

Cuyo resultado es:  EKpANqCNqpKpApCqNp

Dejaremos la barra de Sheffer como ejercicio para el lector.

Un método para el cálculo restringido de predicados

El método de la cuarta edición de Hilbert-Ackerman (Grundzüge der theoretischen Logic) para demostrar las fórmulas válidas proposicionales fue presentado en este post.

Sobre dicha base se formula en el mismo libro un sistema axiomático para la expresiones universalmente válidas del cálculo restringido de predicados (la lógica de primer orden).

Se reformula el concepto de fórmula elemental¹. Serán elementales las fórmulas que consistan en una disyunción «α₁ ∨ ... ∨ α₂» donde:

1) α_i será una fórmula primaria, una fórmula primaria negada o será de la forma: «∃x β» o «∃y β» o «∃z β», etc.
2) han de existir una α_i y uan α_j tales que α_i sea una fórmula primaria y α_j sea «¬α_i».

Las reglas de deducción son:

(a)


   θ ∨ α ∨ γ 
θ ∨ ¬¬α ∨ γ

No es necesario que θ y γ estén presentes en la deducción. Si lo hace γ, ninguno de sus miembros disyuntivos tendrá la forma «¬¬β», «¬(β ∨ δ)» o «¬∃x β» (ni tener una forma así).

(b)

θ ∨ ¬α ∨ γ             θ ∨ ¬β ∨ γ
        θ ∨ ¬(α ∨ β) ∨ γ

Aquí se cumplen para θ y γ las mismas reglas que en (a). En cuanto a β, ésta no puede ser una disyunción.

la siguiente regla no tenía lugar en el cálculo proposicional:

(c)

  θ ∨ ¬α(y) ∨ γ 
θ ∨ ¬∃x α(x) ∨ γ

La expresión «α(y)» contiene una variable libre y. θ y γ (que están sujetas a idénticas condiciones que en (a)) pueden no estar presentes y si lo están en ellas no aparecerá dicha variable, ni tampoco la variable x (pueden tener otras variables).

La última regla es la siguiente:

(d)

θ ∨ ∃x α(x) ∨ α(y) ∨ γ
   θ ∨   ∃x α(x)   ∨   γ

θ y γ deben cumplir con las mismas condiciones que en (a) se exigen para θ. «α(y)» no debe aparecer como miembro disyuntivo una segunda en la fórmula superior.

La equivalencia entre las fórmulas de cada uno de los pisos de (c) se vé así: «¬α(y)» significa que esta fórmula si es verdadero, lo es de cualquier y, pues es una variable libre. Esto equivale a decir que lo es de todo «y», es decir «∀y ¬α(y)». Es cierto además que decir que para todo «x» se cumple que no es α es lo mismo que decir que no existe «x» alguno para el que se cumpla α. O sea: «¬∃y α(y)».

La equivalencia entre los pisos de (d) se sigue de la equivalencia siguiente:

∃x α(x) ∨ α(x)   ≡eq   ∃x α(x)

Esto es así porque:

Primero: ∃x α(x) ∨ α(x)  →   ∃x α(x)

1) ∃x α(x) implica   ∃x α(x) por motivos obvios.
2) Si α(x), esto significa que α es verdadero de cualquier x, asi dado que el dominio de la función no es vacío, existe en él al menos un x que es α

Segundo: ∃x α(x)   →    ∃x α(x) ∨ α(x)

Basta con que el antecedente implique cualquiera de los miembros disyuntivos del consecuente, que es el caso de 1).

___________
1. Se agregan las fórmulas con letras de predicados y cuantificadores a las variables proposicionales.