De Morgan's Theorem

De Morgan's theorems are two complementary identities linking the AND, OR and NOT operations -- proved directly using truth tables in the two sub-sections below -- and they carry an important circuit-design consequence covered in a note beside them: any logic function can, in principle, be built using only NAND gates or only NOR gates. Both theorems are two mirror-image statements about how the complement (NOT) operation distributes over AND and OR, and each is proved directly with a truth table rather than simply asserted -- a pattern that matters because the same proof technique (write out all four input combinations, evaluate both sides independently, and check the output columns match row for row) is the standard way any Boolean identity in this chapter, including the simplification law used in the 9.6 worked example, is formally verified. A companion note beside the second theorem draws out the theorems' single most important practical con …