---
tag: 6KFS240R42
kind: definition
name: Sheffer function
msc: [08A40, "06E30", 03B50]
defines: 1K829SJG3K
uses: [TDZVCWYJ9F, PTKR703G6A, EJ8YJVM9BW]
sources:
  - url: https://en.wikipedia.org/wiki/Sheffer_stroke
---

## Definition

Let $A$ be a finite set with at least two elements.
An [[operation|EJ8YJVM9BW]] $f$ on $A$ is a *Sheffer function* if the set $\set{f}$ is [[functionally complete|TDZVCWYJ9F]].
That is, the [[clone|PTKR703G6A]] generated by $f$ contains every finitary operation on $A$.

## Remarks

Example: NAND, $x \uparrow y = \neg(x \wedge y)$ on $\set{0, 1}$, is a Sheffer function.
Check: $\neg x = x \uparrow x$ and $x \wedge y = \neg(x \uparrow y)$, and $\set{\wedge, \neg}$ is functionally complete.
Non-example: $\wedge$ on $\set{0, 1}$ is not a Sheffer function.
Every operation generated by $\wedge$ maps $(0, \dots, 0)$ to $0$, so $\neg$ is not generated.
NOR, $x \downarrow y = \neg(x \vee y)$, is the only other binary Sheffer function on $\set{0, 1}$.
A Sheffer function must have arity at least $2$, since a unary operation generates only essentially unary operations.