Jump to content

Polish notation: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
Further reading: Change heading to reflect use of sources in article
Delinking "Kennedy, John" for obvious reasons.
 
(21 intermediate revisions by 8 users not shown)
Line 5: Line 5:
{{Operator notation sidebar |logo=[[File:Prefix-dia.svg|125px]]}}
{{Operator notation sidebar |logo=[[File:Prefix-dia.svg|125px]]}}


'''Polish notation''' ('''PN'''), also known as '''normal Polish notation''' ('''NPN'''),<ref name="Jorke_1989"/> '''Łukasiewicz notation''', '''Warsaw notation''', '''Polish prefix notation''' or simply '''prefix notation''', is a mathematical notation in which [[Operation (mathematics)|operators]] ''precede'' their [[operand]]s, in contrast to the more common [[infix notation]], in which operators are placed ''between'' operands, as well as [[reverse Polish notation]] (RPN), in which operators ''follow'' their operands. It does not need any parentheses as long as each operator has a fixed [[arity|number of operands]]. The description "Polish" refers to the [[nationality]] of [[logician]] [[Jan Łukasiewicz]],<ref name="Łukasiewicz_1929"/>{{rp|page=24}}<ref name="Łukasiewicz_1957"/>{{rp|page=78}}<ref name="Kennedy_1982"/> who invented Polish notation in 1924.<ref name="Łukasiewicz_1931"/>{{rp|page=367, Footnote 3)}}<ref name="Łukasiewicz_1970"/>{{rp|page=180, Footnote 3)}}
'''Polish notation''' ('''PN'''), also known as '''normal Polish notation''' ('''NPN'''),<ref name="Jorke_1989"/> '''Łukasiewicz notation''', '''Warsaw notation''', '''Polish prefix notation''' or simply '''prefix notation''', is a mathematical notation in which [[Operation (mathematics)|operators]] ''precede'' their [[operand]]s, in contrast to the more common [[infix notation]], in which operators are placed ''between'' operands, as well as [[reverse Polish notation]] (RPN), in which operators ''follow'' their operands. It does not need any parentheses as long as each operator has a fixed [[arity|number of operands]]. The description "Polish" refers to the [[nationality]] of [[logician]] [[Jan Łukasiewicz]],<ref name="Łukasiewicz_1929"/>{{rp|page=24}}<ref name="Łukasiewicz_1957"/>{{rp|page=78}}<ref name="Kennedy_1982"/> who invented Polish notation in 1924.<ref name="Łukasiewicz_1931"/>{{rp|page=367, Footnote 3}}<ref name="Łukasiewicz_1970"/>{{rp|page=180, Footnote 3}}


The term ''Polish notation'' is sometimes taken (as the opposite of ''infix notation'') to also include reverse Polish notation.<ref name="Main_2006"/>
The term ''Polish notation'' is sometimes taken (as the opposite of ''infix notation'') to also include reverse Polish notation.<ref name="Main_2006"/>
Line 13: Line 13:
== History ==
== History ==


A quotation from a paper by [[Jan Łukasiewicz]] in 1931<ref name="Łukasiewicz_1931"/>{{rp|page=367, Footnote 3)}}<ref name="Łukasiewicz_1970"/>{{rp|page=180, Footnote 3)}} states how the notation was invented:
A quotation from a paper by [[Jan Łukasiewicz]] in 1931<ref name="Łukasiewicz_1931"/>{{rp|page=367, Footnote 3}}<ref name="Łukasiewicz_1970"/>{{rp|page=180, Footnote 3}} states how the notation was invented:


<blockquote>I came upon the idea of a parenthesis-free notation in 1924. I used that notation for the first time in my article Łukasiewicz (1), p. 610, footnote.</blockquote>
<blockquote>I came upon the idea of a parenthesis-free notation in 1924. I used that notation for the first time in my article Łukasiewicz (1), p. 610, footnote.</blockquote>


The reference cited by Łukasiewicz, i.e., Łukasiewicz (1)<ref name="Łukasiewicz_1929a"/>, is apparently a lithographed report in [[Polish language|Polish]]. The referring paper<ref name="Łukasiewicz_1931"/> by Łukasiewicz was reviewed by [[Henry Pogorzelski|Henry A. Pogorzelski]] in the ''Journal of Symbolic Logic'' in 1965.<ref name="Pogorzelski_1965"/> [[Heinrich Behmann]], editor in 1924 of the article of [[Moses Schönfinkel]],<ref name="Mengelberg"/> already had the idea of eliminating parentheses in logic formulas. In one of his papers Łukasiewicz stated that his notation is the most compact and the first linearly written parentheses-free notation, but not the first one as [[Gottlob Frege]] proposed his parentheses-free [[Begriffsschrift]] notation in 1879 already.<ref name="Gottschall_2005"/>
The reference cited by Łukasiewicz, i.e., Łukasiewicz (1),<ref name="Łukasiewicz_1929a"/> is apparently a lithographed report in [[Polish language|Polish]]. The referring paper<ref name="Łukasiewicz_1931"/> by Łukasiewicz was reviewed by [[Henry Pogorzelski|Henry A. Pogorzelski]] in the ''Journal of Symbolic Logic'' in 1965.<ref name="Pogorzelski_1965"/> [[Heinrich Behmann]], editor in 1924 of the article of [[Moses Schönfinkel]],<ref name="Mengelberg"/> already had the idea of eliminating parentheses in logic formulas. In one of his papers Łukasiewicz stated that his notation is the most compact and the first linearly written parentheses-free notation, but not the first one as [[Gottlob Frege]] proposed his parentheses-free [[Begriffsschrift]] notation in 1879 already.<ref name="Gottschall_2005"/>


[[Alonzo Church]] mentions this notation in his classic book on [[mathematical logic]] as worthy of remark in notational systems even contrasted to [[Alfred North Whitehead|Alfred Whitehead]] and [[Bertrand Russell]]'s logical notational exposition and work in [[Principia Mathematica]].<ref name="Church_1944"/>
[[Alonzo Church]] mentions this notation in his classic book on [[mathematical logic]] as worthy of remark in notational systems even contrasted to [[Alfred North Whitehead|Alfred Whitehead]] and [[Bertrand Russell]]'s logical notational exposition and work in [[Principia Mathematica]].<ref name="Church_1944"/>
Line 58: Line 58:
|- style="border-top:3px solid #999;"
|- style="border-top:3px solid #999;"
|-
|-
|[[Negation]]||<math>\neg\phi</math>||<math> N\phi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=27-28}}||{{lang|pl|negacja}}
|[[Negation]]||<math>\neg\phi</math>||<math> N\phi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=27–28}}||{{lang|pl|negacja}}
|-
|-
|[[Material conditional]]||<math>\phi\to\psi</math>||<math>C\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=28-31}}||{{lang|pl|implikacja}}
|[[Material conditional]]||<math>\phi\to\psi</math>||<math>C\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=28–31}}||{{lang|pl|implikacja}}
|-
|-
|[[Disjunction]]||<math>\phi\lor\psi</math>||<math>A\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=34-35}}||{{lang|pl|alternatywa}}
|[[Disjunction]]||<math>\phi\lor\psi</math>||<math>A\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=34–35}}||{{lang|pl|alternatywa}}
|-
|-
|[[Logical conjunction|Conjunction]]||<math>\phi\land\psi</math>||<math>K\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=35-36}}||{{lang|pl|koniunkcja}}
|[[Logical conjunction|Conjunction]]||<math>\phi\land\psi</math>||<math>K\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=35–36}}||{{lang|pl|koniunkcja}}
|-
|-
|[[Sheffer stroke|Non-conjunction]]||<math>\phi\mid\psi </math>||<math>D\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|page=36}}||{{lang|pl|dysjunkcja}}
|[[Sheffer stroke|Non-conjunction]]||<math>\phi\mid\psi </math>||<math>D\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|page=36}}||{{lang|pl|dysjunkcja}}
Line 70: Line 70:
|[[Biconditional]]||<math>\phi\leftrightarrow\psi</math>||<math>E\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|page=37}} or <math>Q\phi\psi</math><ref name="Łukasiewicz_1957"/>{{rp|page=108}}||{{lang|pl|ekwiwalencja}}
|[[Biconditional]]||<math>\phi\leftrightarrow\psi</math>||<math>E\phi\psi</math><ref name="Łukasiewicz_1929"/>{{rp|page=37}} or <math>Q\phi\psi</math><ref name="Łukasiewicz_1957"/>{{rp|page=108}}||{{lang|pl|ekwiwalencja}}
|-
|-
|[[Universal quantification|Universal quantifier]]||<math>\forall p\,\phi</math>||<math>\varPi p\,\phi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=154-156}}||{{lang|pl|kwantyfikator ogólny}}
|[[Universal quantification|Universal quantifier]]||<math>\forall p\,\phi</math>||<math>\varPi p\,\phi</math><ref name="Łukasiewicz_1929"/>{{rp|pages=154–156}}||{{lang|pl|kwantyfikator ogólny}}
|-
|-
|[[Existential quantification|Existential quantifier]]||<math>\exists p\,\phi</math>||<math>\varSigma p\,\phi</math><ref name="Łukasiewicz_1929"/>{{rp|page=157}}||{{lang|pl|kwantyfikator szczegółowy}}
|[[Existential quantification|Existential quantifier]]||<math>\exists p\,\phi</math>||<math>\varSigma p\,\phi</math><ref name="Łukasiewicz_1929"/>{{rp|page=157}}||{{lang|pl|kwantyfikator szczegółowy}}
|-
|-
|[[Verum]]||<math>\top</math>||<math>V</math><ref name="Łukasiewicz_1939"/>{{rp|page=275}}||{{lang|pl|prawdziwy}}
|[[Verum]]||<math>\top</math>||<math>V</math><ref name="Łukasiewicz_1939"/>{{rp|page=275}}||{{lang|pl|prawda, prawdziwy}}
|-
|[[Falsum]]||<math>\bot</math>||<math>O</math><ref name="Łukasiewicz_1939"/>{{rp|page=275}}||{{lang|pl|fałsz, fałszywy}}
|-
|-
|[[Modal logic|Possibility]]||<math>\Diamond\phi</math>||<math>M\phi</math><ref name="Łukasiewicz_1930x"/>{{rp|page=52}}<ref name="Łukasiewicz_1957"/>{{rp|page=134}} or <math>\varDelta\phi</math><ref name="Łukasiewicz_1953"/>{{rp|page=111}}||{{lang|pl|możliwość}}
|[[Modal logic|Possibility]]||<math>\Diamond\phi</math>||<math>M\phi</math><ref name="Łukasiewicz_1930x"/>{{rp|page=52}}<ref name="Łukasiewicz_1957"/>{{rp|page=134}} or <math>\varDelta\phi</math><ref name="Łukasiewicz_1953"/>{{rp|page=111}}||{{lang|pl|możliwość}}
Line 83: Line 85:
Note that the [[quantifier (logic)|quantifiers]] ranged over propositional values in Łukasiewicz's work on many-valued logics.
Note that the [[quantifier (logic)|quantifiers]] ranged over propositional values in Łukasiewicz's work on many-valued logics.


[[Józef Maria Bocheński|Bocheński]] introduced a system of Polish notation that names all 16 binary [[logical connective|connectives]] of classical [[propositional logic]].<ref name="Bochenski1954">{{cite book |last1=Bocheński |first1=J. M. |title=Précis de logique mathématique |trans-title=A Precis of Mathematical Logic |url=https://burjcdigital.urjc.es/bitstream/handle/10115/1425/PRECIS_DE_LOGIQUE_MATHEMATIQUE.pdf?sequence=1&isAllowed=y |date=1954 |location=Netherlands |publisher=F. G. Kroonder, Bussum, Pays-Bas |language=French |page=16}}</ref> For classical propositional logic, it is a compatible extension of the notation of Łukasiewicz. But the notations are incompatible in the sense that Bocheński uses <math>L</math> and <math>M</math> (for nonimplication and converse nonimplication) in propositional logic and Łukasiewicz uses <math>L</math> and <math>M</math> in modal logic.
[[Józef Maria Bocheński|Bocheński]] introduced a system of Polish notation that names all 16 binary [[logical connective|connectives]] of classical [[propositional logic]].<ref name="Bochenski_1949"/>{{rp|page=16}} For classical propositional logic, it is a compatible extension of the notation of Łukasiewicz. But the notations are incompatible in the sense that Bocheński uses <math>L</math> and <math>M</math> (for nonimplication and converse nonimplication) in propositional logic and Łukasiewicz uses <math>L</math> and <math>M</math> in modal logic.


==Implementations==
==Implementations==
Prefix notation has seen wide application in [[Lisp (programming language)|Lisp]] [[S-expressions]], where the brackets are required since the operators in the language are themselves data ([[first-class function]]s). Lisp functions may also be [[Variadic function|variadic]]. The [[Tcl]] programming language, much like Lisp also uses Polish notation through the mathop library. The Ambi<ref name="Ambi"/> programming language uses Polish notation for arithmetic operations and program construction. [[LDAP]] filter syntax uses Polish prefix notation.<ref name="LDAPSyntax"/>
Prefix notation has seen wide application in [[Lisp (programming language)|Lisp]] [[S-expressions]], where the parentheses are required since the operators in the language are themselves data ([[first-class function]]s). Lisp functions may also be [[Variadic function|variadic]]. The [[Tcl]] programming language, much like Lisp also uses Polish notation through the mathop library. The Ambi<ref name="Ambi"/> programming language uses Polish notation for arithmetic operations and program construction. [[LDAP]] filter syntax uses Polish prefix notation.<ref name="LDAPSyntax"/>


Postfix notation is used in many [[stack-oriented programming language]]s like [[PostScript]] and [[Forth (programming language)|Forth]]. [[CoffeeScript]] syntax also allows functions to be called using prefix notation, while still supporting the unary postfix syntax common in other languages.
Postfix notation is used in many [[stack-oriented programming language]]s like [[PostScript]] and [[Forth (programming language)|Forth]]. [[CoffeeScript]] syntax also allows functions to be called using prefix notation, while still supporting the unary postfix syntax common in other languages.
Line 112: Line 114:
==References==
==References==
{{reflist|refs=
{{reflist|refs=
<ref name="Łukasiewicz_1929a">{{cite journal |last1=Łukasiewicz |first1=Jan |title=O znaczeniu i potrzebach logiki matematycznej |journal=Nauka Polska |date=1929 |volume=10 |pages=604-620 |language=Polish |url=https://www.sbc.org.pl/dlibra/publication/22955/edition/20205/content?format_id=2}}</ref>
<ref name="Łukasiewicz_1929a">{{cite journal |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |title=O znaczeniu i potrzebach logiki matematycznej |journal=Nauka Polska |date=1929 |volume=10 |pages=604–620 |language=pl |url=https://www.sbc.org.pl/dlibra/publication/22955/edition/20205/content?format_id=2}}</ref>
<ref name="Łukasiewicz_1929">{{cite book |title=Elementy logiki matematycznej |language=pl |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |location=Warsaw, Poland |edition=1 |publisher=[[Państwowe Wydawnictwo Naukowe]] |date=1929 |postscript=none}}; {{cite book |title=Elements of Mathematical Logic |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |translator-first=Olgierd Adrian |translator-last=Wojtasiewicz |translator-link=:pl:Olgierd Adrian Wojtasiewicz |date=1963 |publication-place=New York, USA |publisher=[[The MacMillan Company]]}}</ref>
<ref name="Łukasiewicz_1929">{{cite book |title=Elementy logiki matematycznej |language=pl |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |location=Warsaw, Poland |edition=1 |publisher=[[Państwowe Wydawnictwo Naukowe]] |date=1929 |postscript=none}}; {{cite book |title=Elements of Mathematical Logic |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |translator-first=Olgierd Adrian |translator-last=Wojtasiewicz |translator-link=:pl:Olgierd Adrian Wojtasiewicz |date=1963 |publication-place=New York, USA |publisher=[[The MacMillan Company]]}}</ref>
<ref name="Łukasiewicz_1930">{{cite journal |title=Untersuchungen über den Aussagenkalkül |language= |trans-title=Investigations into the sentential calculus |author-last1=Łukasiewicz |author-first1=Jan |author-link1=Jan Łukasiewicz |author-last2=Tarski |author-first2=Alfred |author-link2=Alfred Tarski |journal=Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie |volume=23 |date=1930 |number=Cl. III |pages=31–32}}</ref>
<ref name="Łukasiewicz_1930">{{cite journal |title=Untersuchungen über den Aussagenkalküls |trans-title=Investigations into the Sentential Calculus |url=https://rcin.org.pl/impan/dlibra/publication/4839/edition/50601/content |language=de |author-last1=Łukasiewicz |author-first1=Jan |author-link1=Jan Łukasiewicz |author-last2=Tarski |author-first2=Alfred |author-link2=Alfred Tarski |journal=Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie |volume=23 |number=Cl. III |pages=30–50 |date=1930}}</ref>
* <ref name="Łukasiewicz_1930x">{{cite journal |title=Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls |url=https://rcin.org.pl/impan/dlibra/publication/4839/edition/50601/content |language=de |trans-title=Philosophical Remarks on Many-Valued Systems of Propositional Logics |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |journal=Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie |volume=23 |pages=51–77 |date=1930}} Translated by H. Weber in Storrs McCall, ''Polish Logic 1920–1939'', [[Clarendon Press]]: Oxford (1967).</ref>
<ref name="Łukasiewicz_1930x">{{cite journal |title=Untersuchungen über den Aussagenkalküls |trans-title=Investigations into the Sentential Calculus |url=https://rcin.org.pl/impan/dlibra/publication/4839/edition/50601/content |language=de |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |journal=Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie |volume=23 |number=Cl. III |pages=51–77 |date=1930}}</ref>
<ref name="Łukasiewicz_1931">{{cite encyclopedia |url=https://sbc.org.pl/dlibra/docmetadata?showContent=true&id=18864 |title=Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej' |trans-title=Comments on Nicod's Axiom and on 'Generalizing Deduction' |encyclopedia=Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie, 12. II. 1904-12. II. 1929 |date=1931 |last=Łukasiewicz |first=Jan |publisher=Wydawnictwo Polskie Towarzystwo Filozoficzne |location=Lwów |pages=366-383 |language=Polish}}</ref>
<ref name="Łukasiewicz_1931">{{cite encyclopedia |url=https://sbc.org.pl/dlibra/docmetadata?showContent=true&id=18864 |title=Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej' |trans-title=Comments on Nicod's Axiom and on 'Generalizing Deduction' |encyclopedia=Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie, 12. II. 1904–1912. II. 1929 |date=1931 |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |publisher=Wydawnictwo Polskie Towarzystwo Filozoficzne |location=Lwów |pages=366–383 |language=pl}}</ref>
<ref name="Łukasiewicz_1939">{{cite journal |last1=Łukasiewicz |first1=Jan |title=Der Äquivalenzenkalkül |journal=Collectanea Logica |date=1939 |volume=1 |pages=145-169 |language=German}}</ref>
<ref name="Łukasiewicz_1939">{{cite journal |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |title=Der Äquivalenzenkalkül |journal=Collectanea Logica |date=1939 |volume=1 |pages=145–169 |language=de}}</ref>
<ref name="Łukasiewicz_1957">{{cite book |title=Aristotle's Syllogistic from the Standpoint of Modern Formal Logic |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |publisher=[[Oxford University Press]] |orig-date=1951 |date=1957 |edition=2}} (Reprinted by [[Garland Publishing]] in 1987, {{isbn|0-8240-6924-2}}.)</ref>
<ref name="Łukasiewicz_1957">{{cite book |title=Aristotle's Syllogistic from the Standpoint of Modern Formal Logic |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |publisher=[[Oxford University Press]] |orig-date=1951 |date=1957 |edition=2}} (Reprinted by [[Garland Publishing]] in 1987, {{isbn|0-8240-6924-2}}.)</ref>
<ref name="Łukasiewicz_1953">{{cite journal |last1=Łukasiewicz |first1=Jan |title=A System of Modal Logic |journal=The Journal of Computing Systems |date=1953 |volume=3 |issue=1 |pages=111-149}}</ref>
<ref name="Łukasiewicz_1953">{{cite journal |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |title=A System of Modal Logic |journal=The Journal of Computing Systems |date=1953 |volume=3 |issue=1 |pages=111–149}}</ref>
<ref name="Łukasiewicz_1970">{{cite encyclopedia |title=Comments on Nicod's Axiom and on 'Generalizing Deduction' |encyclopedia=Selected Works |date=1970 |last=Łukasiewicz |first=Jan |editor1-last=Borkowski |editor1-first=L. |publisher=North-Holland Publishing Company/Polish Scientific Publishers |location=Amsterdam and London/Warszawa |pages=179-196}}</ref>
<ref name="Łukasiewicz_1970">{{cite encyclopedia |title=Comments on Nicod's Axiom and on 'Generalizing Deduction' |encyclopedia=Selected Works |date=1970 |author-last=Łukasiewicz |author-first=Jan |author-link=Jan Łukasiewicz |editor-last=Borkowski |editor-first=L. |publisher=North-Holland Publishing Company/Polish Scientific Publishers |location=Amsterdam and London/Warszawa |pages=179–196}}</ref>
<ref name="Kennedy_1982">{{cite journal |title=RPN Perspective |author-first=John |author-last=Kennedy |author-link=John Kennedy |location=Mathematics Department, Santa Monica College, Santa Monica, California, USA |journal=[[PPC Calculator Journal]] |volume=9 |number=5 |date=August 1982 |pages=26–29 |citeseerx=10.1.1.90.6448 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.6448&rep=rep1&type=pdf |access-date=2022-07-02 |url-status=live |archive-url=https://web.archive.org/web/20220701223543/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.6448&rep=rep1&type=pdf |archive-date=2022-07-01}} (12 pages)</ref>
<ref name="Kennedy_1982">{{cite journal |title=RPN Perspective |author-first=John |author-last=Kennedy |location=Mathematics Department, Santa Monica College, Santa Monica, California, USA |journal=[[PPC Calculator Journal]] |volume=9 |number=5 |date=August 1982 |pages=26–29 |citeseerx=10.1.1.90.6448 |url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.6448&rep=rep1&type=pdf |access-date=2022-07-02 |url-status=live |archive-url=https://web.archive.org/web/20220701223543/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.6448&rep=rep1&type=pdf |archive-date=2022-07-01}} (12 pages)</ref>
<ref name="Jorke_1989">{{cite book |title=Arithmetische Algorithmen der Mikrorechentechnik |trans-title=Arithmetic algorithms in microcomputers |author-first1=Günter |author-last1=Jorke |author-first2=Bernhard |author-last2=Lampe |author-first3=Norbert |author-last3=Wengel |edition=1 |publisher=[[VEB Verlag Technik]] |location=Berlin, Germany |date=1989 |language=de |isbn=3-34100515-3 |id={{EAN|978-3-34100515-6}}. MPN 5539165. License 201.370/4/89 |url=https://books.google.com/books?id=DqYWAQAAMAAJ |access-date=2015-12-01}}</ref>
<ref name="Jorke_1989">{{cite book |title=Arithmetische Algorithmen der Mikrorechentechnik |trans-title=Arithmetic algorithms in microcomputers |author-first1=Günter |author-last1=Jorke |author-first2=Bernhard |author-last2=Lampe |author-first3=Norbert |author-last3=Wengel |edition=1 |publisher=[[VEB Verlag Technik]] |location=Berlin, Germany |date=1989 |language=de |isbn=3-34100515-3 |id={{EAN|978-3-34100515-6}}. MPN 5539165. License 201.370/4/89 |url=https://books.google.com/books?id=DqYWAQAAMAAJ |access-date=2015-12-01}}</ref>
<ref name="Main_2006">{{cite book |title=Data structures and other objects using Java |edition=3 |author-first=Michael |author-last=Main |publisher=[[Pearson PLC]] [[Addison-Wesley]] |date=2006 |isbn=978-0-321-37525-4 |page=334 |url=https://books.google.com/books?id=Tok_AQAAIAAJ}}</ref>
<ref name="Pogorzelski_1965">{{cite journal |title=Reviewed work(s): Remarks on Nicod's Axiom and on "Generalizing Deduction" by Jan Łukasiewicz, Jerzy Słupecki, Państwowe Wydawnictwo Naukowe |author-last=Pogorzelski |author-first=Henry Andrew |author-link=Henry Andrew Pogorzelski |url=https://www.jstor.org/stable/2269644 |type=Review |journal=[[The Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |volume=30 |number=3 |date=September 1965 |pages=376–377 |jstor=2269644}} (NB. The original 1931 paper "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej" by [[Jan Łukasiewicz]] was re-published at [[Państwowe Wydawnictwo Naukowe]] (National Scientific Publishers), [[Warsaw]], Poland in 1961 in a volume edited by [[Jerzy Słupecki]].)</ref>
<ref name="Mengelberg">{{cite journal |title=Über die Bausteine der mathematischen Logik |language=de |trans-title=On the building blocks of mathematical logic |author-last=Schönfinkel |author-first=Moses |author-link=Moses Schönfinkel |journal=[[Mathematische Annalen]] |date=1924 |volume=92 |pages=305–316 |doi=10.1007/BF01448013 |s2cid=118507515 |issue=3–4 |postscript=none}}; {{cite book |chapter=On the building blocks of mathematical logic |translator-first=Stefan |translator-last=Bauer-Mengelberg |translator-link=:nl:Stefan Bauer-Mengelberg |editor-first=Jean |editor-last=van Heijenoort |editor-link=Jean van Heijenoort |date=1967 |title=A Source Book in Mathematical Logic, 1879–1931 |publisher=[[Harvard University Press]] |pages=355–366}}</ref>
<ref name="Church_1944">{{cite book |author-first=Alonzo |author-last=Church |author-link=Alonzo Church |title=Introduction to Mathematical Logic |location=Princeton, New Jersey, USA |publisher=[[Princeton University Press]] |date=1944 |page=38 |quote=[…] Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. […]}}</ref>
<ref name="Martínez_2011">{{citation |contribution=Mhy bib I fail logic? Dyslexia in the teaching of logic |author-first=Xóchitl |author-last=Martínez Nava |pages=162–169 |title=Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, 1–4 June 2011, Proceedings |volume=6680 |series=Lecture Notes in Artificial Intelligence |publisher=[[Springer Nature]] |date=2011-06-01 |isbn=978-3-64221349-6 |editor-first1=Patrick |editor-last1=Blackburn |editor-first2=Hans |editor-last2=van Ditmarsch |editor-first3=Maria |editor-last3=Manzano |editor-link3=María Manzano |editor-first4=Fernando |editor-last4=Soler-Toscano |doi=10.1007/978-3-642-21350-2_19 |url=https://books.google.com/books?id=be-pTR5TmZIC&pg=PA166 |quote=[…] Polish or prefix notation has come to disuse given the difficulty that using it implies. […]}}</ref>
<ref name="Ambi">{{cite web |title=Google Code Archive - Long-term storage for Google Code Project Hosting |url=https://code.google.com/p/ambi/ |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20170928175932/https://code.google.com/archive/p/ambi/ |archive-date=2017-09-28}}</ref>
<ref name="RPN_HP35S">{{cite web |title=HP calculators - HP 35s RPN Mode |publisher=[[Hewlett-Packard]] |url=http://h20331.www2.hp.com/Hpsub/downloads/35_02_RPN_Mode.pdf |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20220121192354/http://h20331.www2.hp.com/Hpsub/downloads/35_02_RPN_Mode.pdf |archive-date=2022-01-21}}</ref>
<ref name="LDAPSyntax">{{cite web |title=LDAP Filter Syntax |url=http://www.ldapexplorer.com/en/manual/109010000-ldap-filter-syntax.htm |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20221014105027/https://www.ldapexplorer.com/en/manual/109010000-ldap-filter-syntax.htm |archive-date=2022-10-14}}</ref>
<ref name="Gottschall_2005">{{cite book |title=Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht. |language=de |trans-title= |author-first=Christian |author-last=Gottschall |type=Diploma thesis |location=Vienna, Austria |date=2005 |quote-page=88 |quote=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, also auch keine genauere Zeitangabe geben.}}</ref>
<ref name="Bochenski_1949">{{cite book |author-last=Bocheński |author-first=Józef Maria |author-link=Józef Maria Bocheński |title=Précis de logique mathématique |date=1949 |publication-place=Bussum, Pays-Bas, Netherlands |location=Fribourg |publisher=F. G. Kroonder |language=fr |series=Collection Synthese |volume=2 |url=https://burjcdigital.urjc.es/bitstream/handle/10115/1425/PRECIS_DE_LOGIQUE_MATHEMATIQUE.pdf?sequence=1&isAllowed=y |access-date=2023-11-12 |url-status=live |archive-url=https://web.archive.org/web/20230803130610/https://burjcdigital.urjc.es/bitstream/handle/10115/1425/PRECIS_DE_LOGIQUE_MATHEMATIQUE.pdf?sequence=1&isAllowed=y |archive-date=2023-08-03}} Translated as {{cite book |author-last=Bocheński |author-first=Józef Maria |author-link=Józef Maria Bocheński |translator-last=Bird |translator-first=Otto A. |translator-link=:d:Q94507730 |title=A Precis of Mathematical Logic |date=1959 |publisher=D. Reidel Publishing Company |location=Dordrecht, Netherlands}}</ref>
<!--
<!--
<ref name="Hamblin_1962">{{cite journal |author-first=Charles Leonard |author-last=Hamblin |author-link=Charles Leonard Hamblin |date=1962 |title=Translation to and from Polish notation |journal=[[Computer Journal]] |volume=5 |issue=3 |pages=210–213 |doi=10.1093/comjnl/5.3.210 |doi-access=free}}</ref>
<ref name="Hamblin_1962">{{cite journal |author-first=Charles Leonard |author-last=Hamblin |author-link=Charles Leonard Hamblin |date=1962 |title=Translation to and from Polish notation |journal=[[Computer Journal]] |volume=5 |issue=3 |pages=210–213 |doi=10.1093/comjnl/5.3.210 |doi-access=free}}</ref>
<ref name="Ball_1978">{{cite book |title=Algorithms for RPN calculators |author-first=John A. |author-last=Ball |date=1978 |edition=1 |publisher=[[Wiley-Interscience]], [[John Wiley & Sons, Inc.]] |location=Cambridge, Massachusetts, USA |isbn=0-471-03070-8 |url-access=registration |url=https://archive.org/details/algorithmsforrpn0000ball}}</ref>
-->
-->
<ref name="Main_2006">{{cite book |title=Data structures and other objects using Java |edition=3rd |author-first=Michael |author-last=Main |publisher=[[Pearson PLC]] [[Addison-Wesley]] |date=2006 |isbn=978-0-321-37525-4 |page=334 |url=https://books.google.com/books?id=Tok_AQAAIAAJ}}</ref>
<ref name="Pogorzelski_1965">{{cite journal |title=Reviewed work(s): Remarks on Nicod's Axiom and on "Generalizing Deduction" by Jan Łukasiewicz, Jerzy Słupecki, Państwowe Wydawnictwo Naukowe |author-last=Pogorzelski |author-first=Henry Andrew |author-link=Henry Andrew Pogorzelski |url=https://www.jstor.org/stable/2269644 |type=Review |journal=[[The Journal of Symbolic Logic]] |publisher=[[Association for Symbolic Logic]] |volume=30 |number=3 |date=September 1965 |pages=376–377|jstor=2269644 }} (NB. The original 1931 paper "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej" by [[Jan Łukasiewicz]] was re-published at [[Państwowe Wydawnictwo Naukowe]] (National Scientific Publishers), [[Warsaw]], Poland in 1961 in a volume edited by [[Jerzy Słupecki]].)</ref>
<ref name="Mengelberg">{{cite journal |title=Über die Bausteine der mathematischen Logik |language=de |trans-title=On the building blocks of mathematical logic |author-last=Schönfinkel |author-first=Moses |author-link=Moses Schönfinkel |journal=[[Mathematische Annalen]] |date=1924 |volume=92 |pages=305–316 |doi=10.1007/BF01448013 |s2cid=118507515 |issue=3–4 |postscript=none}}; {{cite book |chapter=On the building blocks of mathematical logic |translator-first=Stefan |translator-last=Bauer-Mengelberg |translator-link=:nl:Stefan Bauer-Mengelberg |editor-first=Jean |editor-last=van Heijenoort |editor-link=Jean van Heijenoort |date=1967 |title=A Source Book in Mathematical Logic, 1879–1931 |publisher=[[Harvard University Press]] |pages=355–366}}</ref>
<ref name="Church_1944">{{cite book |author-first=Alonzo |author-last=Church |author-link=Alonzo Church |title=Introduction to Mathematical Logic |location=Princeton, New Jersey, USA |publisher=[[Princeton University Press]] |date=1944 |page=38 |quote=[…] Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. […]}}</ref>
<ref name="Martínez_2011">{{citation |contribution=Mhy bib I fail logic? Dyslexia in the teaching of logic |author-first=Xóchitl |author-last=Martínez Nava |pages=162–169 |title=Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, June 1–4, 2011, Proceedings |volume=6680 |series=Lecture Notes in Artificial Intelligence |publisher=[[Springer Nature]] |date=2011-06-01 |isbn=978-3-64221349-6 |editor-first1=Patrick |editor-last1=Blackburn |editor-first2=Hans |editor-last2=van Ditmarsch |editor-first3=Maria |editor-last3=Manzano |editor-link3=María Manzano |editor-first4=Fernando |editor-last4=Soler-Toscano |doi=10.1007/978-3-642-21350-2_19 |url=https://books.google.com/books?id=be-pTR5TmZIC&pg=PA166 |quote=[…] Polish or prefix notation has come to disuse given the difficulty that using it implies. […]}}</ref>
<ref name="Ambi">{{cite web |title=Google Code Archive - Long-term storage for Google Code Project Hosting |url=https://code.google.com/p/ambi/ |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20170928175932/https://code.google.com/archive/p/ambi/ |archive-date=2022-11-14}}</ref>
<ref name="RPN_HP35S">{{cite web |title=HP calculators - HP 35s RPN Mode |publisher=[[Hewlett-Packard]] |url=http://h20331.www2.hp.com/Hpsub/downloads/35_02_RPN_Mode.pdf |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20220121192354/http://h20331.www2.hp.com/Hpsub/downloads/35_02_RPN_Mode.pdf |archive-date=2022-11-14}}</ref>
<ref name="LDAPSyntax">{{cite web |title=LDAP Filter Syntax |url=http://www.ldapexplorer.com/en/manual/109010000-ldap-filter-syntax.htm |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20221014105027/https://www.ldapexplorer.com/en/manual/109010000-ldap-filter-syntax.htm |archive-date=2022-11-14}}</ref>
<ref name="Gottschall_2005">{{cite book |title=Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht. |language=de |trans-title= |author-first=Christian |author-last=Gottschall |type=Diploma thesis |location=Vienna, Austria |date=2005 |page=88 |quote-page=88 |quote=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, also auch keine genauere Zeitangabe geben.}}</ref>
}}
}}


==Bibliography==
==Further reading==
* {{cite book |title=Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial |language=de |trans-title=Cellar, stack and automatic memory - a structure with potential |editor-first1=Michael |editor-last1=Fothe |editor-first2=Thomas |editor-last2=Wilke |type=Tagungsband zum Kolloquium 14. November 2014 in Jena |location=Jena, Germany |volume=T-7 |series=GI Series: Lecture Notes in Informatics (LNI) – Thematics |publisher=[[Gesellschaft für Informatik]] (GI) / Köllen Druck + Verlag GmbH |isbn=978-3-88579-426-4 |issn=1614-3213 |date=2015 |orig-date=2014-11-14 |publication-place=Bonn, Germany |url=https://dl.gi.de/bitstream/handle/20.500.12116/4381/lni-t-7.pdf?sequence=1&isAllowed=y |access-date=2020-04-12 |url-status=live |archive-url=https://web.archive.org/web/20200412122706/https://dl.gi.de/bitstream/handle/20.500.12116/4381/lni-t-7.pdf?sequence=1&isAllowed=y |archive-date=2020-04-12}} [https://web.archive.org/web/20221210100112/https://dl.gi.de/handle/20.500.12116/4374/browse?type=title&sort_by=4] (77 pages)
* {{cite book |title=Keller, Stack und automatisches Gedächtnis – eine Struktur mit Potenzial |language=de |trans-title=Cellar, stack and automatic memory - a structure with potential |editor-first1=Michael |editor-last1=Fothe |editor-first2=Thomas |editor-last2=Wilke |type=Tagungsband zum Kolloquium 14. November 2014 in Jena |location=Jena, Germany |volume=T-7 |series=GI Series: Lecture Notes in Informatics (LNI) – Thematics |publisher=[[Gesellschaft für Informatik]] (GI) / Köllen Druck + Verlag GmbH |isbn=978-3-88579-426-4 |issn=1614-3213 |date=2015 |orig-date=2014-11-14 |publication-place=Bonn, Germany |url=https://dl.gi.de/bitstream/handle/20.500.12116/4381/lni-t-7.pdf?sequence=1&isAllowed=y |access-date=2020-04-12 |url-status=live |archive-url=https://web.archive.org/web/20200412122706/https://dl.gi.de/bitstream/handle/20.500.12116/4381/lni-t-7.pdf?sequence=1&isAllowed=y |archive-date=2020-04-12}} [https://web.archive.org/web/20221210100112/https://dl.gi.de/handle/20.500.12116/4374/browse?type=title&sort_by=4] (77 pages)
* {{cite book |title=Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat |language=de |trans-title=Friedrich L. Bauer's and Klaus Samelson's works in the 1950s on the introduction of the terms cellar principle and cellar automaton |author-first=Hans |author-last=Langmaack |author-link=:de:Hans Langmaack (Informatiker) |location=Kiel, Germany |publisher=Institut für Informatik, Christian-Albrechts-Universität zu Kiel |publication-place=Jena, Germany |date=2015 |orig-date=2014-11-14 |pages=19–29 |url=https://dl.gi.de/bitstream/handle/20.500.12116/33413/19.pdf?sequence=1&isAllowed=y |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20221114205159/https://dl.gi.de/bitstream/handle/20.500.12116/33413/19.pdf?sequence=1&isAllowed=y |archive-date=2022-11-14}} (11 pages) (NB. Published in {{citeref|Fothe|Wilke|2015|Fothe & Wilke|style=plain}}.)
* {{cite book |title=Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat |language=de |trans-title=Friedrich L. Bauer's and Klaus Samelson's works in the 1950s on the introduction of the terms cellar principle and cellar automaton |author-first=Hans |author-last=Langmaack |author-link=:de:Hans Langmaack (Informatiker) |location=Kiel, Germany |publisher=Institut für Informatik, Christian-Albrechts-Universität zu Kiel |publication-place=Jena, Germany |date=2015 |orig-date=2014-11-14 |pages=19–29 |url=https://dl.gi.de/bitstream/handle/20.500.12116/33413/19.pdf?sequence=1&isAllowed=y |access-date=2022-11-14 |url-status=live |archive-url=https://web.archive.org/web/20221114205159/https://dl.gi.de/bitstream/handle/20.500.12116/33413/19.pdf?sequence=1&isAllowed=y |archive-date=2022-11-14}} (11 pages) (NB. Published in {{citeref|Fothe|Wilke|2015|Fothe & Wilke|style=plain}}.)

Latest revision as of 23:56, 22 July 2024

Polish notation (PN), also known as normal Polish notation (NPN),[1] Łukasiewicz notation, Warsaw notation, Polish prefix notation or simply prefix notation, is a mathematical notation in which operators precede their operands, in contrast to the more common infix notation, in which operators are placed between operands, as well as reverse Polish notation (RPN), in which operators follow their operands. It does not need any parentheses as long as each operator has a fixed number of operands. The description "Polish" refers to the nationality of logician Jan Łukasiewicz,[2]: 24 [3]: 78 [4] who invented Polish notation in 1924.[5]: 367, Footnote 3 [6]: 180, Footnote 3 

The term Polish notation is sometimes taken (as the opposite of infix notation) to also include reverse Polish notation.[7]

When Polish notation is used as a syntax for mathematical expressions by programming language interpreters, it is readily parsed into abstract syntax trees and can, in fact, define a one-to-one representation for the same. Because of this, Lisp (see below) and related programming languages define their entire syntax in prefix notation (and others use postfix notation).

History

[edit]

A quotation from a paper by Jan Łukasiewicz in 1931[5]: 367, Footnote 3 [6]: 180, Footnote 3  states how the notation was invented:

I came upon the idea of a parenthesis-free notation in 1924. I used that notation for the first time in my article Łukasiewicz (1), p. 610, footnote.

The reference cited by Łukasiewicz, i.e., Łukasiewicz (1),[8] is apparently a lithographed report in Polish. The referring paper[5] by Łukasiewicz was reviewed by Henry A. Pogorzelski in the Journal of Symbolic Logic in 1965.[9] Heinrich Behmann, editor in 1924 of the article of Moses Schönfinkel,[10] already had the idea of eliminating parentheses in logic formulas. In one of his papers Łukasiewicz stated that his notation is the most compact and the first linearly written parentheses-free notation, but not the first one as Gottlob Frege proposed his parentheses-free Begriffsschrift notation in 1879 already.[11]

Alonzo Church mentions this notation in his classic book on mathematical logic as worthy of remark in notational systems even contrasted to Alfred Whitehead and Bertrand Russell's logical notational exposition and work in Principia Mathematica.[12]

In Łukasiewicz's 1951 book, Aristotle's Syllogistic from the Standpoint of Modern Formal Logic, he mentions that the principle of his notation was to write the functors before the arguments to avoid brackets and that he had employed his notation in his logical papers since 1929.[3]: 78  He then goes on to cite, as an example, a 1930 paper he wrote with Alfred Tarski on the sentential calculus.[13]

While no longer used much in logic,[14] Polish notation has since found a place in computer science.

Explanation

[edit]

The expression for adding the numbers 1 and 2 is written in Polish notation as + 1 2 (prefix), rather than as 1 + 2 (infix). In more complex expressions, the operators still precede their operands, but the operands may themselves be expressions including again operators and their operands. For instance, the expression that would be written in conventional infix notation as

(5 − 6) × 7

can be written in Polish notation as

× (− 5 6) 7

Assuming a given arity of all involved operators (here the "−" denotes the binary operation of subtraction, not the unary function of sign-change), any well-formed prefix representation is unambiguous, and brackets within the prefix expression are unnecessary. As such, the above expression can be further simplified to

× − 5 6 7

The processing of the product is deferred until its two operands are available (i.e., 5 minus 6, and 7). As with any notation, the innermost expressions are evaluated first, but in Polish notation this "innermost-ness" can be conveyed by the sequence of operators and operands rather than by bracketing.

In the conventional infix notation, parentheses are required to override the standard precedence rules, since, referring to the above example, moving them

5 − (6 × 7)

or removing them

5 − 6 × 7

changes the meaning and the result of the expression. This version is written in Polish notation as

− 5 × 6 7.

When dealing with non-commutative operations, like division or subtraction, it is necessary to coordinate the sequential arrangement of the operands with the definition of how the operator takes its arguments, i.e., from left to right. For example, ÷ 10 5, with 10 to the left of 5, has the meaning of 10 ÷ 5 (read as "divide 10 by 5"), or − 7 6, with 7 left to 6, has the meaning of 7 − 6 (read as "subtract from 7 the operand 6").

Evaluation algorithm

[edit]

Prefix/postfix notation is especially popular for its innate ability to express the intended order of operations without the need for parentheses and other precedence rules, as are usually employed with infix notation. Instead, the notation uniquely indicates which operator to evaluate first. The operators are assumed to have a fixed arity each, and all necessary operands are assumed to be explicitly given. A valid prefix expression always starts with an operator and ends with an operand. Evaluation can either proceed from left to right, or in the opposite direction. Starting at the left, the input string, consisting of tokens denoting operators or operands, is pushed token for token on a stack, until the top entries of the stack contain the number of operands that fits to the top most operator (immediately beneath). This group of tokens at the stacktop (the last stacked operator and the according number of operands) is replaced by the result of executing the operator on these/this operand(s). Then the processing of the input continues in this manner. The rightmost operand in a valid prefix expression thus empties the stack, except for the result of evaluating the whole expression. When starting at the right, the pushing of tokens is performed similarly, just the evaluation is triggered by an operator, finding the appropriate number of operands that fits its arity already at the stacktop. Now the leftmost token of a valid prefix expression must be an operator, fitting to the number of operands in the stack, which again yields the result. As can be seen from the description, a push-down store with no capability of arbitrary stack inspection suffices to implement this parsing.

The above sketched stack manipulation works—with mirrored input—also for expressions in reverse Polish notation.

Polish notation for logic

[edit]

The table below shows the core of Jan Łukasiewicz's notation in modern logic. Some letters in the Polish notation table stand for particular words in Polish, as shown:

Concept Conventional
notation
Polish
notation
Polish
term
Negation [2]: 27–28  negacja
Material conditional [2]: 28–31  implikacja
Disjunction [2]: 34–35  alternatywa
Conjunction [2]: 35–36  koniunkcja
Non-conjunction [2]: 36  dysjunkcja
Biconditional [2]: 37  or [3]: 108  ekwiwalencja
Universal quantifier [2]: 154–156  kwantyfikator ogólny
Existential quantifier [2]: 157  kwantyfikator szczegółowy
Verum [15]: 275  prawda, prawdziwy
Falsum [15]: 275  fałsz, fałszywy
Possibility [16]: 52 [3]: 134  or [17]: 111  możliwość
Necessity [3]: 134  or [17]: 111  konieczność

Note that the quantifiers ranged over propositional values in Łukasiewicz's work on many-valued logics.

Bocheński introduced a system of Polish notation that names all 16 binary connectives of classical propositional logic.[18]: 16  For classical propositional logic, it is a compatible extension of the notation of Łukasiewicz. But the notations are incompatible in the sense that Bocheński uses and (for nonimplication and converse nonimplication) in propositional logic and Łukasiewicz uses and in modal logic.

Implementations

[edit]

Prefix notation has seen wide application in Lisp S-expressions, where the parentheses are required since the operators in the language are themselves data (first-class functions). Lisp functions may also be variadic. The Tcl programming language, much like Lisp also uses Polish notation through the mathop library. The Ambi[19] programming language uses Polish notation for arithmetic operations and program construction. LDAP filter syntax uses Polish prefix notation.[20]

Postfix notation is used in many stack-oriented programming languages like PostScript and Forth. CoffeeScript syntax also allows functions to be called using prefix notation, while still supporting the unary postfix syntax common in other languages.

The number of return values of an expression equals the difference between the number of operands in an expression and the total arity of the operators minus the total number of return values of the operators.

Polish notation, usually in postfix form, is the chosen notation of certain calculators, notably from Hewlett-Packard.[21] At a lower level, postfix operators are used by some stack machines such as the Burroughs large systems.

See also

[edit]

References

[edit]
  1. ^ Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithmen der Mikrorechentechnik [Arithmetic algorithms in microcomputers] (in German) (1 ed.). Berlin, Germany: VEB Verlag Technik. ISBN 3-34100515-3. EAN 978-3-34100515-6. MPN 5539165. License 201.370/4/89. Retrieved 2015-12-01.
  2. ^ a b c d e f g h i Łukasiewicz, Jan (1929). Elementy logiki matematycznej (in Polish) (1 ed.). Warsaw, Poland: Państwowe Wydawnictwo Naukowe; Łukasiewicz, Jan (1963). Elements of Mathematical Logic. Translated by Wojtasiewicz, Olgierd Adrian [in Polish]. New York, USA: The MacMillan Company.
  3. ^ a b c d e Łukasiewicz, Jan (1957) [1951]. Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (2 ed.). Oxford University Press. (Reprinted by Garland Publishing in 1987, ISBN 0-8240-6924-2.)
  4. ^ Kennedy, John (August 1982). "RPN Perspective". PPC Calculator Journal. 9 (5). Mathematics Department, Santa Monica College, Santa Monica, California, USA: 26–29. CiteSeerX 10.1.1.90.6448. Archived from the original on 2022-07-01. Retrieved 2022-07-02. (12 pages)
  5. ^ a b c Łukasiewicz, Jan (1931). "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej'" [Comments on Nicod's Axiom and on 'Generalizing Deduction']. Księga pamiątkowa Polskiego Towarzystwa Filozoficznego We Lwowie, 12. II. 1904–1912. II. 1929 (in Polish). Lwów: Wydawnictwo Polskie Towarzystwo Filozoficzne. pp. 366–383.
  6. ^ a b Łukasiewicz, Jan (1970). "Comments on Nicod's Axiom and on 'Generalizing Deduction'". In Borkowski, L. (ed.). Selected Works. Amsterdam and London/Warszawa: North-Holland Publishing Company/Polish Scientific Publishers. pp. 179–196.
  7. ^ Main, Michael (2006). Data structures and other objects using Java (3 ed.). Pearson PLC Addison-Wesley. p. 334. ISBN 978-0-321-37525-4.
  8. ^ Łukasiewicz, Jan (1929). "O znaczeniu i potrzebach logiki matematycznej". Nauka Polska (in Polish). 10: 604–620.
  9. ^ Pogorzelski, Henry Andrew (September 1965). "Reviewed work(s): Remarks on Nicod's Axiom and on "Generalizing Deduction" by Jan Łukasiewicz, Jerzy Słupecki, Państwowe Wydawnictwo Naukowe". The Journal of Symbolic Logic (Review). 30 (3). Association for Symbolic Logic: 376–377. JSTOR 2269644. (NB. The original 1931 paper "Uwagi o aksjomacie Nicoda i 'dedukcji uogólniającej" by Jan Łukasiewicz was re-published at Państwowe Wydawnictwo Naukowe (National Scientific Publishers), Warsaw, Poland in 1961 in a volume edited by Jerzy Słupecki.)
  10. ^ Schönfinkel, Moses (1924). "Über die Bausteine der mathematischen Logik" [On the building blocks of mathematical logic]. Mathematische Annalen (in German). 92 (3–4): 305–316. doi:10.1007/BF01448013. S2CID 118507515; van Heijenoort, Jean, ed. (1967). "On the building blocks of mathematical logic". A Source Book in Mathematical Logic, 1879–1931. Translated by Bauer-Mengelberg, Stefan [in Dutch]. Harvard University Press. pp. 355–366.
  11. ^ Gottschall, Christian (2005). Logische Notationen und deren Verarbeitung auf elektronischen Rechenanlagen aus theoretischer, praktischer und historischer Sicht (Diploma thesis) (in German). Vienna, Austria. p. 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, also auch keine genauere Zeitangabe geben.{{cite book}}: CS1 maint: location missing publisher (link)
  12. ^ Church, Alonzo (1944). Introduction to Mathematical Logic. Princeton, New Jersey, USA: Princeton University Press. p. 38. […] Worthy of remark is the parenthesis-free notation of Jan Łukasiewicz. In this the letters N, A, C, E, K are used in the roles of negation, disjunction, implication, equivalence, conjunction respectively. […]
  13. ^ Łukasiewicz, Jan; Tarski, Alfred (1930). "Untersuchungen über den Aussagenkalküls" [Investigations into the Sentential Calculus]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (in German). 23 (Cl. III): 30–50.
  14. ^ Martínez Nava, Xóchitl (2011-06-01), "Mhy bib I fail logic? Dyslexia in the teaching of logic", in Blackburn, Patrick; van Ditmarsch, Hans; Manzano, Maria; Soler-Toscano, Fernando (eds.), Tools for Teaching Logic: Third International Congress, TICTTL 2011, Salamanca, Spain, 1–4 June 2011, Proceedings, 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, […] Polish or prefix notation has come to disuse given the difficulty that using it implies. […]
  15. ^ a b Łukasiewicz, Jan (1939). "Der Äquivalenzenkalkül". Collectanea Logica (in German). 1: 145–169.
  16. ^ Łukasiewicz, Jan (1930). "Untersuchungen über den Aussagenkalküls" [Investigations into the Sentential Calculus]. Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (in German). 23 (Cl. III): 51–77.
  17. ^ a b Łukasiewicz, Jan (1953). "A System of Modal Logic". The Journal of Computing Systems. 3 (1): 111–149.
  18. ^ Bocheński, Józef Maria (1949). Written at Fribourg. Précis de logique mathématique (PDF). Collection Synthese (in French). Vol. 2. Bussum, Pays-Bas, Netherlands: F. G. Kroonder. Archived (PDF) from the original on 2023-08-03. Retrieved 2023-11-12. Translated as Bocheński, Józef Maria (1959). A Precis of Mathematical Logic. Translated by Bird, Otto A. [at Wikidata]. Dordrecht, Netherlands: D. Reidel Publishing Company.
  19. ^ "Google Code Archive - Long-term storage for Google Code Project Hosting". Archived from the original on 2017-09-28. Retrieved 2022-11-14.
  20. ^ "LDAP Filter Syntax". Archived from the original on 2022-10-14. Retrieved 2022-11-14.
  21. ^ "HP calculators - HP 35s RPN Mode" (PDF). Hewlett-Packard. Archived (PDF) from the original on 2022-01-21. Retrieved 2022-11-14.

Further reading

[edit]
[edit]