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.