Now that we have a switch, we can start building logic out of it.

In CMOS, rearranging how the pMOS and nMOS transistors are wired gives you NAND (0 only when both inputs are 1) and NOR (1 only when both inputs are 0) directly. And it is a known result that NAND alone is enough to construct AND, OR, NOT, and XOR — all of them. This property is called completeness. Real designs use several gate types for reasons of speed and area, but in principle the single NAND would do.

Building addition