# semantic equivalence proof

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

• sigh...have realized what I though was a correct result is not correct. If anyone can provide any guidance on where I went wrong it will be very helpful. Thank you – CompilerSaysNo May 17 '14 at 0:46
• Without going further, at step two you have introduced an ambiguity by forgetting to group the conjuncts. At step 3 you have recovered the proper grouping, but that's not justified by 'associativity'. – Hunan Rostomyan May 17 '14 at 0:49
• What rules are you allowed to use? You can also tell us what book you're using instead of describing the rules. – Hunan Rostomyan May 17 '14 at 1:03
• In addition to what Hunan points out, you applied "De Morgan's" incorrectly. – Doug Spoonwood May 17 '14 at 1:23
• Rules of semantic equivalence. Our book is The Essence of Logic, by John Kelly. – CompilerSaysNo May 17 '14 at 10:06

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

• yes excellent answer - i have upvoted – CompilerSaysNo May 22 '14 at 22:30

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