HW #2

§1.2: Propositional Equivalences

All exercises come from the Rosen text.

Each HW problem's solution should consist of:

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

All solutions must be handwritten.

1. (3 points for truth table; 3 points for explanation; 6 points total)

   p. 28: 4a

   • Use truth tables to show that 2 propositions are logically equivalent.

   • You must not only show the complete truth table, including all intermediate columns,
     but you must also say why or how the truth table shows that the two propositions are equivalent.

   ---

2. (12 points)

   p. 28: 8b

   • Compute the negation of an English sentence.

   • Do this problem in 4 steps (3 points each; you do not have to construct a truth table, however!):
     1. (3 points)
        Identify the atomic propositions and choose letters to represent them.

     2. (3 points)
        Represent the compound proposition that is given in the problem (i.e., translate it from English to the language of propositional logic).

     3. (3 points)
        Use DeMorgan's Laws (and any other logical equivalences from Table 6 in the text) to construct its negation.

     4. (3 points)
        Translate back into English.

   ---

3. (24 points)

   to correct page:
   p. 29: 44

   • Show that negation (¬) and conjunction (∧) are "functionally complete",
     i.e., that only the two connectives ¬ and ∧ are needed in order to represent any molecular proposition.
     (I.e., show that you don't need to use ∨, ⊕, →, or ↔.)

   • Be sure to read the paragraph on p. 29 between problems 42 and 43 that defines "functionally complete"

   • To show that these two connectives are functionally complete, you need to do two things:
     1. (3 points each; total = 12 points)
        For any proposition containing ∨, →, ↔, or ⊕,
        find a logically equivalent proposition that only contains ¬ and ∧.

     2. (3 points each; total = 12 points)
        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 (i)

        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 only ∧ 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 to show that you can re-write it using only ¬ and ∧.

   ---

4. (3 points each; total = 6 points)

   p. 29: 48, 50b

   • The binary connective NOR, symbolized by a "dagger": ↓
     (think of it as an inclusive-disjunction symbol that has been crossed out)
     is functionally complete.

     For this problem, you are only asked to show only that ∨ is not needed because it can be replaced by a suitable combination of ↓s.

   • Be sure to read the paragraph on p. 29 between problems 45 and 46 that defines the "dagger" connective (also known as the "Peirce arrow" (pronounced "purse", named after the American logician Charles Sanders Peirce; note the spelling),* and [this is a joke!] not to be confused with the "Pierce Arrow" automobile (note the spelling!) that was once manufactured in Buffalo :-)

   • To do 50b, use the truth table for NOR that you constructed in problem 48 to help you show the logical equivalence.

Total points = 48

Tentative grading scheme:

A       46-48
A-      43-45
B+      41-42
B       38-40
B-      35-37
C+      33-34
C       27-32
C-      22-26
D+      17-21
D        9-16
F        0- 8

* UB philosophy Prof. Randall R. Dipert is the "Charles Sanders Peirce Professor of American Philosophy".