MATH 300 Fall 2018 Assignment 09

Truth Tables for Statements, Logical Equivalence

The following is the list of problems for Sections 2.5 and 2.6 of the Book of Proof (pages 48, 51). There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

Exercises for Section 2.5

Write a truth table for the logical statements in problems 1—9:

  1. \( P \land (Q \implies R) \)
  2. \( (Q \lor R) \iff (R \land Q) \)
  3. \( \lnot (P \implies Q) \)
  4. \( \lnot (P \lor Q) \lor (\lnot P) \)
  5. \( (P \land \lnot P) \lor Q \)
  6. \( (P \land \lnot P) \land Q \)
  7. \( (P \land \lnot P) \implies Q \)
  8. \( P \lor (Q \land \lnot R) \)
  9. \( \lnot ( \lnot P \lor \lnot Q) \)
  10. Suppose the statement \( ((P \land Q) \lor R) \implies (R \lor S) \) is false. Find the truth values of \( P, Q, R \) and \( S \). (This can be done without a truth table.)
  11. Suppose \( P \) is false and that the statement \( (R \implies S) \iff (P \land Q) \) is true. Find the truth values of \( R \) and \( S \). (This can be done without a truth table.)

Exercises for Section 2.6

A. Use truth tables to show that the following statements are logically equivalent.

  1. \( P \land (Q \lor R) = (P \land Q) \lor (P \land R) \)
  2. \( P \lor ( Q \land R) = (P \lor Q) \land (P \lor R) \)
  3. \( P \implies Q = (\lnot P) \lor Q \)
  4. \( \lnot (P \lor Q) = (\lnot P) \land (\lnot Q) \)
  5. \( \lnot (P \lor Q \lor R) = (\lnot P) \land (\lnot Q) \land (\lnot R) \)
  6. \( \lnot (P \land Q \land R) = (\lnot P) \lor (\lnot Q) \lor (\lnot R) \)
  7. \( P \implies Q = (P \lor \lnot Q) \implies (Q \land \lnot Q) \)
  8. \( \lnot P \iff Q = (P \implies \lnot Q) \land (\lnot Q \implies P) \)

B. Decide whether or not the following pairs of statements are logically equivalent.

  1. \( P \land Q \) and \( \lnot(\lnot P \lor \lnot Q) \)
  2. \( (P \implies Q) \lor R \) and \( \lnot((P \land \lnot Q) \land \lnot R) \)
  3. \( (\lnot P) \land (P \implies Q) \) and \( \lnot (Q \implies P) \)
  4. \( \lnot (P \implies Q) \) and \( P \land \lnot Q \)
  5. \( P \lor (Q \land R) \) and \( (P \lor Q) \land R \)
  6. \( P \land (Q \lor \lnot Q) \) and \( (\lnot P) \implies (Q \land \lnot Q) \)