9.4 Simplifying bit expressions

When we compose gates, we can often rearrange and simplify the combinations. If x and y are bits, then

• not not x = x
• x and 1 = 1
• x and x = x
• 0(x) = x and (not x) = 0
• x and y = y and x
• x or 0 = x
• x or x = x
• 1(x) = x or (not x) = 1
• x or y = y or x
• not (x and y) = (not x) or (not y)
• not (x or y) = (not x) and (not y)

The last two are known as De Morgan’s Laws after British mathematician Augustus De Morgan. With a third bit z we also have:

• x and (y and z) = (x and y) and z
• x or (y or z) = (x or y) or z
• x and (y or z) = (x and y) or (x and z)
• x or (y and z) = (x or y) and (x or z)

Exercise 9.19

Which of these relationships hold for xor, nand, nor, xnor, and their...