# 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

${}\end{center}Observethat$P↑Q$istrueifandonlyifeither$P$or$Q${{{isfalse.Forthisreason,theShefferstrokeissometimescalled\emph{alternative % denial}or\emph{NAND}.\inner@par ThePeircearrowisdefinedbythetruthtable% \begin{center}\begin{tabular}[]{ccc}P&Q&P\downarrow Q\\ \hline F&F&T\\ F&T&F\\ T&F&F\\ T&T&F}\end{tabular}}}\end{center}Theproposition$P↓Q$istrueifandonlyifboth$P$and$Q$arefalse.Forthisreason,thePeircearrowissometimescalled\emph{joint denial}or% \emph{NOR}.\inner@par ToshowthesufficiencyoftheShefferstroke,allwehavetodoisdefineboth$¬$and$$intermsof$$.Theproposition$P↑P$assertsthateither$P$isfalse,or$P$isfalse;thuswecandefine$¬$by$¬P := P↑P$.Wedefine$$by$P\lor Q:=(P\uparrow P)\uparrow(Q\uparrow Q),$sincethisassertsthateither$P↑P$isfalse(thatis,that$P$istrue)orthat$Q↑Q$isfalse(thatis,that$Q$istrue).\inner@par WecanshowthesufficiencyofthePeircearrowinasimilarway.Define% $\lnot P:=P\downarrow P$and$P\lor Q:=(P\downarrow Q)\downarrow(P\downarrow Q% ).$Thisexpressionassertsthat$P↓Q$isfalse,thatis,thatitisfalsethatboth$P$and$Q$arefalse.ByDeMorgan^{\prime}slaw,thisisequivalenttoassertingthatatleastoneof$P$and$Q${{{istrue.\inner@par\textbf{Remark}.Itcanbeshownthatnobinaryconnective,% otherthanShefferstrokeandPeircearrow,isfunctionallycomplete.\begin{flushright}% \begin{tabular}[]{|ll|}\hline Title&Sheffer stroke\\ Canonical name&ShefferStroke\\ Date of creation&2013-03-22 18:51:55\\ Last modified on&2013-03-22 18:51:55\\ Owner&CWoo (3771)\\ Last modified by&CWoo (3771)\\ Numerical id&4\\ Author&CWoo (3771)\\ Entry type&Definition\\ Classification&msc 03B05\\ Synonym&alternative denial\\ Synonym&NAND\\ Synonym&joint denial\\ Synonym&NOR\\ Defines&Peirce arrow\\ \hline}\end{tabular}}}\end{flushright}\end{document}$