Logical NOR

The NOR operation is a logical operation on two logical values, typically the values of two propositions, that produces a value of true if and only if both operands are false. In other words, it produces a value of false if and only if at least one operand is true.

The truth table of $A\; \backslash downarrow\; B$ is as follows:

{{2-ary truth table|1|0|0|0|$A\; \backslash downarrow\; B$}}

The logical NOR $\backslash downarrow$ is the negation of the disjunction:

Peirce is the first to show the functional completeness of non-disjunction while he doesn't publish his result.{{cite encyclopedia |last1=Peirce |first1=C. S. |title=A Boolian Algebra with One Constant |encyclopedia=Collected Papers of Charles Sanders Peirce, Volume IV The Simplest Mathematics |editor1-last=Hartshorne |editor1-first=C. |editor2-last=Weiss |editor2-first=P. |orig-date=1880 |date=1933 |pages=13–18 |location=Massachusetts |publisher=Harvard University Press}}{{cite encyclopedia |last1=Peirce |first1=C. S. |title=The Simplest Mathematics |encyclopedia=Collected Papers of Charles Sanders Peirce, Volume IV The Simplest Mathematics |editor1-last=Hartshorne |editor1-first=C. |editor2-last=Weiss |editor2-first=P. |orig-date=1902 |date=1933 |pages=189–262 |location=Massachusetts |publisher=Harvard University Press}} Peirce used $\backslash overline\{\backslash curlywedge\}$ for non-conjunction and $\backslash curlywedge$ for non-disjunction (in fact, what Peirce himself used is $\backslash curlywedge$ and he didn't introduce $\backslash overline\{\backslash curlywedge\}$ while Peirce's editors made such disambiguated use). Peirce called $\backslash curlywedge$ the {{visible anchor|ampheck}} (from Ancient Greek {{lang|grc|ἀμφήκης}}, {{transliteration|grc|amphēkēs}}, "cutting both ways").

In 1911, {{ill|Edward Stamm|lt=Stamm|pl}} was the first to publish a description of both non-conjunction (using $\backslash sim$, the Stamm hook), and non-disjunction (using $*$, the Stamm star), and showed their functional completeness.{{cite web |last1=Zach |first1=R. |title=Sheffer stroke before Sheffer: Edward Stamm |url=https://richardzach.org/2023/02/sheffer-stroke-before-sheffer-edward-stamm/ |date=18 February 2023|access-date=2 July 2023}} Note that most uses in logical notation of $\backslash sim$ use this for negation.

In 1913, Sheffer described non-disjunction and showed its functional completeness. Sheffer used $\backslash mid$ for non-conjunction, and $\backslash wedge$ for non-disjunction.

In 1935, Webb described non-disjunction for $n$-valued logic, and use $\backslash mid$ for the operator. So some people call it Webb operator, Webb operation or Webb function.

In 1940, Quine also described non-disjunction and use $\backslash downarrow$ for the operator.{{cite book |last1=Quine |first1=W. V |title=Mathematical Logic |date=1981 |orig-date=1940 |publisher=Harvard University Press |location=Cambridge, London, New York, New Rochelle, Melbourne and Sydney |edition=Revised |page=45}} So some people call the operator Peirce arrow or Quine dagger.

In 1944, Church also described non-disjunction and use $\backslash overline\{\backslash vee\}$ for the operator.{{cite book |last1=Church |first1=A. |title=Introduction to Mathematical Logic |orig-date=1944|date=1996 |publisher=Princeton University Press |location=New Jersey |page=37}}

In 1954, Bocheński used $X$ in $Xpq$ for non-disjunction in Polish notation.{{cite book |last1=Bocheński |first1=J. M. |title=Précis de logique mathématique |date=1954 |location=Netherlands |publisher=F. G. Kroonder, Bussum, Pays-Bas |language=French |page=11}}

NOR is commutative but not associative, which means that $P\; \backslash downarrow\; Q\; \backslash leftrightarrow\; Q\; \backslash downarrow\; P$ but $(P\; \backslash downarrow\; Q)\; \backslash downarrow\; R\; \backslash not\backslash leftrightarrow\; P\; \backslash downarrow\; (Q\; \backslash downarrow\; R)$.{{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=22 |language=en}}

The logical NOR, taken by itself, is a functionally complete set of connectives.{{Cite book |last=Smullyan |first=Raymond M. |title=First-order logic |date=1995 |publisher=Dover |isbn=978-0-486-68370-6 |location=New York |pages=5, 11, 14 |language=en}} This can be proved by first showing, with a truth table, that $\backslash neg\; A$ is truth-functionally equivalent to $A\; \backslash downarrow\; A$.{{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}} Then, since $A\; \backslash downarrow\; B$ is truth-functionally equivalent to $\backslash neg\; (A\; \backslash lor\; B)$, and $A\; \backslash lor\; B$ is equivalent to $\backslash neg(\backslash neg\; A\; \backslash land\; \backslash neg\; B)$, the logical NOR suffices to define the set of connectives $\backslash \{\backslash land,\; \backslash lor,\; \backslash neg\backslash \}$, which is shown to be truth-functionally complete by the Disjunctive Normal Form Theorem.

This may also be seen from the fact that Logical NOR does not possess any of the five qualities (truth-preserving, false-preserving, linear, monotonic, self-dual) required to be absent from at least one member of a set of functionally complete operators.

NOR has the interesting feature that all other logical operators can be expressed by interlaced NOR operations. The logical NAND operator also has this ability.

Expressed in terms of NOR $\backslash downarrow$, the usual operators of propositional logic are:

|   

|

|-

| 

|-

|

|   

|

|}

• Bitwise NOR
• Boolean algebra
• Boolean domain
• Boolean function
• Functional completeness
• NOR gate
• Propositional logic
• Sole sufficient operator
• Sheffer stroke as symbol for the logical NAND

{{reflist|refs=

{{cite journal |title=Generation of any n-valued logic by one binary operation |author-first=Donald Loomis |author-last=Webb |date=May 1935 |journal=Proceedings of the National Academy of Sciences |volume=21 |issue=5 |pages=252–254 |publisher=National Academy of Sciences |location=USA|doi=10.1073/pnas.21.5.252 |doi-access=free |pmid=16577665 |bibcode=1935PNAS...21..252W |pmc=1076579 }}

{{cite web |title=Who is Donald L. Webb? |author-first1=Michael |author-last1=Freimann |author-first2=Dave L. |author-last2=Renfro |author-first3=Norman |author-last3=Webb |date=2018-05-24 |orig-date=2017-02-10 |website=Stack Exchange |department=History of Science and Mathematics |url=https://hsm.stackexchange.com/questions/5680/who-is-donald-l-webb |access-date=2023-05-18 |url-status=live |archive-url=https://web.archive.org/web/20230518155850/https://hsm.stackexchange.com/questions/5680/who-is-donald-l-webb |archive-date=2023-05-18}}

{{cite book |author-first=Vadim O. |author-last=Vasyukevich |title=Asynchronous Operators of Sequential Logic: Venjunction & Sequention — Digital Circuits Analysis and Design |chapter=1.10 Venjunctive Properties (Basic Formulae) |publisher=Springer-Verlag |publication-place=Berlin / Heidelberg, Germany |location=Riga, Latvia |date=2011 |edition=1st |series=Lecture Notes in Electrical Engineering (LNEE) |volume=101 |isbn=978-3-642-21610-7 |doi=10.1007/978-3-642-21611-4 |issn=1876-1100 |lccn=2011929655 |page=20 |quote-page=20 |quote=Historical background […] Logical operator NOR named Peirce arrow and also known as Webb-operation.}} (xiii+1+123+7 pages) (NB. The back cover of this book erroneously states volume 4, whereas it actually is volume 101.)

{{cite journal |title=Beitrag zur Algebra der Logik |language=de |trans-title= |author-last=Stamm |author-first=Edward Bronisław |author-link=:pl:Edward Bronisław Stamm |journal=Monatshefte für Mathematik und Physik |date=1911 |volume=22 |issue=1 |doi=10.1007/BF01742795 |pages=137–149|s2cid=119816758 }}

{{cite book |title=Journey to the Moon: The History of the Apollo Guidance Computer |author-first=Eldon C. |author-last=Hall |author-link=Eldon C. Hall |place=Reston, Virginia, USA |publisher=American Institute of Aeronautics and Astronautics |date=1996 |isbn=1-56347-185-X |page=196}}

}}

• {{Commons category-inline}}

{{Logical connectives}}

NOR

Category:Charles Sanders Peirce