Definition:Polish Notation

From ProofWiki
Jump to navigation Jump to search


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$


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

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