View source for Logical NOR

{{Short description|Binary operation that is true if and only if both operands are false}}
{{About|NOR in the logical sense|the electronic gate|NOR gate|other uses|Nor (disambiguation){{!}}Nor}}
{{Redirect-distinguish|Webb operation|Web operations}}
{{Redirect-distinguish-text|Peirce arrow|[[Pierce-Arrow]], an automobile manufacturer}}
{{Use dmy dates|date=May 2023|cs1-dates=y}}
{{Use list-defined references|date=May 2023}}
{{Infobox logical connective
| title        = Logical NOR
| other titles = NOR
| wikifunction = Z10231
| Venn diagram = Venn1000.svg
| definition   = <math>\overline{x + y}</math>
| truth table  = <math>(0001)</math>
| logic gate   = NOR_ANSI.svg
| DNF          = <math>\overline{x} \cdot \overline{y}</math>
| CNF          = <math>\overline{x} \cdot \overline{y}</math>
| Zhegalkin    = <math>1 \oplus x \oplus y \oplus xy</math>
| 0-preserving = no
| 1-preserving = no
| monotone     = no
| affine       = no
| self-dual    = no
}}
{{Logical connectives sidebar}}
{{C. S. Peirce articles}}
In [[Boolean logic]], '''logical NOR''','''<ref name=":13">{{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=43}}</ref>''' '''non-disjunction''', or '''joint denial<ref name=":13" />''' is a truth-functional operator which produces a result that is the negation of [[logical disjunction|logical or]]. That is, a sentence of the form (''p'' NOR ''q'') is true precisely when neither ''p'' nor ''q'' is true—i.e. when both ''p'' and ''q'' are ''false''. It is logically equivalent to <math>\neg(p \lor q)</math> and <math>\neg p \land \neg q</math>, where the symbol <math>\neg</math> signifies logical [[negation]], <math>\lor</math> signifies [[logical disjunction|OR]], and <math>\land</math> signifies [[logical conjunction|AND]].

Non-disjunction is usually denoted as <math>\downarrow</math> or <math>\overline{\vee}</math> or <math>X</math> (prefix) or <math>\operatorname{NOR}</math>.

As with its [[duality (mathematics)|dual]], the [[NAND operator]] (also known as the [[Sheffer stroke]]—symbolized as either <math>\uparrow</math>, <math>\mid</math> or <math>/</math>), NOR can be used by itself, without any other logical operator, to constitute a logical [[formal system]] (making NOR [[functional completeness|functionally complete]]).

The [[computer]] used in the spacecraft that first carried humans to the [[moon]], the [[Apollo Guidance Computer]], was constructed entirely using NOR gates with three inputs.<ref name="Hall_1996"/>

==Definition==
The '''NOR operation''' is a [[logical operation]] on two [[logical value]]s, typically the values of two [[proposition]]s, 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.

===Truth table===
The [[truth table]] of <math>A \downarrow B</math> is as follows:

{{2-ary truth table|1|0|0|0|<math>A \downarrow B</math>}}

===Logical equivalences===
The logical NOR <math>\downarrow</math> is the negation of the disjunction:

{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>P \downarrow Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>\neg (P \lor Q)</math>
|-
|[[File:Venn1000.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>\neg</math> [[File:Venn0111.svg|50px]]
|}

==Alternative notations and names==
[[Charles Sanders Peirce|Peirce]] is the first to show the functional completeness of non-disjunction while he doesn't publish his result.<ref name="peirce1880">{{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}}</ref><ref name="peirce1902">{{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}}</ref> Peirce used <math>\overline{\curlywedge}</math> for [[Sheffer stroke|non-conjunction]] and <math>\curlywedge</math> for non-disjunction (in fact, what Peirce himself used is <math>\curlywedge</math> and he didn't introduce <math>\overline{\curlywedge}</math> while Peirce's editors made such disambiguated use).<ref name="peirce1902"/> Peirce called <math>\curlywedge</math> the '''{{visible anchor|ampheck}}''' (from Ancient Greek {{lang|grc|ἀμφήκης}}, {{transliteration|grc|amphēkēs}}, "cutting both ways").<ref name="peirce1902"/>

In 1911, {{ill|Edward Stamm|lt=Stamm|pl}} was the first to publish a description of both non-conjunction (using <math>\sim</math>, the Stamm hook), and non-disjunction (using <math>*</math>, the Stamm star), and showed their functional completeness.<ref name="Stamm_1911"/><ref>{{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}}</ref> Note that most uses in logical notation of <math>\sim</math> use this for negation.

In 1913, [[Henry Maurice Sheffer|Sheffer]] described non-disjunction and showed its functional completeness. Sheffer used <math>\mid</math> for non-conjunction, and <math>\wedge</math> for non-disjunction.

In 1935, [[Donald L. Webb|Webb]] described non-disjunction for <math>n</math>-valued logic, and use <math>\mid</math> for the operator. So some people call it '''Webb operator''',<ref name="Webb_1935"/> '''Webb operation'''<ref name="Vasyukevich_2011"/> or '''Webb function'''.<ref name="Freimann-Renfro-Webb_2017"/>

In 1940, [[Willard Van Orman Quine|Quine]] also described non-disjunction and use <math>\downarrow</math> for the operator.<ref name="quine1940">{{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}}</ref> So some people call the operator '''Peirce arrow''' or '''Quine dagger'''.

In 1944, [[Alonzo Church|Church]] also described non-disjunction and use <math>\overline{\vee}</math> for the operator.<ref name="church1944">{{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}}</ref>

In 1954, [[Józef Maria Bocheński|Bocheński]] used <math>X</math> in <math>Xpq</math> for non-disjunction in [[Polish notation]].<ref name="Bochenski1954">{{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}}</ref>

==Properties==
NOR is commutative but not associative, which means that <math>P \downarrow Q \leftrightarrow Q \downarrow P</math> but <math>(P \downarrow Q) \downarrow R \not\leftrightarrow P \downarrow (Q \downarrow 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=22 |language=en}}</ref>

===Functional completeness===
The logical NOR, taken by itself, is a [[Functional completeness|functionally complete]] set of connectives.<ref name=":29">{{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}}</ref> This can be proved by first showing, with a [[truth table]], that <math>\neg A</math> is truth-functionally equivalent to <math>A \downarrow 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 \downarrow B</math> is truth-functionally equivalent to <math>\neg (A \lor 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 logical NOR 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" />

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

==Other Boolean operations in terms of the logical NOR==
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 <math>\downarrow</math>, the usual operators of propositional logic are:

{|
|-
|<!--- not --->
{| style="text-align: center; border: 1px solid darkgray;"
|-
|<math>\neg P</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>P \downarrow P</math>
|-
|<math>\neg</math> [[File:Venn01.svg|36px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn10.svg|36px]]
|}<!--- end not--->
|&nbsp;&nbsp;&nbsp;
|<!--- arrow --->
{| style="text-align: center; border: 1px solid darkgray;" 
|-
|<math>P \rightarrow Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>\Big( (P \downarrow P) \downarrow Q \Big)</math>
|<math>\downarrow</math>
|<math>\Big( (P \downarrow P) \downarrow Q \Big)</math>
|-
|[[File:Venn1011.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn0100.svg|50px]]
|<math>\downarrow</math>
|[[File:Venn0100.svg|50px]]
|}<!--- end arrow --->
|-
|&nbsp;
|-
|<!--- and --->
{| style="text-align: center; border: 1px solid darkgray;" 
|-
|<math>P \land Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \downarrow P)</math> 
|<math>\downarrow</math> 
|<math>(Q \downarrow Q)</math>
|-
|[[File:Venn0001.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn1010.svg|50px]] 
|<math>\downarrow</math> 
|[[File:Venn1100.svg|50px]]
|}<!--- end and --->
|&nbsp;&nbsp;&nbsp;
|<!--- or --->
{| style="text-align: center; border: 1px solid darkgray;" 
|-
|<math>P \lor Q</math>
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|<math>(P \downarrow Q)</math> 
|<math>\downarrow</math> 
|<math>(P \downarrow Q)</math> 
|-
|[[File:Venn0111.svg|50px]]
|&nbsp;&nbsp;&nbsp;&nbsp;<math>\Leftrightarrow</math>&nbsp;&nbsp;&nbsp;&nbsp;
|[[File:Venn1000.svg|50px]] 
|<math>\downarrow</math> 
|[[File:Venn1000.svg|50px]] 
|}<!--- end or --->
|}

==See also==
* [[Bitwise NOR]]
* [[Boolean algebra (logic)|Boolean algebra]]
* [[Boolean domain]]
* [[Boolean function]]
* [[Functional completeness]]
* [[NOR gate]]
* [[Propositional logic]]
* [[Sole sufficient operator]]
* [[Sheffer stroke]] as symbol for the logical NAND

==References==
{{reflist|refs=
<ref name="Webb_1935">{{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 }}</ref>
<ref name="Freimann-Renfro-Webb_2017">{{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}}</ref>
<ref name="Vasyukevich_2011">{{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.)</ref>
<ref name="Stamm_1911">{{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 }}</ref>

<!--<ref name="Sheffer_1913">{{cite journal |title=A set of five independent postulates for Boolean algebras, with application to logical constants |author-last=Sheffer |author-first=Henry Maurice |author-link=Henry Maurice Sheffer |journal=[[Transactions of the American Mathematical Society]] |date=1913 |doi=10.1090/S0002-9947-1913-1500960-1 |doi-access=free |volume=14 |issue=4 |pages=481–488}}</ref>

<ref name="Nicod_1917">{{cite journal |title=A reduction in the number of the primitive propositions of logic |author-last=Nicod |author-first=Jean George Pierre |author-link=Jean George Pierre Nicod |journal=Proceedings of the Cambridge Philosophical Society, Mathematical and Physical Sciences |date=1917 |volume=19 |pages=32–41}}</ref>

<ref name="Quine_1940">{{cite book |title=Mathematical logic |author-last=Quine |author-first=Willard Van Orman |author-link=Willard Van Orman Quine |edition=1 |publisher=[[W. W. Norton & Co.]] |location=New York, USA |date=1940 |url=http://archive.org/details/mathematicallogi00quin}}</ref>

<ref name="Peirce">{{cite book |author-first=Charles Sanders |author-last=Peirce |author-link=Charles Sanders Peirce |title=Charles Sanders Peirce Bibliography |title-link=Charles Sanders Peirce bibliography#CP |id=4.264 |date=}}</ref>
  -->
<ref name="Hall_1996">{{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}}</ref>
}}

==External links==
* {{Commons category-inline}}

{{Logical connectives}}

[[Category:Logical connectives|NOR]]
[[Category:Charles Sanders Peirce]]

[[de:Peirce-Funktion]]
[[it:Algebra di Boole#NOR]]