Sheffer stroke

In the late 19th century and early 20th century, Charles Sanders Peirce and H.M. Sheffer independently discovered that a single binary logical connective suffices to define all logical connectives (they are each functionally complete). Two such connectives are

• $\uparrow$ : the Sheffer stroke (sometimes denoted by $|$ ) and
• $\downarrow$ : the Peirce arrow (sometimes denoted by $\bot$ ).

The Sheffer stroke is defined by the truth table

Observe that $P\uparrow Q$ is true if and only if either $P$ or $Q$ is false. For this reason, the Sheffer stroke is sometimes called alternative denial or NAND.

The Peirce arrow is defined by the truth table

The proposition $P\downarrow Q$ is true if and only if both $P$ and $Q$ are false. For this reason, the Peirce arrow is sometimes called joint denial or NOR.

To show the sufficiency of the Sheffer stroke, all we have to do is define both $\lnot$ and $\lor$ in terms of $\uparrow$ . The proposition $P\uparrow P$ asserts that either $P$ is false, or $P$ is false; thus we can define $\lnot$ by $\lnot P := P\uparrow P$ . We define $\lor$ by$$ P \lor Q := (P\uparrow P)\uparrow(Q\uparrow Q),$$ since this asserts that either $P\uparrow P$ is false (that is, that $P$ is true) or that $Q\uparrow Q$ is false (that is, that $Q$ is true).

We can show the sufficiency of the Peirce arrow in a similar way. Define$$ \lnot P := P\downarrow P$$ and$$ P\lor Q := (P\downarrow Q)\downarrow(P\downarrow Q).$$ This expression asserts that $P\downarrow Q$ is false, that is, that it is false that both $P$ and $Q$ are false. By DeMorgan's law, this is equivalent to asserting that at least one of $P$ and $Q$ is true.

Remark. It can be shown that no binary connective, other than Sheffer stroke and Peirce arrow, is functionally complete.