On p. 327, we discussed the use of tautologies in optimizing compilers. In particular, these compilers will perform the following optimization, transforming the first block of code into the second: ...

On p. 327, we discussed the use of tautologies in optimizing compilers. In particular, these compilers will perform the following optimization, transforming the first block of code into the second:

The compiler performs this transformation because p ∨ ¬p is a tautology—no matter what the truth value of p, the proposition p ∨ ¬p is true. But there are situations in which this code translation actually changes the behavior of the program, if p can be an arbitrary expression (rather than just a Boolean variable)! Describe such a situation. (Hint: why do (some) people watch auto racing?)

The unknown circuit in Figure 3.18 takes three inputs {p, q,r}, and either turns on a light bulb (output of the circuit = true) or leaves it off (output = false). For each of the following, draw a circuit—using at most three ∧, ∨, and ¬ gates—that is consistent with the listed behavior. The light’s status is unknown for unlisted inputs. (If multiple circuits are consistent with the given behavior, draw any one them.)

Figure 3.18: A circuit with at most 3 gates