Logic: Problem 2

Part (a)

For which values of p, q, and r is the following logical expression true? $$(\neg p \vee q) \wedge (q \rightarrow r) \wedge (\neg r \vee p)$$

Give a succinct description of which combinations of input values work, rather than the whole truth table.

Answer: p, q, and r must either be all true or all false.

Self-check: If you got some other answer, proofread your work. It's easy to make small errors, both with truth tables and logical identities.

Part (b)

Show that the following two expressions aren't logically equivalent: $$(p \rightarrow q) \wedge r$$ $$p \rightarrow (q \wedge r)$$

$$(p \rightarrow q) \wedge r \equiv (\neg p \vee q) \wedge r$$ $$p \rightarrow (q \wedge r) \equiv \neg p \vee (q \wedge r) \equiv (\neg p \vee q) \wedge (\neg p \vee r)$$
Since the second expression has an extra $$\neg p$$ in it, the two expressions can't always return the same answer.
There's two things wrong with this answer. First, the author is trying to make a general argument when a specific counterexample would have been sufficient. Second, the last sentence is handwaving. How do we know that the extra $$\neg p$$ changes the behavior of the expression? There are cases where adding something to an expression doesn't change what it computes.