Sheffer記号

同義語：Shefferの棒Sheffer stroke否定論理積NAND

概要

前提知識: 命題論理, 論理的同値

「$p$ かつ $q$ ではない」という 1 種類の結合子だけで、否定も連言も選言も含意も書ける。この結合子 $p\uparrow q$ を Sheffer 記号（Sheffer stroke）または否定論理積（NAND）という。命題論理の記事の系「否定論理積だけで書けること」で見たように、$\uparrow$ だけを使った論理式で任意の真理関数が表せる。同じことは「$p$ でも $q$ でもない」という結合子 $p\downarrow q$（否定論理和、NOR）でも成り立つ。この記事では、1 種類だけで任意の真理関数を表せる関数（Sheffer 関数）がどのようなものかを調べる。2 変数ではそれが NAND と NOR の 2 つに限ることを示し、一般の $n$ 変数では「すべて偽の入力で真、すべて真の入力で偽を返し、入力をすべて反転させたときに出力が反転するとは限らない」という判定条件を証明する。その帰結として、$n$ 変数の Sheffer 関数の個数を数える。

定義

真理値の真を $1$、偽を $0$ で表す。$\{0,1\}^n$ から $\{0,1\}$ への写像を $n$ 変数の Boole 関数 という（命題論理の記事の「真理関数」と同じものである）。$x=(x_1,\dots,x_n)\in\{0,1\}^n$ の各成分を反転させたものを $\bar x:=(1-x_1,\dots,1-x_n)$ と書き、$\mathbf 0:=(0,\dots,0)$、$\mathbf 1:=(1,\dots,1)$ とする。

Sheffer記号とNOR

2 項結合子 Sheffer 記号 $\uparrow$ と NOR $\downarrow$ を、論理式 $\varphi,\psi$ の真理値によって
$$ v(\varphi\uparrow\psi)=0\iff v(\varphi)=v(\psi)=1,\qquad v(\varphi\downarrow\psi)=1\iff v(\varphi)=v(\psi)=0 $$
で定める。すなわち $\varphi\uparrow\psi$ は $\lnot(\varphi\land\psi)$ と、$\varphi\downarrow\psi$ は $\lnot(\varphi\lor\psi)$ と論理的に同値である。$\varphi\uparrow\psi$ を $\varphi\mid\psi$ とも書き、否定論理積、NAND ともいう。$\downarrow$ を Peirce 矢印（Peirce arrow）、否定論理和 ともいう。

真理値表は次のとおりである。

$p$	$q$	$p\uparrow q$	$p\downarrow q$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$
$1$	$0$	$1$	$0$
$1$	$1$	$0$	$0$

狭い意味の Sheffer 記号は NAND を指す。1 種類だけで任意の真理関数を表せる結合子を広く Sheffer 関数 とよび、NOR もそれに含める。

f-式とSheffer関数

$f$ を $n$ 変数の Boole 関数とする。命題変数 $p_1,p_2,\dots$ から始めて、「$t_1,\dots,t_n$ が $f$-式なら $f(t_1,\dots,t_n)$ も $f$-式」という規則を有限回使って作った式を $f$-式 という。$f$-式 $t$ の変数が $p_1,\dots,p_m$ の中にあるとき、変数への $0,1$ の代入ごとに $t$ の値が決まり、$m$ 変数の Boole 関数 $F_t$ が定まる。これを $t$ が表す Boole 関数という。
任意の $m\ge1$ と任意の $m$ 変数 Boole 関数が何らかの $f$-式で表せるとき、$f$ を Sheffer 関数 という（$\{f\}$ が 関数的に完全 であるともいう）。

$f$-式の変数に $f$-式を代入したものはまた $f$-式であり、それが表す関数はもとの関数の合成である。したがって、$f$-式で表せる関数どうしを合成した関数も $f$-式で表せる。定数関数（どの入力にも同じ値を返す関数）も、変数を含む $f$-式で表せれば、ほかの関数に合成して使える。
$n$ 変数 Boole 関数 $f$ について、次の言葉を使う。

$f(\mathbf 0)=0$ のとき $0$ を保つ、$f(\mathbf 1)=1$ のとき $1$ を保つ という。
すべての $x$ で $f(\bar x)=1-f(x)$ のとき、$f$ は 自己双対 であるという。入力をすべて反転させると、出力も反転するということである。
たとえば否定 $\lnot p$ は自己双対であり、3 変数の多数決関数 $\mathrm{maj}(x,y,z)$（3 つのうち 2 つ以上が $1$ なら $1$）も自己双対である。$p\land q$ は $0$ も $1$ も保ち、自己双対でない（$x=(0,1)$ で $f(x)=0$、$f(\bar x)=0$）。

直感

$p\uparrow q$ は「連言をとってから否定する」ので、2 つの入力を同じにすれば否定が取り出せ、否定をもう 1 度かければ連言が戻る。否定と連言がそろえば何でも書けるので、1 種類で足りる。逆に、1 種類で足りるためには越えるべき壁がある。どの入力もすべて $0$ のとき出力が $0$ になる結合子は、いくら組み合わせても「すべて $0$ なら $0$」の式しか作れず、否定を表せない。$1$ についても同じである。さらに自己双対な結合子からは自己双対な式しか作れない。判定条件の定理は、この 3 つの壁を越えれば必ず完全になることを主張する。

例

標準の結合子の書き換え

$\uparrow$ だけで、主な結合子は次のように書ける。各式は $p,q$ の値の 4 通りを調べれば確かめられる。
$$ \lnot p\equiv p\uparrow p,\qquad p\land q\equiv(p\uparrow q)\uparrow(p\uparrow q),\qquad p\lor q\equiv(p\uparrow p)\uparrow(q\uparrow q),\qquad p\to q\equiv p\uparrow(q\uparrow q). $$
最後の式は、右辺が $\lnot(p\land\lnot q)$ と同値で、これが $\lnot p\lor q$ と同値であることによる。$\downarrow$ では、$\land$ と $\lor$ の役割を入れ替えて
$$ \lnot p\equiv p\downarrow p,\qquad p\lor q\equiv(p\downarrow q)\downarrow(p\downarrow q),\qquad p\land q\equiv(p\downarrow p)\downarrow(q\downarrow q) $$
となる。定数も作れる。$p\uparrow(p\uparrow p)$ は $\lnot(p\land\lnot p)$ と同値でつねに $1$、それを $t$ として $t\uparrow t$ はつねに $0$ である。

括弧を省けない

$\uparrow$ も $\downarrow$ も可換である（$p\uparrow q\equiv q\uparrow p$）が、結合的ではない。$p=0$、$q=r=1$ とすると $(p\uparrow q)\uparrow r=1\uparrow1=0$、$p\uparrow(q\uparrow r)=0\uparrow0=1$ である。$\downarrow$ では $p=q=0$、$r=1$ で $(p\downarrow q)\downarrow r=1\downarrow1=0$、$p\downarrow(q\downarrow r)=0\downarrow0=1$ となる。したがって $p\uparrow q\uparrow r$ のような括弧のない書き方はできない。また $p\uparrow p\equiv\lnot p$ なので冪等でもない。

性質

合成で保たれる性質

3 つの性質は合成で保たれる

$f$ を Boole 関数とし、$t$ を $f$-式とする。

$f$ が $0$ を保つなら、$F_t$ も $0$ を保つ。
$f$ が $1$ を保つなら、$F_t$ も $1$ を保つ。
$f$ が自己双対なら、$F_t$ も自己双対である。

式の組み立てに沿った帰納法

$t$ の組み立てについての帰納法による。$t$ が変数 $p_i$ なら $F_t(x)=x_i$ で、$0$ も $1$ も保ち、$F_t(\bar x)=1-x_i=1-F_t(x)$ なので自己双対である。$t=f(t_1,\dots,t_n)$ とし、各 $F_{t_j}$ について主張が成り立つとする。1：$F_t(\mathbf 0)=f(F_{t_1}(\mathbf 0),\dots,F_{t_n}(\mathbf 0))=f(\mathbf 0)=0$。2 も同様である。3：$F_t(\bar x)=f(F_{t_1}(\bar x),\dots,F_{t_n}(\bar x))=f\bigl(1-F_{t_1}(x),\dots,1-F_{t_n}(x)\bigr)=1-f(F_{t_1}(x),\dots,F_{t_n}(x))=1-F_t(x)$。2 つ目の等号は帰納法の仮定、3 つ目は $f$ の自己双対性による。$\square$

この補題から、Sheffer 関数であるための必要条件が出る。$f$ が $0$ を保てば、$f$-式は否定 $\lnot p_1$（$0$ を保たない）を表せない。$1$ を保つ場合も同じである。$f$ が自己双対なら、$f$-式は $p_1\land p_2$（自己双対でない）を表せない。

2 を法とする多項式

十分条件の証明には、Boole 関数を 2 元体 $\mathbb F_2=\{0,1\}$ 上の多項式で書く。$\oplus$ を 2 を法とする和（排他的論理和）、積を通常の積（$=\land$）とする。

代数標準形

任意の $n$ 変数 Boole 関数 $f$ は、係数 $c_S\in\{0,1\}$ によって
$$ f(x)=\bigoplus_{S\subset\{1,\dots,n\}}c_S\prod_{i\in S}x_i $$
とただ 1 通りに書ける（空集合 $S$ の積は $1$ とする）。これを $f$ の 代数標準形 という。

1 変数ずつ分ける

存在を $n$ についての帰納法で示す。$n=0$ では $f$ は定数 $c_\emptyset$ である。$n\ge1$ では、$x=(x',x_n)$ と分けると、$x_n\in\{0,1\}$ のどちらでも
$$ f(x',x_n)=f(x',0)\oplus x_n\bigl(f(x',0)\oplus f(x',1)\bigr) $$
が成り立つ。$f(x',0)$ と $f(x',0)\oplus f(x',1)$ は $n-1$ 変数の Boole 関数なので、帰納法の仮定によりこの形に書け、展開すれば $f$ もこの形に書ける。
一意性：係数の選び方 $(c_S)_S$ は $2^{2^n}$ 通りあり、$n$ 変数 Boole 関数も $2^{2^n}$ 個ある。係数の組に関数を対応させる写像は、存在の主張により全射であり、有限集合の間の同じ個数の全射なので単射でもある。$\square$

$c_S=1$ となる $S$ の最大の大きさを $f$ の次数という。次数が $1$ 以下、すなわち $f(x)=c\oplus\bigoplus_{i\in T}x_i$ の形の関数を アフィン という。

Sheffer 関数の判定

Sheffer関数の判定条件

$n$ 変数 Boole 関数 $f$ が Sheffer 関数であるための必要十分条件は、次の 3 つがすべて成り立つことである。

$f(\mathbf 0)=1$（$0$ を保たない）。
$f(\mathbf 1)=0$（$1$ を保たない）。
$f$ は自己双対でない。

否定・定数・連言を順に作る

必要性は lem-shf-invariants の後に述べた。十分性を示す。1〜3 を仮定する。
否定：$g(p):=f(p,\dots,p)$ は、1・2 により $g(0)=1$、$g(1)=0$ なので否定 $\lnot p$ を表す。
定数：3 により、$f(\bar a)\ne1-f(a)$、すなわち $f(\bar a)=f(a)$ となる $a\in\{0,1\}^n$ がある。$a_i=1$ なら $\ell_i:=p$、$a_i=0$ なら $\ell_i:=\lnot p$（上の $g$ で表す）として、$h(p):=f(\ell_1,\dots,\ell_n)$ とおく。$h(1)=f(a)$、$h(0)=f(\bar a)$ なので $h$ は定数関数であり、その値を $c$ とすると、$g(h(p))$ は定数 $1-c$ を表す。よって定数 $0$ と $1$ がともに $f$-式で表せる。
連言：まず $f$ はアフィンでない。実際、$f(x)=c\oplus\bigoplus_{i\in T}x_i$ とすると、1 から $c=1$、2 から $\lvert T\rvert$ は奇数であり、
$$ f(\bar x)=1\oplus\bigoplus_{i\in T}(1\oplus x_i)=1\oplus\lvert T\rvert\oplus\bigoplus_{i\in T}x_i=\bigoplus_{i\in T}x_i=1-f(x) $$
（$\lvert T\rvert$ は 2 を法として $1$）となって 3 に反する。よって lem-shf-anf の代数標準形に、2 個以上の変数の積がある。変数の番号を付け替えて $x_1x_2$ を含む積があるとし、代数標準形の項を $x_1,x_2$ を含むかどうかで分けて
$$ f(x)=x_1x_2\,u_0\oplus x_1\,u_1\oplus x_2\,u_2\oplus u_3 $$
と書く。$u_0,\dots,u_3$ は $x_3,\dots,x_n$ の多項式で、$x_1x_2$ を含む積があるので $u_0$ は $0$ でない多項式である。lem-shf-anf の一意性により、$u_0$ は $0$ でない関数なので、$u_0(e_3,\dots,e_n)=1$ となる $e_i\in\{0,1\}$ がある。$x_3,\dots,x_n$ に定数 $e_3,\dots,e_n$ を代入すると、$f$-式で表せる 2 変数関数
$$ k(x_1,x_2)=x_1x_2\oplus\alpha x_1\oplus\beta x_2\oplus\gamma\qquad(\alpha,\beta,\gamma\in\{0,1\}) $$
が得られる。$x_1\oplus\beta$ は $\beta=0$ なら $x_1$、$\beta=1$ なら $\lnot x_1$ なので $f$-式で表せ、$x_2\oplus\alpha$ も同様である。展開すると
$$ k(x_1\oplus\beta,\ x_2\oplus\alpha)=x_1x_2\oplus\alpha x_1\oplus\beta x_2\oplus\alpha\beta\oplus\alpha x_1\oplus\alpha\beta\oplus\beta x_2\oplus\alpha\beta\oplus\gamma=x_1x_2\oplus(\alpha\beta\oplus\gamma) $$
である。$\alpha\beta\oplus\gamma=0$ ならこれは $x_1\land x_2$ そのもの、$1$ なら $\lnot(x_1\land x_2)=x_1\uparrow x_2$ である。どちらの場合も、必要なら否定 $g$ を合成して $x_1\uparrow x_2$ が $f$-式で表せる。
まとめ：$\uparrow$ だけの論理式で任意の真理関数が表せる（命題論理の記事の系「否定論理積だけで書けること」）。その論理式の各 $\uparrow$ を、いま得た $x_1\uparrow x_2$ を表す $f$-式で置き換えれば、同じ関数を表す $f$-式が得られる。よって $f$ は Sheffer 関数である。$\square$

1 変数の Boole 関数で 1・2 を満たすのは否定だけで、否定は自己双対なので、1 変数の Sheffer 関数はない。

2 変数の Sheffer 関数は NAND と NOR だけ

2 変数の Boole 関数 $f$ が Sheffer 関数であるための必要十分条件は、$f$ が $\uparrow$ または $\downarrow$ であることである。

残る 4 つを調べる

thm-shf-criterion の 1・2 により $f(0,0)=1$、$f(1,1)=0$ である。残る値 $(f(0,1),f(1,0))$ は 4 通りあり、$(1,1)$ なら $\uparrow$、$(0,0)$ なら $\downarrow$、$(1,0)$ なら $f(x_1,x_2)=1-x_1$、$(0,1)$ なら $f(x_1,x_2)=1-x_2$ である。後の 2 つは否定に変数を 1 つ足したもので、$f(\bar x)=1-f(x)$ を満たすので自己双対であり、Sheffer 関数でない。前の 2 つは自己双対でない。$\uparrow$ では $x=(0,1)$ で $f(x)=1=f(\bar x)$、$\downarrow$ では $x=(0,1)$ で $f(x)=0=f(\bar x)$ だからである。よって thm-shf-criterion により $\uparrow$ と $\downarrow$ は Sheffer 関数である。$\square$

2 変数の Boole 関数は全部で $16$ 個あり、その中で 1 種類だけで完全なのは NAND と NOR の 2 つである。この事実は MBTZ25 §46.2（pp. 379–380）で証明なしに述べられている。

Sheffer関数の個数

$n\ge1$ のとき、$n$ 変数の Sheffer 関数はちょうど $2^{2^n-2}-2^{2^{n-1}-1}$ 個ある。

条件 1・2 を満たすものから自己双対なものを除く

$n\ge1$ では $\mathbf 0\ne\mathbf 1$ なので、$f(\mathbf 0)=1$、$f(\mathbf 1)=0$ を満たす関数は、残りの $2^n-2$ 点での値を自由に選べて $2^{2^n-2}$ 個ある。自己双対な関数は、$\{x,\bar x\}$ の形の $2^{n-1}$ 組（$x\ne\bar x$ なので組は 2 点ずつ）の各組で一方の値を選べば他方が決まるので、$2^{2^{n-1}}$ 個ある。そのうち $f(\mathbf 0)=1$ のもの（このとき自己双対性から $f(\mathbf 1)=0$）は、組 $\{\mathbf 0,\mathbf 1\}$ の値が決まっているので $2^{2^{n-1}-1}$ 個である。これらが条件 1・2 を満たし 3 を満たさない関数のすべてなので、thm-shf-criterion により個数は差で与えられる。$\square$

$n=1,2,3,4$ では、個数はそれぞれ $0$、$2$、$56$、$16256$ である。$n=2$ の $2$ は cor-shf-binary と一致する。変数が増えると、条件 1・2 を満たす関数の中で自己双対なものの割合は急速に小さくなる。

3 変数の Sheffer 関数

$f(x,y,z):=\lnot(x\lor(y\land z))$ は Sheffer 関数である。$f(\mathbf 0)=\lnot0=1$、$f(\mathbf 1)=0$ であり、$f(\bar x,\bar y,\bar z)=x\land(y\lor z)$ と $1-f(x,y,z)=x\lor(y\land z)$ は $(x,y,z)=(1,0,0)$ で値が $0$ と $1$ に分かれるので、自己双対でない。$f$ の値は 3 つの変数すべてに依存する（$y=0$ のとき $x$ で、$x=0$、$z=1$ のとき $y$ で、$x=0$、$y=1$ のとき $z$ で値が変わる）ので、2 変数の NAND や NOR に変数を足しただけのものではない。

反例：条件を外すと成り立たない

thm-shf-criterion の 3 つの条件は、どれも外せない。各行の関数は、ほかの 2 つの条件を満たし、その行の条件だけを破る。

外す条件	反例	成り立たなくなること
1：$f(\mathbf 0)=1$	$f(x,y)=x\land\lnot y$	Sheffer 関数であること（否定が表せない）
2：$f(\mathbf 1)=0$	含意 $f(x,y)=x\to y$	Sheffer 関数であること（否定が表せない）
3：自己双対でない	多数決の否定 $f(x,y,z)=\lnot\mathrm{maj}(x,y,z)$	Sheffer 関数であること（連言が表せない）

反例の確かめ

1 行目：$f(0,0)=0$ で、$f(1,1)=1\land0=0$ であり、$x=(0,0)$ で $f(x)=0=f(\bar x)$ なので自己双対でない。$f$ は $0$ を保つので、lem-shf-invariants により $f$-式はすべて $0$ を保ち、$\lnot p_1$ を表せない。
2 行目：$f(0,0)=1$、$f(1,1)=1$ であり、$x=(0,0)$ で $f(x)=1=f(\bar x)$ なので自己双対でない。$f$ は $1$ を保つので、$f$-式は $\lnot p_1$ を表せない。含意と否定を合わせれば完全になるが、含意だけでは足りない。
3 行目：$f(\mathbf 0)=1$、$f(\mathbf 1)=0$ である。$\mathrm{maj}(\bar x,\bar y,\bar z)$ は「$0$ が 2 つ以上」で $1$ になるので $1-\mathrm{maj}(x,y,z)$ に等しく、$\mathrm{maj}$ は自己双対であり、その否定 $f$ も自己双対である。lem-shf-invariants により $f$-式はすべて自己双対で、$p_1\land p_2$ を表せない。否定は $f(p,p,p)$ で表せるのに、完全にはならない。

注意

式の長さ：$\uparrow$ だけで書ける、ということは短く書けるということではない。ex-shf-translation の $p\land q$ のように、部分式を 2 回書く置き換えを繰り返すと、式の長さは入れ子の深さについて指数的に増えうる。論理回路では同じ部分の出力を何度も使えるので、式の長さと回路の大きさは別に数える。
記号 $\mid$ の多義性：$p\mid q$ は数論では「$p$ が $q$ を割り切る」の意味で使われる。紛れるときは $\uparrow$ を使うのがよい。
古典論理への依存：この記事の議論は真理値が $0,1$ の 2 つだけの古典論理のものである。直観主義論理のように結合子の意味が真理値表で決まらない論理では、同じ置き換えは使えない。
名前の由来：MBTZ25 §46.1（p. 378）によれば、NAND の完全性は H. M. Sheffer が 1913 年の論文で原始記号を減らすために用い、C. S. Peirce はそれより約 30 年前に同じことに気づいていたが公表しなかった。

分野ごとの使われ方

命題論理・証明論：原始記号を 1 種類に減らした言語で論理式を扱える。一階の言語では、関数的に完全な結合子の集まりと、$\forall$・$\exists$ の一方とを原始記号にすれば足り（OLT26 §15.2、p. 209）、結合子の集まりとして $\{\uparrow\}$ がとれる。ただし読みやすさのため、通常は $\lnot,\land,\lor,\to$ を併用する。
論理回路：NAND ゲートだけ、または NOR ゲートだけで、任意の組合せ回路が作れる。これは cor-shf-binary の回路での言い換えである。
Boole 関数の分類：$0$ を保つ・$1$ を保つ・自己双対といった、合成で保たれる性質で Boole 関数の集まりを分類する見方は、lem-shf-invariants の考え方を一般化したものである。