Formulate a condition that function f(x,y) must hold in order to be considered as "associative".

Question

Let $f(x,y)\colon\{0,1\}^2\to\{0,1\}$ be a Boolean function. Answer the following "warm-up" questions:

Prove or dispute: The function $f$ can be one-to-one.
Formulate a condition that function $f(x,y)$ must hold in order to be considered as "associative".

my attempts:

disproving: domain is bigger than the range.
is it simply the definition of "associative".

It's mildly interesting that exactly half of the 16 possible functions are associative. Perhaps there's a simpler test than just trying all 8 combinations of inputs. — hmakholm left over Monica, Oct 31 '14 at 13:29

score 1 · Accepted Answer · answered Oct 31 '14 at 08:48

For part a) you are right, the pigeonhole principle guaruntees that it cannot be injective, since there are 4 elements of $\{0,1\}^2$, but only 2 in $\{0,1\}$ (so domain is bigger than codomain).

For part b) I'm guessing they want you to be a bit more explicit. A binary operation $\cdot$ on a set $X$ (i.e. a function from $X\times X\to X$) is typically said to be associative if for all $x,y,z\in X$:

$$(x\cdot y)\cdot z= x\cdot(y\cdot z)$$

If we want to write this in functional notation as in your example, the condition becomes that for all $x,y,z\in\{0,1\}$ we must have that

$$f(f(x,y),z)=f(x,f(y,z)).$$

Formulate a condition that function f(x,y) must hold in order to be considered as "associative".

1 Answers1