La notación polaca ( PN ), también conocida como notación polaca normal ( NPN ), [1] notación de Łukasiewicz , notación de Varsovia , notación de prefijo polaca o simplemente notación de prefijo , es una notación matemática en la que los operadores preceden a sus operandos , a diferencia de la más común. Notación infija , en la que los operadores se colocan entre operandos, así como notación polaca inversa (RPN), en la que los operadores siguen a 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 , [2] : 24 [3] : 78 [4] quien inventó la notación polaca en 1924. [5] : 367, nota al pie 3 [6] : 180, nota al pie 3
El término notación polaca a veces se utiliza (como lo opuesto a notación infija ) para incluir también la notación polaca inversa. [7]
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 los mismos. Debido a esto, Lisp (ver más abajo) y los lenguajes de programación relacionados definen toda su sintaxis en notación de prefijo (y otros usan notación de postfijo).
Una cita de un artículo de Jan Łukasiewicz en 1931 [5] : 367, nota al pie 3 [6] : 180, nota al pie 3 indica cómo se inventó la notación:
Se me ocurrió 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 al pie.
La referencia citada por Łukasiewicz, es decir, Łukasiewicz (1), [8] es aparentemente un informe litografiado en polaco . El artículo de referencia [5] de Łukasiewicz fue revisado por Henry A. Pogorzelski en el Journal of Symbolic Logic en 1965. [9] Heinrich Behmann , editor en 1924 del artículo de Moses Schönfinkel , [10] ya tenía la idea de eliminar los paréntesis en 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 ya en 1879. [11]
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 . [12]
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 functores antes de los argumentos para evitar corchetes y que había empleado su notación en sus artículos de lógica desde 1929. [3 ] : 78 Luego cita, como ejemplo, un artículo de 1930 que escribió con Alfred Tarski sobre el cálculo oracional . [13]
Si bien ya no se usa mucho en lógica, [14] la notación polaca ha encontrado desde entonces un lugar en la informática .
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 propios operandos pueden ser expresiones que incluyan nuevamente 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
Suponiendo una aridad dada de todos los operadores involucrados (aquí el "-" 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 difiere hasta que sus dos operandos estén disponibles (es decir, 5 menos 6 y 7). Como ocurre con cualquier notación, las expresiones más internas se evalúan primero, pero en la notación polaca esta "intimidad" puede transmitirse mediante la secuencia de operadores y operandos en lugar de entre corchetes.
En la notación infija convencional, se requieren paréntesis para anular las reglas de precedencia estándar , ya que, haciendo referencia al ejemplo anterior, moverlos
o quitándolos
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 división o 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 (leído como "dividir 10 entre 5"), o − 7 6 , con 7 a la izquierda de 6, tiene el significado de 7 − 6 (leído como "resta de 7 el operando 6").
La notación de prefijo/posfijo es especialmente popular por su capacidad innata de expresar el orden previsto de las operaciones sin la necesidad de paréntesis y otras reglas de precedencia, como se suelen emplear con la notación infija . En cambio, la notación indica de forma única qué operador evaluar primero. Se supone que cada operador tiene una aridad fija y 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 realizarse de izquierda a derecha o en dirección opuesta. Comenzando por la izquierda, la cadena de entrada, que consta de tokens que indican operadores u operandos, se inserta token por token en una pila , hasta que las entradas superiores de la pila contienen la cantidad de operandos que se ajustan 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 operandos. Luego el procesamiento de la entrada continúa de esta manera. El operando situado más a la derecha en una expresión de prefijo válida vacía la pila, excepto el resultado de evaluar toda la expresión. Cuando se comienza por la derecha, el envío de tokens se realiza de manera similar, solo que un operador activa la evaluación y encuentra el número apropiado de operandos que se ajustan 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 ajusta al número de operandos en la pila, lo que nuevamente produce el resultado. Como se puede ver en la descripción, un almacén push-down sin capacidad de inspección arbitraria de la pila es suficiente para implementar este análisis .
La manipulación de pila esbozada arriba funciona (con entrada reflejada) también para expresiones en notación polaca inversa .
La siguiente tabla muestra el núcleo de la notación de Jan Łukasiewicz en la lógica moderna. Algunas letras en la tabla de notación polaca representan palabras particulares en polaco , como se muestra:
Tenga en cuenta que los cuantificadores abarcaron valores proposicionales en el trabajo de Łukasiewicz sobre lógica de muchos valores.
Bocheński introdujo un sistema de notación polaca que nombra los 16 conectivos binarios de la lógica proposicional clásica . [18] : 16 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 en que Bocheński usa y (para no implicación y no implicación inversa) en lógica proposicional y Łukasiewicz usa y en lógica modal.
La notación de prefijo ha tenido una amplia aplicación en las expresiones S de Lisp , donde se requieren paréntesis ya que los operadores en el lenguaje son en sí mismos datos ( funciones de primera clase ). Las funciones Lisp también pueden ser variadas . El lenguaje de programación Tcl , al igual que Lisp, también utiliza notación polaca a través de la biblioteca mathop. El lenguaje de programación Ambi [19] utiliza notación polaca para operaciones aritméticas y construcción de programas. La sintaxis del filtro LDAP utiliza notación de prefijo polaca. [20]
La notación Postfix se utiliza en muchos lenguajes de programación orientados a pilas como PostScript y Forth . La sintaxis de CoffeeScript también permite llamar a funciones utilizando notación de prefijo, al mismo tiempo que admite la sintaxis de sufijo unario común en otros lenguajes.
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 sufijo, es la notación elegida por ciertas calculadoras , en particular de Hewlett-Packard . [21] En un nivel inferior, algunas máquinas apilables, como los grandes sistemas de Burroughs , utilizan operadores postfix .
Die ältesten Texte in den 'Selected Works', in denen Łukasiewicz polnische Notation verwendet, datieren relativ spät, sind aber Präsentationen vorangehender Arbeiten, die 'in the course of the years 1920-1930' (S. 131) stattgefunden haben, también Auch keine genauere Zeitangabe geben.
{{cite book}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )[…] Es digna de mención la notación sin paréntesis de Jan Łukasiewicz. En esto, las letras N, A, C, E, K se utilizan en los roles de negación, disyunción, implicación, equivalencia y conjunción respectivamente. […]
[…] La notación polaca o de prefijo ha caído en desuso dada la dificultad que implica su uso. […]
Medios relacionados con la notación polaca (matemáticas) en Wikimedia Commons