I don't know how to solve the question above without using a truth table. If anyone could help me, that would be great! The method used should be used something like LHS and RHS.
Asked
Active
Viewed 103 times
2
-
You have to use Logical equivalences. – Mauro ALLEGRANZA Sep 12 '17 at 07:49
-
Alternatively, you can prove the equivalence showing: (i) $[P \lor (P \land Q)] \to P$ and (ii) $P \to [P \lor (P \land Q)]$. – Mauro ALLEGRANZA Sep 12 '17 at 07:55
-
(ii) is trivial, using Addition. – Mauro ALLEGRANZA Sep 12 '17 at 07:56
-
For (i), you have to use Proof by cases. – Mauro ALLEGRANZA Sep 12 '17 at 07:56
3 Answers
2
You use $\phi\rightarrow \phi\lor\psi$ (disjunction introduction) and $\phi\land\psi\rightarrow\phi$ (conjunction elimination) together with the distsributive law and idempotence:
$$\begin{align} P\lor(P\land Q) &\leftrightarrow (P\lor P)\land(P\lor Q) & \text{Distributive law}\\ &\leftrightarrow P\land (P\lor Q)&\text{Idempotence}\\ &\rightarrow P &{\phi\land\psi\rightarrow\phi}\\ &\rightarrow P\lor (P\land Q) & \phi\rightarrow\phi\lor\psi \end{align}$$
Then of course you use that $\phi\rightarrow\psi\rightarrow\phi$ means that $\phi\leftrightarrow\psi$.
skyking
- 16,654
0
You have 2 cases:
$\mathcal{P}$ is false $\Leftrightarrow (\mathcal{P} \wedge\mathcal{Q})$ is false $\Leftrightarrow \mathcal{P}\vee (\mathcal{P} \wedge\mathcal{Q})$ is false.
$\mathcal{P}$ is true $\Leftrightarrow \mathcal{P}\vee (\mathcal{P} \wedge\mathcal{Q})$ is true.
Wyllich
- 1,477
0
$$P\land (P \lor Q) \Leftrightarrow \text{ (Identity)}$$
$$(P \lor \bot) \land (P \lor Q) \Leftrightarrow \text{ (Distribution)}$$
$$P \lor (\bot \land Q) \Leftrightarrow \text{ (Annihilation)}$$
$$P \lor \bot \Leftrightarrow \text{ (Identity)}$$
$$P$$
Bram28
- 100,612
- 6
- 70
- 118