# Properties semantic equivalence proof - too many steps.

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

• 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. – Mauro ALLEGRANZA May 17 '14 at 19:22
• 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. – André Nicolas May 17 '14 at 19:50

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

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