From the [wikipedia article that you cited][1]: > The Toffoli gate is universal; this means that for any boolean > function f(x1, x2, ..., xm), there is a circuit consisting of Toffoli > gates which takes x1, x2, ..., xm and some extra bits set to 0 or 1 > and outputs x1, x2, ..., xm, f(x1, x2, ..., xm), and some extra bits > (called garbage). Essentially, this means that one can use Toffoli gates > to build systems that will perform any desired boolean function > computation in a reversible manner. Which means in simple terms that any boolean function may be constructed only with Toffoli gates. Boolean functions are typically constructed from OR, AND and NOT gates, which may be combined to form any boolean function. It is widely know that the same is possible only with NOR gates or only with NAND gates. The Toffoli gate may be summarized as: Toffoli(a, b, c) = (a, b, ¬c) when a=1 and b=1 (a, b, c) otherwise Since the first and the second outputs are always equal to the first and second inputs, we may disconsider them. So we have: Toffoli'(a, b, c) = ¬c when a=1 and b=1 c otherwise With that, it is possible to define the NAND gate as: NAND(a, b) = Toffoli'(a, b, 1) Since the NAND gate is universal and the NAND gate may be defined as a Toffoli gate, then the Toffoli gate is universal. There is another way to prove that Toffoli is universal, by direct constructing the AND and NOT gates: NOT(x) = Toffoli'(1, 1, x) AND(a, b) = Toffoli'(a, b, 0) Then, we may construct the OR gate using [De Morgan's laws][2]: OR(a, b) = NOT(AND(NOT(a), NOT(b)) = Toffoli'(1, 1, Toffoli'(Toffoli'(1, 1, a), Toffoli'(1, 1, b), 0)) [1]: https://en.wikipedia.org/wiki/Toffoli_gate [2]: http://en.wikipedia.org/wiki/De_Morgan%27s_laws