Try It Now

Exercises

1. Given the following propositions generated by p, q, and r, which are equivalent to one another?
   1. (p ∧ r) ∨ q
   2. p ∨ (r ∨ q)
   3. r ∧ p
   4. ¬r ∨ p
   5. (p ∨ q) ∧ (r ∨ q)
   6. r → p
   7. r ∨ ¬p
   8. p → r
      
      
3. Is an implication equivalent to its converse? Verify your answer using a truth table.
   
   
5. How large is the largest set of propositions generated by p and q with the property that no two elements are equivalent?
   
   
7. Explain why a contradiction implies any proposition and any proposition implies a tautology.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Solutions

1. Answer: a ⇔ e, d ⇔ f, g ⇔ h
   
   
3. Solution: No. In symbolic form, the question is: Is (p → q) ⇔  (q → p)?
   
   
   
   This table indicates that an implication is not always equivalent to its converse.
   
   
5. Solution: Let x be any proposition generated by p and q. The truth table for x has 4 rows and there are 2 choices for a truth value for x for each row, so there are 2 · 2 · 2 · 2 = 2⁴  possible propositions.
   
   
7. Answer: 0 → p and p → 1 are tautologies.