Entrada polaca
La notación polaca ( registro ), también conocida como notación de prefijo (registro), es una forma de escribir expresiones lógicas , aritméticas y algebraicas . Un rasgo característico de tal notación es que el operador está ubicado a la izquierda de los operandos . Si el operador tiene una aridad fija , dicha notación no tendrá paréntesis y podrá interpretarse sin ambigüedad. El lógico polaco Jan Lukasiewicz inventó esta notación alrededor de 1920 para simplificar la lógica proposicional .
Alonzo Church mencionó esta notación en su libro clásico sobre lógica matemática como un sistema notable de notación, e incluso contrastó las exposiciones de notaciones lógicas de Alfred Whitehead y Bertrand Russell en Principia Mathematica . [una]
Aunque la notación polaca no se usa en matemáticas, se usa mucho en informática .
Aritmética
En notación de prefijos , la suma de los números 1 y 2 se escribirá "+ 1 2" en lugar de escribir "1 + 2". En expresiones más complejas, los operadores preceden a los operandos, pero los operandos mismos pueden ser expresiones no triviales que contengan sus propios operadores. Por ejemplo, una expresión que está escrita en notación infija tradicional
(5 − 6) * 7en prefijo se puede escribir como
*(− 5 6) 7o simplemente
* − 5 6 7Dado que cualquier operación aritmética simple es binaria, su representación de prefijo no se puede interpretar de dos maneras, por lo que no es necesario usar paréntesis. En el ejemplo anterior, se necesitaban paréntesis en la notación infija tradicional, y ahora los moveremos
5 − (6 * 7)o simplemente eliminar
5 − 6 * 7esto cambiará el significado y el resultado de la evaluación de toda la expresión. La notación de prefijo correspondiente para tal expresión se vería así:
− 5 * 6 7El cálculo de la resta se retrasa hasta que se hayan leído ambos operandos (5 y el resultado de multiplicar 6 y 7). Como con cualquier otra notación, las expresiones más profundas se evalúan primero, pero en la notación polaca, la profundidad de una expresión está determinada por el orden, no por los paréntesis.
La notación de prefijos en aritmética simple es de gran interés académico. Al igual que la notación de postfijo, la notación de prefijo se ha utilizado para algunas computadoras comerciales (HP-11C). Aprender sobre la notación de prefijos suele ser el primer paso en el diseño del compilador.
Programación
La notación de prefijo se usa ampliamente en expresiones s en el lenguaje de programación Lisp , donde se necesitan paréntesis porque los operadores aritméticos tienen diferentes aridades. El lenguaje de programación Ambi utiliza la notación polaca para las operaciones aritméticas y la estructura del programa. La notación Postfix se usa en muchos lenguajes de pila , como PostScript , y es la base de muchas máquinas informáticas (calculadoras), especialmente las máquinas informáticas Hewlett-Packard .
También es importante tener en cuenta que el número de operandos en una expresión debe ser uno más que el número de operaciones, de lo contrario, la expresión no tiene sentido (dado que solo se usan operaciones binarias en la expresión ). Esto puede pasarse por alto fácilmente cuando se trabaja con expresiones largas y complejas, lo que conducirá a errores. Por lo tanto, es necesario prestar atención al número de operaciones y operandos cuando se utiliza la notación de prefijos.
Orden de Operaciones
El orden de las operaciones está determinado por la estructura de la notación de prefijos y se puede determinar fácilmente. Lo principal a recordar es que al evaluar una expresión, se debe preservar el orden de los operandos. Esto no es importante para las operaciones que son conmutativas , pero para las operaciones no conmutativas como la resta y la división , este hecho es clave para analizar la expresión. Por ejemplo, la siguiente expresión:
/ 10 5 = 2 (notación de prefijo)
debe leerse como "dividir 10 entre 5". Por lo tanto, el resultado del cálculo será 2, no ½, que sería el resultado de un análisis incorrecto de la expresión.
La notación de prefijos es especialmente popular en los lenguajes de pila debido a su capacidad para distinguir fácilmente el orden de las operaciones sin usar paréntesis. Para determinar el orden de evaluación de los operadores en notación de prefijos, ni siquiera es necesario memorizar toda la jerarquía operativa, como ocurre con la notación de infijos . En lugar de analizar la expresión para encontrar el operador que se evaluará primero, se debe leer la expresión de izquierda a derecha, observando el operador y sus dos operandos más cercanos. Si hay otro operador entre estos operandos, la evaluación del primer operador se retrasa hasta que se evalúa el nuevo operador. Las iteraciones de este proceso se repiten hasta que se evalúa el operador, lo que eventualmente debe suceder si el número de operandos en la expresión es uno más que el número de operaciones (en el caso de operaciones binarias). Una vez que se ha evaluado un operador, éste y sus dos operandos se reemplazan por el valor resultante (el operando). Dado que el operador y dos operandos se reemplazan por el operando calculado, hay un operador y un operando menos. Después de eso, N operadores y N + 1 operandos también permanecen en la expresión, lo que le permite continuar iterativamente el proceso.
En el siguiente ejemplo, puede ver que una expresión aparentemente complicada en notación de prefijo, de hecho, no es tan difícil de entender (a la derecha del signo igual, la expresión correspondiente en notación de infijo):
- * / 15 - 7 + 1 1 3 + 2 + 1 1 = 15 / (7 - (1 + 1) ) * 3 - (2 + (1 + 1)) - * / 15 - 7 2 3 + 2 + 1 1 = 15 / (7 - 2) * 3 - (2 + (1 + 1)) - * / 15 5 3 + 2 + 1 1 = 15 / 5 * 3 - (2 + (1 + 1)) - * 3 3 + 2 + 1 1 = 3 * 3 - (2 + (1 + 1)) - 9 + 2 + 1 1 = 9 - (2 + (1 + 1) ) - 9 + 2 2 = 9 - (2 + 2) - 9 4 = 9 - 4 5 = 5Notación polaca en lógica
La siguiente tabla muestra la notación central propuesta por Jan Lukasiewicz para la lógica proposicional . Algunas letras de la notación polaca representan palabras específicas en polaco :
| concepto | notación condicional |
notación polaca |
Польское слово |
|---|---|---|---|
| Negación | φ | Nφ | negacja |
| Conjunción | φ ψ | Kφψ | koniunkcja |
| Disyunción | φ ψ | Aφψ | alternancia |
| implicación | φ ψ | Cφψ | |
| Equivalencia | φ ψ | Eφψ | ekwiwalencja |
| Golpe de Schaeffer | Dφψ | disjunkcja | |
| Posibilidad | φ | Mφ | możliwość |
| Necesitar | φ | Lφ | |
| cuantificador universal | φ | Πφ | |
| Cuantificador de existencia | φ | Σφ |
Tenga en cuenta que en el artículo de Lukasiewicz sobre lógica de muchos valores, los cuantificadores están ordenados por valor proposicional.
Véase también
Notas
- ↑ Iglesia, Alonso. Introducción a la Lógica Matemática . — Princeton, New Jersey: Princeton University Press , 1944. — p.38: “Digno de comentario es 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, conjunción, respectivamente. ... "
Literatura
- Lukasiewicz , enero . La silogística de Aristóteles desde el punto de vista de la lógica formal moderna . — Prensa de la Universidad de Oxford , 1957.
- Ł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). Traducido por H. Weber como "Philosophical Remarks on Many-Valued Systems of Propositional Logics", en Storrs McCall, Polish Logic 1920-1939 , Clarendon Press: Oxford (1967).