Sheffer ストローク | 用語集

定義

Sheffer ストローク は、単独でブール論理の すべての関数を生成できる 二項演算子のこと。代表例は NAND（Not AND）で、記号は $A \uparrow B$ 。

$A$	$B$	$A \uparrow B$ （NAND）
0	0	1
0	1	1
1	0	1
1	1	0

NAND は AND の否定で、両方が 1 のときだけ 0 を返します。Henry Maurice Sheffer が 1913 年の論文で「ブール代数全体を 1 つの演算子で公理化できる」ことを示しました（Sheffer, Trans. Amer. Math. Soc. 14 (1913)）。

性質

機能完全性: NAND だけで AND・OR・NOT・XOR などあらゆるブール関数を表現できる
NOR も Sheffer ストローク: $A \downarrow B = \overline{A \lor B}$ （NOR）も同じく単独でブール代数全体を生成
可換だが非結合: $A \uparrow B = B \uparrow A$ は成立するが、 $(A \uparrow B) \uparrow C \ne A \uparrow (B \uparrow C)$ に注意（カッコの位置で結果が変わる）
NAND と NOR が唯一の 2 元 Sheffer 演算子: 16 個ある 2 入力ブール関数のうち、機能完全性を単独で持つのはこの 2 つのみ

視覚的に見る

2 入力ブール関数 NAND と AND の出力を、4 つの入力組合せ $(0,0), (0,1), (1,0), (1,1)$ ごとに並べた図です。NAND は AND の出力を反転したものになっています。

緑が NAND、青が AND。両方が 1 になる $(1,1)$ のときだけ NAND が 0 を返し、それ以外はすべて 1。AND と完全に逆の出力です。この単純な反転構造から、NOT・AND・OR をすべて構成できる豊かな表現力が生まれます。

実世界での使われ方

NAND は理論的興味だけでなく、現代の計算機ハードウェアと密接に結びついています。

CMOS NAND ゲート: 半導体メモリ・CPU の物理回路で、NAND ゲートは最も基本的な構成要素の一つ。p-MOS と n-MOS のトランジスタを 4 個組み合わせて構成され、AND ゲートより少ない素子で実装できるため、NAND を中心にした設計が一般的（Weste & Harris, CMOS VLSI Design 4th ed., Pearson 2010）。
NAND フラッシュメモリ: スマートフォン・SSD で使われるフラッシュメモリは、NAND セルアレイで構成されます。NAND ゲートをセル単位で並べた構造から命名され、シリアル接続による高密度実装が可能。世界の NAND フラッシュ市場は年間 600 億ドル規模（Statista 2024）。
FPGA・ASIC 設計: VLSI 設計の論理合成では、回路を NAND-NAND または NOR-NOR の二段構造に正規化する手法（De Morgan 変換）が標準的に使われます。これにより同じゲート種類だけで複雑な論理関数を実装できる。
量子コンピュータ: 可逆計算では Toffoli ゲート（3 入力の制御制御 NOT、CCNOT）が古典論理の万能ゲートにあたり、NAND の万能性が可逆・量子計算へ引き継がれます。ただし Toffoli 単独では量子万能ではなく、Hadamard など本質的に量子的なゲートとの併用が必要です。

深掘り

NAND だけで AND・OR・NOT を構成する

NAND の機能完全性は、以下の構成で示されます。

\begin{aligned} \lnot A &= A \uparrow A \\ A \land B &= (A \uparrow B) \uparrow (A \uparrow B) \\ A \lor B &= (A \uparrow A) \uparrow (B \uparrow B) \end{aligned}

NOT は同じ入力を 2 回 NAND に通すだけ。AND は NAND の出力をさらに NAND（自己 NAND）で反転。OR はド・モルガンの法則 $A \lor B = \lnot(\lnot A \land \lnot B)$ を NAND だけで書き直したもの。これらが組み合わさり、任意のブール関数が NAND の組合せで表現できます。

16 個の 2 入力関数のなかでなぜ NAND と NOR だけが機能完全か

2 入力 1 出力のブール関数は $2^4 = 16$ 個あります。Post の機能完全性定理は、ある演算子集合が機能完全である必要十分条件を 5 つの「Post クラス」（定数保存・否定保存・単調・線形・自己双対）すべてに属さないこととして特徴づけました。単独の演算子で機能完全になるのは、これら 5 クラスすべてから外れる NAND と NOR の 2 つだけ。残りの 14 個の演算子はいずれか 1 つ以上のクラスに属するため、単独では不完全です（Post, The Two-Valued Iterative Systems of Mathematical Logic, Annals of Mathematics Studies 5, Princeton University Press, 1941）。

Sheffer 以前と独立発見

Sheffer の 1913 年の論文以前に、Charles S. Peirce が 1880 年頃に同じ発見を独立にしていたことが後年判明しました。Peirce は NAND（彼の表記では「amphecks」）と NOR を同時に発見し、ブール代数の単一演算子による公理化を示唆していましたが、原稿は未公開のまま長年埋もれていました（Brent, Charles Sanders Peirce: A Life, Indiana University Press, 1993 等）。Sheffer の論文が決定版として広まり、NAND は今も「Sheffer ストローク」の名前で呼ばれています。

連続数学への拡張: EML Sheffer

ブール代数の Sheffer ストローク（NAND）が離散領域の万能演算子だとすると、連続数学（実数・複素数上の関数）に同じ性質をもつ演算子があるかは自然に湧く論点です。2026 年 3 月、Andrzej Odrzywołek は EML Sheffer 演算子 $\mathrm{eml}(x, y) = \exp(x) - \ln(y)$ を発表し、 $\mathrm{eml}$ と入力変数 $x$ 、定数 $1$ から $\sin$ ・ $\cos$ ・ $\exp$ ・ $\log$ ・四則演算を含む幅広い解析関数を生成できることを示しました。式空間の構造は完全二分木と同型で、深さに対する式の総数は Catalan 数で支配されます。詳細は Academy 記事 academy-eml-sheffer を参照。

詳しくは

Academy: EML Sheffer 演算子 — 連続数学版の Sheffer ストロークと、その式空間で Catalan 数が支配する構造
Sheffer, H. M. A Set of Five Independent Postulates for Boolean Algebras, Trans. Amer. Math. Soc. 14 (1913): https://www.ams.org/journals/tran/1913-014-04/S0002-9947-1913-1500960-1/
Post, E. L. The Two-Valued Iterative Systems of Mathematical Logic, 1941