Prove that addition is associative with respect to this ring

Question

I'm having trouble with this task:

We can identify the Boolean algebra of propositions with the Boolean ring $(\Bbb Z/2\Bbb Z,+,·)$ (so, this set has two operations: addition and multiplication - but they’re not the usual ones!) by defining $\neg x:= 1 +x,x∨y:=x+y+x·y,$ and $x\land y:=x·y$, where all arithmetic occurs modulo $2$. It’s not difficult to verify that negation and conjunction so defined are associative operations, however, addition is another matter. Prove that addition so defined is associative.

Associativity means that $a + (b + c) = (b+c)+a$. I'm guessing it wants me to prove that $x + y$ is associative.

Does it want me to use the definition of $x\lor y$ to prove this? Then I suppose I would have to prove $x\lor y=(x+y)+xy$ and $x\lor y=xy+(x+y)$. Is this the right way to go?

Answer 1

The guy must have been falling asleep when he wrote this. Or drunk.

I can only assume (and I could be dead wrong)

That he is defining

Addition = $\lor$, which is defined by $x \lor y = x + y + x\cdot y$.

Multiplication = $\land$ which is defined by $x \land y = x \land y$.

(I have the slightest idea why the #### he brought up negation, which being a unary and not binary operation can't be associative.)

$\land$ is just modulo multiplication so of course it is associative.

But $\lor$ is not so obvious. I'm assuming that is what you must prove is associative. i.e. that $x\lor (y \lor z) = (x\lor y)\lor z$.

Answer 2

hint: the OP seems to be making two mistakes in his attack of the problem.
1. As Michael McGovern suggested, you need to determine whether for all values x,y,z, does (xVy)Vz = xV(yVz).
2. If I understand the problem correctly, x,y,z are all in $\{0,1\}.$ Therefore, there are only 2x2x2 = 8 possible combinations to check. Checking all 8, you will either find a counter example or demonstrate universal associativity.

The problem may have intended that you strive for a "step back" insight. Examining the 2x2 = 4 combinations of x,y, which of the 4 combinations yields xVy = 0. Can you immediately intuit precisely when (for example) (((aVb)Vc)Vd)Ve will equal 0? If so, can you use that intuition to form a rule that will immediately resolve whether the operation is associative? Note that by definition, the operation is commutative.

Answer 3

The assignment is to prove that $\vee$ is associative (calling it “addition” is not really being gentle to the poor student); it's actually quite easy: \begin{align} x\vee(y\vee z) &=x\vee(y+z+yz)\\ &=x+(y+z+yz)+x(y+z+yz)\\ &=x+y+z+yz+xy+xz+xyz \end{align} and \begin{align} (x\vee y)\vee z &=(x+y+xy)\vee z\\ &=x+y+xy+z+(x+y+xy)z\\ &=x+y+xy+z+xz+yz+xyz \end{align} The two final terms are equal.