2
$\begingroup$

I would like to prove

$$(p ⇒ q) ⇒ r ≡ (r \vee p) ∧ (q ⇒ r)$$

Have I used too many steps? It seems long. Mind you I do want to show each step individually so implication in two separate steps for example is required. I am asked to show simple steps like commutativity.

implication

$ (¬p \vee q) ⇒ r$

implication

$ ¬(¬ p \vee q) \vee r$

DeMorgans

$ (¬¬p ∧ ¬q) \vee r$

double negation

$ (¬ p ∧ ¬q) \vee r$

commutativity

$ r \vee (¬ p ∧ ¬q)$

distributivity

$(r \vee p) ∧ (r \vee ¬q)$

commutativity

$ (r \vee p) ∧ (¬q \vee r ) $

implication

$ (r \vee p) ∧ (¬q ⇒ r ) $

thank you in advance

$\endgroup$
  • $\begingroup$ Double neg is wrong; it must be : (p ∧ ¬q) v r; but after you have corrected it. The last line must be (q ⇒ r). With the correction of these two typos, it works. $\endgroup$ – Mauro ALLEGRANZA May 17 '14 at 19:22
  • 2
    $\begingroup$ It seems to me that if semantic equivalence is asked for, what is expected is a truth-table calculation, perhaps shortened by just examining the cases where the left-hand side is false. $\endgroup$ – André Nicolas May 17 '14 at 19:50
1
$\begingroup$

We start from $(p\rightarrow q) \rightarrow r$ and as you did, we can use the definition of implication to get

$$ \equiv (¬p \vee q) \rightarrow r$$

Using implication again, we get

$$ \equiv ¬(¬ p \vee q) \vee r$$

As as you invoked, from DeMorgan's we know

$$ \equiv (¬¬p \land ¬q) \vee r$$

So far so good. Now, we can certainly invoke double negation, but correctly applied it gives us

$$\equiv (p\land ¬q) \vee r$$

We can commute to get

$$\equiv r \vee (p \land ¬q)$$ And by the distributive rule, we obtain

$$\equiv(r \vee p) \land (r \vee ¬q)$$

Sure, we can commute again (very often we can use commutativity and associativity without listing those as separate steps)

$$ \equiv (r \vee p) \land (¬q \vee r ) $$

Now, by the definition of implication, we know that $\lnot q \lor r \equiv q \rightarrow r$, so you we need to eliminate the negation of $q$ when transforming the second term into an implication:

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

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

Following André's observation, we could also give a semantic justification. Consider an arbitrary truth-assignment $\mathcal M$ s.t.: $$\mathcal{M} \models (p \rightarrow q) \rightarrow r)_{(1)}.$$ From (1) we know that: $$\mathcal M \not\models p \rightarrow q_{(1_L)} \text{ or } \mathcal M \models r_{(1_R)}.$$

($1_L$) means that $\mathcal M \models p$ and $\mathcal M \not\models q$, which when distributed with ($1_R$) tells us that: $$\mathcal M \models p \lor r_{(2_L)} \text{ and } \mathcal M \models \lnot q \lor r_{(2_R)}.$$

Commuting the disjuncts in $(2_L)$ and applying the definition of $\rightarrow$ in ($2_R$) we obtain: $$\mathcal M \models r \lor p \text{ and } \mathcal M \models q \rightarrow r.$$

Combining the conjuncts we obtain the desired conclusion, i.e.: $\mathcal{M} \models (r \lor p)\land (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.