# semantic equivalence

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?

## 1 Answer

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}

• 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. – user131673 Feb 26 '14 at 18:32
• 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$. – amWhy Feb 26 '14 at 18:39