Notación polaca

Notación polaca (PN), también conocida como notación polaca normal (NPN), La notación Łukasiewicz, la notación de Varsovia, la notación de prefijos en polaco o simplemente la notación de prefijos, es una notación matemática en la que los operadores preceden sus operandos, en contraste con la notación infija más común, en la que los operadores se colocan entre operandos, así como la notación polaca inversa (RPN), en la que los operadores siguen sus operandos. No necesita paréntesis siempre que cada operador tenga un número fijo de operandos. La descripción "Polaco" se refiere a la nacionalidad del lógico Jan Łukasiewicz, quien inventó la notación polaca en 1924.

El término notación polaca se toma a veces (como lo contrario de notación infija) para incluir también la notación polaca inversa.

Cuando los intérpretes de lenguajes de programación utilizan la notación polaca como sintaxis para expresiones matemáticas, se analiza fácilmente en árboles de sintaxis abstracta y, de hecho, puede definir una representación uno a uno para la misma. Debido a esto, Lisp (ver más abajo) y los lenguajes de programación relacionados definen su sintaxis completa en notación de prefijo (y otros usan notación de sufijo).

Historia

Una cita de un artículo de Jan Łukasiewicz, Remarks on Nicod's Axiom and on "Generalizing Deduction", página 180, establece cómo se inventó la notación:

Vine sobre la idea de una notación sin paréntesis en 1924. Usé esa notación por primera vez en mi artículo Łukasiewicz(1), p. 610, nota de pie de página.

La referencia citada por Łukasiewicz aparentemente es un informe litografiado en polaco. El artículo de referencia de Łukasiewicz Remarks on Nicod's Axiom and on "Generalizing Deduction" fue revisado por Henry A. Pogorzelski en el Journal of Symbolic Logic en 1965. Heinrich Behmann, editor en 1924 del artículo de Moses Schönfinkel, ya tenía la idea de eliminar los paréntesis en las fórmulas lógicas. En uno de sus artículos, Łukasiewicz afirmó que su notación es la más compacta y la primera notación sin paréntesis escrita linealmente, pero no la primera, ya que Gottlob Frege propuso su notación Begriffsschrift sin paréntesis en 1879.

Alonzo Church menciona esta notación en su libro clásico sobre lógica matemática como digna de mención en los sistemas de notación, incluso en contraste con la exposición y el trabajo de notación lógica de Alfred Whitehead y Bertrand Russell en Principia Mathematica.

En el libro de Łukasiewicz de 1951, La silogística de Aristóteles desde el punto de vista de la lógica formal moderna, menciona que el principio de su notación era escribir los funtores antes que los argumentos para evitar corchetes y que había empleado su notación en sus artículos lógicos desde 1929. Luego pasa a citar, como ejemplo, un artículo de 1930 que escribió con Alfred Tarski sobre el cálculo de oraciones.

Aunque ya no se usa mucho en lógica, la notación polaca ha encontrado un lugar en la informática.

Explicación

La expresión para sumar los números 1 y 2 se escribe en notación polaca como + 1 2 (prefijo), en lugar de 1 + 2 (infijo). En expresiones más complejas, los operadores aún preceden a sus operandos, pero los operandos mismos pueden ser expresiones que incluyen de nuevo operadores y sus operandos. Por ejemplo, la expresión que se escribiría en notación infija convencional como

se puede escribir en notación polaca como

Asumiendo una aridad dada de todos los operadores involucrados (aquí "−" denota la operación binaria de resta, no la función unaria de cambio de signo), cualquier representación de prefijo bien formada es inequívoca, y los corchetes dentro de la expresión del prefijo son innecesarios. Como tal, la expresión anterior se puede simplificar aún más a

El procesamiento del producto se aplaza hasta que sus dos operandos estén disponibles (es decir, 5 menos 6 y 7). Al igual que con cualquier notación, las expresiones más internas se evalúan primero, pero en la notación polaca esta "innermost-ness" puede transmitirse mediante la secuencia de operadores y operandos en lugar de entre paréntesis.

En la notación de infijo convencional, se requieren paréntesis para anular las reglas de precedencia estándar, ya que, en referencia al ejemplo anterior, moverlos

o eliminarlos

cambia el significado y el resultado de la expresión. Esta versión está escrita en notación polaca como

Cuando se trata de operaciones no conmutativas, como la división o la resta, es necesario coordinar la disposición secuencial de los operandos con la definición de cómo el operador toma sus argumentos, es decir, de izquierda a derecha. Por ejemplo, ÷ 10 5, con 10 a la izquierda de 5, tiene el significado de 10 ÷ 5 (léase "divide 10 entre 5"), o − 7 6, quedando 7 en 6, tiene el significado de 7 − 6 (léase como "restar de 7 el operando 6").

Algoritmo de evaluación

La notación de prefijo/postfijo es especialmente popular por su capacidad innata para expresar el orden deseado de las operaciones sin la necesidad de paréntesis y otras reglas de precedencia, como se suele emplear con la notación infija. En cambio, la notación indica de forma única qué operador evaluar primero. Se supone que los operadores tienen una aridad fija cada uno, y se supone que todos los operandos necesarios se dan explícitamente. Una expresión de prefijo válida siempre comienza con un operador y termina con un operando. La evaluación puede proceder de izquierda a derecha o en la dirección opuesta. Comenzando por la izquierda, la cadena de entrada, que consta de tokens que denotan operadores u operandos, se inserta token por token en una pila, hasta que las entradas superiores de la pila contengan el número de operandos que se ajusta al operador superior (inmediatamente debajo). Este grupo de tokens en la parte superior de la pila (el último operador apilado y el número correspondiente de operandos) se reemplaza por el resultado de ejecutar el operador en estos/este(s) operando(s). Luego, el procesamiento de la entrada continúa de esta manera. El operando más a la derecha en una expresión de prefijo válida vacía la pila, excepto por el resultado de evaluar la expresión completa. Cuando se comienza por la derecha, el empuje de tokens se realiza de manera similar, solo un operador activa la evaluación, encontrando el número apropiado de operandos que se ajusta a su aridad ya en la parte superior de la pila. Ahora, el token más a la izquierda de una expresión de prefijo válida debe ser un operador, que se ajuste al número de operandos en la pila, lo que nuevamente produce el resultado. Como se puede ver en la descripción, un almacenamiento push-down sin capacidad de inspección de pila arbitraria es suficiente para implementar este análisis.

La manipulación de la pila esbozada arriba funciona, con entrada duplicada, también para expresiones en notación polaca inversa.

Notación polaca para lógica

La siguiente tabla muestra el núcleo de la notación de Jan Łukasiewicz para la lógica de oraciones. Algunas letras en la tabla de notación polaca representan palabras particulares en polaco, como se muestra:

Concepto	Convención notación	Polaco notación	Polaco mandato
Negación	¬ ¬ φ φ {displaystyle neg varphi }	Nφ φ {displaystyle mathrm {N} varphi }	negacja
Conjunción	φ φ ∧ ∧ ↑ ↑ {displaystyle varphi land psi }	Kφ φ ↑ ↑ {displaystyle mathrm {K} varphi psi }	koniunkcja
Disjunción	φ φ Alternativa Alternativa ↑ ↑ {displaystyle varphi lor psi }	Aφ φ ↑ ↑ {displaystyle mathrm {A} varphi psi }	alternanciawa
Disyunción exclusiva	φ φ ≢↑ ↑ {displaystyle varphi not equiv psi }	Jφ φ ↑ ↑ {displaystyle mathrm {J} varphi psi }	alternanciawa rozłączna
Material condicional	φ φ → → ↑ ↑ {displaystyle varphi to psi }	Cφ φ ↑ ↑ {displaystyle mathrm {C} varphi psi }	implikacja
Bicondicional	φ φ Administración Administración ↑ ↑ {displaystyle varphi leftrightarrow psi }	Eφ φ ↑ ↑ {displaystyle mathrm {E} varphi psi }	ekwiwalencja
Falsum	⊥ ⊥ {displaystyle bot }	O{displaystyle mathrm {O}	fałsz
Apoplejía.	φ φ ▪ ▪ ↑ ↑ {displaystyle varphi mid psi }	Dφ φ ↑ ↑ {displaystyle mathrm {D} varphi psi }	dysjunkcja
Posibilidad	Cause Cause φ φ {displaystyle Diamond varphi }	Mφ φ {displaystyle mathrm {M} varphi }	możliwość
Necesidad	▪ ▪ φ φ {displaystyle Box varphi }	Lφ φ {displaystyle mathrm {L} varphi }	konieczność
Cuantificador universal	О О pφ φ {displaystyle forall p,varphi }	▪ ▪ pφ φ {displaystyle Pi p,varphi }	kwantyfikator ogólny
Cuantificador existencial	∃ ∃ pφ φ {displaystyle exists p,varphi }	.. pφ φ {displaystyle Sigma p,varphi }	kwantyfikator szczegółowy

Tenga en cuenta que los cuantificadores oscilaron entre los valores proposicionales en el trabajo de Łukasiewicz sobre la lógica multivaluada.

Bocheński introdujo un sistema de notación polaca que nombra los 16 conectores binarios de la lógica proposicional clásica. Para la lógica proposicional clásica, es una extensión compatible de la notación de Łukasiewicz. Pero las notaciones son incompatibles en el sentido de que Bocheński usa L y M (para no implicación y no implicación inversa) en lógica proposicional y Łukasiewicz usa L y M en lógica modal.

Implementaciones

La notación de prefijos ha visto una amplia aplicación en las expresiones S de Lisp, donde los corchetes son obligatorios ya que los operadores en el lenguaje son en sí mismos datos (funciones de primera clase). Las funciones Lisp también pueden ser variádicas. El lenguaje de programación Tcl, al igual que Lisp, también usa la notación polaca a través de la biblioteca mathop. El lenguaje de programación Ambi utiliza la notación polaca para operaciones aritméticas y construcción de programas. La sintaxis del filtro LDAP utiliza la notación de prefijo polaco.

La notación Postfix se usa en muchos lenguajes de programación orientados a la pila, como PostScript y Forth. La sintaxis de CoffeeScript también permite que las funciones se llamen usando la notación de prefijo, al mismo tiempo que admite la sintaxis de posfijo unaria común en otros idiomas.

El número de valores de retorno de una expresión es igual a la diferencia entre el número de operandos en una expresión y la aridad total de los operadores menos el número total de valores de retorno de los operadores.

La notación polaca, generalmente en forma de postfijo, es la notación elegida por ciertas calculadoras, especialmente de Hewlett-Packard. En un nivel más bajo, algunas máquinas de apilado, como los sistemas grandes de Burroughs, utilizan operadores de posfijo.