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

Answer:

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.

Buggy answer:

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