With the full complement of rod logic gates, let's build a 1-bit full adder out of LEGO. There is an impressive and complete collection of LEGO logic built by Martin Howard. His logic also uses the position of rods (in or out) to register state, but the basis of the design is unclocked: the power to drive the outputs comes strictly from the power used to drive the inputs. From this, he builds clocked logic.
The rod logic I've described here is based on clocked logic. All the rods at one stage are pushed, then the next stage is pushed, and so on. None of the rod logic is unclocked: the power to drive the outputs comes strictly from the power used to drive the outputs. On the other hand, I don't have a clocking mechanism other than manually pushing the rods. I suspect that a mechanism that can push the rods in the right order will add the complexity that rods crossing each other took away.
So let's write out the equations for a full adder:
S = (-A -B Cin) + (-A B -Cin) + (A -B -Cin) + (A B Cin)
Cout = (A B -Cin) + (A -B Cin) + (-A B Cin) + (A B Cin)
This is AND-OR logic: a set of AND operations followed by a set of OR operations. However, a naive implementation would require three stages of logic, one for the AND and two for the OR, unless we are willing to live with inverted outputs.
We could do some algebraic manipulation to come up with suitable AND-NOR logic, but realizing that the three inputs have eight combinations, and that each output is set only on four combinations means that each output must also be reset on the opposite four combinations:
S = not( (A B -Cin) + (A -B Cin) + (-A B Cin) + (-A -B -Cin) )
Cout = not( (-A -B Cin) + (-A B -Cin) + (A -B -Cin) + (-A -B -Cin) )
Each output then requires four AND terms, and then a NOR term. Even better, one of the AND terms is common to both outputs, the (-A -B -Cin) term. Here's a logic diagram of the result:
There is a recurring theme here. Output rods always have nubs next to their input rods that "sense" the state of the input rod. The input rod has a nub at the position of an output rod if the input rod must be in the 1 position for the output rod to move, or a nub next to the output rod if the input rod must be in the 0 position. This rule should make it easy to construct even the most complex logic.
Note that I have used this rule in the diagram, although six of the red nubs do not need to be present: the three bottom S nubs, and the three top Cout nubs. I just did that because... well, because I forgot that I didn't need them.
Let's implement this in LEGO!
At first I tried using axles as rods: I could string perpendicular axle joiners on them as nubs, and put them through holes in beams. However, after some experimentation, I found that it was too easy to bend long axles when they were pushed. Also, the axle joiners tended to slide along the axles, and I didn't want to glue anything in place. So instead, I decided to use beams as rods, and to build a framework to house the beams out of more beams.
Below are the building instructions, along with the LDraw file describing the design. If you want to get all the parts needed to build this thing, I highly recommend BrickLink.com. Nearly 3500 people throughout the world with LEGO to sell put what they have into the BrickLink database. When you want a bunch of parts, you can find the people selling those parts in the database, put together your order, and you get the parts in the mail.