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
v t e

Logical connectives
AND ${\displaystyle A\land B}$, ${\displaystyle A\cdot B}$, ${\displaystyle AB}$, ${\displaystyle A\&B}$, ${\displaystyle A\&\&B}$ equivalent ${\displaystyle A\equiv B}$, ${\displaystyle A\Leftrightarrow B}$, ${\displaystyle A\leftrightharpoons B}$ implies ${\displaystyle A\Rightarrow B}$, ${\displaystyle A\supset B}$, ${\displaystyle A\rightarrow B}$ NAND ${\displaystyle A{\overline {\land }}B}$, ${\displaystyle A\uparrow B}$, ${\displaystyle A\mid B}$, ${\displaystyle {\overline {A\cdot B}}}$ nonequivalent ${\displaystyle A\not \equiv B}$, ${\displaystyle A\not \Leftrightarrow B}$, ${\displaystyle A\nleftrightarrow B}$ NOR ${\displaystyle A{\overline {\lor }}B}$, ${\displaystyle A\downarrow B}$, ${\displaystyle {\overline {A+B}}}$ NOT ${\displaystyle \neg A}$, ${\displaystyle -A}$, ${\displaystyle {\overline {A}}}$, ${\displaystyle \sim A}$ OR ${\displaystyle A\lor B}$, ${\displaystyle A+B}$, ${\displaystyle A\mid B}$, ${\displaystyle A\parallel B}$ XNOR ${\displaystyle A\ {\text{XNOR}}\ B}$ XOR ${\displaystyle A{\underline {\lor }}B}$, ${\displaystyle A\oplus B}$ converse ${\displaystyle A\Leftarrow B}$, ${\displaystyle A\subset B}$, ${\displaystyle A\leftarrow B}$
Related concepts
Propositional calculus Predicate logic Boolean algebra Truth table Truth function Boolean function Functional completeness
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

Definition

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

Logical equivalences

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 }$

Alternative notations and names

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]

History

The stroke is named after

This can also be realized as follows: All three elements of the functionally complete set {AND, OR, NOT} can be constructed using only NAND. Thus the set {NAND} must be functionally complete as well.

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 }$

Functional completeness

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

References