Sheffer ストローク

定義

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

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 の機能完全性は、以下の構成で示されます。

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 数 $C_n$ は内部ノードが $n$ 個のラベルなし完全二分木を数えます。これは演算子や葉のラベルを選んだ式総数でも、深さだけを固定した式総数でもありません。詳細は Academy 記事 academy-eml-sheffer を参照。

関連する用語

• Catalan 数 — 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