# 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)$$

Suppose we let p and r be false, and q be true. Then the first expression is false, and the second is true. So the two expressions cannot be logically equivalent.

Self-check: A concrete counter-example is the best way to show that a general claim is false. Make sure that you gave a specific set of values for the variables (p and r are false, and q is true). Also make sure you briefly explained why the claim fails for this set of values.

$$(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.