InBoolean logic, logical NOR,[1]non-disjunction, or joint denial[1] is a truth-functional operator which produces a result that is the negation of 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 and , where the symbol signifies logical negation, signifies OR, and signifies AND.
Non-disjunction is usually denoted as oror (prefix) or .
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.[2]
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.
Peirce is the first to show the functional completeness of non-disjunction while he doesn't publish his result.[3][4] Peirce used for non-conjunction and for non-disjunction (in fact, what Peirce himself used is and he didn't introduce while Peirce's editors made such disambiguated use).[4] Peirce called asampheck (from Ancient Greek ἀμφήκης, amphēkēs, "cutting both ways").[4]
In 1911, Stamm [pl] was the first to publish a description of both non-conjunction (using , the Stamm hook), and non-disjunction (using , the Stamm star), and showed their functional completeness.[5][6] Note that most uses in logical notation of use this for negation.
In 1913, Sheffer described non-disjunction and showed its functional completeness. Sheffer used for non-conjunction, and for non-disjunction.
In 1935, Webb described non-disjunction for -valued logic, and use for the operator. So some people call it Webb operator,[7]Webb operation[8]orWebb function.[9]
In 1940, Quine also described non-disjunction and use for the operator.[10] So some people call the operator Peirce arroworQuine dagger.
In 1944, Church also described non-disjunction and use for the operator.[11]
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. Thus, the set containing only NOR suffices as a complete set.
Other Boolean operations in terms of the logical NOR[edit]
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 , the usual operators of propositional logic are:
The logical NOR, taken by itself, is a functionally complete set of connectives.[13] This can be proved by first showing, with a truth table, that is truth-functionally equivalent to .[14] Then, since is truth-functionally equivalent to ,[14] and is equivalent to ,[14] the logical NOR suffices to define the set of connectives ,[14] which is shown to be truth-functionally complete by the Disjunctive Normal Form Theorem.[14]
^Peirce, C. S. (1933) [1880]. "A Boolian Algebra with One Constant". In Hartshorne, C.; Weiss, P. (eds.). Collected Papers of Charles Sanders Peirce, Volume IV The Simplest Mathematics. Massachusetts: Harvard University Press. pp. 13–18.
^ abcPeirce, C. S. (1933) [1902]. "The Simplest Mathematics". In Hartshorne, C.; Weiss, P. (eds.). Collected Papers of Charles Sanders Peirce, Volume IV The Simplest Mathematics. Massachusetts: Harvard University Press. pp. 189–262.
^Vasyukevich, Vadim O. (2011). "1.10 Venjunctive Properties (Basic Formulae)". Written at Riga, Latvia. Asynchronous Operators of Sequential Logic: Venjunction & Sequention — Digital Circuits Analysis and Design. Lecture Notes in Electrical Engineering (LNEE). Vol. 101 (1st ed.). Berlin / Heidelberg, Germany: Springer-Verlag. p. 20. doi:10.1007/978-3-642-21611-4. ISBN978-3-642-21610-7. ISSN1876-1100. LCCN2011929655. p. 20: 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.)
^Freimann, Michael; Renfro, Dave L.; Webb, Norman (2018-05-24) [2017-02-10]. "Who is Donald L. Webb?". History of Science and Mathematics. Stack Exchange. Archived from the original on 2023-05-18. Retrieved 2023-05-18.
^Quine, W. V (1981) [1940]. Mathematical Logic (Revised ed.). Cambridge, London, New York, New Rochelle, Melbourne and Sydney: Harvard University Press. p. 45.
^Church, A. (1996) [1944]. Introduction to Mathematical Logic. New Jersey: Princeton University Press. p. 37.
^Bocheński, J. M. (1954). Précis de logique mathématique (in French). Netherlands: F. G. Kroonder, Bussum, Pays-Bas. p. 11.
^Smullyan, Raymond M. (1995). First-order logic. New York: Dover. pp. 5, 11, 14. ISBN978-0-486-68370-6.
^ abcdeHowson, Colin (1997). Logic with trees: an introduction to symbolic logic. London ; New York: Routledge. pp. 41–43. ISBN978-0-415-13342-5.