---
tag: 1K829SJG3K
kind: concept
name: Sheffer function
msc: [08A40, "06E30", 03B50]
sources:
  - url: https://en.wikipedia.org/wiki/Sheffer_stroke
---

## Summary

A Sheffer function on a finite set $A$ is a single operation on $A$ that is [[functionally complete|TDZVCWYJ9F]] by itself.
Every operation on $A$ can then be written as a composition of copies of it.
On $\set{0, 1}$ the binary Sheffer functions are NAND and NOR.
Sheffer functions show that one well-chosen operation can carry the whole expressive power of a many-valued logic.

## Explanations

### L1 human

The NAND gate outputs $0$ only when both inputs are $1$.
Chips can be built from NAND gates alone, because NAND can imitate every other gate.
For example, $\neg x$ is $x \uparrow x$, and $x \wedge y$ is $(x \uparrow y) \uparrow (x \uparrow y)$.
An operation with this "one gate does everything" property is called a Sheffer function.