prove that P -> (Q \/ R) = ~R -> (P -> Q)

[solomon_13000]

I have a problem with understanding algebra in discrete mathematics. The problem is with the following question:

P -> (Q \/ R) = ~R -> (P -> Q)

to prove that P -> (Q \/ R) = ~R -> (P -> Q)

I have manage to move to this level:

P -> (Q \/ R)

(P -> Q) \/ (P -> R)

(~P \/ Q) \/ (P -> R) - Identity Law

I am not sure what to do next to proof that

P -> (Q \/ R) = ~R -> (P -> Q)

How do I solve the problem.

 

[pka]

Here is one proof.
\(\displaystyle \L \[
\begin{array}{rcl}
P \to \left( {Q \vee R} \right) & \equiv & \sim P \vee \left( {Q \vee R} \right) \\
& \equiv & \left( {\sim P \vee Q} \right) \vee R \\
& \equiv & \sim \left( {\sim P \vee Q} \right) \to R \\
& \equiv & \sim R \to \left( {\sim P \vee Q} \right) \\
& \equiv & \sim R \to \left( {P \to Q} \right) \\
\end{array}\)

 

[solomon_13000]

P -> (Q \/ R) = (~P \/ Q) \/ R - I understand

but why is it not (~P \/ Q) \/ (P -> R)

How did (~P \/ Q) \/ R become ~(~P \/ Q) -> R


Regards.

 

[soroban]

Hello, Solomon!

Another approach . . .

"Identity": \(\displaystyle \p\,\rightarrow\,q)\;\Longleftrightarrow\; (\sim p\,\vee\,q)\)

Prove: \(\displaystyle \\,\rightarrow\,(Q\,\vee\,R)\;\Longleftrightarrow\;\sim R\,\rightarrow\,(P\,\rightarrow\,Q)\)

Start with the right side:

. . \(\displaystyle \sim R\,\rightarrow\,(P\,\rightarrow\,Q)\)

. . \(\displaystyle \sim R\,\rightarrow\,(\sim P\,\vee\,Q)\;\) Identity

. . \(\displaystyle R\,\vee\,(\sim P\,\vee\,Q)\;\) Identity

. . \(\displaystyle \sim P\,\vee\,(Q\,\vee\,R)\;\) commutative & associative properties

. . \(\displaystyle P\,\rightarrow\,(Q\,\vee\,R)\;\) Identity

 

[solomon_13000]

~P V (Q V R) commutative & associative properties

now how does ~P become P ->

 

[pka]

In a course on formal logic we would call the identity \(\displaystyle \left( {p \to q} \right) \equiv \sim p \vee q\) Material Implication.

The identity \(\displaystyle \left( {p \to q} \right) \equiv \left( { \sim q \to \sim p} \right)\) is known as Transposition or Contrapositive.

 

[solomon_13000]

why do we use ~ outside (~P \/ Q) -> R.

 

[pka]

The identity \(\displaystyle A \to B \equiv \sim A \vee B\) is used here

\(\displaystyle \left( {P \vee Q} \right) \to R \equiv \sim \left( {P \vee Q} \right) \vee R.\)

 

[solomon_13000]

why is it that the indentity A -> B = ~A \/ B instead of ~A /\ B

 

[pka]

Construct a truth a table for each of those!