Proving Logical Equivalence with Laws of Logic

Question

I'm working on Logical Equivalence problems and I'm having trouble understand what to do with this first problem.

The problem is to show that these two statements are equivalent to one another step-by-step using the laws of logic.

The statements are:

P->(~Q -> R) = P ^ ~Q -> R

I'm not very familiar with how to deal with the implies(->) when it comes to the rules.

Any advice would be welcome!

Answer 1

Use the definition of "$\rightarrow$" by \begin{equation}A\rightarrow B :\Leftrightarrow \neg A\vee B.\end{equation} Then you get by the De-Morgan rules

\begin{align}&P\rightarrow \left(\neg Q\rightarrow R\right)\\ \Leftrightarrow&\neg P \vee \left(Q\vee R\right)\\ \Leftrightarrow&\neg P \vee Q\vee R\\ \Leftrightarrow&\neg P \vee \neg\neg Q\vee R\\ \Leftrightarrow& \neg\left(P\wedge\neg Q\right)\vee R\\ \Leftrightarrow& \left(P\wedge\neg Q\right)\rightarrow R\end{align}

Answer 2

It strictly depends on the way propositional logic is presented... anyway, to prove the equivalence, considering that they are propositional formulae, you can prove their equivalence showing that their truth tables are identical.

Answer 3

The implies symbol, ->, or otherwise $\rightarrow$.

The best way to do logical equivalences, is to get rid of the arrows.

So to get rid of the arrows, go step by step. Do not attempt to get rid of the arrows all at the same time or you will mess up.

$p\rightarrow (\neg q \rightarrow r)\equiv (p\wedge \neg q) \rightarrow r$

$\neg p\vee (\neg q \rightarrow r)$ Logical Equivalence: $p\rightarrow q \equiv \neg p \vee q$

$\neg p\vee (\neg (\neg q) \vee r)$ We use it again inside the parenthesis

At that point, we've gotten rid of all the right arrows. We can do other logical equivalences.

$\neg p\vee (q \vee r)$ Double Negation $\neg (\neg q) \equiv q$

$(\neg p\vee q) \vee r$ Associative (All symbols are OR)

$\neg(\neg p\vee q) \rightarrow r$ Logical Equivalence: $\neg p \vee q \equiv p \rightarrow q$

$(\neg (\neg p) \wedge \neg q) \rightarrow r$ De Morgan's Law $\neg(p\vee q) \equiv (\neg p \wedge \neg q)$

$(p \wedge \neg q) \rightarrow r$ Double Negation

Therefore, $p\rightarrow (\neg q \rightarrow r)\equiv (p\wedge \neg q) \rightarrow r$