Logical NOR

From Wikipedia, the free encyclopedia

This article is about NOR in the logical sense. For the electronic NOR gates see NOR gate, for other uses of similar terms, see NOR (disambiguation).

NOR Logic Gate

In boolean logic, logical nor or joint denial is a truth-functional operator which produces a result that is the inverse 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 of p and q are false. In grammar, nor is a coordinating conjunction.

The NOR operator is also known as Webb-operation or Peirce arrow, named after Charles Peirce who demonstrated that any logical operation can be expressed in terms of logical NOR. Thus, as with NAND operator, NOR can be used by itself, without any other logical operator, to constitute a logical formal system (making NOR functionally complete). It is also known as Quine's dagger.

1 Definition
- 1.1 Truth table
- 1.2 Venn diagram
2 Properties
3 Joint denial
4 See also

[edit] Definition

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.

[edit] Truth table

The truth table of p NOR q (also written as p ⊥ q or p ↓ q) is as follows:

p	q	↓
T	T	F
T	F	F
F	T	F
F	F	T

[edit] Venn diagram

The Venn Diagram of "Neither A nor B" (in the red area the statement is true)

One way of expressing p NOR q is $\overline{p \lor q}$ , where the symbol $\or$ signifies OR and the bar over the expression signifies the negation of the expression under the bar. In essence, simply $\neg(p \lor q)$ . Another way of expressing p NOR q is $\overline{p + q}$ .

[edit] Properties

Nor does not possess any of the five qualities, each of which is required to be absent from at least one member of a set of functionally complete operators. (truth-preserving, false-preserving, linear, monotonic, self-dual). This is why it suffices alone for a complete set.

[edit] Joint denial

NOR has the interesting feature that all other logical operators can be expressed by various functions of NOR.

"not p" is equivalent to "p NOR p"	$\overline{p} \equiv \overline{p + p}$
"p and q" is equivalent to "(p NOR p) NOR (q NOR q)"	$p \cdot q \equiv \overline{\overline{(p + p)} + \overline{(q + q)}}$
"p or q" is equivalent to "(p NOR q) NOR (p NOR q)"	$p + q \equiv \overline{\overline{(p + q)} + \overline{(p + q)}}$
"p implies q" is equivalent to "((p NOR q) NOR q) NOR ((p NOR q) NOR q)"	$p \rightarrow q \equiv \overline{\overline{(\overline{(p+q)} + q)}+\overline{(\overline{(p + q)} + q)}}$

The logical NAND operator also has this ability to express all logical operations.

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.