# distributive law in polish notation

On page 18 "Logic as Algebra" Halmos&Givant wrote the distributive law in Polish notation as $$= \times a + bc + \times ab \times ac$$ I fail to see anything remarkable here, is there a combinatorial pattern that I'm missing?

-
What exactly do me mean when you say 'remarkable'? Are you asking how to interpret Polish notation? Or the reason why one might represent things in this way? – matt Nov 22 '11 at 3:58
After rereading the passage it seems that I should lower my expectations. The authors indicated that they can write distributive law without parenthesis, and that's probably all to it. On a related note, is there any algebraic identity which is syntactically much clearer in PN? – Tegiri Nenashi Nov 22 '11 at 4:39
I think you are right, the main advantage of Polish notation is omission of parentheses. Some formulas in symbolic logic become impenetrable masses of parentheses, so there was a need to do something about it if mere humans were to read it. Another attempt was a system of dots to replace parentheses. – GEdgar Nov 22 '11 at 16:15
I've had a Hewlett Packard 48G (graphing calculator) for years. It uses a stack (and thus reverse polish notation). I have to say it wasn't easy to use at first, but there are some tasks it really speeds up and makes incredibly efficient. However, given we're "all" trained to regularly use infix notation, mental gymnastics are needed to more over into the world of prefix/postfix notation. And programming in the world of prefix or postfix notation, ouch, my head hurts. :( – Bill Cook Nov 22 '11 at 19:54
Programming field suggested several insights how to handle expression complexity, and PN is not one of them. Nested expressions are just parse trees which structure can be emphasized with generous use of carriage return and proper identation. – Tegiri Nenashi Nov 23 '11 at 1:11

I'm not quite sure what you're looking for, but here's a bit about the distributive laws.

The polish notation: $=\times a+bc+\times ab \times ac$ in standard infix notation is: $a \times (b+c) = a \times b + a \times c$.

What this means is one gets the same result if one multiplies then adds or adds then multiplies.

Using abstract algebra terminology, the distributive laws say that multiplication operators are group homomorphisms addition preserving maps. An group homomorphism (using additive notation) addition preserving map is a function such that $\varphi(b+c)=\varphi(b)+\varphi(c)$ (you can add then map or map then add). So in polish notation this is: $= \varphi + b \; c + \varphi \; b \; \varphi \; c$. This is the general pattern you're looking for (I guess).

This property is capturing a kind of commutativity: It doesn't matter which is done first: map or add. Or in your context, it doesn't matter which is done first: add or multiply.

-
Helpful, thank you: mathoverflow.net/questions/62567/… – Tegiri Nenashi Nov 22 '11 at 4:57
Do you perhaps mean that the multiplication operators satisfy the homomorphic equation? Specifically, I don't see why you've said "group homomorphisms", since we could have another structure here. – Doug Spoonwood Nov 22 '11 at 19:37
Also, I don't see how the distributive laws correspond to homomorphisms. If we have F(a+b)=F(a)+F(b), then F is unary, and + is binary. In the distrubitve laws, both operations are binary. Note that no matter which notation you pick, the homomorphic equation doesn't match that of the distributive law also, so long as the arity of all symbols comes as clear. – Doug Spoonwood Nov 22 '11 at 19:45
@DougSpoonwood you're right. When I wronte my answer I was thinking of operating in the context of a ring. I guess I should use a more general term like "$\varphi$ is an addition preserving map." – Bill Cook Nov 22 '11 at 19:46
After fixing an element, say $a$, the left multiplication operator $L_a(x)=ax$ is unary and $L_a(x+y)=L_a(x)+L_a(y)$ so the left multiplication operator (for a fixed element) is a group homomorphism. – Bill Cook Nov 22 '11 at 19:48

I'd say that Polish notation (or reverse Polish notation) makes it clearer that the "the outer operation moves to the inside and doubles, and the inner operation moves to the outside" when applying distributivity. Syntactically speaking, expressions in Polish notation (and reverse Polish notation) come as almost always clearer than in ubiquitous infix notation.

If you consider ax(b+c)=ab+ac, or a(b+c)=(axb)+(axc) and most other infix notation expressions you have to consider more than just the syntax of the expressions involved (such as what the author intends to say, which he may have stated earlier in the text, however, this is not part of the syntax of expressions). In other words, if you interpret either ax(b+c)=ab+ac or a(b+c)=(axb)+(axc) purely in terms of what your formation rules (rules for what well-formed formulas, or formulas) say exactly, they'll come out as nonsensical, or at best as ambiguous. On the other hand in Polish notation, so long as you know the arity of the operations, predicates/relations (for "=") something like =×a+bc+×ab×ac comes as clear from basically the formation rules.

For instance, with this condensed formation rule

1. If "p" and "q" all represent well-defined values, then +pq, ×pq, and =pq each represent well-defined values.

and this axiom:

1. "a", "b", and "c" represent well-defined values,

then you can formally prove =×a+bc+×ab×ac as well-defined also as follows:

1 +bc by rule 1, and axiom 2
2 ×ab by rule 1, and axiom 2
3 ×ac by rule 1, and axiom 2
4 +×ab×ac by steps 2 and 3, and rule 1
5 ×a+bc by axiom 2, step 1, and rule 1
6 =×a+bc+×ab×ac by steps 3 and 4 and rule 1


You have to fully parenthesize an infix expression in order to do something like this.

-