Polnische Notation, auch bekannt als polnische Präfix-Notation oder einfach Präfix-Notation, ist eine Form der Notation für die Logik, Arithmetik und Algebra. Sein Unterscheidungsmerkmal ist, dass es Maschinenbediener links von ihrem operands legt. Wenn der arity der Maschinenbediener befestigt wird, ist das Ergebnis eine Syntax, die an Parenthesen oder anderen Klammern Mangel hat, die noch ohne Zweideutigkeit grammatisch analysiert werden können. Der polnische Logiker Jan Łukasiewicz hat diese Notation 1920 erfunden, um sentential Logik zu vereinfachen.

Die polnische Begriff-Notation wird manchmal (als das Gegenteil der klammerlosen Darstellung) genommen, um auch polnische Notation der postüblen Lage oder polnische Rücknotation einzuschließen, in die der Maschinenbediener nach dem operands gelegt wird.

Wenn polnische Notation als eine Syntax für mathematische Ausdrücke von Dolmetschern von Programmiersprachen verwendet wird, wird sie in abstrakte Syntax-Bäume sogleich grammatisch analysiert und kann tatsächlich eine isomorphe Darstellung für dasselbe definieren. Wegen dessen definieren Lispeln (sieh unten) und verwandte Programmiersprachen ihre komplette Syntax in Bezug auf die Präfix-Notation (und andere verwenden Notation der postüblen Lage).

Hier ist ein Kostenvoranschlag von einem Vortrag von Jan Łukasiewicz, Bemerkungen auf dem Axiom von Nicod und bei der "Generalisierung des Abzugs", der Seite 180.

Die Verweisung, die von Jan Łukasiewicz oben zitiert ist, ist anscheinend ein lithographierter Bericht in Polnisch. Der sich beziehende Vortrag von Łukasiewicz-Bemerkungen auf dem Axiom von Nicod und bei der "Generalisierung des Abzugs" wurde von H. A. Pogorzelski in der Zeitschrift der Symbolischen Logik 1965 nachgeprüft.

Kirche von Alonzo erwähnt diese Notation in seinem klassischen Buch auf der Mathematischen Logik als würdig der Bemerkung in notational Systemen, die sogar zu Whiteheads logischer notational Ausstellung und Russells und Arbeit in Principia Mathematica gegenübergestellt sind.

Im Łukasiewicz 1951-Buch, von der Einstellung der Modernen Formalen Logik Syllogistischer Aristoteles, erwähnt er, dass der Grundsatz seiner Notation den functors vor den Argumenten schreiben sollte, um Klammern zu vermeiden, und dass er seine Notation in seinen logischen Zeitungen seit 1929 verwendet hatte. Er setzt dann fort, als ein Beispiel, eine 1930-Zeitung zu zitieren, die er mit Alfred Tarski über die sentential Rechnung geschrieben hat.

Während nicht mehr nicht verwendet, viel in der Logik hat polnische Notation einen Platz in der Informatik seitdem gefunden.

Arithmetik

Der Ausdruck, für die Nummern 1 und 2 hinzuzufügen, ist in der Präfix-Notation, schriftlich "+ 1 2" aber nicht "1 + 2". In komplizierteren Ausdrücken gehen die Maschinenbediener noch ihrem operands voran, aber der operands kann selbst nichttriviale Ausdrücke einschließlich Maschinenbediener ihres eigenen sein. Zum Beispiel, der Ausdruck, der in der herkömmlichen klammerlosen Darstellung als geschrieben würde

: (5  6) * 7

kann im Präfix als geschrieben werden

: * ( 5 6) 7

Da die einfachen arithmetischen Maschinenbediener die ganze Dualzahl sind (mindestens, in arithmetischen Zusammenhängen), ist jede Präfix-Darstellung davon eindeutig, und das Einklammern des Präfix-Ausdrucks ist unnötig. Als solcher kann der vorherige Ausdruck weiter zu vereinfacht werden

: *  5 6 7

Die Verarbeitung des Produktes wird aufgeschoben, bis seine zwei operands (d. h., 5 minus 6, und 7) verfügbar sind. Als mit jeder Notation werden die innersten Ausdrücke zuerst bewertet, aber in der Präfix-Notation können diese "Innerkeiten" durch die Ordnung anstatt des Einklammerns befördert werden.

In der klassischen Notation waren die Parenthesen in der Infix-Version, seit dem Bewegen von ihnen erforderlich

: 5  (6 * 7)

oder einfach das Entfernen von ihnen

: 5  6 * 7

würde die Bedeutung und das Ergebnis des gesamten Ausdrucks wegen der Prioritätsregel ändern.

Computerprogrammierung

Präfix-Notation hat breite Anwendung in Lispeln-S-Ausdrücken gesehen, wo die Klammern wegen der arithmetischen Maschinenbediener erforderlich sind, die Variable arity haben. Die Ambi Programmiersprache verwendet polnische Notation für arithmetische Operationen und Programm-Aufbau. Die Rückseite der postüblen Lage wird polnische Notation auf vielen Stapel-basierten Programmiersprachen wie PostScript und Hervor verwendet, und ist der Betriebsgrundsatz von bestimmten Rechenmaschinen namentlich von Hewlett Packard.

Die Zahl von Rückwerten eines Ausdrucks kommt dem Unterschied zwischen der Zahl von operands in einem Ausdruck und dem ganzen arity der Maschinenbediener minus die Gesamtzahl von Rückwerten der Maschinenbediener gleich.

Ordnung von Operationen

Die Ordnung von Operationen wird innerhalb der Struktur der Präfix-Notation definiert und kann leicht bestimmt werden. Ein Ding zu beachten besteht darin, dass, wenn man eine Operation durchführt, die Operation auf den ersten operand durch den zweiten operand angewandt wird. Das ist nicht ein Problem mit Operationen, die pendeln, aber für Nichtersatzoperationen wie Abteilung oder Subtraktion, ist diese Tatsache für die Analyse einer Behauptung entscheidend. Zum Beispiel, die folgende Behauptung:

/ 10 5 = 2 (Präfix)

wird gelesen, weil Sich "10 DURCH 5 Teilen". So ist die Lösung 2, nicht ½, wie das Ergebnis einer falschen Analyse sein würde.

Präfix-Notation ist bei Stapel-basierten Operationen wegen seiner angeborenen Fähigkeit besonders populär, Ordnung von Operationen ohne das Bedürfnis nach Parenthesen leicht zu unterscheiden. Um Ordnung von Operationen laut der Präfix-Notation zu bewerten, braucht man sich keine betriebliche Hierarchie, als mit der klammerlosen Darstellung sogar einzuprägen. Statt dessen schaut man direkt zur Notation, um der Maschinenbediener zu entdecken, zuerst zu bewerten. Einen Ausdruck vom linken bis Recht lesend, sucht ein erster nach einem Maschinenbediener und fährt fort, nach zwei operands zu suchen. Wenn ein anderer Maschinenbediener gefunden wird, bevor zwei operands gefunden werden, dann wird der alte Maschinenbediener beiseite gelegt, bis dieser neue Maschinenbediener aufgelöst wird. Dieser Prozess wiederholt, bis ein Maschinenbediener aufgelöst wird, der schließlich geschehen muss, weil es einen mehr operand geben muss als, gibt es Maschinenbediener in einer ganzen Behauptung. Einmal aufgelöst werden der Maschinenbediener und die zwei operands durch einen neuen operand ersetzt. Weil ein Maschinenbediener und zwei operands entfernt werden und ein operand hinzugefügt wird, gibt es einen Nettoverlust eines Maschinenbedieners und eines operand, der noch einen Ausdruck mit N Maschinenbedienern und N+1 operands verlässt, so dem wiederholenden Prozess erlaubend, weiterzugehen. Das ist die allgemeine Theorie hinter dem Verwenden von Stapeln auf Programmiersprachen, um eine Behauptung in der Präfix-Notation zu bewerten, obwohl es verschiedene Algorithmen gibt, die den Prozess manipulieren. Einmal analysiert wird eine Behauptung in der Präfix-Notation weniger Einschüchtern-für den Menschenverstand, weil es eine Trennung aus der Tagung mit der zusätzlichen Bequemlichkeit erlaubt. Ein Beispiel zeigt die Bequemlichkeit, mit der eine komplizierte Behauptung in der Präfix-Notation durch die Ordnung von Operationen entziffert werden kann:

- * / 15 - 7 + 1 1 3 + 2 + 1 1 =

- * / 15 - 7 2 3 + 2 + 1 1 =

- * / 15 5 3 + 2 + 1 1 =

- * 3 3 + 2 + 1 1 =

- 9 + 2 + 1 1 =

- 9 + 2 2 =

- 9 4 =

5

Ein gleichwertiges Infix ist wie folgt:

((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1)) = 5

Hier ist eine Durchführung (im Pseudocode) von der Präfix-Einschätzung mit einem Stapel. Bemerken Sie, dass unter dieser Durchführung die Eingangsschnur vom Recht bis linken gescannt wird. Das unterscheidet sich vom Algorithmus, der oben beschrieben ist, in dem die Schnur vom linken bis Recht bearbeitet wird. Beide Algorithmen schätzen denselben Wert für alle gültigen Schnuren.

Scannen Sie den gegebenen Präfix-Ausdruck vom Recht bis linken

für jedes Symbol

{\

wenn operand dann

stoßen Sie auf den Stapel

wenn Maschinenbediener dann

{\

operand1=pop schobern auf

operand2=pop schobern auf

schätzen Sie operand1 Maschinenbediener operand2

stoßen Sie Ergebnis auf den Stapel

}\

}\

geben Sie Spitze des Stapels als Ergebnis zurück

Polnische Notation für die Logik

Der Tisch zeigt unten den Kern von Jan Łukasiewicz's Notation für die sentential Logik. Die "herkömmliche" Notation ist so bis zu den 1970er Jahren und den 80er Jahren nicht geworden. Einige Briefe im polnischen Notationstisch bedeuten ein bestimmtes Wort in Polnisch, wie gezeigt:

Bemerken Sie, dass sich der quantifiers über Satzwerte in der Łukasiewicz'S-Arbeit an der vielgeschätzten Logik erstreckt hat.

Bocheński hat ein unvereinbares System der polnischen Notation eingeführt, die alle 16 binären Bindewörter der klassischen Satzlogik nennt.

Siehe auch

Kehren Sie polnische Notation um

• Funktionsanwendung
• Lambda-Rechnung
• Lispeln (Programmiersprache)
• S-Ausdruck
• Ungarische Notation

Weiterführende Literatur

• Ł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). Übersetzt von H. Weber als "Philosophische Bemerkungen auf Vielgeschätzten Systemen der Satzlogik", in Storrs McCall, polnische Logik 1920-1939, Clarendon Press: Oxford (1967).