HW #2

Reminder: Each HW problem solution should consist of:

• a restatement of the entire problem (you may copy it word for word),
• followed by a complete solution with all intermediate steps shown.

All exercises are from §1.2 (propositional equivalences).

1. p. 28: 6 (show that 2 propositions are logically equivalent)
   • Don't just construct a complete truth table showing all intermediate columns (although you must do that, too!).
     You must also say why the truth table shows that the propositions are equivalent.

   ---

2. p. 28: 8d (find the negation of a proposition)
   (Hint: Treat "or" as exclusive!)
   Do this problem in 4 steps (you do not have to construct a truth table, however!):
   1. Identify the atomic propositions and choose letters to represent them.
   2. Represent the compound proposition that is given in the problem
      (i.e., translate it from English to the language of propositional logic).
   3. Use DeMorgan's Laws to construct its negation.
   4. Translate back into English.

   ---

3. p. 29: 44 (show that only ¬ and ∧ are needed)
   • Be sure to read the paragraph on p. 29 between problems 42 and 43 that defines "functionally complete".
   • To show that negation (¬) and conjunction (∧) are functionally complete, you need to do two things:
     1. find logically equivalent propositions
     2. construct truth tables that show the following:
        1. Any proposition of the form "(p ∨ q)" can be written as a logically equivalent proposition using only ¬ and ∧ (using the hint in the text).

        2. Any proposition of the form "(p → q)" can be written as a logically equivalent proposition using only ¬ and ∧.
           • Hint: Either directly show that "(p → q)" can be written as a logically equivalent proposition using only ¬ and ∧
             or else show that it can be written as a logically equivalent proposition using only ¬ and ∨ and then use the equivalence in part (a)

        3. Any proposition of the form "(p ↔ q)" can be written as a logically equivalent proposition using only ¬ and ∧.
           • Hint: Show that "(p ↔ q)" can be written as a logically equivalent proposition using ∧ and →.
             Then, using previous equivalences, show how it can be re-written using only ¬ and ∧.

        4. Any proposition of the form "(p ⊕ q)" can be written as a logically equivalent proposition using only ¬ and ∧.
           • Hint: Show that "(p ⊕ q)" can be written as a logically equivalent proposition using ¬, ∨, and ∧.
             Then use previous equivalences (above) to show that you can rewrite it using only ¬ and ∧.

   ---

4. p. 29: 46 (construct a truth table)
   • Be sure to read the paragraph on p. 29 between problems 45 and 46 that defines the "Sheffer stroke" connective (also known as "NAND")

   ---

5. Show that
   ((p | q) | (p | q))

   is logically equivalent to:

   (p ∧ q).

   (This is part of p. 29, #52.)

   • Use the truth table for NAND that you constructed in problem 46 to help you show the logical equivalence.