semantic equivalence proof

Question

Using properties of semantic equivalence I would like to prove:

(p⇒r) ∧ (q⇒r) ≡ (p V q) ⇒ r

I have wound up with the correct result however the steps it took to get there seemed excessive. If anyone can tell me if I have added unnecessary steps it would be very helpful. I am asked to not use a rule twice in one step - hence the separation of implication rules in the beginning. Thank you in advance.

(implication)

(﹁p) V r ∧ (q ⇒ r)

(implication)

(﹁p) V r ∧ (﹁q) V r

(associativity)

(﹁p V r) ∧ (﹁q V r)

(commutavity)

(r V ﹁p) ∧ (r V ﹁q)

(distributivity)

r V (﹁p ∧ ﹁q)

(commutativity)

(﹁p ∧ ﹁q) V r

(deMorgan's)

﹁(p ∧ q) V r

(implication)

(p ∧ q) ⇒ r   

Answer 1

You start out just fine, but you can save yourself a couple of lines by keeping expressions in parentheses.

Starting from

$$(p \rightarrow r) \land (q \rightarrow r)\tag 1$$

we can apply the definition of implication twice: once for each expression in parentheses.

$$\equiv ((\lnot p) \lor r) \land ((\lnot q) \lor r)\tag 2$$

Now, using distributivity ("backwards"), we see that we have:

$$\equiv (\lnot p \land \lnot q) \lor r\tag{3}$$

But by DeMorgan's, we can write $(3)$ as $$\equiv \lnot(p \lor q) \lor r\tag 4$$

And now we can invoke the definition of implication ("backwards") to get the desired result:

$$\equiv (p \lor q)\rightarrow r\tag{5}$$

Answer 2

Here's one way of proceeding. We start with this:

$$(p \rightarrow r) \land (q \rightarrow r)$$

Applying the definition of '$\rightarrow$' we obtain:

$$(\lnot p \lor r) \land (q \rightarrow r)$$

Applying the definition of '$\rightarrow$' again we obtain:

$$(\lnot p \lor r) \land (\lnot q \lor r)$$

Factoring the $r$ out gives us:

$$(\lnot p \land \lnot q) \lor r$$

De Morgan that to obtain:

$$\lnot(p \lor q) \lor r$$

Applying the definition of '$\rightarrow$' for the last time we get:

$$(p \lor q) \rightarrow r$$