Editing Sheffer stroke (section)

==Properties==

NAND is commutative but not associative, which means that <math>P \uparrow Q \leftrightarrow Q \uparrow P</math> but <math>(P \uparrow Q) \uparrow R \not\leftrightarrow P \uparrow (Q \uparrow R)</math>.<ref>{{Cite book |last=Rao |first=G. Shanker |url=https://books.google.com/books?id=M-5m_EdvxuIC |title=Mathematical Foundations of Computer Science |date=2006 |publisher=I. K. International Pvt Ltd |isbn=978-81-88237-49-4 |pages=21 |language=en}}</ref>

===Functional completeness===
The Sheffer stroke, taken by itself, is a [[Functional completeness|functionally complete]] set of connectives.<ref name=":18">{{Cite web |last=Weisstein |first=Eric W. |title=Propositional Calculus |url=https://mathworld.wolfram.com/ |access-date=2024-03-22 |website=mathworld.wolfram.com |language=en}}</ref><ref name=":2">{{Citation |last=Franks |first=Curtis |title=Propositional Logic |date=2023 |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/archives/fall2023/entries/logic-propositional/ |access-date=2024-03-22 |edition=Fall 2023 |publisher=Metaphysics Research Lab, Stanford University |editor2-last=Nodelman |editor2-first=Uri |encyclopedia=The Stanford Encyclopedia of Philosophy}}</ref> This can be seen from the fact that NAND does not possess any of the following five properties, each of which is required to be absent from, and the absence of all of which is sufficient for, at least one member of a set of [[functionally complete]] operators: truth-preservation, falsity-preservation, [[affine transformation|linearity]], [[monotonic]]ity, [[self-duality]]. (An operator is truth-preserving if its value is truth whenever all of its arguments are truth, or falsity-preserving if its value is falsity whenever all of its arguments are falsity.)<ref>{{cite book | url=https://dokumen.pub/qdownload/the-two-valued-iterative-systems-of-mathematical-logic-am-5-volume-5-9781400882366.html | isbn=9781400882366 | doi=10.1515/9781400882366 | author=Emil Leon Post | title=The Two-Valued Iterative Systems of Mathematical Logic | location=Princeton | publisher=Princeton University Press | series=Annals of Mathematics studies | volume=5 | date=1941 }}</ref>

It can also be proved by first showing, with a [[truth table]], that <math>\neg A</math> is truth-functionally equivalent to <math>A \uparrow A</math>.<ref name=":132">{{Cite book |last=Howson |first=Colin |title=Logic with trees: an introduction to symbolic logic |date=1997 |publisher=Routledge |isbn=978-0-415-13342-5 |location=London; New York |pages=41–43}}</ref> Then, since <math>A \uparrow B</math> is truth-functionally equivalent to <math>\neg (A \land B)</math>,<ref name=":132" /> and <math>A \lor B</math> is equivalent to <math>\neg(\neg A \land \neg B)</math>,<ref name=":132" /> the Sheffer stroke suffices to define the set of connectives <math>\{\land, \lor, \neg\}</math>,<ref name=":132" /> which is shown to be truth-functionally complete by the [[Disjunctive Normal Form Theorem]].<ref name=":132" />