Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How can you prove with equivalence laws that $p \land (p\lor q)$ is equivalent to $p$? I know you have to get rid of $q$, but I'm not sure how.

Thanks in advance

share|improve this question
2  
To prove using equivalence laws, we need your list of equivalence laws. There are many possible "standard" lists. –  user7530 Sep 10 '13 at 19:35
    
I have to use laws like distributivity, De Morgan, True/False-elimination –  Guest001 Sep 10 '13 at 19:39

4 Answers 4

up vote 8 down vote accepted

We have: \begin{align*} p \wedge (p \vee q) &= (p \vee F) \wedge (p \vee q) & \text{identity for } \vee \\ &= p \vee (F \wedge q) & \text{distributivity of } \vee \text{ over } \wedge \\ &= p \vee F & \text{annihilator for } \wedge \\ &= p & \text{identity for } \vee. \end{align*}

share|improve this answer
    
Note, that $F$ is an arbitrary false statement, such as $p \wedge \neg p$ –  AlexR Sep 10 '13 at 19:44
    
thank you very much! That's what I was looking for –  Guest001 Sep 10 '13 at 19:46
    
@Guest001 If you feel satisfied with this answer, you may accept it. –  Doug Spoonwood Sep 11 '13 at 1:30

When proving simple tautologies like this one, I like to break it into cases: if $p$ is $T$ and if $p$ is $F$.

If $p$ is $T$, then we have $T \wedge (T\vee q) = T\wedge T = T$.

If $p$ is $F$, then we have $F \wedge (F\vee q) = F$.

share|improve this answer
1  
This is usually what I do myself. A good approach! –  New_to_this Sep 10 '13 at 20:14

Here is a third way, - just pointing out, that there are several ways;

$$ \begin{align*} p\wedge (p\vee q)&\equiv (p\wedge p)\vee(p\wedge q)\ - \ Distributive \ law\\ &\equiv p\vee(p\wedge q) \ - \ Idempotent \ law\\ &\equiv p \ - \ Absorption \ law \end{align*} $$

share|improve this answer

I have to use laws like distributivity, De Morgan, True/False-elimination

In that case: $$(p ∧ (p ∨ q)) ⇔ (p ∧ (p ∨ q)) ∨ (p ∧ ¬p) ⇔ (p ∧ ((p ∨ q) ∨ ¬p)) ⇔ p$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.