Polnische Notation - Polish notation

Postfix-Notation ("Reverse Polish") Infix-Notation Präfix-Notation ("Polnisch")

v T e

Polnische Notation ( PN ), auch bekannt als normale polnische Notation ( NPN ), Łukasiewicz - Notation , Warschauer Notation , polnische Präfixnotation oder einfach Präfixnotation , ist eine mathematische Notation , bei der Operatoren ihren Operanden vorangehen , im Gegensatz zur üblicheren Infix - Notation . in der Operatoren zwischen Operanden platziert werden , sowie umgekehrte polnische Notation (RPN), in der Operatoren ihren Operanden folgen . Es braucht keine Klammern, solange jeder Operator eine feste Anzahl von Operanden hat . Die Bezeichnung "Polnisch" bezieht sich auf die Nationalität des Logikers Jan Łukasiewicz , der 1924 die polnische Notation erfand.

Der Begriff polnische Notation wird manchmal (als Gegenteil von Infix-Notation ) so verstanden, dass er auch die umgekehrte polnische Notation umfasst.

Wenn polnische Notation als Syntax für mathematische Ausdrücke verwendet wird , durch die Sprache der Programmierung Dolmetschers ist es leicht in analysiert abstrakte Syntaxbäume und kann in der Tat, definiert eine Eins-zu-Eins - Darstellung für das gleiche. Aus diesem Grund definieren Lisp ( siehe unten ) und verwandte Programmiersprachen ihre gesamte Syntax in Präfix-Notation (und andere verwenden Postfix-Notation).

Geschichte

Ein Zitat aus einem Aufsatz von Jan Łukasiewicz , Bemerkungen zu Nicods Axiom und zu "Generalizing Deduction" , Seite 180, gibt an, wie die Notation erfunden wurde:

Auf die Idee einer Notation ohne Klammern kam ich 1924. Diese Notation habe ich zum ersten Mal in meinem Artikel Łukasiewicz(1), S. 1 verwendet. 610, Fußnote.

Die von Łukasiewicz zitierte Referenz ist offenbar ein lithographierter Bericht in polnischer Sprache . Das darauf verweisende Papier von Łukasiewicz Remarks on Nicod's Axiom and on "Generalizing Deduction" wurde 1965 von Henry A. Pogorzelski im Journal of Symbolic Logic rezensiert . Heinrich Behmann , 1924 Herausgeber des Artikels von Moses Schönfinkel , hatte bereits die Idee, Klammern in logischen Formeln.

Alonzo Church erwähnt diese Notation in seinem klassischen Buch über mathematische Logik als bemerkenswert in Notationssystemen, die sogar im Gegensatz zu Alfred Whiteheads und Bertrand Russells logischer Notationsdarstellung und Arbeit in Principia Mathematica stehen .

In Łukasiewicz' Buch von 1951, Aristoteles's Syllogistic from the Standpoint of Modern Formal Logic , erwähnt er, dass das Prinzip seiner Notation darin bestand, die Funktoren vor den Argumenten zu schreiben , um Klammern zu vermeiden, und dass er diese Notation seit 1929 in seinen logischen Papieren verwendet führt als Beispiel eine Arbeit aus dem Jahr 1930 an, die er zusammen mit Alfred Tarski über die Aussagenkalküle verfasste .

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

Erläuterung

Der Ausdruck zum Addieren der Zahlen 1 und 2 wird in polnischer Schreibweise als + 1 2 (Präfix) und nicht als 1 + 2 (In-Fix) geschrieben. In komplexeren Ausdrücken stehen die Operatoren immer noch vor ihren Operanden, aber die Operanden können selbst Ausdrücke sein, die wieder-Operatoren und ihre Operanden enthalten. Zum Beispiel der Ausdruck, der in konventioneller Infix-Notation geschrieben würde als

(5 − 6) × 7

kann in polnischer Notation geschrieben werden als

× (− 5 6) 7

Unter der Annahme einer gegebenen Stelligkeit aller beteiligten Operatoren (hier bezeichnet das "–" die binäre Subtraktionsoperation, nicht die unäre Funktion des Vorzeichenwechsels), ist jede wohlgeformte Präfixdarstellung davon eindeutig, und Klammern innerhalb des Präfixausdrucks sind unnötig. Als solcher kann der obige Ausdruck weiter vereinfacht werden zu

× − 5 6 7

Die Verarbeitung des Produkts wird verschoben, bis seine beiden Operanden verfügbar sind (dh 5 minus 6 und 7). Wie bei jeder Notation werden die innersten Ausdrücke zuerst ausgewertet, aber in der polnischen Notation kann diese "Innerste-ness" eher durch die Folge von Operatoren und Operanden als durch Klammern vermittelt werden.

In der herkömmlichen Infix-Notation sind Klammern erforderlich, um die Standard- Vorrangregeln zu überschreiben , da sie gemäß dem obigen Beispiel verschoben werden

5 − (6 × 7)

oder sie entfernen

5 − 6 × 7

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

− 5 × 6 7 .

Bei nichtkommutativen Operationen wie Division oder Subtraktion ist es notwendig, die sequentielle Anordnung der Operanden mit der Definition der Argumentation des Operators, dh von links nach rechts, zu koordinieren. Zum Beispiel hat ÷ 10 5 , wobei 10 bis 5 übrig ist, die Bedeutung von 10 ÷ 5 (gelesen als "dividiere 10 durch 5"), oder - 7 6 , mit 7 links bis 6, hat die Bedeutung von 7 - 6 ( gelesen als "subtrahiere von 7 den Operanden 6").

Auswertealgorithmus

Die Präfix-/Postfix-Notation ist besonders beliebt wegen ihrer angeborenen Fähigkeit, die beabsichtigte Reihenfolge von Operationen auszudrücken, ohne dass Klammern und andere Vorrangregeln erforderlich sind, wie sie normalerweise bei der Infix-Notation verwendet werden . Stattdessen gibt die Notation eindeutig an, welcher Operator zuerst ausgewertet werden soll. Es wird angenommen, dass die Operatoren jeweils eine feste Arität haben, und alle notwendigen Operanden werden als explizit angegeben angenommen. Ein gültiger Präfixausdruck beginnt immer mit einem Operator und endet mit einem Operanden. Die Auswertung kann entweder von links nach rechts oder in umgekehrter Richtung erfolgen. Links beginnend wird die Eingabezeichenfolge, bestehend aus Tokens, die Operatoren oder Operanden bezeichnen, Token für Token auf einen Stack geschoben , bis die obersten Einträge des Stack die Anzahl der Operanden enthalten, die zum obersten Operator (direkt darunter) passen. Diese Gruppe von Token am Stacktop (der letzte gestapelte Operator und die entsprechende Anzahl von Operanden) wird durch das Ergebnis der Ausführung des Operators auf diesem/diesen Operanden ersetzt. Dann wird die Verarbeitung der Eingabe auf diese Weise fortgesetzt. Der am weitesten rechts stehende Operand in einem gültigen Präfixausdruck leert somit den Stack, mit Ausnahme des Ergebnisses der Auswertung des gesamten Ausdrucks. Rechts beginnend erfolgt das Pushen der Token ähnlich, lediglich die Auswertung wird durch einen Operator ausgelöst, der bereits am Stacktop die entsprechende Anzahl von Operanden findet, die seiner Arität entspricht. Nun muss das Token ganz links eines gültigen Präfix-Ausdrucks ein Operator sein, der zur Anzahl der Operanden im Stack passt, was wiederum das Ergebnis liefert. Wie aus der Beschreibung ersichtlich ist, reicht ein Push-Down-Speicher ohne die Fähigkeit zur willkürlichen Stack-Inspektion aus, um dieses Parsing zu implementieren .

Die oben skizzierte Stapelmanipulation funktioniert – bei gespiegelter Eingabe – auch für Ausdrücke in umgekehrter polnischer Notation .

Polnische Notation für Logik

Die folgende Tabelle zeigt den Kern von Jan Łukasiewiczs Notation für die Satzlogik . Einige Buchstaben in der polnischen Notationstabelle stehen für bestimmte Wörter im Polnischen , wie gezeigt:

Konzept	Konventionelle Notation	Polnische Notation	Polnischer 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
Materialbedingt	${\displaystyle\varphi\to\psi}$	${\displaystyle \mathrm {C} \varphi\psi}$	implikacja
Biconditional	${\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ść
Universalquantifizierer	${\displaystyle \forall p\,\varphi}$	${\displaystyle \Pi p\,\varphi }$	kwantyfikator ogólny
Existenzieller Quantor	${\displaystyle \exists p\,\varphi}$	${\displaystyle \Sigma p\,\varphi}$	kwantyfikator szczegółowy

Beachten Sie, dass sich die Quantoren in ukasiewicz' Arbeit über mehrwertige Logiken über propositionale Werte erstreckten.

Bocheński führte ein System der polnischen Notation ein, das alle 16 binären Konnektoren der klassischen Aussagenlogik benennt . Für die klassische Aussagenlogik ist es eine kompatible Erweiterung der Notation von Łukasiewicz. Aber die Notationen sind insofern inkompatibel, als Bocheński L und M (für Nichtimplikation und umgekehrte Nichtimplikation) in der Aussagenlogik verwendet und Łukasiewicz L und M in der Modallogik verwendet.

Implementierungen

Die Präfixnotation hat eine breite Anwendung in Lisp- S-Ausdrücken gefunden , wo die Klammern erforderlich sind, da die Operatoren in der Sprache selbst Daten sind ( erstklassige Funktionen ). Lisp-Funktionen können auch variadisch sein . Die Programmiersprache Tcl verwendet, ähnlich wie Lisp, auch die polnische Notation über die Mathop-Bibliothek. Die Programmiersprache Ambi verwendet die polnische Notation für arithmetische Operationen und die Programmkonstruktion. Die LDAP- Filtersyntax verwendet die polnische Präfixnotation.

Die Postfix-Notation wird in vielen stapelorientierten Programmiersprachen wie PostScript und Forth verwendet . Die CoffeeScript- Syntax ermöglicht auch den Aufruf von Funktionen mit Präfix-Notation, während die in anderen Sprachen übliche unäre Postfix-Syntax unterstützt wird.

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

Die polnische Notation, normalerweise in Postfix-Form, ist die gewählte Notation bestimmter Taschenrechner , insbesondere von Hewlett-Packard . Auf einer niedrigeren Ebene werden Postfix-Operatoren von einigen Stapelmaschinen wie den großen Systemen von Burroughs verwendet .

Siehe auch

• Umgekehrte polnische Notation
• Funktionsanwendung
• Lambda-Kalkül
• Curry
• Lisp (Programmiersprache)
  • S-Ausdruck
• Polnische Schule für Mathematik
• Ungarische Notation
• Verb–Subjekt–Objekt (VSO)
• Verb–Objekt–Subjekt (VOS)

Verweise

Weiterlesen

• ukasiewicz, Jan (1957). Die Syllogistik des Aristoteles vom Standpunkt der modernen formalen Logik . Oxford University Press .
• ukasiewicz, Jan (1930). "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.Übersetzt von H. Weber in Storrs McCall, Polish Logic 1920-1939 , Clarendon Press : Oxford (1967).

Externe Links

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