Polsk notasjon

Polsk notasjon ( PN ), også kjent som normal polsk notasjon ( NPN ), prefiksnotasjon , Łukasiewicz-notasjon eller Warszawa normalform , er (innen informatikk og matematisk logikk ) en notasjon uten parentes for formler eller generelt for uttrykk der operatøren står foran Operand er skrevet:

Operatør Operand1 Operand2 ... OperandN

Den polske notasjonen skylder navnet til den polske matematikeren Jan Łukasiewicz , som utviklet den på 1920-tallet (en mer presis datering er sannsynligvis ikke mulig). Łukasiewicz introduserte den polske notasjonen som en kompakt og brakettfri notasjon for proposisjonslogikk . Som forbindelsessteder (eller connectives) han brukte Nfor negasjon , Kden forbindelse , Afor motsetninger , Cfor betinget og Efor Biconditional . Han bruker små bokstaver som setningsbokstaver som står for enhver uttalelse. Fra dette kan uttalelser som Np("det er ikke slik at p") eller Cpq("hvis p, så q") settes sammen.

Łukasiewicz påpeker selv at stavemåten er den mest kompakte og den første lineære stavemåten uten parentes, men ikke den første stavemåten uten parentes i det hele tatt. Fortjenesten ved å ha frigjort logikk fra parentesene går til Gottlob Frege med sin konseptuelle notasjon publisert i 1879 .

I tillegg til en nisje i logikk, har den polske notasjonen en fast plass i dag, spesielt i programmeringsspråk . Her er operatøren et kommandoord (f.eks. Mnemonic på forsamlingsspråk ) eller betegnelsen på ønsket funksjon, og operandene er de tilknyttede parametrene eller funksjonsargumentene:

Kommandoord Parameter1 Parameter2 ... ParameterN

eller.

Funksjonsbeskrivelse Argument1 Argument2 ... ArgumentN

Innen matematikkfeltet er de fleste funksjonene skrevet i polsk notasjon i vanlig notasjon, f.eks. B. Sinus (" ") eller logaritme (" "). To- sifrede lenker som B. de grunnleggende aritmetiske operasjonene . Her er en infiksnotasjon vanlig, der operatøren skrives mellom argumentene (“operander”) (“ ” i stedet for “ ”). Også i proposisjonell logikk dominerer infiksnotasjoner i dag, for det meste varianter av den tidlige Peano-Russell-notasjonen . ${\ displaystyle \ sin 30}$ ${\ displaystyle \ ln 10}$ ${\ displaystyle a + b}$ ${\ displaystyle {+} \; a \; b}$

Eksempler

Tillegget av tallene 21 og 43 er representert i prefiksnotasjonen som følger:

+ 21 43

Uttalelsen "P → Q" er skrevet i polsk notasjon som følger:

Cpq

I den kjente Infix-notasjonen krever følgende begrep flere parenteser:

(4 + 9) : (17 + 2)

Med prefiksnotasjonen er imidlertid ingen:

: + 4 9 + 17 2

Uttalelsen er analog

(P → (Q → R)) → ((P → Q) → (P → R))

for den kortere

CCpCqrCCpqCpr

applikasjon

I tillegg til funksjonsnotasjonen i matematikk, der funksjonsnavnet går foran argumentene i mange tilfeller (f.eks. "Sin 30" eller "lg 10") og en nisjeposisjon i logikken, der noen forfattere fortsatt bruker polsk notasjon i dag denne notasjonen er for tiden mest fremtredende representert innen informatikk . De fleste kommandolinjetolker bruker polsk notasjon (f.eks. " dir *.doc" Eller " ls -a /").

I analogi med matematisk bruk, i de fleste programmeringsspråk er matematiske funksjoner eller generelt funksjonsanrop skrevet i polsk notasjon, men da for det meste med ekstra parenteser (f.eks. "Sin (30)" eller "exp (log (10))"). Programmeringsspråk med polsk notasjon er APL , Assembler , Tcl og Lisp . Sistnevnte (i likhet med dialektene, f.eks. Skjema ) regnes blant anvendelsene av polsk notasjon på grunn av dens nærhet til lambdakalkulus og tilhørende funksjonell notasjon. Fordelen med frihet fra parentes går tapt i Lisp, men fordi det for det første ikke kan skilles tydelig fra operander i sammenhengen (variabler, fungerer som operander) og for det andre fordi ariteten til en operator (dvs. antall operander) er ikke entydig. Løsningen valgt i Lisp, å sette en åpningsbrakett foran operatøren og en lukkebrakett etter den siste operanden, kalles "Cambridge-varianten av polsk notasjon".

Den polske notasjonen (og enda mer den omvendte polske notasjonen, se nedenfor) er godt egnet til å bli evaluert på en enkel måte av maskinen. Spesielt i begynnelsen av elektronisk databehandling ble denne notasjonen derfor ofte opprettet eller brukt som et mellomprodukt av kompilatorer og tolker for å forenkle den videre behandlingen av en inngang i en mer brukervennlig notasjon for datasystemet.

Omvendt polsk notasjon

Den omvendte polske notasjonen, kort sagt UPN, er en variant av den polske notasjonen der operatørene ikke er skrevet før, men etter argumentene. Følgelig er UPN-postfiks-notasjonen eller omvendt prefiksnotasjon, sjelden også kalt Schinlop-notasjon.

Den brukes i lommeregnerne fra Hewlett-Packard og på programmeringsspråkene Forth og PostScript , men var i stor grad begrenset til disse.

Se også

Curry som et eksempel på bruk av polsk notasjon
Polsk matematikerskole

litteratur

Jan Łukasiewicz : Utvalgte verk . Red.: Ludwik Borkowski (= Studier i logikk og grunnlaget for matematikk . Nei. 54 ). North-Holland Publishing Company / Polish Scientific Publishers, Amsterdam / Warszawa 1970, ISBN 0-7204-2252-3 .
Charles L. Hamblin : Oversettelse til og fra polsk notasjon . I: The Computer Journal . teip 5 , nr. 3 , 1962, s. 210-213 , doi : 10.1093 / comjnl / 5.3.210 ( PDF ).

Individuelle bevis

↑ Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetic Algorithms of Micro Computing Technology , 1. utgave, VEB Verlag Technik , Berlin 1989, ISBN 3341005153 , EAN: 9783341005156, MPN: 5539165.
^ Bauer, Goos: Informatik, En innledende oversikt , bind 1. Springer-Verlag, Berlin 1982, s. 224.
↑ "De eldste tekstene i 'Utvalgte verk', der [Łukasiewicz] bruker polsk notasjon, dateres relativt sent, men er presentasjoner av tidligere verk som fant sted 'i løpet av årene 1920–1930' (side 131), så ikke gi en mer presis tid. ”(Ch. Gottschall: Logiske notasjoner og deres behandling på elektroniske datamaskiner fra et teoretisk, praktisk og historisk synspunkt (vitnemål), Wien: 2005, side 88).
^ "On the history of the logic of propositions", trykt i: Łukasiewicz 1970 , side 207 ff.
^ Michael L. Scott: Programming Language Pragmatics . 4. utgave. Morgan Kaufmann, Elsevier, Amsterdam / Boston 2015, ISBN 978-0-12-410409-9 , pp. 225 (amerikansk engelsk). For å forklare navnet står det: "Lisp-lignende parentes syntaks ble først ansatt (for ikke-beregningsmessige formål) av filosofen WV Quine fra Harvard University (Cambridge, MA)."
^ Charles L. Hamblin : Oversettelse til og fra polsk notasjon . I: The Computer Journal . teip 5 , nr. 3 , 1962, s. 210-213 , doi : 10.1093 / comjnl / 5.3.210 ( PDF ).

[Jorke_1989-1] Günter Jorke, Bernhard Lampe, Norbert Wengel: Arithmetic Algorithms of Micro Computing Technology , 1. utgave, VEB Verlag Technik , Berlin 1989, ISBN 3341005153 , EAN: 9783341005156, MPN: 5539165.

[Bauer_1982-2] Bauer, Goos: Informatik, En innledende oversikt , bind 1. Springer-Verlag, Berlin 1982, s. 224.

[3] "De eldste tekstene i 'Utvalgte verk', der [Łukasiewicz] bruker polsk notasjon, dateres relativt sent, men er presentasjoner av tidligere verk som fant sted 'i løpet av årene 1920–1930' (side 131), så ikke gi en mer presis tid. ”(Ch. Gottschall: Logiske notasjoner og deres behandling på elektroniske datamaskiner fra et teoretisk, praktisk og historisk synspunkt (vitnemål), Wien: 2005, side 88).

[4] "On the history of the logic of propositions", trykt i: Łukasiewicz 1970 , side 207 ff.

[5] Michael L. Scott: Programming Language Pragmatics . 4. utgave. Morgan Kaufmann, Elsevier, Amsterdam / Boston 2015, ISBN 978-0-12-410409-9 , pp. 225 (amerikansk engelsk). For å forklare navnet står det: "Lisp-lignende parentes syntaks ble først ansatt (for ikke-beregningsmessige formål) av filosofen WV Quine fra Harvard University (Cambridge, MA)."

[6] Charles L. Hamblin : Oversettelse til og fra polsk notasjon . I: The Computer Journal . teip 5 , nr. 3 , 1962, s. 210-213 , doi : 10.1093 / comjnl / 5.3.210 ( PDF ).

Languages