Definition:Polish Notation

From ProofWiki
Jump to navigation Jump to search

Definition

Polish notation is a method of writing expressions without the need for parentheses.

The main method in writing an expression in Polish notation is to output an operator $\Box$, directly followed by the output of all its arguments $p, q, \ldots$, yielding:

$\Box p q \ldots$

If we had another, operator $\diamond$ taking only one argument, then also:

$\Box {\diamond} p {\diamond} q \ldots$

is in Polish notation.

Note that for the applicability of Polish notation, it is vital to be able to efficiently distinguish an argument from an operator, or a sequence of arguments.


Formal Definition

Let $\AA$ be an alphabet.

Let each $s \in \AA$ be assigned a natural number called its arity.


The formal grammar for Polish notation is given by the single bottom-up rule:

If $s$ has arity $n$ and $\phi_1, \ldots, \phi_n$ are well-formed formulas, then:
$s \phi_1 \cdots \phi_n$
is also a well-formed formula.


Notably, in the case where $s$ has arity $0$, this is a vacuous truth, so any such $s$ constitutes a well-formed formula.


Reverse Polish Notation

For stack-based programming languages, reverse Polish language is a useful variant of Polish notation, because it naturally coincides with how the input is to be structured for the language.

As the name suggests, a string $\mathsf P$ is in reverse Polish language if and only if reversing it gives a string $\tilde {\mathsf P}$ in Polish notation.

Thus the reverse Polish language equivalents of these examples of Polish notation:

$\Box p q \ldots$
$\Box {\diamond} p {\diamond} q \ldots$

are:

$\ldots q p \Box$
$\ldots q {\diamond} p {\diamond} \Box$



This article is complete as far as it goes, but it could do with expansion.
In particular: Could benefit from being defined in BNF or otherwise formally, as an exercise in formal languages
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


Historical Note

Polish notation, along with its variant reverse Polish notation, was developed by a group of Polish mathematicians, led by Jan Łukasiewicz who invented it in the $1920$s.


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Polish_Notation&oldid=689165"