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

  • : the Sheffer strokePlanetmathPlanetmath (sometimes denoted by |) and

  • : the Peirce arrow (sometimes denoted by ).

The Sheffer stroke is defined by the truth tableMathworldPlanetmath

P Q PQ
F F T
F T T
T F T
T T F

ObservethatP↑QistrueifandonlyifeitherPorQisfalse.Forthisreason,theShefferstrokeissometimescalledalternative denialorNAND.ThePeircearrowisdefinedbythetruthtable P Q P Q FFTFTFTFFTTFThepropositionP↓QistrueifandonlyifbothPandQarefalse.Forthisreason,thePeircearrowissometimescalledjoint denialorNOR.ToshowthesufficiencyoftheShefferstroke,allwehavetodoisdefineboth¬andintermsof.ThepropositionP↑PassertsthateitherPisfalse,orPisfalse;thuswecandefine¬by¬P := P↑P.Wedefineby P ∨ Q := ( P ↑ P ) ↑ ( Q ↑ Q ) , sincethisassertsthateitherP↑Pisfalse(thatis,thatPistrue)orthatQ↑Qisfalse(thatis,thatQistrue).WecanshowthesufficiencyofthePeircearrowinasimilarway.Define ⁢ ¬ P := P ↓ P and P ∨ Q := ( P ↓ Q ) ↓ ( P ↓ Q ) . ThisexpressionassertsthatP↓Qisfalse,thatis,thatitisfalsethatbothPandQarefalse.ByDeMorganslaw,thisisequivalenttoassertingthatatleastoneofPandQistrue.𝐑𝐞𝐦𝐚𝐫𝐤.Itcanbeshownthatnobinaryconnective,otherthanShefferstrokeandPeircearrow,isfunctionallycomplete.TitleSheffer strokeCanonical nameShefferStrokeDate of creation2013-03-22 18:51:55Last modified on2013-03-22 18:51:55OwnerCWoo (3771)Last modified byCWoo (3771)Numerical id4AuthorCWoo (3771)Entry typeDefinitionClassificationmsc 03B05Synonymalternative denialSynonymNANDSynonymjoint denialSynonymNORDefinesPeirce arrow