Definition:Logical NAND

From ProofWiki
Jump to navigation Jump to search

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:

\(\ds \map {f^\uparrow} {\F, \F}\) \(=\) \(\ds \T\)
\(\ds \map {f^\uparrow} {\F, \T}\) \(=\) \(\ds \T\)
\(\ds \map {f^\uparrow} {\T, \F}\) \(=\) \(\ds \T\)
\(\ds \map {f^\uparrow} {\T, \T}\) \(=\) \(\ds \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:

$\map v {\mathbf A \uparrow \mathbf B} = \begin {cases}

\T & : \map v {\mathbf A} = \F \text { or } \map v {\mathbf B} = \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 \mathop {\mathsf {NAND} } q$
$p \mathop / q$ 1959: A.H. Basson and D.J. O'Connor: Introduction to Symbolic Logic who refer to it as the stroke function
$p \mathop {\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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Logical_NAND&oldid=624982"