0
$\begingroup$

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?

  • 1
    Programming field $s$uggested 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.2011-11-23

3 Answers 3

3

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.

  • 3
    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.2011-11-22
-3

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.