Reescritura

En la lógica, el procedimiento para obtener la forma normal conjuntiva (FNC) de una fórmula se puede implementar como un sistema de reescritura.^[6] Las reglas para un ejemplo de tal sistema serían:

${\displaystyle \neg \neg A\to A}$ (eliminación de doble negación)

${\displaystyle \neg (A\land B)\to \neg A\lor \neg B}$ (Leyes de De Morgan)

${\displaystyle \neg (A\lor B)\to \neg A\land \neg B}$

${\displaystyle (A\land B)\lor C\to (A\lor C)\land (B\lor C)}$ (distributividad)

${\displaystyle A\lor (B\land C)\to (A\lor B)\land (A\lor C),}$^{[nota 1]}

donde el símbolo (${\displaystyle \to }$) indica que una expresión que coincida con el lado izquierdo de la regla se puede reescribir como una formada por el lado derecho, y donde cada símbolo denota una subexpresión. En tal sistema, cada regla se elige de para que el lado izquierdo sea equivalente al lado derecho y, en consecuencia, cuando el lado izquierdo coincida con una subexpresión, realizar una reescritura de esa subexpresión de la izquierda al derecho se mantiene la consistencia y el valor lógicos de toda la expresión.

Los sistemas de reescritura de términos se pueden utilizar para calcular operaciones aritméticas entre números naturales. Para hacer esto, cada uno de tales números debe codificarse como un término. La codificación más sencilla es la utilizada en los axiomas de Peano, basada en la constante 0 (cero) y la función sucesora S. Por ejemplo, los números 0, 1, 2 y 3 están representados por los términos 0, S(0), S(S(0)) y S(S(S(0))), respectivamente. El siguiente término sistema de reescritura se puede usar para calcular la suma y el producto de números naturales dados.^[7]

${\displaystyle {\begin{aligned}A+0&\to A&{\textrm {(1)}},\\A+S(B)&\to S(A+B)&{\textrm {(2)}},\\A\cdot 0&\to 0&{\textrm {(3)}},\\A\cdot S(B)&\to A+(A\cdot B)&{\textrm {(4)}}.\end{aligned}}}$

Por ejemplo, el cálculo que 2+2 resuelta en 4 se puede duplicar por reescritura de término de la siguiente manera:

${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(\;S(S(0))+S(0)\;)}$ ${\displaystyle \;\;{\stackrel {(2)}{\to }}\;\;}$ ${\displaystyle S(S(\;S(S(0))+0\;))}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

donde el número de la regla se da encima de la flecha de reescritura a (el símbolo ${\displaystyle \to }$).

Por otro ejemplo, el cálculo de 2⋅2 se hace así:

${\displaystyle S(S(0))\cdot S(S(0))}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))\cdot S(0)}$ ${\displaystyle \;\;{\stackrel {(4)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+S(S(0))\cdot 0}$ ${\displaystyle \;\;{\stackrel {(3)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))+0}$ ${\displaystyle \;\;{\stackrel {(1)}{\to }}\;\;}$ ${\displaystyle S(S(0))+S(S(0))}$ ${\displaystyle \;\;{\stackrel {\textrm {s.a.}}{\to }}\;\;}$ ${\displaystyle S(S(S(S(0)))),}$

donde el último paso utiliza el cálculo del ejemplo anterior.

En la lingüística, las reglas de estructura de frases, también llamadas reglas de reescritura, se utilizan en algunos sistemas de gramática generativa,^[8] como un medio para generar las oraciones gramaticalmente correctas de un idioma. Tal regla típicamente sigue la forma ${\displaystyle {\rm {A\rightarrow X}}}$, donde A es una etiqueta de categoría sintáctica, como un sintagma nominal o una oración, y X es una secuencia de tales etiquetas o morfemas, expresando el hecho que A puede ser reemplazada por X al generar la estructura constitutiva de una oración. Por ejemplo, la regla ${\displaystyle {\rm {O\rightarrow SN\ SV}}}$ significa que una oración (O) puede consistir en una sintagma nominal (SN) seguida de una sintagma verbal (SV); otras reglas especificarán en cuáles subconstituyentes puede consistir un sintagma nominal o verbal, y así sucesivamente.

1. ↑ Esta variante de la regla anterior es necesario ya que la ley conmutativa A∨B = B∨A no puede convertirse en una regla de reescritura. Una regla como A∨B → B∨A haría que el sistema de reescritura sea interminable.