# Definition:Polish Notation

## Contents

## 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 $\mathcal A$ be an alphabet.

Let each $s \in \mathcal A$ 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$

## 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

- 1993: M. Ben-Ari:
*Mathematical Logic for Computer Science*... (previous) ... (next): Chapter $2$: Propositional Calculus: $\S 2.2$: Propositional formulas - 2009: Kenneth Kunen:
*The Foundations of Mathematics*... (previous) ... (next): $\mathrm{II}.4$ Polish Notation - 2012: M. Ben-Ari:
*Mathematical Logic for Computer Science*(3rd ed.) ... (previous) ... (next): $\S 2.1.3$