Chapter 1.3, Problem 54E

We now present a group of exercises that involve the logical operators NAND and NOR. The propositionpNANDq, is true when eitherporq, or both, are false; and it is false when bothpandqare true. The propositionpNORqis true when bothpandqare false, and it is false otherwise. The propositionspNANDqandpNORqare denoted by $p|q$

$p\downarrow q$, respectively. (The operators|and $\downarrow$are called theSheffer strokeand thePeirce arrowafter H. M. Sheffer and C. S. Peirce, respectively.)

54. In this exercise we will show that $\{\downarrow \}$is a functionally complete collection of logical operators.

a) Show that $p\downarrow q$is logically equivalent to $\neg p$.

b) Show that

$\left(p\downarrow q\right)\downarrow \left(p\downarrow q\right)$is logically equivalent to $\neg p\vee q$.

c) Conclude from parts (a) and (b), and Exercise 49, that $\{\downarrow \}$is a functionally complete collection of logical operators.

*49 Show that $\neg$and $\vee$form a functionally complete collection of logical operators.