Rule 110 is not a simple boolean function. It's a cellular automata. The boolean function is part of its description but not the whole thing.
For example if you take the standard rule 110, but run it with a different background pattern (for example the one where every cell is by default in state 0) it isn't Turing complete any more.
I suggest you take a look at the proof that 110 is Turing complete (pdf here http://www.complex-systems.com/pdf/15-1-1.pdf). It doesn't just follow from elementary properties of the boolean gates AND and XOR.
To be fair, it's pretty nasty that the Rules are named ambiguously, where a critical part of the "Rule+" of interest is something (the background pattern) in the CA system but outside the Rule system. It's fixable, but still gross, and plays into Wolfram's style of making things seem more profound by hiding the ball.
For example if you take the standard rule 110, but run it with a different background pattern (for example the one where every cell is by default in state 0) it isn't Turing complete any more.
I suggest you take a look at the proof that 110 is Turing complete (pdf here http://www.complex-systems.com/pdf/15-1-1.pdf). It doesn't just follow from elementary properties of the boolean gates AND and XOR.