Introduction to Computer Systems - Bitwise Boolean Arithmetic Operators
Question #2
In class and in Data Lab, you will learn and interact a lot with the bitwise Boolean arithmetic operators provided by C, & | ^ ~, as well as some useful tools for manipulating Boolean formulas, such as De Morgan’s Laws.
a. Write a formula that calculates a & b using only the ~ and | operators. (Hint: this is one of De Morgan’s Laws.)
b. Write a formula that calculates a | b using only ~ and & operations. (Hint: this is the other one.)
c. Write a formula that calculates a ^ b using only ~, &, and | operations. (Hint: this is not one of De Morgan’s Laws.)
d. As you can see from the previous three questions, it’s not technically necessary to have all of the Boolean operators in your programming language; if you had only AND and NOT, you could construct all of the others from them. This is called “functional completeness.” There are two special Boolean operators that are functionally complete all by themselves: if you have either NAND (a NAND b == ~(a & b)) or NOR (a NOR b == ~(a | b)) then you can construct all the other Boolean operators from them.
Write formulas that compute ~a, a | b, and a & b using only NOR. As shorthand, you can use a $ b to mean a NOR b.
