Proving logical equivalence: $P \Leftrightarrow P \vee (P \wedge Q)$

Question

I'm a first year CS student about to write his first term test and this question is part of our practice package. I have not been successful in writing a sequence of equivalences to justify this proof.

$P \Leftrightarrow P \vee (P \wedge Q)$

I've tried using the distributive property and simplifying conjunction and disjunction pairs on the right side but have only got to this step so far.

$$P \vee (P \wedge Q) \\ \Leftrightarrow (P \vee P) \wedge (P \wedge P) \\ \Leftrightarrow P \wedge P \wedge Q \\ \Leftrightarrow P \wedge Q$$

Is there a "trick" for these types of proofs? A special technique? Any form of help is appreciated!

Answer 1

We prove each direction of the double implication. $$A \equiv B \Leftrightarrow (A\Rightarrow B) \land (B \Rightarrow A)$$Note that

$$P \implies (P \lor (P\land Q))\equiv \lnot P \lor P \lor (P\land Q)\equiv T \lor (P\land Q) \equiv T\tag{$\Rightarrow$}$$

Note: In the preceding string of equivalencies, $T$ denotes "true", and infact, we see that the forward implication is a tautology. Now, for the $\Leftarrow$ direction:

$$P\lor (P \land Q) \equiv (P\lor P) \land (P \lor Q) \equiv P \land (P \lor Q) \implies P\tag{$\Leftarrow$}$$

Therefore $$P \iff (P \lor (P \land Q))$$

Answer 2

Suppose first that P is true. From there you want to show that either P is true or P and Q are true. This basically follows.

Then you want to suppose that P or P and Q are true. Take two cases. The first where P is true to show that P is true and then the second where P and Q are true. You want to then show that P is true.

Answer 3

Here is a simple direct way to prove this: \begin{align} & P \Leftrightarrow P \lor (P \land Q) \\ \Leftrightarrow & \;\;\;\;\;\text{"$\;p \lor q \Leftrightarrow q\;$ is one of the many ways to write $\;p \Rightarrow q\;$"} \\ & P \land Q \Rightarrow P \\ \Leftrightarrow & \;\;\;\;\;\text{"$\;\lnot p \lor q\;$ is another way to write $\;p \Rightarrow q\;$; DeMorgan"} \\ & \lnot P \lor \lnot Q \lor P \\ \Leftrightarrow & \;\;\;\;\;\text{"simplify: excluded middle; $\;p \lor \text{true} \Leftrightarrow \text{true}\;$"} \\ & \text{true} \\ \end{align}

Answer 4

Left to right:
If a in P then a in P and also a in P U Q then a in P ^ (P U Q)

Right to left:
If a in P ^ (P U Q) then a in P