3
$\begingroup$

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   
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – CompilerSaysNo May 17 '14 at 0:46
  • 1
    $\begingroup$ 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'. $\endgroup$ – Hunan Rostomyan May 17 '14 at 0:49
  • $\begingroup$ What rules are you allowed to use? You can also tell us what book you're using instead of describing the rules. $\endgroup$ – Hunan Rostomyan May 17 '14 at 1:03
  • 1
    $\begingroup$ In addition to what Hunan points out, you applied "De Morgan's" incorrectly. $\endgroup$ – Doug Spoonwood May 17 '14 at 1:23
  • $\begingroup$ Rules of semantic equivalence. Our book is The Essence of Logic, by John Kelly. $\endgroup$ – CompilerSaysNo May 17 '14 at 10:06
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ yes excellent answer - i have upvoted $\endgroup$ – CompilerSaysNo May 22 '14 at 22:30
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.