Polnische Notation

Polnische Notation (Pn), auch bekannt als Normale polnische Notation (Npn),^[1] ŁukaSiewicz Notation, Warschauer Notation, Polnisches Präfixnotation oder einfach Präfixnotation, ist eine mathematische Notation, in der Betreiber vorausgehen ihr Operandenim Gegensatz zu den häufigeren Infixnotation, in welchen Betreibern platziert werden zwischen Operanden ebenso wie Polnische Notation umgekehrt (RPN), in welchem Betreiber Folgen ihre Operanden. Es braucht keine Klammern, solange jeder Bediener einen festen Bestand hat Anzahl der Operanden. Die Beschreibung "Politur" bezieht sich auf die Staatsangehörigkeit von Logiker Jan łukasiewicz,^[2]^[3]^[4]^[5] der 1924 polnische Notation erfunden hat.^[6]^[7]

Der Begriff Polnische Notation wird manchmal genommen (als Gegenteil von Infixnotation) auch umgekehrte polnische Notation einbeziehen.^[8]

Wenn die polnische Notation als Syntax für mathematische Ausdrücke verwendet wird Programmiersprache Dolmetscher, es ist leicht analysiert Abstrakte Syntaxbäume und kann tatsächlich a definieren Eins-zu-eins-Darstellung für das Selbe. Aus diesem Grund, Lispeln (siehe unten) und verwandte Programmiersprachen definieren ihre gesamte Syntax in der Präfixnotation (und andere verwenden Postfix -Notation).

Geschichte

Ein Zitat aus einem Papier von Jan łukasiewicz, Anmerkungen zu Nicods Axiom und zum "Verallgemeinerungsabzug", Seite 180, gibt an, wie die Notation erfunden wurde:

Ich stieß 1924 auf die Idee einer unterenthaltsfreien Notation. Ich habe diese Notation zum ersten Mal in meinem Artikel łukaSiewicz (1), p. 610, Fußnote.

Die von łukasiewicz zitierte Referenz ist anscheinend ein lithografierter Bericht in Polieren. Das überweisende Papier von łukasiewicz Anmerkungen zu Nicods Axiom und zum "Verallgemeinerungsabzug" wurde von bewertet von Henry A. Pogorzelski in dem Zeitschrift für symbolische Logik 1965.^[9] Heinrich Behmann, Herausgeber von 1924 des Artikels von Moses Schönfinkel,^[10] hatte bereits die Idee, Klammern in logischen Formeln zu beseitigen.

Alonzo -Kirche erwähnt diese Notation in seinem klassischen Buch über Mathematische Logik als bemerkenswerte Bemerkung in notationalen Systemen sogar im Gegensatz zu Gegenstand zu Alfred Whitehead und Bertrand Russelllogische Notationsausstellung und arbeiten in Principia Mathematica.^[11]

In łukasiewicz 'Buch von 1951, Buch, Aristoteles syllogistisch vom Standpunkt der modernen formalen LogikEr erwähnt, dass das Prinzip seiner Notation darin bestand, das zu schreiben Funkern Vor dem Argumente Um Klammern zu vermeiden und seine Notation seit 1929 in seinen logischen Papieren eingesetzt zu haben.^[3] Anschließend zitiert er als Beispiel eine Zeitung von 1930, mit der er schrieb Alfred Tarski auf der Sential Calculus.^[12]

Während nicht viel in der Logik verwendet wird,^[13] Die polnische Notation hat seitdem einen Platz in gefunden Informatik.

Erläuterung

Der Ausdruck für das Hinzufügen der Zahlen 1 und 2 ist in polnischer Notation als + 1 2 (Präfix) und nicht als als 1 + 2 (Infix). In komplexeren Ausdrücken gehen die Betreiber immer noch ihren Operanden voraus, aber die Operanden können selbst Ausdruck sein, einschließlich der Betreiber und deren Operanden. Zum Beispiel der Ausdruck, der in der konventionellen Infix -Notation geschrieben wird

(5 - 6) × 7

kann in polnischer Notation als geschrieben werden als

× ( - 5 6) 7

Annahme eines gegebenen Arity Von allen beteiligten Operatoren (hier bezeichnet das "-" den binären Subtraktionsbetrieb und nicht die unäre Funktion des Vorzeichenwechsels), jede gut geformte Präfixdarstellung ist eindeutig, und Klammern innerhalb des Präfix-Ausdrucks sind unnötig. Daher kann der obige Ausdruck weiter vereinfacht werden zu

× - 5 6 7

Die Verarbeitung des Produkts wird aufgeschoben, bis seine beiden Operanden verfügbar sind (d. H. 5 minus 6 und 7). Wie mit irgendein Notation, die innersten Ausdrücke werden zuerst bewertet, aber in polnischer Notation kann diese "innerste Ness" eher von der Abfolge von Operatoren und Operanden als durch Klammern vermittelt werden.

In der konventionellen Infix -Notation müssen Klammern den Standard überschreiben VorrangregelnDa sich auf das obige Beispiel bezieht, bewegt sie sie

5 - (6 × 7)

oder sie entfernen

5 - 6 × 7

ändert die Bedeutung und das Ergebnis des Ausdrucks. Diese Version ist in polnischer Notation als geschrieben als

- 5 × 6 7.

Beim Umgang mit nichtkommutativen Operationen wie Teilung oder Subtraktion ist es notwendig, die sequentielle Anordnung der Operanden mit der Definition zu koordinieren, wie der Bediener seine Argumente nimmt, d. H. Von links nach rechts. Zum Beispiel, ÷ 10 5, mit 10 links bis 5, hat die Bedeutung von 10 ÷ 5 (als "Division 10 x 5" gelesen) oder - 7 6mit 7 links bis 6 die Bedeutung von 7 - 6 (als "Subtrahieren von 7 der Operand 6").

Bewertungsalgorithmus

Präfix/Postfix -Notation ist besonders beliebt für seine angeborene Fähigkeit, die beabsichtigte Ordnung der Operationen auszudrücken, ohne dass Klammern und andere Vorrangregeln erforderlich sind, wie normalerweise mit Infixnotation. Stattdessen gibt die Notation eindeutig an, welchen Operator zuerst bewertet werden soll. Es wird angenommen, dass die Betreiber eine feste Stelle haben Arity Jedes und alle notwendigen Operanden werden als explizit angenommen. Ein gültiger Präfixausdruck beginnt immer mit einem Operator und endet mit einem Operanden. Die Bewertung kann entweder von links nach rechts oder in die entgegengesetzte Richtung gehen. Ab links wird die Eingangszeichenfolge, die aus Token besteht, die Operatoren oder Operanden bezeichnet Stapel, bis die oberen Einträge des Stapels die Anzahl der Operanden enthalten, die zum obersten obersten Operator (unmittelbar unten) passt. Diese Gruppe von Token am Stacktop (der letzte gestapelte Bediener und die Anzahl der Operanden) wird durch das Ergebnis der Ausführung des Bedieners für diese/diese Operanden ersetzt. Dann wird die Verarbeitung der Eingabe auf diese Weise fortgesetzt. Der operierte Operand in einem gültigen Präfixexpression wird somit den Stapel entleert, mit Ausnahme des Ergebniss der Bewertung des gesamten Ausdrucks. Wenn Sie rechts anfangen, wird das Drücken von Token ähnlich durchgeführt, nur die Bewertung wird von einem Bediener ausgelöst, wodurch die entsprechende Anzahl von Operanden findet, die zu seiner Arität bereits auf dem Stacktop passt. Jetzt muss das Token eines gültigen Präfixausdrucks ein Operator sein, der an die Anzahl der Operanden im Stapel passt, was das Ergebnis erneut ergibt. Wie aus der Beschreibung ersichtlich ist, a Push-Down-Laden ohne die Fähigkeit einer willkürlichen Stapelinspektion ausreicht, um dies umzusetzen Parsing.

Die oben skizzierte Stapelmanipulation funktioniert - mit gespiegelten Eingaben - sowie für Ausdrücke in Polnische Notation umgekehrt.

Polnische Notation für die Logik

Die folgende Tabelle zeigt den Kern von Jan łukasiewiczNotation für Sential Logic.^[14] Einige Buchstaben in der polnischen Notationstabelle stehen für bestimmte Wörter in Polieren, wie gezeigt:

Konzept	Konventionell Notation	Polieren Notation	Polieren Begriff
Negation	${\ displayStyle \ neg \ varphi}$	${\ displayStyle \ mathrm {n} \ varphi}$	negacja
Verbindung	${\ displaystyle \ varphi \ land \ psi}$	${\ displayStyle \ mathrm {k} \ varphi \ psi}$	koniunkcja
Disjunktion	${\ displaystyle \ varphi \ lor \ psi}$	${\ displayStyle \ mathrm {a} \ varphi \ psi}$	alternatywa
Material bedingt	${\ displaystyle \ varphi \ to \ psi}$	${\ displayStyle \ mathrm {c} \ varphi \ psi}$	implikacja
Zweikonditionell	${\ displaystyle \ varphi \ leftrightarrow \ psi}$	${\ displayStyle \ mathrm {e} \ varphi \ psi}$	ekwiwalencja
Falsum	${\ displayStyle \ bot}$	${\ displayStyle \ mathrm {o}}$	fałsz
Sheffer Schlaganfall	${\ displayStyle \ varphi \ mid \ psi}$	${\ displayStyle \ mathrm {d} \ varphi \ psi}$	dysjunkcja
Wahrscheinlichkeit	${\ displayStyle \ diamond \ varphi}$	${\ displayStyle \ mathrm {m} \ varphi}$	możliwość
Notwendigkeit	${\ displayStyle \ box \ varphi}$	${\ displayStyle \ mathrm {l} \ varphi}$	konieczność
Universeller Quantifizierer	${\ displaystyle \ forall p \, \ varphi}$	${\ displaystyle \ pi p \, \ varphi}$	kwantyfikator ogólny
Existenzieller Quantifizierer	${\ displayStyle \ existiert p \, \ varphi}$	${\ displaystyle \ sigma p \, \ varphi}$	kwantyfikator szczegółowy

Notiere dass der Quantifizierer über die Aussagewerte in łukasiewicz 'Arbeit über viele bewertete Logiken reicht.

Bocheński stellte ein System der polnischen Notation ein, das alle 16 binären Namen nennt Verbindungen von klassisch Aussagelogik. Für die klassische Aussagelogik ist es eine kompatible Erweiterung der Notation von łukasiewicz. Die Notationen sind jedoch in dem Sinne nicht kompatibel, dass Bocheński L und M (zur Nichtimplikation und der Umkehrung der Nichtimplikation) in der Propositionslogik verwendet, und łukaSiewicz verwendet L und M in der modalen Logik.^[15]

Implementierungen

Präfixnotation hat eine breite Anwendung in Lispeln S-Expressionen, wo die Klammern erforderlich sind, da die Operatoren in der Sprache selbst Daten sind (Daten sinderstklassige Funktionen). Lisp -Funktionen können auch sein variadisch. Das Tcl Die Programmiersprache verwendet, ähnlich wie Lisp, auch polnische Notation durch die Mathop -Bibliothek. Der Ambi^[16] Die Programmiersprache verwendet polnische Notation für arithmetische Operationen und Programmkonstruktion. LDAP Die Filtersyntax verwendet polnisches Präfixnotation.^[17]

Postfix -Notation wird in vielen verwendet Stack-orientierte Programmiersprachen wie PostScript und Weiter. CoffeeScript Mit der Syntax können Funktionen auch mithilfe von Präfixnotation aufgerufen werden, während die unary Postfix -Syntax in anderen Sprachen gleichzeitig unterstützt wird.

Die Anzahl der Rückgabewerte eines Ausdrucks entspricht der Differenz zwischen der Anzahl der Operanden in einem Ausdruck und der Gesamtarität der Operatoren abzüglich der Gesamtzahl der Rückgabewerte der Operatoren.

Die polnische Notation, normalerweise in Postfixform, ist die gewählte Notation bestimmter Taschenrechner, insbesondere von Hewlett Packard.^[18] Auf einer niedrigeren Ebene werden Postfix -Operatoren von einigen verwendet Stapelmaschinen so wie die Burroughs große Systeme.

Siehe auch

Verweise

^ Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithen der Mikrorechentechnik [Arithmetische Algorithmen in Mikrocomputern] (auf Deutsch) (1 Ed.). Berlin, Deutschland: Veb Verlag Technik. ISBN 3-34100515-3. Ean 978-3-34100515-6. MPN 5539165. Lizenz 201.370/4/89. Abgerufen 2015-12-01.
^ ŁukaSiewicz, Jan (Februar 1929). Elementy Logiki Matematycznej (in polnischer) (1 ed.). Warschau, Polen: Państwewe Wydawnictwo Naukowe; ŁukaSiewicz, Jan (1963). Elemente der mathematischen Logik. Übersetzt von Wojtasiewicz, Olgierd Adrian. New York, USA: Die Macmillan Company. p. 24.
^ ^a ^b ŁukaSiewicz, Jan (1951). "Kapitel IV. Aristoteles System in symbolischer Form (Abschnitt über" Erklärung der Symbolik ")". Aristoteles syllogistisch vom Standpunkt der modernen formalen Logik (1 ed.). p. 78.
^ ŁukaSiewicz, Jan (1957). Aristoteles syllogistisch vom Standpunkt der modernen formalen Logik (2 ed.). Oxford University Press. (Nachdruck von Garland Publishing im Jahr 1987 ISBN0-8240-6924-2.))
^ Kennedy, John (August 1982). "RPN Perspektive". PPC Calculator Journal. Mathematikabteilung, Santa Monica College, Santa Monica, Kalifornien, USA. 9 (5): 26–29. Archiviert vom Original am 2022-07-01. Abgerufen 2022-07-02. (12 Seiten)
^ Hamblin, Charles Leonard (1962). "Übersetzung von und von polnischer Notation". Computerjournal. 5 (3): 210–213. doi:10.1093/comjnl/5.3.210.
^ Ball, John A. (1978). Algorithmen für RPN -Taschenrechner (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8.
^ Main, Michael (2006). Datenstrukturen und andere Objekte mit Java (3. Aufl.). Pearson plc Addison-Wesley. p. 334. ISBN 978-0-321-37525-4.
^ Pogorzelski, Henry A., "Bewertete Arbeiten): Bemerkungen zu Nicods Axiom und zu" Verallgemeinerung des Abzugs "von Jan łukasiewicz; Jerzy Słupecki;, Das Journal of Symbolic Logic, Vol. 30, Nr. 3 (September 1965), S. 376–377. Das Originalpapier von łukasiewicz wurde veröffentlicht in Warschau 1961 in einem von Jerzy Słupecki herausgegebenen Band.
^ "Über Die Baateine der Mathematischen Logik", Mathematische Annalen 92, Seiten 305–316. Übersetzt von Stefan Bauer Mengelberg als "auf den Bausteinen der mathematischen Logik" in Jean van Heijenoort, 1967. Ein Quellbuch in mathematischer Logik, 1879–1931. Harvard University Press: 355–366.
^ Kirche, Alonzo (1944). Einführung in die mathematische Logik. Princeton, New Jersey, USA: Princeton University Press. p. 38. […] Bemerkenswert ist die parenthesisfreie Notation von Jan łukasiewicz. Darin werden die Buchstaben N, A, C, E, K in den Rollen von Negation, Disjunktion, Implikation, Äquivalenz, Konjunktion verwendet. […]
^ ŁukaSiewicz, Jan; Tarski, Alfred, "Intersuchungen über den Ausagenkalkül" ["Untersuchungen zum sententialen Kalkül"],] COMPTES Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Vol. 23 (1930) Cl. III, S. 31–32.
^ Martínez Nava, Xóchitl (2011-06-01), "My Bib I Fail Logic? Legasthenie in der Lehre der Logik", in Blackburn, Patrick; Van Ditmarsch, Hans; Manzano, Maria; Soler-Toscano, Fernando (Hrsg.), Instrumente für die Lehrlogik: Dritter internationaler Kongress, Ticttl 2011, Salamanca, Spanien, 1. bis 4. Juni 2011, Proceedings, Vorlesungen in der künstlichen Intelligenz, Vol. 6680, Springer Natur, S. 162–169, doi:10.1007/978-3-642-21350-2_19, ISBN 978-3-64221349-6, […] Polnische oder Präfixnotation ist angesichts der Schwierigkeiten, die sie verwenden, nicht zu veranlassen. […]
^ Craig, Edward (1998), Routledge -Enzyklopädie der Philosophie, Band 8, Taylor & Francis, p. 496, ISBN 978-0-41507310-3.
^ Bocheński, Józef Maria (1959). Eine Präzision der mathematischen Logik, übersetzt von Otto Bird aus den französischen und deutschen Ausgaben, D. Reidel: Dordrecht, Holland.
^ "Google Code Archiv - Langzeitspeicher für Google Code -Projekthosting".
^ "LDAP -Filtersyntax".
^ "HP -Taschenrechner | HP 35s RPN -Modus " (PDF). Hewlett Packard.

Weitere Lektüre

ŁukaSiewicz, Jan (1930). "Philosophische Bemerkungen zu Mehrwertigen Systemen des Ausagenkalküls" [Philosophische Bemerkungen zu vielen bewerteten Systemen der Subjektlogik]. COMPTES Rendus des Séances de la Société des Sciences et des Lettres de Varsovie (auf Deutsch). 23: 51–77. Übersetzt von H. Weber in Storrs McCall, Polnische Logik 1920–1939, Clarendon Press: Oxford (1967).

Externe Links

Medien im Zusammenhang mit polnischer Notation (Mathematik) bei Wikimedia Commons

[Jorke_1989-1] Jorke, Günter; Lampe, Bernhard; Wengel, Norbert (1989). Arithmetische Algorithen der Mikrorechentechnik [Arithmetische Algorithmen in Mikrocomputern] (auf Deutsch) (1 Ed.). Berlin, Deutschland: Veb Verlag Technik. ISBN 3-34100515-3. Ean 978-3-34100515-6. MPN 5539165. Lizenz 201.370/4/89. Abgerufen 2015-12-01.

[Łukasiewicz_1929-2] ŁukaSiewicz, Jan (Februar 1929). Elementy Logiki Matematycznej (in polnischer) (1 ed.). Warschau, Polen: Państwewe Wydawnictwo Naukowe; ŁukaSiewicz, Jan (1963). Elemente der mathematischen Logik. Übersetzt von Wojtasiewicz, Olgierd Adrian. New York, USA: Die Macmillan Company. p. 24.

[Łukasiewicz_1951-3] ŁukaSiewicz, Jan (1951). "Kapitel IV. Aristoteles System in symbolischer Form (Abschnitt über" Erklärung der Symbolik ")". Aristoteles syllogistisch vom Standpunkt der modernen formalen Logik (1 ed.). p. 78.

[Łukasiewicz_1957-4] ŁukaSiewicz, Jan (1957). Aristoteles syllogistisch vom Standpunkt der modernen formalen Logik (2 ed.). Oxford University Press. (Nachdruck von Garland Publishing im Jahr 1987 ISBN0-8240-6924-2.))

[Kennedy_1982-5] Kennedy, John (August 1982). "RPN Perspektive". PPC Calculator Journal. Mathematikabteilung, Santa Monica College, Santa Monica, Kalifornien, USA. 9 (5): 26–29. Archiviert vom Original am 2022-07-01. Abgerufen 2022-07-02. (12 Seiten)

[Hamblin_1962-6] Hamblin, Charles Leonard (1962). "Übersetzung von und von polnischer Notation". Computerjournal. 5 (3): 210–213. doi:10.1093/comjnl/5.3.210.

[Ball_1978-7] Ball, John A. (1978). Algorithmen für RPN -Taschenrechner (1 ed.). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8.

[Main_2006-8] Main, Michael (2006). Datenstrukturen und andere Objekte mit Java (3. Aufl.). Pearson plc Addison-Wesley. p. 334. ISBN 978-0-321-37525-4.

[Pogorzelski_1965-9] Pogorzelski, Henry A., "Bewertete Arbeiten): Bemerkungen zu Nicods Axiom und zu" Verallgemeinerung des Abzugs "von Jan łukasiewicz; Jerzy Słupecki;, Das Journal of Symbolic Logic, Vol. 30, Nr. 3 (September 1965), S. 376–377. Das Originalpapier von łukasiewicz wurde veröffentlicht in Warschau 1961 in einem von Jerzy Słupecki herausgegebenen Band.

[Mengelberg-10] "Über Die Baateine der Mathematischen Logik", Mathematische Annalen 92, Seiten 305–316. Übersetzt von Stefan Bauer Mengelberg als "auf den Bausteinen der mathematischen Logik" in Jean van Heijenoort, 1967. Ein Quellbuch in mathematischer Logik, 1879–1931. Harvard University Press: 355–366.

[Church_1944-11] Kirche, Alonzo (1944). Einführung in die mathematische Logik. Princeton, New Jersey, USA: Princeton University Press. p. 38. […] Bemerkenswert ist die parenthesisfreie Notation von Jan łukasiewicz. Darin werden die Buchstaben N, A, C, E, K in den Rollen von Negation, Disjunktion, Implikation, Äquivalenz, Konjunktion verwendet. […]

[Łukasiewicz_1930-12] ŁukaSiewicz, Jan; Tarski, Alfred, "Intersuchungen über den Ausagenkalkül" ["Untersuchungen zum sententialen Kalkül"],] COMPTES Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Vol. 23 (1930) Cl. III, S. 31–32.

[Martínez_2011-13] Martínez Nava, Xóchitl (2011-06-01), "My Bib I Fail Logic? Legasthenie in der Lehre der Logik", in Blackburn, Patrick; Van Ditmarsch, Hans; Manzano, Maria; Soler-Toscano, Fernando (Hrsg.), Instrumente für die Lehrlogik: Dritter internationaler Kongress, Ticttl 2011, Salamanca, Spanien, 1. bis 4. Juni 2011, Proceedings, Vorlesungen in der künstlichen Intelligenz, Vol. 6680, Springer Natur, S. 162–169, doi:10.1007/978-3-642-21350-2_19, ISBN 978-3-64221349-6, […] Polnische oder Präfixnotation ist angesichts der Schwierigkeiten, die sie verwenden, nicht zu veranlassen. […]

[Craig_1998-14] Craig, Edward (1998), Routledge -Enzyklopädie der Philosophie, Band 8, Taylor & Francis, p. 496, ISBN 978-0-41507310-3.

[Bocheński_1959-15] Bocheński, Józef Maria (1959). Eine Präzision der mathematischen Logik, übersetzt von Otto Bird aus den französischen und deutschen Ausgaben, D. Reidel: Dordrecht, Holland.

[Ambi-16] "Google Code Archiv - Langzeitspeicher für Google Code -Projekthosting".

[LDAPSyntax-17] "LDAP -Filtersyntax".

[RPN_HP35S-18] "HP -Taschenrechner | HP 35s RPN -Modus " (PDF). Hewlett Packard.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]