Notação polonesa - Polish notation

Notação polaca ( PN ), também conhecido como notação normais polaca ( NPN ), notação Łukasiewicz , notação Warsaw , notação prefixo polaca ou simplesmente prefixo notação , é uma notação matemática em que os operadores preceder seus operandos , em contraste com o mais comum notação infixa , em que os operadores são colocados entre operandos, bem como a notação polonesa reversa (RPN), na qual os operadores seguem seus operandos. Não precisa de parênteses, desde que cada operador tenha um número fixo de operandos . A descrição "Polonês" refere-se à nacionalidade do lógico Jan Łukasiewicz , que inventou a notação polonesa em 1924.

O termo notação polonesa às vezes é considerado (como o oposto da notação infixa ) para incluir também a notação polonesa reversa.

Quando a notação polonesa é usada como sintaxe para expressões matemáticas por intérpretes de linguagem de programação , ela é prontamente analisada em árvores de sintaxe abstratas e pode, de fato, definir uma representação um-para-um para a mesma. Por causa disso, Lisp ( veja abaixo ) e linguagens de programação relacionadas definem sua sintaxe inteira em notação de prefixo (e outras usam notação de pós-fixada).

História

Uma citação de um artigo de Jan Łukasiewicz , Remarks on Nicod's Axiom e em "Generalizing Deduction" , página 180, afirma como a notação foi inventada:

Tive a ideia de uma notação sem parênteses em 1924. Usei essa notação pela primeira vez em meu artigo Łukasiewicz (1), p. 610, nota de rodapé.

A referência citada por Łukasiewicz é aparentemente um relatório litografado em polonês . O artigo de referência de Łukasiewicz Remarks on Nicod's Axiom e sobre "Generalizing Deduction" foi revisado por Henry A. Pogorzelski no Journal of Symbolic Logic em 1965. Heinrich Behmann , editor em 1924 do artigo de Moses Schönfinkel , já tinha a ideia de eliminar parênteses em fórmulas lógicas.

Alonzo Church menciona essa notação em seu livro clássico sobre lógica matemática como digna de observação em sistemas de notação, mesmo em contraste com a exposição de notação lógica de Alfred Whitehead e Bertrand Russell e seu trabalho em Principia Mathematica .

No livro de Łukasiewicz de 1951, Aristóteles Silogística do Ponto de Vista da Lógica Formal Moderna , ele menciona que o princípio de sua notação era escrever os functores antes dos argumentos para evitar colchetes e que ele havia empregado sua notação em seus papéis lógicos desde 1929. Ele então prossegue citando, como exemplo, um artigo de 1930 que escreveu com Alfred Tarski sobre o cálculo sentencial .

Embora não seja mais muito usada em lógica, a notação polonesa encontrou um lugar na ciência da computação .

Explicação

A expressão para adicionar os números 1 e 2 é escrita na notação polonesa como + 1 2 (prefixado), em vez de 1 + 2 (corrigido). Em expressões mais complexas, os operadores ainda precedem seus operandos, mas os operandos podem ser expressões incluindo novamente os operadores e seus operandos. Por exemplo, a expressão que seria escrita em notação infixa convencional como

(5 - 6) × 7

pode ser escrito em notação polonesa como

× (- 5 6) 7

Assumindo uma determinada aridade de todos os operadores envolvidos (aqui o "-" denota a operação binária de subtração, não a função unária de mudança de sinal), qualquer representação de prefixo bem formada é inequívoca e os colchetes dentro da expressão de prefixo são desnecessários. Como tal, a expressão acima pode ser ainda mais simplificada para

× - 5 6 7

O processamento do produto é adiado até que seus dois operandos estejam disponíveis (ou seja, 5 menos 6 e 7). Como acontece com qualquer notação, as expressões mais internas são avaliadas primeiro, mas na notação polonesa essa "condição íntima" pode ser transmitida pela seqüência de operadores e operandos, em vez de colchetes.

Na notação infixa convencional, os parênteses são necessários para substituir as regras de precedência padrão , uma vez que, referindo-se ao exemplo acima, movê-los

5 - (6 × 7)

ou removê-los

5 - 6 × 7

muda o significado e o resultado da expressão. Esta versão foi escrita em notação polonesa como

- 5 × 6 7 .

Ao lidar com operações não comutativas, como divisão ou subtração, é necessário coordenar o arranjo sequencial dos operandos com a definição de como o operador leva seus argumentos, ou seja, da esquerda para a direita. Por exemplo, ÷ 10 5 , com 10 sobrando para 5, tem o significado de 10 ÷ 5 (leia como "divida 10 por 5"), ou - 7 6 , com 7 sobrando para 6, tem o significado de 7 - 6 ( leia como "subtraia de 7 o operando 6").

Algoritmo de avaliação

A notação de prefixo / pós-fixação é especialmente popular por sua capacidade inata de expressar a ordem pretendida de operações sem a necessidade de parênteses e outras regras de precedência, como geralmente são empregadas com a notação de infixo . Em vez disso, a notação indica exclusivamente qual operador avaliar primeiro. Os operadores são assumidos como tendo uma aridade fixa cada, e todos os operandos necessários são fornecidos explicitamente. Uma expressão de prefixo válida sempre começa com um operador e termina com um operando. A avaliação pode prosseguir da esquerda para a direita ou na direção oposta. Começando à esquerda, a string de entrada, que consiste em tokens denotando operadores ou operandos, é empurrada token para token em uma pilha , até que as entradas superiores da pilha contenham o número de operandos que se ajusta ao operador superior (imediatamente abaixo). Este grupo de tokens no topo da pilha (o último operador empilhado e o número de operandos de acordo) é substituído pelo resultado da execução do operador nestes / neste (s) operando (s). Em seguida, o processamento da entrada continua dessa maneira. O operando mais à direita em uma expressão de prefixo válida, portanto, esvazia a pilha, exceto para o resultado da avaliação de toda a expressão. Ao iniciar pela direita, o push dos tokens é realizado de forma semelhante, apenas a avaliação é disparada por um operador, encontrando o número adequado de operandos que se ajusta à sua aridade já no topo da pilha. Agora, o token mais à esquerda de uma expressão de prefixo válida deve ser um operador, ajustando-se ao número de operandos na pilha, o que novamente produz o resultado. Como pode ser visto na descrição, um armazenamento push-down sem capacidade de inspeção arbitrária da pilha é suficiente para implementar essa análise .

A manipulação de pilha esboçada acima funciona - com entrada espelhada - também para expressões em notação polonesa reversa .

Notação polonesa para lógica

A tabela abaixo mostra o núcleo da notação de Jan Łukasiewicz para lógica sentencial . Algumas letras na tabela de notação polonesa representam palavras específicas em polonês , conforme mostrado:

Conceito	Notação convencional	Notação polonesa	Termo polonês
Negação	${\ displaystyle \ neg \ varphi}$	${\ displaystyle \ mathrm {N} \ varphi}$	negacja
Conjunção	${\ displaystyle \ varphi \ land \ psi}$	${\ displaystyle \ mathrm {K} \ varphi \ psi}$	Koniunkcja
Disjunção	${\ displaystyle \ varphi \ lor \ psi}$	${\ displaystyle \ mathrm {A} \ varphi \ psi}$	Alternatywa
Condicional de material	${\ displaystyle \ varphi \ to \ psi}$	${\ displaystyle \ mathrm {C} \ varphi \ psi}$	implikacja
Bicondicional	${\ displaystyle \ varphi \ leftrightarrow \ psi}$	${\ displaystyle \ mathrm {E} \ varphi \ psi}$	ekwiwalencja
Falsum	${\ displaystyle \ bot}$	${\ displaystyle \ mathrm {O}}$	Fałsz
AVC Sheffer	${\ displaystyle \ varphi \ mid \ psi}$	${\ displaystyle \ mathrm {D} \ varphi \ psi}$	Disjunkcja
Possibilidade	${\ displaystyle \ Diamond \ varphi}$	${\ displaystyle \ mathrm {M} \ varphi}$	możliwość
Necessidade	${\ displaystyle \ Box \ varphi}$	${\ displaystyle \ mathrm {L} \ varphi}$	konieczność
Quantificador universal	${\ displaystyle \ forall p \, \ varphi}$	${\ displaystyle \ Pi p \, \ varphi}$	kwantyfikator ogólny
Quantificador existencial	${\ displaystyle \ exists p \, \ varphi}$	${\ displaystyle \ Sigma p \, \ varphi}$	kwantyfikator szczegółowy

Observe que os quantificadores variaram sobre valores proposicionais no trabalho de Łukasiewicz sobre lógicas de muitos valores.

Bocheński introduziu um sistema de notação polonesa que nomeia todos os 16 conectivos binários da lógica proposicional clássica . Para a lógica proposicional clássica, é uma extensão compatível da notação de Łukasiewicz. Mas as notações são incompatíveis no sentido de que Bocheński usa L e M (para não-implicação e não-implicação inversa) na lógica proposicional e Łukasiewicz usa L e M na lógica modal.

Implementações

A notação de prefixo teve ampla aplicação em expressões S do Lisp , onde os colchetes são necessários, uma vez que os operadores na linguagem são eles próprios dados ( funções de primeira classe ). As funções Lisp também podem ser variáveis . A linguagem de programação Tcl , assim como Lisp, também usa a notação polonesa por meio da biblioteca mathop. A linguagem de programação Ambi usa notação polonesa para operações aritméticas e construção de programas. A sintaxe do filtro LDAP usa notação de prefixo polonês.

A notação Postfix é usada em muitas linguagens de programação orientadas a pilha, como PostScript e Forth . A sintaxe do CoffeeScript também permite que funções sejam chamadas usando notação de prefixo, ao mesmo tempo em que oferece suporte à sintaxe postfix unária comum em outras linguagens.

O número de valores de retorno de uma expressão é igual à diferença entre o número de operandos em uma expressão e a aridade total dos operadores menos o número total de valores de retorno dos operadores.

A notação polonesa, geralmente na forma pós-fixada, é a notação escolhida para certas calculadoras , principalmente da Hewlett-Packard . Em um nível inferior, os operadores postfix são usados por algumas máquinas de pilha , como os grandes sistemas Burroughs .

Veja também

Referências

Leitura adicional

Łukasiewicz, Jan (1957). A Silogística de Aristóteles do Ponto de Vista da Lógica Formal Moderna . Oxford University Press .
Łukasiewicz, Jan (1930). "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls" [Observações filosóficas sobre sistemas de muitos valores de lógica proposicional]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (em alemão). 23 : 51–77.Traduzido por H. Weber em Storrs McCall, Polish Logic 1920-1939 , Clarendon Press : Oxford (1967).

links externos

Mídia relacionada à notação polonesa (matemática) no Wikimedia Commons

Languages

In other projects