Polish Notation

Introduction

Polish notation, also known as prefix notation, is a form of notation used in logic, arithmetic and algebra. It was created by Jan Łukasiewicz during the twenties of the 20th century. Its main feature, why it is known as prefix notation, is that operators precede operands, meaning, in logical terms, that connectives are placed before variables.

Connective scope is fully determined by its position in the formula, the more to the left the higher the scope. Hence, the main connective is the first one to the left.

This notation form avoids the use of auxiliary symbols (such as brackets) to stablish the scope of a connective, as we do in standard notation. Any formula can be parsed without ambiguity without using auxiliary symbols. This feature makes it more compact to write.

For example, the non-contradiction axiom, which can be written as ¬(p ∧ ¬ p) in standard notation, would be expressed as NKpNp.

Polish notation connectives

Traditionally, Polish notation use capital letters to name connectives, normally taking the first letter of its name in Polish. Here is a list of the most common symbols with its equivalent in standard notation:

Well formed fomula definition in Polish notation

Taking the list of connectives above plus a set of propositional variables as language alphabet, we can provide the following recursive definition of a well formed formula (wff) in this language:

• Let α be a propositional variable, then α is a wff.
• Let α, β be two wffs. Then Nα, Cαβ, Kαβ, Aαβ, Eαβ, Mα, Lα, Πα, Σα are wffs.

Procedure to translate wffs in standard notation to Polish notation

(1) Find the main connective and write its equivalent in Polish notation.

(2) If it is an unary connective, take its argument as a subformula and apply (1).

(3) If it is a binary connective, (3a) take its first argument and apply (1), then take the second one and apply (1).

(4) If the symbol is a propositional variable, append it.

This procedure finishes in a finite number of steps because successive applications of (1) take shorter (less complex) formulas and (4) assures recursion termination. If we are applying this method to a wff in standard notation, it finishes with a wff in polish notation. This desciption shows how the procedure can be formalized.

In practice, using the method as is would be tedious. It is more suitable to understand its mechanics by examples and applying it directly - with some training, translation can be done almost automatically.

As an example of this procedure we are going to use an instance of the De Morgan law, which in standard notation we write: ¬(p ∧ q) → (¬p ∨ ¬q). In this example the main connective is an implication, a binary connective, and its arguments main connectives are the negation and disjunction respectively. We have to translate these subformulas until we reach the propositional variables.

¬(p ∧ q) → (¬p ∨ ¬q)

C

(1), (3)

¬(p ∧ q) → (¬p ∨ ¬q)

C_____ _____

  (3a)

¬(p ∧ q)

CN

    (1)

¬(p ∧ q)

CN____

      (2)

  p ∧ q

CNK_ _

        (1), (3)

  p ∧ q

CNKp

          (3a), (4)

  p ∧ q

CNKpq

          (3b), (4)

¬(p ∧ q) → (¬p ∨ ¬q)

CNKpq_____

  (3b)

            ¬p ∨ ¬q

CNKpqA__ __

    (1), (3)

            ¬p ∨ ¬q

CNKpqA__ __

      (3a)

            ¬p

CNKpqAN_

        (1), (2)

            ¬p

CNKpqANp

          (4)

            ¬p ∨ ¬q

CNKpqANp__

      (3b)

                 ¬q

CNKpqANpN_

        (1), (2)

                 ¬q

CNKpqANpNq

          (4)