Polish Notation

In the preface to his Elements of Mathematical Logic, Łukasiewicz describes his primary contributions.

I enumerate here the more important new results whose authorship, I think, I may ascribe to myself. They are as follows: 1. The parenthesis-free notation of expressions in the sentential calculus and in Aristotle’s syllogistic...1

He uses the notation throughout the entire work, but only briefly covers the contribution he is most well known for.

In our logical symbolism we shall always write functors at the beginning of the functions in question. In this way we avoid the need to write parentheses. A similar notation could just as well be used in arithmetic. Should we write down the sum of two numbers a+b as +ab, then we could write the law of associativity


in the parenthesis-free notation as


In reading the last line we must bear in mind that every symbol + forms a sum together with two numerical expressions that stand to the right of it. These numerical expressions may in turn be either variables or sums.2

What Łukasiewicz refers to as a functor is what in modern parlance would be called a functional predicate. He attributes this neologism to Kotarbiński.3

Proposition. Infix notation is ambiguous.

Proof. For simplicity we will be working with a grammar which only supports addition for single-digit integers.

Consider the infix grammar G=(N,Σ,P,E), where N={E,A,V} and Σ={+,0,1,2,3,4,5,6,7,8,9}. The set of production rules P is defined as follows.

We can easily prove infix is ambiguous with an example. Let q=1+2+3. There is more than one leftmost derivation in G which yield q.

Proposition. Polish notation is unambiguous.

Proof. Consider the Polish grammar G=(N,Σ,P,E), where N={E,A,V} and Σ={+,0,1,2,3,4,5,6,7,8,9}. The set of production rules P is defined as follows.

Nothing has changed from the previous example except the production rule A has the addition operator in prefix position. This has made the grammar unambiguous.

Let wL(G). We prove by contradiction. Assume there exist two distinct leftmost derivations of w. Consider the first replacement at which they differ. If the rule is E then one derivation must chose A and the other V. The derivation from A must produce a +, but the derivation from V cannot. They must produce different strings. Similarly if the rule is V they must produce different strings since all symbols derived from V start with different digits. We have arrived at a contradiction because both derivations must arrive at the same string, namely w.