A li’l paper I wrote in response to a question/conversation with Allen Hazen and Jeff Pelletier a couple of months ago went online today in the Journal Philosophical Logic: Natural Deduction for the Sheffer Stroke and Peirce’s Arrow (and any Other Truth-Functional Connective)
(If you’re not blessed with a Springer Link subscription, there’s a preprint on arXiv.)
Abstract: Methods available for the axiomatization of arbitrary finite-valued logics can be applied to obtain sound and complete intelim rules for all truth-functional connectives of classical logic including the Sheffer stroke (nand) and Peirce’s arrow (nor). The restriction to a single conclusion in standard systems of natural deduction requires the introduction of additional rules to make the resulting systems complete; these rules are nevertheless still simple and correspond straightforwardly to the classical absurdity rule. Omitting these rules results in systems for intuitionistic versions of the connectives in question.
I’ve described the method for finite-valued logics before on the blog in response to a question by Greg Restall; here I’m just applying it to the 2-valued case.
Since I sent off the final version, I found three other related papers, which each contain alternative deduction systems for NAND or NOR :
Laurence Gagnon. NOR logic: a system of natural deduction. Notre Dame Journal of Formal Logic 17 (1976), 293-294.
Krister Segerberg, Arbitrary truth-value functions and natural deduction, Zeitschrift für mathematische Logik und Grundlagen, 29 (1983) 557–564.
Franz von Kutschera, Zum Deduktionsbegriff der klassischen Prädikatenlogik erster Stufe. In Logik und Logikkalkül, eds. Max Käsbauer
and Franz von Kutschera, 211–236. Freiburg and Munich: Karl Alber, 1962