Definition:Logical NAND
Contents
Definition
NAND (that is, not and), is a binary connective, written symbolically as $p \uparrow q$, whose behaviour is as follows:
- $p \uparrow q$
is defined as:
- it is not the case that $p$ and $q$ are both true.
$p \uparrow q$ is voiced:
- $p$ nand $q$
Truth Function
The NAND connective defines the truth function $f^\uparrow$ as follows:
\(\displaystyle f^\uparrow \left({F, F}\right)\) | \(=\) | \(\displaystyle T\) | |||||||||||
\(\displaystyle f^\uparrow \left({F, T}\right)\) | \(=\) | \(\displaystyle T\) | |||||||||||
\(\displaystyle f^\uparrow \left({T, F}\right)\) | \(=\) | \(\displaystyle T\) | |||||||||||
\(\displaystyle f^\uparrow \left({T, T}\right)\) | \(=\) | \(\displaystyle F\) |
Truth Table
The characteristic truth table of the logical NAND operator $p \uparrow q$ is as follows:
- $\begin{array}{|cc||c|} \hline p & q & p \uparrow q \\ \hline F & F & T \\ F & T & T \\ T & F & T \\ T & T & F \\ \hline \end{array}$
Boolean Interpretation
The truth value of $\mathbf A \uparrow \mathbf B$ under a boolean interpretation $v$ is given by:
- $v \left({\mathbf A \uparrow \mathbf B}\right) = \begin{cases} T & : v \left({\mathbf A}\right) = F \text{ or } v \left({\mathbf B}\right) = F\\ F & : \text{otherwise} \end{cases}$
Notational Variants
Various symbols are encountered that denote the concept of logical NAND:
Symbol | Origin | Known as |
---|---|---|
$p \mid q$ | Henry Sheffer | Sheffer stroke |
$p \uparrow q$ | Also sometimes referred to as the Sheffer stroke | |
$p \ \mathsf{NAND} \ q$ | ||
$p / q$ | 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic | who refer to it as the stroke function |
$p \bar \curlywedge q$ | Charles Sanders Peirce | Modified Ampheck |
The all-uppercase rendition NAND originates from the digital electronics industry, where, because NAND is Functionally Complete, this operator has a high importance.
Also known as
The symbol $\uparrow$ is sometimes known as the Sheffer stroke, named after Henry Sheffer, who proved the important result that NAND is Functionally Complete.
Some authors even refer to the NAND operation itself as the Sheffer stroke function, but it can be argued that this conflation of the notation with the operation it is intended to denote can cause confusion, and can obscure the idea that is being portrayed.
Note that the actual original Sheffer stroke is in fact the $\mid$ symbol.
Also see
- Results about logical NAND can be found here.
Sources
- 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic (3rd ed.) ... (previous) ... (next): $\S 2.5$: Further Logical Constants
- 1965: E.J. Lemmon: Beginning Logic ... (previous) ... (next): $\S 2.3$: Truth-Tables: Exercise $2 \ \text{(ii)}$
- 1972: A.G. Howson: A Handbook of Terms used in Algebra and Analysis ... (previous) ... (next): $\S 1$: Some mathematical language: Connectives
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.1$: The need for logic: Exercise $(5)$
- 1993: M. Ben-Ari: Mathematical Logic for Computer Science (1st ed.) ... (previous) ... (next): $\S 2.1$: Boolean operators