You can make NOT gates from NAND.
So you can make AND gates from NOT and NAND.
Now, you can make OR gates from NOT and AND (use DeMorgan's)
Now you can make anything. Won't be an endless cycle, because the above list of gate dependencies is not circular.