Sheffer stroke

Sheffer stroke

NAND
Definition	${\displaystyle {\overline {x\cdot y}}}$
Truth table	${\displaystyle (0111)}$
Logic gate
Normal forms
Disjunctive	${\displaystyle {\overline {x}}+{\overline {y}}}$
Conjunctive	${\displaystyle {\overline {x}}+{\overline {y}}}$
Zhegalkin polynomial	${\displaystyle 1\oplus xy}$
Post's lattices
0-preserving	no
1-preserving	no
Monotone	no
Affine	no
Self-dual	no
v t e

Logical connectives
NOT ${\displaystyle \neg A,-A,{\overline {A}},\sim A}$ AND ${\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}$ NAND ${\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}$ OR ${\displaystyle A\lor B,A+B,A\mid B,A\parallel B}$ NOR ${\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}$ XNOR ${\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}$ └ equivalent ${\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}$ XOR ${\displaystyle A{\underline {\lor }}B,A\oplus B}$ └nonequivalent ${\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}$ implies ${\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}$ nonimplication (NIMPLY) ${\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}$ converse ${\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}$ converse nonimplication ${\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness Scope (logic)
Applications
Digital logic Programming languages Mathematical logic Philosophy of logic
Category
v t e

In

${\displaystyle \mid }$

${\displaystyle \uparrow }$

${\displaystyle {\overline {\wedge }}}$

${\displaystyle Dpq}$

Its

The non-conjunction is a

The truth table of ${\displaystyle A\uparrow B}$ is as follows.

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\uparrow B}$
F	F	T
F	T	T
T	F	T
T	T	F

The Sheffer stroke of ${\displaystyle P}$ and ${\displaystyle Q}$ is the negation of their conjunction

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg (P\land Q)}$
	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg }$

By De Morgan's laws, this is also equivalent to the disjunction of the negations of ${\displaystyle P}$ and ${\displaystyle Q}$

${\displaystyle P\uparrow Q}$	${\displaystyle \Leftrightarrow }$	${\displaystyle \neg P}$	${\displaystyle \lor }$	${\displaystyle \neg Q}$
	${\displaystyle \Leftrightarrow }$		${\displaystyle \lor }$

Peirce was the first to show the functional completeness of non-conjunction (representing this as ${\displaystyle {\overline {\curlywedge }}}$) but didn't publish his result.^[2][3] Peirce's editor added ${\displaystyle {\overline {\curlywedge }}}$) for non-disjunction^{[citation needed]}.^[3]

In 1911, Stamm was the first to publish a proof of the completeness of non-conjunction, representing this with ${\displaystyle \sim }$ (the Stamm hook)^[4] and non-disjunction in print at the first time and showed their functional completeness.^[5]

In 1913,

${\displaystyle \mid }$

${\displaystyle \wedge }$

${\displaystyle \mid }$

In 1928, Hilbert and Ackermann described non-conjunction with the operator ${\displaystyle /}$.^[6][7]

In 1929, Łukasiewicz used ${\displaystyle D}$ in ${\displaystyle Dpq}$ for non-conjunction in his Polish notation.^[8]

An alternative notation for non-conjunction is ${\displaystyle \uparrow }$. It is not clear who first introduced this notation, although the corresponding ${\displaystyle \downarrow }$ for non-disjunction was used by Quine in 1940.^[9]

The stroke is named after

NAND is commutative but not associative, which means that ${\displaystyle P\uparrow Q\leftrightarrow Q\uparrow P}$ but ${\displaystyle (P\uparrow Q)\uparrow R\not \leftrightarrow P\uparrow (Q\uparrow R)}$.[13]

The Sheffer stroke, taken by itself, is a

It can also be proved by first showing, with a truth table, that ${\displaystyle \neg A}$ is truth-functionally equivalent to ${\displaystyle A\uparrow A}$.^[17] Then, since ${\displaystyle A\uparrow B}$ is truth-functionally equivalent to ${\displaystyle \neg (A\land B)}$,^[17] and ${\displaystyle A\lor B}$ is equivalent to ${\displaystyle \neg (\neg A\land \neg B)}$,^[17] the Sheffer stroke suffices to define the set of connectives ${\displaystyle \{\land ,\lor ,\neg \}}$,

Other Boolean operations in terms of the Sheffer stroke

Expressed in terms of NAND ${\displaystyle \uparrow }$, the usual operators of propositional logic are:

${\displaystyle \neg P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle P}$ ${\displaystyle \uparrow }$ ${\displaystyle P}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\rightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle ~P}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\leftrightarrow Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle ((P\uparrow P)\uparrow (Q\uparrow Q))}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$
${\displaystyle P\land Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow Q)}$ ${\displaystyle \uparrow }$ ${\displaystyle (P\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$		${\displaystyle P\lor Q}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle (P\uparrow P)}$ ${\displaystyle \uparrow }$ ${\displaystyle (Q\uparrow Q)}$     ${\displaystyle \Leftrightarrow }$     ${\displaystyle \uparrow }$

See also