stringtranslate.com

Notación polaca

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 , en contraste con la notación infija más común , en la que los operadores se colocan entre los operandos, así como la notación polaca inversa (RPN), en la que los operadores siguen a sus operandos. No necesita ningún paréntesis siempre que cada operador tenga un número fijo de operandos . La descripción "polaca" se refiere a la nacionalidad del lógico Jan Łukasiewicz , [2] : 24  [3] : 78  [4] que 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 toma (como el opuesto de 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 puede analizar fácilmente en árboles sintácticos abstractos y, de hecho, se puede definir una representación uno a uno de los mismos. Por este motivo, Lisp (ver más abajo) y otros lenguajes de programación relacionados definen toda su sintaxis en notación de prefijo (y otros utilizan notación de posfijo).

Historia

Una cita de un artículo de Jan Łukasiewicz de 1931 [5] : 367, Nota al pie 3  [6] : 180, Nota al pie 3  indica cómo se inventó la notación:

La idea de una notación sin paréntesis se me ocurrió en 1924. Utilicé esa notación por primera vez en mi artículo Łukasiewicz (1), p. 610, nota a pie de página.

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 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 libre de paréntesis escrita linealmente, pero no la primera, ya que Gottlob Frege propuso su notación Begriffsschrift libre de 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 de notación lógica de Alfred Whitehead y Bertrand Russell y su trabajo en Principia Mathematica . [12]

En el libro de 1951 de Łukasiewicz, 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 de los argumentos para evitar paréntesis y que había empleado su notación en sus artículos de lógica desde 1929. [3] : 78  Luego continúa citando, como ejemplo, un artículo de 1930 que escribió con Alfred Tarski sobre el cálculo oracional . [13]

Aunque ya no se utiliza mucho en lógica, [14] la notación polaca ha encontrado desde entonces 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 como 1 + 2 (infijo). En expresiones más complejas, los operadores aún preceden a sus operandos, pero los 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

(5 − 6) × 7

se puede escribir en notación polaca como

× (− 5 6) 7

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 de prefijo son innecesarios. Por lo tanto, la expresión anterior se puede simplificar aún más a

× − 5 6 7

El procesamiento del producto se pospone hasta que estén disponibles sus dos operandos (es decir, 5 menos 6 y 7). Como en cualquier notación, las expresiones más internas se evalúan primero, pero en la notación polaca esta "extremidad interna" se puede transmitir mediante la secuencia de operadores y operandos en lugar de mediante 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

5 − (6 × 7)

o eliminarlos

5 − 6 × 7

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

− 5 × 6 7.

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 (que se lee como "dividir 10 por 5"), o − 7 6 , con 7 a la izquierda de 6, tiene el significado de 7 − 6 (que se lee como "restar de 7 el operando 6").

Algoritmo de evaluación

La notación de prefijo/postfijo es especialmente popular por su capacidad innata de expresar el orden de operaciones deseado sin la necesidad de paréntesis y otras reglas de precedencia, como se emplean habitualmente con la notación de infijo . En cambio, la notación indica de forma única qué operador evaluar primero. Se supone que cada operador tiene una aridad fija y se supone que todos los operandos necesarios se dan explícitamente. Una expresión de prefijo válida siempre empieza con un operador y termina con un operando. La evaluación puede proceder de izquierda a derecha o en la dirección opuesta. Empezando por la izquierda, la cadena de entrada, que consta de tokens que denotan operadores u operandos, se introduce token por token en una pila , hasta que las entradas superiores de la pila contienen el número de operandos que cabe en el 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 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 el resultado de evaluar toda la expresión. Cuando se comienza por la derecha, el empuje de tokens se realiza de manera similar, solo que la evaluación se activa mediante un operador, que 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 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 de empuje hacia abajo sin capacidad de inspección de pila arbitraria es suficiente para implementar este análisis .

La manipulación de pila esbozada anteriormente funciona (con entrada reflejada) 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 en la lógica moderna. Algunas letras de la tabla de notación polaca representan palabras específicas en polaco , como se muestra:

Obsérvese que los cuantificadores abarcaron valores proposicionales en el trabajo de Łukasiewicz sobre lógicas multivaluadas.

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 de 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.

Implementaciones

La notación de prefijo ha sido ampliamente utilizada en las expresiones S de Lisp , donde los paréntesis son necesarios ya que los operadores en el lenguaje son en sí mismos datos ( funciones de primera clase ). Las funciones de Lisp también pueden ser variádicas . El lenguaje de programación Tcl , al igual que Lisp, también utiliza la notación polaca a través de la biblioteca mathop. El lenguaje de programación Ambi [19] utiliza la notación polaca para operaciones aritméticas y construcción de programas. La sintaxis de filtro LDAP utiliza la notación de prefijo polaca. [20]

La notación sufija se utiliza en muchos lenguajes de programación orientados a la pila, como PostScript y Forth . La sintaxis de CoffeeScript también permite llamar a funciones mediante notación de prefijo, a la vez que sigue siendo compatible con la sintaxis sufija unaria 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, normalmente en forma sufija, es la notación elegida por ciertas calculadoras , en particular las de Hewlett-Packard . [21] En un nivel inferior, los operadores sufijos son utilizados por algunas máquinas de pila como los grandes sistemas de Burroughs .

Véase también

Referencias

  1. ^ Jorke, Günter; Lampe, Bernhard; Wengel, Norberto (1989). Arithmetische Algorithmen der Mikrorechentechnik [ Algoritmos aritméticos en microcomputadoras ] (en alemán) (1 ed.). Berlín, Alemania: VEB Verlag Technik . ISBN 3-34100515-3. EAN  978-3-34100515-6. MPN 5539165. Licencia 201.370/4/89 . Consultado el 1 de diciembre de 2015 .
  2. ^ abcdefghi Łukasiewicz, enero (1929). Elementy logiki matematycznej (en polaco) (1 ed.). Varsovia, Polonia: Państwowe Wydawnictwo Naukowe; Łukasiewicz, enero (1963). Elementos de Lógica Matemática . Traducido por Wojtasiewicz, Olgierd Adrian [en polaco] . Nueva York, Estados Unidos: The MacMillan Company .
  3. ^ abcde Łukasiewicz, Jan (1957) [1951]. La silogística de Aristóteles desde el punto de vista de la lógica formal moderna (2.ª ed.). Oxford University Press .(Reimpreso por Garland Publishing en 1987, ISBN 0-8240-6924-2 .) 
  4. ^ Kennedy, John (agosto de 1982). "RPN Perspective". PPC Calculator Journal . 9 (5). Departamento de Matemáticas, Santa Monica College, Santa Monica, California, EE. UU.: 26–29. CiteSeerX 10.1.1.90.6448 . Archivado desde el original el 2022-07-01 . Consultado el 2022-07-02 . (12 páginas)
  5. ^ abc Łukasiewicz, enero (1931). "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej'" [Comentarios sobre el axioma de Nicod y sobre la 'generalización de la deducción']. Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie, 12. II. 1904-1912. II. 1929 (en polaco). Lwów: Wydawnictwo Polskie Towarzystwo Filozoficzne. págs. 366–383.
  6. ^ ab Łukasiewicz, Jan (1970). "Comentarios sobre el axioma de Nicod y sobre la 'deducción generalizadora'"". En Borkowski, L. (ed.). Obras seleccionadas . Ámsterdam y Londres/Varsovia: North-Holland Publishing Company/Polish Scientific Publishers. págs. 179–196.
  7. ^ Main, Michael (2006). Estructuras de datos y otros objetos utilizando Java (3.ª ed.). Pearson PLC Addison-Wesley . p. 334. ISBN  978-0-321-37525-4.
  8. ^ Łukasiewicz, enero (1929). "O znaczeniu i potrzebach logiki matematycznej". Nauka Polska (en polaco). 10 : 604–620.
  9. ^ Pogorzelski, Henry Andrew (septiembre de 1965). "Trabajo(s) revisado(s): comentarios sobre el axioma de Nicod y sobre la" generalización de la deducción "por Jan Łukasiewicz, Jerzy Słupecki, Państwowe Wydawnictwo Naukowe". La revista de lógica simbólica (revisión). 30 (3). Asociación de Lógica Simbólica : 376–377. JSTOR  2269644.(NB. El artículo original de 1931 "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej" de Jan Łukasiewicz fue reeditado en Państwowe Wydawnictwo Naukowe (National Scientific Publishers), Varsovia , Polonia en 1961 en un volumen editado por Jerzy Słupecki .)
  10. ^ Schönfinkel, Moisés (1924). "Über die Bausteine ​​der mathematischen Logik" [Sobre los componentes básicos de la lógica matemática]. Mathematische Annalen (en alemán). 92 (3–4): 305–316. doi :10.1007/BF01448013. S2CID  118507515; van Heijenoort, Jean , ed. (1967). "Sobre los elementos básicos de la lógica matemática". Un libro de consulta sobre lógica matemática, 1879–1931 . Traducido por Bauer-Mengelberg, Stefan [en holandés] . Harvard University Press . págs. 355–366.
  11. ^ Gottschall, cristiano (2005). Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (tesis de diploma) (en alemán). Viena, Austria. pag. 88: 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 de CS1: falta la ubicación del editor ( enlace )
  12. ^ Church, Alonzo (1944). Introducción a la lógica matemática . Princeton, Nueva Jersey, EE. UU.: Princeton University Press . pág. 38. […] Es digna de mención la notación sin paréntesis de Jan Łukasiewicz. En ella, las letras N, A, C, E, K se utilizan en los roles de negación, disyunción, implicación, equivalencia y conjunción respectivamente. […]
  13. ^ Łukasiewicz, enero ; Tarski, Alfred (1930). "Untersuchungen über den Aussagenkalküls" [Investigaciones sobre el cálculo oracional]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (en alemán). 23 (Cl.III): 30–50.
  14. ^ Martínez Nava, Xóchitl (2011-06-01), "¿Por qué me falla la lógica? La dislexia en la enseñanza de la lógica", en Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria ; Soler-Toscano, Fernando (eds.), Herramientas para la enseñanza de la lógica: Tercer Congreso Internacional, TICTTL 2011, Salamanca, España, 1–4 de junio de 2011, Actas, Lecture Notes in Artificial Intelligence, vol. 6680, Springer Nature , pp. 162–169, doi :10.1007/978-3-642-21350-2_19, ISBN 978-3-64221349-6, […] La notación polaca o prefijal ha caído en desuso dada la dificultad que implica su utilización. […]
  15. ^ ab Łukasiewicz, enero (1939). "Der Äquivalenzenkalkül". Collectanea Logica (en alemán). 1 : 145–169.
  16. ^ Łukasiewicz, enero (1930). "Untersuchungen über den Aussagenkalküls" [Investigaciones sobre el cálculo oracional]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (en alemán). 23 (cl.III): 51–77.
  17. ^ ab Łukasiewicz, Jan (1953). "Un sistema de lógica modal". Revista de sistemas informáticos . 3 (1): 111–149.
  18. ^ Bocheński, Józef María (1949). Escrito en Friburgo. Précis de lógica matemática (PDF) . Colección Síntesis (en francés). vol. 2. Bussum, Pays-Bas, Países Bajos: FG Kroonder. Archivado (PDF) desde el original el 3 de agosto de 2023 . Consultado el 12 de noviembre de 2023 .Traducido como Bocheński, Józef Maria (1959). Un resumen de lógica matemática . Traducido por Bird, Otto A. [en Wikidata] . Dordrecht, Países Bajos: D. Reidel Publishing Company.
  19. ^ "Archivo de código de Google: almacenamiento a largo plazo para el alojamiento de proyectos de código de Google". Archivado desde el original el 28 de septiembre de 2017. Consultado el 14 de noviembre de 2022 .
  20. ^ "Sintaxis del filtro LDAP". Archivado desde el original el 14 de octubre de 2022. Consultado el 14 de noviembre de 2022 .
  21. ^ "Calculadoras HP - Modo RPN de la HP 35s" (PDF) . Hewlett-Packard . Archivado (PDF) del original el 21 de enero de 2022 . Consultado el 14 de noviembre de 2022 .

Lectura adicional

Enlaces externos