Definition:Operation/Binary Operation/Postfix Notation

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\circ: S \times T \to U$ be a binary operation.

The convention that places the symbol for the operation after the two operands:

$z = x y \mathop \circ$

is called postfix notation.

In infix notation it would be presented as: $z = x \circ y$


Examples

Example: $2 3 +$

The expression:

$2 3 \mathop +$

represents what would be written in infix notation as:

$2 + 3$


Example: $3 4 \times 2 +$

The expression:

$3 4 \mathop \times 2 \mathop +$

represents what would be written in infix notation as:

$\paren {3 \times 4} + 2$


Example: $2 3 + 4 \times$

The expression:

$2 3 \mathop + 4 \mathop \times$

represents what would be written in infix notation as:

$\paren {2 + 3} \times 4$


Example $1$ of Use of Łukasiewicz's Notation

Jan Łukasiewicz's Polish notation for propositional logic can also be implemented in its reverse Polish form.

Hence:

$p q \operatorname K$

can be used to express the conjunction:

$p \land q$

which would be expressed in Polish notation as:

$\operatorname K p q$


Example $2$ of Use of Łukasiewicz's Notation

Jan Łukasiewicz's Polish notation for propositional logic can also be implemented in its reverse Polish form.

Hence the expression in postfix notation:

$p q \operatorname K p q \operatorname N \operatorname A \operatorname C$

can be used to express the compound statement:

$\paren {p \land q} \implies \paren {p \lor \lnot q}$

which would be expressed in prefix notation as:

$\operatorname C \operatorname K p q \operatorname A p \operatorname N q$


Also known as

Postfix notation is also known as reverse Polish notation.

Some sources, on introducing this notation, implement parenthesis in order to clarify and distinguish the operator from the operands:

$\tuple {x, y} \circ$


Also see

  • Results about postfix notation can be found here.


Historical Note

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

Hence they are often referred to as reverse Polish notation and Polish notation respectively.

For stack-based programming languages, postfix notation naturally coincides with how the input is to be structured for the language.

Hence it has historically been used for implementation on digital computers, and has also been used on some pocket calculators.


Sources


This page may be the result of a refactoring operation.
As such, the following source works, along with any process flow, will need to be reviewed.
When this has been completed, the citation of that source work (if it is appropriate that it stay on this page) is to be placed above this message, into the usual chronological ordering.
In particular: This came from the page on Definition:Reverse Polish Notation, now merged into this page
If you have access to any of these works, then you are invited to review this list, and make any necessary corrections.
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 {{SourceReview}} from the code.


Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Operation/Binary_Operation/Postfix_Notation&oldid=712422"