Answer to Question #217542 in Discrete Mathematics for lio

Question

Question 5: By using the rules of logical equivalences, show the propositions are logically equivalent:

a)                 Determine whether (p → (q → r)) → (p ˄ q) → r) is Tautology.

b)                 (p ∧ q) ∧ [(q ∧ ¬r) ∨ (p ∧ r)] and ¬(p → ¬q).

c)                 [(p v q) /\ (p → r) /\ (q → r)] →r is Tautology.

 

Answer 1

a) $\left( {p \to \left( {q \to r} \right)} \right) \to \left( {\left( {p \wedge q} \right) \to r} \right) = \overline {\left( {p \to \left( {q \to r} \right)} \right)} \vee \left( {\left( {p \wedge q} \right) \to r} \right) = \overline {\left( {\overline p \vee \left( {q \to r} \right)} \right)} \vee \left( {\overline {\left( {p \wedge q} \right)} \vee r} \right) = \overline {\left( {\overline p \vee \left( {\overline q \vee r} \right)} \right)} \vee \left( {\overline {\left( {p \wedge q} \right)} \vee r} \right) = \overline {\left( {\overline p \vee \overline q \vee r} \right)} \vee \left( {\overline p \vee \overline q \vee r} \right) = p \wedge q \wedge \overline r \vee \overline p \vee \overline q \vee r = \left( {p \vee \overline p \vee \overline q \vee r} \right) \wedge \left( {q \vee \overline p \vee \overline q \vee r} \right) \wedge \left( {\overline r \vee \overline p \vee \overline q \vee r} \right) = \left( {T \vee \overline q \vee r} \right) \wedge \left( {T \vee \overline p \vee r} \right) \wedge \left( {T \vee \overline p \vee \overline q } \right) = T \wedge T \wedge T = T$

Q. E. D.

b) 1) $\left( {p \wedge q} \right) \wedge \left( {\left( {q \wedge \neg r} \right) \vee \left( {p \wedge r} \right)} \right) = \left( {p \wedge q} \right) \wedge \left( {\left( {q \vee p} \right) \wedge \left( {q \vee r} \right) \wedge \left( {\neg r \vee p} \right) \wedge \left( {\neg r \vee r} \right)} \right) = \left( {p \wedge q} \right) \wedge \left( {\left( {q \vee p} \right) \wedge \left( {q \vee r} \right) \wedge \left( {\neg r \vee p} \right) \wedge T} \right) = \left( {p \wedge q} \right) \wedge \left( {\left( {q \vee p} \right) \wedge \left( {q \vee r} \right) \wedge \left( {\neg r \vee p} \right)} \right) = \left( {p \wedge q} \right) \wedge \left( {q \vee \left( {p \wedge r} \right)} \right) \wedge \left( {\neg r \vee p} \right) = \left( {\left( {p \wedge q \wedge q} \right) \vee \left( {p \wedge q \wedge p \wedge r} \right)} \right) \wedge \left( {\neg r \vee p} \right) = \left( {\left( {p \wedge q} \right) \vee \left( {p \wedge q \wedge r} \right)} \right) \wedge \left( {\neg r \vee p} \right) = \left( {p \wedge q} \right) \wedge \left( {T \vee r} \right) \wedge \left( {\neg r \vee p} \right) = \left( {p \wedge q} \right) \wedge T \wedge \left( {\neg r \vee p} \right) = \left( {p \wedge q} \right) \wedge \left( {\neg r \vee p} \right) = p \wedge q \wedge \neg r \vee p \wedge q \wedge p = p \wedge q \wedge \neg r \vee p \wedge q = p \wedge q \wedge \left( {\neg r \vee T} \right) = p \wedge q \wedge T = p \wedge q$

2) $\neg \left( {p \to \neg q} \right) = \neg \left( {\neg p \vee \neg q} \right) = \neg \neg p \wedge \neg \neg q = p \wedge q$

So, $\left( {p \wedge q} \right) \wedge \left( {\left( {q \wedge \neg r} \right) \vee \left( {p \wedge r} \right)} \right) = p \wedge q$ and $\neg \left( {p \to \neg q} \right) = p \wedge q$

Then

$\left( {p \wedge q} \right) \wedge \left( {\left( {q \wedge \neg r} \right) \vee \left( {p \wedge r} \right)} \right) = \neg \left( {p \to \neg q} \right)$

Q. E. D.

c) $\left( {\left( {p \vee q} \right) \wedge \left( {p \to r} \right) \wedge \left( {q \to r} \right)} \right) \to r = \overline {\left( {\left( {p \vee q} \right) \wedge \left( {p \to r} \right) \wedge \left( {q \to r} \right)} \right)} \vee r = \overline {\left( {p \vee q} \right)} \vee \overline {\left( {p \to r} \right)} \vee \overline {\left( {q \to r} \right)} \vee r = \overline {\left( {p \vee q} \right)} \vee \overline {\left( {\overline p \vee r} \right)} \vee \overline {\left( {\overline q \vee r} \right)} \vee r = \left( {\overline p \wedge \overline q } \right) \vee \left( {p \wedge \overline r } \right) \vee \left( {q \wedge \overline r } \right) \vee r = \left( {\overline p \wedge \overline q } \right) \vee \overline r \wedge \left( {p \vee q} \right) \vee r = \overline {\left( {p \vee q} \right)} \vee \overline r \wedge \left( {p \vee q} \right) \vee r = \left( {\overline {\left( {p \vee q} \right)} \vee \overline r } \right) \wedge \left( {\overline {\left( {p \vee q} \right)} \vee \left( {p \vee q} \right)} \right) \vee r = \left( {\overline {\left( {p \vee q} \right)} \vee \overline r } \right) \wedge T \vee r = \left( {\overline {\left( {p \vee q} \right)} \vee \overline r } \right) \vee r = \overline {\left( {p \vee q} \right)} \vee \overline r \vee r = \overline {\left( {p \vee q} \right)} \vee T = T$

Q. E. D.