Consider a simplified class of circuits like those from Exercises 3.84–3.87: there are two inputs {p, q} and at most two gates, each of which is ∧, ∨, or ¬. There are a total of 24 = 16 distinct...

Consider a simplified class of circuits like those from Exercises 3.84–3.87: there are two inputs {p, q} and at most two gates, each of which is ∧, ∨, or ¬. There are a total of 24 = 16 distinct propositions over inputs {p, q}: four different input configurations, each of which can turn the light on or leave it off. Which, if any, of these 16 propositions cannot be expressed using up to two {∧, ∨,¬} gates?

Exercises 3.84–3.87

The light is on when the true inputs are {q} or {r}. The light is off when the true inputs are {p} or {p, q} or {p, q,r}

The light is off when the true inputs are {p, q} or {p,r} or {q,r} or {p, q,r}