You are here
HomeSheffer stroke
Primary tabs
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
$P$  $Q$  $P\uparrow Q$ 

F  F  T 
F  T  T 
T  F  T 
T  T  F 
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
$P$  $Q$  $P\downarrow Q$ 

F  F  T 
F  T  F 
T  F  F 
T  T  F 
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.
Mathematics Subject Classification
03B05 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections