Notación polaca

Notación polaca.

La notación polaca, también conocida como notación de prefijo o notación prefija, es una forma de notación para la lógica, la aritmética, y el álgebra. Su característica distintiva es que coloca los operadores a la izquierda de sus operandos. Si la aridad de los operadores es fija, el resultado es una sintaxis que carece de paréntesis u otros signos de agrupación, y todavía puede ser analizada sin ambigüedad. El lógico polaco Jan Łukasiewicz inventó esta notación alrededor de 1920 para simplificar la lógica proposicional.

Aquí hay una cita de Axiom and Generalizing Deduction de Nicod , página 180.

Vine sobre la idea de una notación libre de paréntesis en 1924. Utilicé esa notación por primera vez en mi artículo Lukasiewicz(1), P. 610, nota al pie de la página.

La referencia de arriba, citada por Jan Lukasiewicz es al parecer un informe litografiado en polaco.

Alonzo Church menciona esta notación en su libro clásico sobre lógica matemática como digna de observación en los sistemas notationales incluso contrastados con la Exposición notacional lógica y el trabajo Principia Mathematica de Whitehead y Russell.^[1]

Mientras que no se ha usado más en lógica, la notación polaca ha encontrado un espacio en las ciencias de la computación.

Aritmética

La expresión para sumar los números uno y dos, en la notación de prefijo, se escribe "+ 1 2" en vez de "1 + 2". En expresiones más complejas, los operadores todavía preceden sus operandos, pero los operandos pueden ser ellos mismos expresiones no triviales incluyendo sus propios operadores. Por ejemplo, la expresión que sería escrita en la notación de infijo convencional como

(5 - 6) * 7

puede ser escrito en prefijo como

* (- 5 6) 7

o simplemente

* - 5 6 7

Puesto que los simples operadores aritméticos son todos binarios (por lo menos, en contextos aritméticos), cualquier representación prefijo de ellos es inequívoca, y poner signos de agrupamiento a la expresión de prefijo es innecesario. En el ejemplo anterior, los paréntesis en la versión de infijo eran requeridos. Si los movemos:

5 - (6 * 7)

o simplemente los quitamos:

5 - 6 * 7

cambiaría el significado y el resultado de toda la expresión. Sin embargo, la versión correspondiente de prefijo de este segundo cálculo sería escrita como:

- 5 * 6 7

El proceso de la substracción es diferido hasta que ambos operandos de la substracción se hayan leído (es decir, 5 y el producto de 6 y 7). Como con cualquier notación, las expresiones más interiores son evaluadas primero, pero en la notación de prefijo este "interioridad" se puede transportar por el orden en vez del agrupamiento.

La notación de prefijo de la aritmética simple es en gran parte de interés académico. Como la similar notación de posfijo o notación polaca inversa, la notación de prefijo ha sido usada en algunas calculadoras comerciales (HP-11C).April 2009^{[cita requerida]} Sin embargo, la aritmética de notación de prefijo es usada con frecuencia como primer paso conceptual en la enseñanza de la construcción de un compilador.

Programación de computadora

La notación de prefijo ha visto una amplia aplicación con las S-expressions de Lisp, donde son requeridos los paréntesis debido a los operadores aritméticos que tienen aridad variable. El lenguaje de programación Ambi usa la notación polaca para operaciones aritméticas y la construcción del programa. La posfija notación polaca inversa es usada en muchos lenguajes de programación basados en pila como PostScript, y es el principio de operación de ciertas calculadoras, notablemente las de Hewlett-Packard.

Aunque sea obvio, es importante observar que el número de operandos en una expresión debe igualar al número de operadores más uno, de lo contrario la sentencia no tiene ningún sentido (asumiendo que solamente son usados operadores binarios en la expresión). Esto puede ser fácil de pasarlo por alto cuando se trata con expresiones más largas y más complicadas con varios operadores, así que se debe tener cuidado de comprobar con minuciosidad que una expresión tiene sentido al usar la notación de prefijo.

Orden de las operaciones

El orden de operaciones es definido dentro de la estructura de la notación de prefijo y puede ser fácilmente determinada. Una cosa a tener presente es que al ejecutar una operación, la operación es aplicada AL primer operando POR el segundo operando. Esto no es un problema con las operaciones que conmutan, pero para las operaciones no conmutativas como la división o la substracción, este hecho es crucial para análisis de una sentencia. Por ejemplo, la sentencia siguiente:

 / 10 5  = 2  (prefijo)

Se lee como "Divide 10 POR 5". Así la solución es 2, no ½ como sería el resultado de un análisis incorrecto de dividir 5 entre 10.

La notación de prefijo es especialmente popular entre las operaciones basadas en pila debido a su capacidad natural de distinguir fácilmente el orden de las operaciones sin la necesidad de paréntesis. Para evaluar el orden de las operaciones bajo la notación de prefijo, incluso no se necesita memorizar una jerarquía operacional, como con la notación de infijo. En lugar de eso, se mira directamente a la notación para descubrir qué operador evaluar primero. Leyendo una expresión de izquierda a derecha, primero se busca un operador y se procede a buscar dos operandos. Si se encuentra otro operador antes de que se encuentren los dos operandos, entonces el operador viejo es colocado a un lado hasta que este nuevo operador sea resuelto. Este proceso se itera hasta que un operador sea resuelto, lo cual debe suceder eventualmente, puesto que en una sentencia completa debe haber un operando más que la cantidad de operadores. Una vez que esté resuelto, el operador y los dos operandos son reemplazados por un nuevo operando. Puesto que un operador y dos operandos son eliminados y un operando es añadido, hay una pérdida neta de un operador y un operando, lo cual todavía deja una expresión con N operadores y N+1 operandos, permitiendo así que el proceso iterativo continúe. Ésta es la teoría general tras el uso de stacks en lenguajes de programación para evaluar una sentencia en la notación de prefijo, aunque hay varios algoritmos que manipulan el proceso. Una vez que es analizada una sentencia en la notación de prefijo, llega a ser menos intimidante mientras que permite una cierta separación desde la convención con una añadida conveniencia. Un ejemplo muestra la facilidad con la cual una sentencia compleja en la notación de prefijo se puede descifrar a través del orden de las operaciones:

La expresión en notación de infijo (15 / (7 - (1 + 1)) * 3) - (2 + (1 + 1)) se resuelve de la siguiente manera en notación polaca o de prefijo:

 - * / 15 - 7 + 1 1 3 + 2 + 1 1 =
 - * / 15 - 7    2  3 + 2 + 1 1 =
 - * / 15     5     3 + 2 + 1 1 =
 - *       3        3 + 2 + 1 1 =
 -             9      + 2 + 1 1 =
 -             9      + 2    2  =
 -             9          4     =
                     5

Notación polaca en lógica

La siguiente tabla muestra el núcleo de la notación para la lógica de sentencias de Jan Łukasiewicz. La notación convencional recién fue establecida entre las décadas de 1970 y 1980. Algunas de las letras usadas corresponden a ciertos vocablos polacos:

Concepto	Notación convencional	Notación polaca	Palabra polaca
Negación	φ	Nφ	negacja
Conjunción	φψ	Kφψ	koniunkcja
Disyunción	φψ	Aφψ	alternatywa
Condicional material	φψ	Cφψ
Bicondicional	φψ	Eφψ	ekwiwalencja
Barra de Sheffer	ϕ | ψ	Dφψ	dysjunkcja
Posibilidad	φ	Mφ	możliwość
Necesidad	φ	Lφ
Cuantificador universal	φ	Πφ
Cuantificador existencial	φ	Σφ

Autómata de pila

La notación polaca es la originada por un Autómata con pila, en la que los operadores siempre preceden a los operandos sobre los que actúan, y que tiene la ventaja de no necesitar paréntesis:

Estándar

      Ejemplo 1: 2 * ( 3 + 5 )
      Ejemplo 2: 2 * 3 + 5

Polaca

      Ejemplo 1: * 2 + 3 5
      Ejemplo 2: + * 2 3 5

Referencias

1. ↑ Church, Alonzo (1944). Introduction to Mathematical Logic. Princeton, New Jersey: Princeton University Press.  - p.38: "Worthy of remark is the parenthesis-free notation of Jan Lukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. ..."

• http://mathworld.wolfram.com/ReversePolishNotation.html

Lecturas relacionadas

• Łukasiewicz, Jan (1957). Aristotle’s Syllogistic from the Standpoint of Modern Formal Logic. Oxford University Press. 
• Łukasiewicz, Jan, "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls", Comptes rendus des séances de la Société des Sciences et des Lettres de Varsovie, 23:51-77 (1930). Translated by H. Weber as "Philosophical Remarks on Many-Valued Systems of Propositional Logics", in Storrs McCall, Polish Logic 1920-1939, Clarendon Press: Oxford (1967).

Véase también

• Notación de infijo
• Notación de postfijo, también llamada notación polaca inversa
• Lenguaje de programación LISP
  • Expresión S
• Notación húngara