On p. 327, we discussed the use of tautologies in optimizing compilers. In particular, these…
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
