viernes, 28 de septiembre de 2012

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.

sábado, 15 de septiembre de 2012

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 «α1 ∨ ... ∨ α2» 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.

miércoles, 12 de septiembre de 2012

Demostraciones lógicas

Obtuvimos de la página rinconmatematico.com (del foro de lógica y teoría de conjuntos), el siguiente ejercicio:


1. El lenguaje a utilizar consta del alfabeto de símbolos: ¬, →, (, ), p, q, etc.

2. Un conjunto de fórmulas bien formadas (fbf), que son aquellas que cumplen:

i. p, q, r, etc. son cada una fbf.

ii. Si A y B son fbf, así lo son ¬A y  ¬B.

iii. El conjunto de todas las fbf. es generado por (i) y (ii)

3. Axiomas. Para cada A, B, fbf  se cumple:

L1  (A → (B → A))
L2  ((A → (B → C) → ((A → B) → (A → C))
L3  (¬A → ¬B) → (B → A)

4. Regla de inferencia.
De A, A → B  es consecuencia inmediata B.

5. También pueden usarse las siguientes formas adicionales de deducción:
1. Si γ, A ⊢ B entonces γ ⊢ (A → B)
2. A → B, B → C ⊢ A → C

A) Demuéstrese:

A.1) (p → q) → ((¬p → ¬q) → (q → q)
A.2) ((p → (q → r)) → (p → q)) → ((p → (q → r)) → (p → r))
A.3) (p → (p → q)) → (p → q)
A.4)  p → (q → (p → q))

B) Como ejercicio adicional puede intentarse demostrar estas formas adicionales a partir de L1, L2, L3 y la regla de inferencia. 

domingo, 9 de septiembre de 2012

Demostraciones formales Implicación estricta

Hace unos días, en este post, citamos un sistema lógico que figura en el libro de Hilbert y Ackermann de la bibliografía, que se caracteriza por un concepto de implicación que no es el mas frecuente. Mostraré ahora cómo puede procederse con él para demostrar algunas de las fórmulas que figuran en este post. Desde ya, de aquellas proposiciones que se demuestran en una línea figura a la derecha el esquema axiomático del que son instancias.


i) A → ¬¬A                              Esquema Axiomático 14


iii) A ∧ (A → B) → B

a) (A → B) → ((A ∧ (A → B) → A) → (A ∧ (A → B ) → B))   EA 3
b) A ∧ (A → B) → A                                                         EA 5
c) (A → B) → (A ∧ (A → B ) → B)                                 Regla IV a,b
d) ((A → B) → (A ∧ (A → B) → B)) → ((A ∧ (A → B) → (A → B)) →
     → ((A ∧ (A → B) → (A ∧ (A → B) → B)))                    
                                                                                           EA3
e) ((A ∧ (A → B) → (A → B)) → ((A ∧ (A → B) → (A ∧ (A → B) → B))
                                                                                   Rega I, c,d
f) A ∧ (A → B) → (A → B)                                                 EA 6
g) A ∧ (A → B) → (A ∧ (A → B) → B)                             Regla I, e,f
h) A ∧ (A → B) → (A ∧ (A → B) → B)) → (A ∧ (A → B) → B)    EA 4
i) A ∧ (A → B) → B                                                       Regla I g,h




iv) (A → B) → (¬B → ¬A)                     E.A. 12



v) (A → B) → ((B → C) → (A → C))        E.A. 3



vi) ¬¬¬A → ¬A                                   E.A. 15



vii) ¬A → ¬¬¬A                                      E.A. 14


viii) ¬A → ¬(A ∧ B)

a)  A ∧ B → A                                          E.A.5
b)  (A ∧ B → A) → (¬A → ¬(A ∧ B))          E.A.12
c)  ¬A → ¬(A ∧ B)                                   R.I, a, b.




xi) ¬(A ∨ B) → ¬A ∧ ¬B

a)  A → A ∨ B                                             E.A.5
b)  B → A ∨ B                                             E.A.6
c)  (A → A ∨ B) → (¬(A ∨ B) → ¬A)            E.A.12
d)  ¬(A ∨ B) → ¬A                                     Regla I, a, c
e)  (B → A ∨ B) → (¬(A ∨ B) → ¬B)              E.A.12
f)  ¬(A ∨ B) → ¬B                                       Regla I, b, e
g)  (¬(A ∨ B) → ¬A) ∧ (¬(A ∨ B) → ¬B) →
    → (¬(A ∨ B) → ¬A ∧ ¬B)                        E.A.7
h)  (¬(A ∨ B) → ¬A) ∧ (¬(A ∨ B) → ¬B)      R.II, d, f.
i)  ¬(A ∨ B) → ¬A ∧ ¬B                              R.I, g, h.

sábado, 8 de septiembre de 2012

Raíces de una función de segundo grado

Sabemos, porque es asignatura de la secundaria, que para hallar las raíces de una función cuadrática f(x) = ax² + bx + c, esto es, para encontrar para dicha función aquellos (o aquél) valores de x para los que dé cero, podemos servirnos de la fórmula siguiente:






Lo que tal vez resulte de utilidad, dado lo ya dicho, es el ver cómo se obtiene a priori, es decir, no sólo con el método a posteriori de ver que de hecho funciona¹.

Entonces, partimos de la siguiente ecuación de segundo grado:

ax² + bx + c = 0

Que equivale a

ax² + bx = −c

Si se multiplican lo miembros de la igualdad por 4a, se obtiene:

4a·(ax² + bx) = 4a·−c

es decir

(1)  4a²x² + 4abx = −4ac

Por otra parte, considerando la siguiente igualdad

(2)  (2ax + b)² = 4a²x² + 4axb + b²

puede verse que el primer miembro de (1) se parece en todo al segundo de ésta última, con la sola diferencia de que en ella se le suma b². Luego, si sumamos b² a sendos miembros de (1) tenemos

4a²x² + 4abx + b² = −4ac + b²

Considerando la equivalencia (2), reemplazamos el primer  miembro:

(2ax + b)² = −4ac + b²

que es equivalente a



Y si despejamos la x hallamos la fórmula buscada.

_______________________
1. Cf. Álgebra, Repetto, Linskens y Fesquet donde figura la derivación que aquí se cita.

domingo, 2 de septiembre de 2012

El cogito cartesiano y una duda.

La formulación del célebre cogito, de parte de Descartes, se encuentra en más de un lugar de sus escritos, por ejemplo en el Discurso del método, o en las Meditaciones metafísicas. El primero apareció antes que las segunda, acompañado de la Dióptrica, los Meteoros y la Geometría y, según Mauro Armiño, lo hicieron inicialmente en forma anónima.

Según relata Descartes, habiéndose propuesto someter a su propio juicio todos los conocimientos que le fueron enseñados, revisando cada una de las cuestiones que se le presentaban al estudio en virtud de una método compuesto de cuatro principios (la equivalencia entre verdad y evidencia, el análisis de las dificultades, el ordenamiento de los conocimientos de los sencillos a los compuestos, la enumeración completa) y habiendo optado por −mientras suspendía su juicio en cuanto a lo especulativo− seguir en lo práctico con ciertas máximas que no reflejaran las incertidumbres del espíritu; dedicaba de tanto en tanto algunas horas a vencer las dificultades que le ofrecía la matemática y de ahí fue que surgieron las obras que acompañaron la primera edición del Discurso.

Si bien eran éstas, las ciencias matemáticas, las que más de su agrado resultaban, su búsqueda apuntaba a algún principio primero para la filosofía. Veamos como lo formula:

Pero en seguida noté que si yo pensaba que todo era falso, yo, que pensaba, debía ser alguna cosa, debía tener alguna realidad; y viendo que esta verdad pienso, luego existo era tan firme y tan segura que nadie podía quebrantar su evidencia, la recibí sin escrúpulo alguno como el primer principio de la filosofía que buscaba” (Discurso del método, cuarta parte).

Algunos años más tarde, escribe:

¿Qué hay, pues, digno de ser considerado verdadero? Tal vez una sola cosa: que nada hay cierto en el mundo.”

¿No me he persuadido también de que yo mismo no existía? Sin duda yo era, puesto que me he persuadido o pensado algo. Pero hay un no sé qué muy poderoso y astuto que emplea toda su industria en engañarme siempre. No hay duda de que soy, si él me engaña; y me engañe todo lo que quiera, no podrá hacer que yo no sea en tanto piense ser alguna cosa. De suerte, que después de pensar mucho y examinar mucho todas las cosas, es preciso concluir que esta proposición: yo soy, yo existo, es necesariamente verdadera siempre que la pronuncio o concibo en mi espíritu” (Meditaciones metafísicas, meditación segunda).

Una lectura posible es considerar esto como una demostración. Ya sabemos que a Descartes le parece evidente, él mismo se persuadió de ello.

Una cuestión a determinar en ese caso es el valor que se le otorga a “pienso” ¿es un hecho primario, un punto de partida absoluto, o es secundario?

Veamos, una cosa es decir que cogito es un dato que tomamos como probado de alguna experiencia y que, partiendo de él, inferimos que la cogitatio implica el sum dado que, según otra premisa razonable, no hay cogitatio sin res cogitans, la cual en este caso no puede ser de alguien más que de mí. Dicho de otro modo, tomamos como probado que si hay pensamiento alguno debe haber aquel que piense, y que hay pensamiento; luego en virtud de un modus ponens podemos decir con certeza que hay alguien que piensa.

Pero no parece que sea eso exactamente lo que dice Descartes. Él cree probar también que hay el pensamiento cierto, no sólo que hay alguien que piensa, y como resultado de un proceso lógico. Al menos esta alternativa parece más acorde a la manera en que se expresa el problema en el discurso del método. Y también en Investigación de la verdad por al luz natural que, sin el auxilio de la religión ni de la filosofía, es capaz de determinar lo que el hombre debe pensar en todos los casos que puedan presentársele en la vida, y penetrar en los secretos de las ciencias más curiosas.

En ese diálogo, Eudoxio dice cosas como:

Cierto es que podéis dudar con razón de todas las cosas no os viene más que por medio de los sentidos; pero ¿podéis dudar de vuestra duda, estáis cierto de si dudáis o no?”

De esta duda universal, como de un punto fijo e inmóvil, quiero que derivéis el conocimiento de Dios, de vos mismo, y el de todas las cosas que existen en la naturaleza”.

Nos limitaremos por lo pronto a conocimiento “de vos mismo”. Es extraño el número de veces que en los escritos de filosofía moderna se encuentran usos de la palabra Dios, pero ello no nos va a ocupar aquí. Ni tampoco las cosas “que existen en la naturaleza”.

¿Qué es ese sí mismo? Obviamente, no es cualquier idea que cualquiera tenga de sí, ni el concepto aristotélico de hombre, ni la noción biológica, etc. Diremos que es simplemente la certeza. La res cogitans es la certeza. La certeza es la res cogians. Son lo mismo. No sabría decir si alguien ya ha propuesto esta interpretación, pues no lo he escuchado así formulado. Probablemente lo que dijo Lacan se asemeje, pero no es exactamente esto.

Así, el célebre “cogito cartesiano” es una fundamentación de la certeza. Perelman ha dicho que Descartes (y tras él toda la ciencia) fue quien de algún modo sepultó lo verosímil, desterrándolo de la especulación, para la que quiso el modelo deductivo.

Hagamos algunos comentarios sobre la “argumentación” que parece involucrar el cogito.

Descartes parece partir de una disyunción: hay certeza o se puede dudar de todo.

Esto es verosímil (si bien, dije, quita lugar a lo verosímil), pues si hay certeza se cumple la disyunción y si se puede dudar de todo también. Supongamos (para una reductio) que: ni hay certeza ni se puede dudar de todo. Como no se puede dudar de todo debe haber algo, p, respecto de lo que no se pueda dudar. Pero si no puede dudarse de p, si es indudable, entonces hay una certeza cabal respecto de p. Así, nuestro supuesto es absurdo, y por ende demostramos la disyunción.

Como lo que se tiene que probar es que hay certeza (es nuestra hipótesis-interpretación), supongamos que se puede dudar de todo. Luego, si se puede dudar de todo entonces dudo de todo. Esto es, o parece, una tautología. Quizá llame la atención cómo se inmiscuye el ego del antecedente al consecuente. No importa: la certeza es algo que le ocurre a un sujeto, y la duda también, de modo que pueden pasar por equivalentes el 'hay duda' (o certeza) o 'alguien duda' (o alguien tiene una certeza), e incluso identificarse con ese alguien es factible si asumimos que se trata de una 'experiencia' que puede hacer cualquiera.

Ahora bien ¿podemos dudar de esto? Es esta la pregunta que citamos arriba: ¿podéis dudar de vuestra duda? Descartes quiere probar que no se puede dudar de la duda. Supongamos que sí, que se puede. Luego, en lugar de no dudar, dudo (respecto de si dudo), puesto que, según nuestro supuesto es cierto que dudo de todo. Pero así llego a que sé que dudo, por lo tanto pretender dudar de que dudo es absurdo. Por ende: no dudo, sé, QED.

En resumen:

1. ni sé algo ni dudo de todo (sup)
2. dudo de algo (1)
3. sé algo (2)
4. ⊥ (1 y 3)
5. no es el caso que ni sé algo ni que dudo de todo (I¬ 1−4)
6. sé algo o dudo de todo (De Morgan, 5)
7. dudo de todo (sup)
8. dudo si dudo de todo (7)
9. ⊥ (7, 8)
10. no dudo de todo (I¬ 7−11)
11. sé algo (regla de separación)

He aquí cómo se puede identificar el saber y el sujeto (res cogitans). Seguramente suscite dudas (y por ello el título del post) el paso de 7 a 8. Probablemente el lector recordará la advertencia de Russell respecto de las totalidades cuya definición era un miembro suyo, y las restricciones de la teoría de los tipos, donde “dudo de todo” sólo se referiría a juicios de un tipo inferior y no podría hacerlo a sí. Entonces ¿sería demostrable el cogito en tales condiciones si lo interpretamos como una identificación del sujeto con el saber? ¿Será un campo propicio par el escepticismo?

sábado, 1 de septiembre de 2012

Una relectura del Discurso del método

René Descartes se encuentra, sin lugar a dudas, entre los más famosos de los filósofos de la modernidad europea. Probablemente sea tal vez uno de los más leídos de entre ellos. Cualquiera se encuentra cada vez que pasa por alguna librería de libros usados con el Discurso del método o las Meditaciones metafísicas. No solo eso, el otro día (hace un tiempo ya), mientras me dirigía a tomar el tren para volver a mi casa, veo una edición que los incluía a ambos y me dije que, dado que debía viajar unas cuantas estaciones y que hace tiempo que no releía esas páginas, sumado al hecho de que la edición que en mi casa se encuentra de las obras completas (que así se llama, pero no están todas) tiene ya sus años y no parece conveniente estar llevándola en el bolso, etc., en fin, compré uno. Pero a poco de haber comenzado me llamó la atención que dijera, en relación a las razones que pueden esgrimirse para estar o no seguro de algo:

Puede suceder, no obstante, que no me equivoque, y que sea solamente cobre y vidrio lo que tomo por oro y diamante”

Desde luego, lo primero que pensé es que me equivoqué, y que, por ejemplo, leí no en lugar de yo, pero no era así. La cosa en sí no tiene nada de llamativo, a no ser porque al llegar a casa y fijarme en una edición que tengo con el Discurso de método encuentro la misma expresión tal cual la cité. Finalmente, al leer la edición que había leído unos cuantos años atrás encuentro, de modo coherente con el contexto en el que figuraba:

Posible es que me equivoque y tome por oro y diamantes lo que sólo es cobre y vidrio”.

Y dado que entre las dos ediciones donde figuraba las expresión estrictamente contradictoria a ésta última transcurrió un lapso de 28 años, me pregunté si, más allá de la accesibilidad del texto, había sido leído de una manera proporcional a ella.

Probablemente nada de esto revista mayor interés. Sucede, además, que existiendo internet y siendo como es hoy por hoy, uno puede buscar el texto, lo que hubiera dado con el fragmento siguiente (que puede encontrarse acá y también puede oirse acá, aunque para ello hay que saber francés, claro):

Toutefois il se peut faire que je me trompe, et ce n’est peut-être qu’un peu de cuivre et de verre que je prends pour de l’or et des diamants.