Answer to Question #172871 in Discrete Mathematics for sushii

Question

Prove the equivalence of the following in three different ways (truth table, simplification,

each is a logical consequence of the other): p → (q ∨ r) ≡ (p ∧ ~q) → r.

Answer 1

We prove the equivalence using the truth table.

We see that the formulas p → (q ∨ r) and (p ∧ ~q) → r take the same truth value therefore the formulas are equivalent.Proven.

Prove by simplifying:

$p \to \left( {q \vee r} \right) \equiv \sim p \vee q \vee r$

$\left( {p \wedge \sim q} \right) \to r \equiv \sim \left( {p \wedge \sim q} \right) \vee r \equiv \sim p \vee q \vee r$

It's obvious that $\sim p \vee q \vee r \equiv \sim p \vee q \vee r \Rightarrow p \to \left( {q \vee r} \right) \equiv \left( {p \wedge \sim q} \right) \to r$ . Proven.

Show that (p ∧ ~q) → r is a logical consequence of p → (q ∨ r).

Let p → (q ∨ r) ≡1. Let's say that (p ∧ ~q) → r ≡0. Then (p ∧ ~q) ≡1 and r ≡0, but then p ≡1 and q≡0. Then p → (q ∨ r) ≡1→(0 ∨ 0)≡0 - we have a contradiction. Therefore, if p → (q ∨ r) ≡1 then (p ∧ ~q) → r ≡1, so $\left. {p \to \left( {q \vee r} \right)} \right| = \left( {p \wedge \sim q} \right) \to r$ .

Show that p → (q ∨ r) is a logical consequence of (p ∧ ~q) → r.

Let (p ∧ ~q) → r≡1. Let's say that p → (q ∨ r) ≡0. Then p ≡1 and (q ∨ r) ≡0. Then q ≡r≡0. But then (p ∧ ~q) → r≡(1 ∧1)→0≡0 - we have a contradiction. Therefore, if (p ∧ ~q) → r≡1 then p → (q ∨ r) ≡1, so $\left. {\left( {p \wedge \sim q} \right) \to r} \right| = p \to \left( {q \vee r} \right)$ .

We have $\left. {p \to \left( {q \vee r} \right)} \right| = \left( {p \wedge \sim q} \right) \to r$ and $\left. {\left( {p \wedge \sim q} \right) \to r} \right| = p \to \left( {q \vee r} \right)$ , therefore p → (q ∨ r) ≡ (p ∧ ~q) → r. Proven.