La notación polaca ( PN ), también conocida como notación polaca normal ( NPN ), [1] notación Łukasiewicz , notación de Varsovia , notación de prefijo polaco 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 notación infija , en la que los operadores se colocan entre operandos, así como la notación polaca inversa (RPN), en la que los operadores siguensus 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] quien inventó la notación polaca en 1924. [3] [4]
El término notación polaca a veces se toma (como lo opuesto a la notación infija ) para incluir también la notación polaca inversa. [5]
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:
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 a pie de página.
La referencia citada por Łukasiewicz es aparentemente 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. [6] Heinrich Behmann , editor en 1924 del artículo de Moses Schönfinkel , [7] Ya tenía la idea de eliminar los paréntesis en las fórmulas lógicas.
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 la notación lógica de Alfred Whitehead y Bertrand Russell en Principia Mathematica . [8]
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 functores antes de los argumentos para evitar los corchetes y que había empleado su notación en sus artículos lógicos desde 1929. [9 ] Luego pasa a citar, como ejemplo, un artículo de 1930 que escribió con Alfred Tarski sobre el cálculo de sentencias . [10]
Aunque ya no se usa mucho en lógica, [11] 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 está escrita en notación polaca como + 1 2 (prefijo), en lugar de como 1 + 2 (fijo). En expresiones más complejas, los operadores todavía preceden a sus operandos, pero los mismos operandos pueden ser expresiones que incluyen operadores de nuevo 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 del prefijo son innecesarios. Como tal, la expresión anterior se puede simplificar aún más para
- × - 5 6 7
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 "más íntima" puede ser transmitida por 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, en referencia al ejemplo anterior, moverlos
- 5 - (6 × 7)
o eliminándolos
- 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 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 a 5, tiene el significado de 10 ÷ 5 (se lee como "dividir 10 entre 5"), o - 7 6 , con 7 a la izquierda a 6, tiene el significado de 7 - 6 ( leer como "restar de 7 el operando 6").
Algoritmo de evaluación
La notación de prefijo / sufijo es especialmente popular por su capacidad innata para expresar el orden previsto de las operaciones sin la necesidad de paréntesis y otras reglas de precedencia, como se suele emplear con la notación de infijo . 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 realizarse 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 contienen el número de operandos que se ajusta al operador superior más (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 / estos operandos. 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. Al comenzar por la derecha, la inserción de tokens se realiza de manera similar, solo la evaluación es activada por un operador, 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 ajusta al número de operandos en la pila, lo que nuevamente produce el resultado. Como puede verse en la descripción, un almacén desplegable sin capacidad de inspección de pila arbitraria es suficiente para implementar este análisis .
La manipulación de la pila bosquejada anteriormente funciona, con entrada reflejada, también para expresiones en notación polaca inversa .
Notación polaca para la lógica
La siguiente tabla muestra el núcleo de la notación de Jan Łukasiewicz para la lógica oracional . [12] Algunas letras en la tabla de notación polaca representan palabras particulares en polaco , como se muestra:
Concepto | Notación convencional | Notación polaca | Término polaco |
---|---|---|---|
Negación | negacja | ||
Conjunción | koniunkcja | ||
Disyunción | alternatywa | ||
Material condicional | implikacja | ||
Bicondicional | ekwiwalencja | ||
Falsum | fałsz | ||
Trazo de sheffer | dysjunkcja | ||
Posibilidad | możliwość | ||
Necesidad | konieczność | ||
Cuantificador universal | kwantyfikator ogólny | ||
Cuantificador existencial | kwantyfikator szczegółowy |
Tenga en cuenta que los cuantificadores variaron sobre los valores proposicionales en el trabajo de Łukasiewicz sobre lógicas de muchos valores.
Bocheński introdujo un sistema de notación polaca que nombra las 16 conectivas binarias 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. [13]
Implementaciones
La notación de prefijo ha tenido una amplia aplicación en las expresiones S de Lisp , donde los corchetes son necesarios ya que los operadores en el lenguaje son 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 usa la notación polaca a través de la biblioteca mathop. El lenguaje de programación Ambi [14] usa notación polaca para operaciones aritméticas y construcción de programas. La sintaxis del filtro LDAP utiliza la notación de prefijo polaco. [15]
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 usando la 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 , especialmente de Hewlett-Packard . [16] En un nivel inferior, algunas máquinas apiladoras , como los grandes sistemas de Burroughs, utilizan operadores de sufijo .
Ver también
- Notación polaca inversa
- Aplicación de función
- Cálculo lambda
- Zurra
- Lisp (lenguaje de programación)
- Expresión-S
- Escuela Polaca de Matemáticas
- Notación húngara
- Verbo-sujeto-objeto (VSO)
- Verbo-objeto-sujeto (VOS)
Referencias
- ^ Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik [ Algoritmos aritméticos en microcomputadoras ] (en alemán) (1 ed.). Berlín, Alemania: VEB Verlag Technik . ISBN 3341005153. EAN 9783341005156 . MPN 5539165. Licencia 201.370 / 4/89 . Consultado el 1 de diciembre de 2015 .
- ^ Łukasiewicz, Jan (1957). La silogística de Aristóteles desde el punto de vista de la lógica formal moderna . Prensa de la Universidad de Oxford . (Reimpreso por Garland Publishing en 1987. ISBN 0-8240-6924-2 )
- ^ Hamblin, Charles Leonard (1962). "Traducción ay desde la notación polaca" . Revista informática . 5 (3): 210–213. doi : 10.1093 / comjnl / 5.3.210 .
- ^ Ball, John A. (1978). Algoritmos para calculadoras RPN (1 ed.). Cambridge, Massachusetts, EE. UU .: Wiley-Interscience , John Wiley & Sons, Inc. ISBN 0-471-03070-8.
- ^ Principal, Michael (2006). Estructuras de datos y otros objetos que utilizan Java (3ª ed.). Pearson PLC Addison-Wesley . pag. 334. ISBN 978-0-321-37525-4.
- ^ Pogorzelski, Henry A., "Trabajo (s) revisado (s): Comentarios sobre el axioma de Nicod y sobre la" Deducción generalizada "de Jan Łukasiewicz; Jerzy Słupecki; Państwowe Wydawnictwo Naukowe" , The Journal of Symbolic Logic , vol. 30, núm. 3 (septiembre de 1965), págs. 376–377. El artículo original de Łukasiewicz se publicó en Varsovia en 1961 en un volumen editado por Jerzy Słupecki.
- ^ "Über die Bausteine der Mathischen Logik", Mathematische Annalen 92 , páginas 305-316. Traducido por Stefan Bauer-Mengelberg como "Sobre los componentes básicos de la lógica matemática" en Jean van Heijenoort , 1967. A Source Book in Mathematical Logic, 1879-1931 . Prensa de la Universidad de Harvard : 355-66.
- ^ Iglesia, Alonzo (1944). Introducción a la lógica matemática . Princeton, Nueva Jersey, Estados Unidos: Princeton University Press . pag. 38.
[…] 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. […]
- ^ Łukasiewicz, (1951) silogística de Aristóteles desde el punto de vista de la lógica formal moderna , Capítulo IV "Sistema de Aristóteles en forma simbólica" (sección de "explicación del simbolismo"), p. 78 en adelante.
- ^ Łukasiewicz, enero; Tarski, Alfred, "Untersuchungen über den Aussagenkalkül" ["Investigaciones sobre el cálculo de sentencias"], Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie , vol. 23 (1930) Cl. III, págs. 31–32.
- ^ Martínez Nava, Xóchitl (2011-06-01), "¿Por qué falto la lógica del biberón? Dislexia en la enseñanza de la lógica", en Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria ; Soler-Toscano, Fernando (eds.), Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, España, 1-4 de junio de 2011, Proceedings , Lecture Notes in Artificial Intelligence, 6680 , Springer Nature , pp. 162– 169, doi : 10.1007 / 978-3-642-21350-2_19 , ISBN 9783642213496,
[…] La notación polaca o de prefijo ha quedado en desuso dada la dificultad que implica su uso. […]
- ^ Craig, Edward (1998), Enciclopedia de Filosofía de Routledge, Volumen 8 , Taylor & Francis , p. 496, ISBN 9780415073103.
- ^ Bocheński, Józef Maria (1959). A Precis of Mathematical Logic, traducido por Otto Bird de las ediciones francesa y alemana, D. Reidel: Dordrecht, Holanda.
- ^ https://code.google.com/p/ambi/
- ^ http://www.ldapexplorer.com/en/manual/109010000-ldap-filter-syntax.htm
- ^ "Calculadoras HP | Modo RPN HP 35s " (PDF) . Hewlett-Packard .
Otras lecturas
- Łukasiewicz, Jan (1957). La silogística de Aristóteles desde el punto de vista de la lógica formal moderna . Prensa de la Universidad de Oxford .
- Łukasiewicz, Jan (1930). "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls" [Observaciones filosóficas sobre sistemas de múltiples valores de lógica proposicional]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (en alemán). 23 : 51–77.Traducido por H. Weber en Storrs McCall, Polish Logic 1920-1939 , Clarendon Press : Oxford (1967).
enlaces externos
- Medios relacionados con la notación polaca (matemáticas) en Wikimedia Commons