Yesterday I entered this project on Hackaday. But thinking never stops. I tried to find a use for the fourth contact on my 2 DPDT relays, but ended up with a similar 3 SPDT solution (good news for Yann), with 5 more functions.

The key is the bridge rectifier for the relay RL2. Two new control signals F4 and F5 can now control RL2, together with the two inputs:

With F4=1 and F5=0, RL2 attracts if A and B are different, just as before.

Now make F4=0. RL2 now always has ground, so will attract if either A or B is high, providing the OR function.

Now consider making F4=1 again, and make F5=1. RL2 now always has 12 volts, so it will attract if either A or B is low, providing a NAND function.

RL1 can still be controlled with the F2 and F3 signals. It controls the polarity of the output signal, so when RL1 is attracted it will transform XOR to XNOR, NAND to AND and OR to NOR.

If we now make F5=1 and F4=0, RL2 will always be attracted. This gives an always-zero (CLR) at the output when RL1 is OFF, and always-one (SET) if RL1 is ON.

In this final situation,  the voltage for the always-on comes from control F1. If we now make F1 low, this voltage is controlled by the SHR-IN input, that is connected to input A of the next bit. So it will give us the Shift-Right function (SHR). A 74181 can't do that ! Note that a Shift-left is already available because it is the same as adding a number to itself.

Only SUB and PassThrough functions are missing. A PassThrough function can be made by clearing the other operand and doing ADD or OR. Subtract might be done by doing a negate function first (XNOR with zero), or inverting the A or B signal in a previous circuit (as in the RISC Relay CPU).