1
$\begingroup$

Hi I am looking to prove that this equivalence holds using rules of semantic equivalence, or if it does not hold give an interpretation that shows it.

(p⇒q)∨(r⇒q)≡p⇒(r⇒q)

I get

≡implication

¬(p∨q)∨(r⇒q)

≡distributivity(X2)

(¬(p∨q)∧r∧(¬p∧q)∧q)

≡demorgan’s

(¬p)∧(¬q)∧r∧(¬(p∨q)∧q

≡demorgan’s

(¬p)∧(¬q)∧r∧(¬p)∧(¬q)∧q)

=demorgan’s

¬(p∨q)∧r∧(¬p)∧(¬q)∧q)

and then I am stuck. can someone please help?

$\endgroup$
2
$\begingroup$

In your first "move", you write:

$$(p\rightarrow q)∨(r\rightarrow q) \equiv \lnot(p\lor q)\lor (r\rightarrow q)$$

That should be: $$(p \rightarrow q)\lor (r\rightarrow q) \equiv (\lnot p\lor q)\lor (r\Rightarrow q)$$

Recall that $$A \rightarrow B \equiv \lnot A \lor B$$ That's really the only "rule" of equivalence we need here, along with one invocation of the equivalence $q\lor q \equiv q$, and the use of associativity and commutativity of disjunction.

From the start: $$\begin{align} (p \rightarrow q)\lor (r\rightarrow q) &\equiv (\lnot p\lor q)\lor (r\Rightarrow q)\\ \\& \equiv (\lnot p\lor q)\lor (\lnot r\lor q)\\ \\ &\equiv\lnot p \lor q \lor \lnot r \lor q \\ \\ &\equiv \lnot p \lor \lnot r\lor q\\ \\ &\equiv p \rightarrow (\lnot r \lor q)\\ \\ & \equiv p \rightarrow (r\rightarrow q)\end{align}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you. I understand this! one question, is there a rule for removing the brackets in the third line, or is this something you can just do? i can trace all rules except for this. $\endgroup$ – user131673 Feb 26 '14 at 18:32
  • $\begingroup$ It's because disjunction, like conjunction, is associative: $a \lor (b\lor c) \equiv (a \lor b)\lor c \equiv a\lor b \lor c$. $\endgroup$ – amWhy Feb 26 '14 at 18:39

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.