その際はタッチ操作で数式を横スクロールしてください
今年(2023)、9番目のデデキント数が発見されて32年ぶりにデデキント数のメンバーが更新されたという情報を耳にしてデデキント数について気になったので、学習メモを残しました。
(注意は払いましたが、もし誤ったor厳密でない記述が含まれていましたらごめんなさい…)
デデキント数について
定義
※ $n$ 番目のデデキント数の表記は著者によって異なりますが、ここでは $D(n)$ の表記を使うことにします。
値の一覧
現在判明している0番目～9番目のデデキント数の値は以下のとおりです。(OEIS：A000372)
| $D(0)$ | $2$ |
| $D(1)$ | $3$ |
| $D(2)$ | $6$ |
| $D(3)$ | $20$ |
| $D(4)$ | $168$ |
| $D(5)$ | $7581$ |
| $D(6)$ | $7828354$ |
| $D(7)$ | $2414682040998$ |
| $D(8)$ | $56130437228687557907788$ |
| $D(9)$ | $286386577668298411128469151667598498812366$ |
ブール関数
- 各変数の入力は 0 または 1 のいずれか
- 出力は 0 または 1 のいずれか
となるような関数です。
(※もう少し正確な定義はこちら)
1変数ブール関数
$$f(x) =
\begin{cases}
0 & (x=0) \\
0 & (x=1)
\end{cases}\\
\text{(入力に関係なく0を返す関数)}$$
$$f(x) =
\begin{cases}
0 & (x=0) \\
1 & (x=1)
\end{cases}\\
\text{(入力された 0, 1 をそのまま返す関数)}$$
$$f(x) =
\begin{cases}
1 & (x=0) \\
0 & (x=1)
\end{cases}\\
\text{(入力された 0, 1 を反転して返す関数)}$$
$$f(x) =
\begin{cases}
1 & (x=0) \\
1 & (x=1)
\end{cases}\\
\text{(入力に関係なく1を返す関数)}$$
1変数の場合、上記4個のブール関数が存在します。
1変数の時のデデキント数 $D(1)$は、上記4個のうち単調であるブール関数の個数です。
ここでいう単調とは、「任意の入力の組合せについて、どの1変数の入力を0から1に変えたとしても出力が1から0に変わることは無い」という条件を指します。
例えば上記の4関数の場合、入力の変数 $x$ が $0$ から $1$ に変わった時に出力が $1$ から $0$ に変わっていないものが1変数単調ブール関数です。
→ 単調
ㅤ
②：$x$ が $0$ から $1$ に変わると出力も $0$ から $1$ に。($1$ から $0$ には変わっていない)
→ 単調
ㅤ
③：$x$ が $0$ から $1$ に変わると出力が $1$ から $0$ に。
→ 単調でない
ㅤ
④：$x$ が $0$ から $1$ に変わっても出力は $1$ のまま。($1$ から $0$ に変わってはいない)
→ 単調
よって1変数ブール関数のうち3個が単調ブール関数だったので、$D(1)=3$ (1番目のデデキント数は 3) です。
2変数ブール関数
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
0 & (x=0,y=1) \\
0 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
0 & (x=0,y=1) \\
0 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
1 & (x=0,y=1) \\
0 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
0 & (x=0,y=1) \\
1 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
0 & (x=0,y=1) \\
0 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
1 & (x=0,y=1) \\
0 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
0 & (x=0,y=1) \\
1 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
0 & (x=0,y=1) \\
0 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
1 & (x=0,y=1) \\
1 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
1 & (x=0,y=1) \\
0 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
0 & (x=0,y=1) \\
1 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
1 & (x=0,y=1) \\
1 & (x=1,y=0) \\
0 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
1 & (x=0,y=1) \\
0 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
0 & (x=0,y=1) \\
1 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
0 & (x=0,y=0) \\
1 & (x=0,y=1) \\
1 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
$$f(x, y) =
\begin{cases}
1 & (x=0,y=0) \\
1 & (x=0,y=1) \\
1 & (x=1,y=0) \\
1 & (x=1,y=1)
\end{cases}$$
※各ブール関数に便宜上、対応する論理演算の名前を付けています。
2変数の場合、上記16個のブール関数が存在します。
2変数の時のデデキント数 $D(2)$は、上記16個のうち単調であるブール関数の個数です。
単調 (任意の入力の組合せについて、どの1変数の入力を0から1に変えたとしても出力が1から0に変わることは無い) 条件を満たすのは全部で6個です。
(①矛盾・⑤論理積・⑩命題 y・⑪命題 x・⑮論理和・⑯恒真)
よって、$D(2)=6$ です。
いくつか例を見ていきます。
→ 単調
ㅤ
⑮：$x$ を増やした時 $(x, y)$：$(0, 0) \rightarrow (1, 0), \ (0, 1) \rightarrow (1, 1)$ も、$y$ を増やした時 $(x, y)$：$(0, 0) \rightarrow (0, 1), \ (1, 0) \rightarrow (1, 1)$ も、出力が $1$ から$0$ に変わることは無い
→ 単調
ㅤ
⑪：$x$ を増やした時 $(x, y)$：$(0, 0) \rightarrow (1, 0), \ (0, 1) \rightarrow (1, 1)$ も、$y$ を増やした時 $(x, y)$：$(0, 0) \rightarrow (0, 1), \ (1, 0) \rightarrow (1, 1)$ も、出力が $1$ から$0$ に変わることは無い
※ $(x, y)$：$(0, 1) \rightarrow (1, 0)$ は $x$ を増やして $y$ を減らしているので、「1変数(だけ)を $0$ から$1$ に変える」には該当しません。(変える1変数以外の他の変数は同時に変えないことが前提)
→ 単調
ㅤ
⑬：$x$ を増やした時に出力が $1$ から$0$ に変わる組合せがある。 $(x, y)$：$(0, 0) \rightarrow (1, 0)$
→ 単調でない
入力の組合せ・0から1への変え方のパターン
2変数になって少しややこしくなったので、ここで1つの変数を 0 から 1 に変える時に考えられるパターンをまとめておきます。
2️⃣ $(x, y)$：$(0, 0) \rightarrow (0, 1)$
3️⃣ $(x, y)$：$(1, 0) \rightarrow (1, 1)$
4️⃣ $(x, y)$：$(0, 1) \rightarrow (1, 1)$
要は、2変数のブール関数がこの 1️⃣ ～ 4️⃣ のいずれのパターンでも出力が $1$ から$0$ に変わることが無いなら、そのブール関数は単調です。
2変数ブール関数の個数について
2変数の場合、全部で16個のブール関数がありました。
入力は $2$ 個の変数それぞれに対して $0$ か $1$ かの2パターンあるので $2^2=4$ 通りあります。
出力が $0$ か $1$ かのどちらかを入力の $4$ パターンそれぞれに対して独立に決められるので、$2$ 変数ブール関数は $2^{4}=16$ 通り存在するのでした。
n変数ブール関数
$n$ 変数の場合、入力は $n$ 個の変数それぞれに対して $0$ か $1$ かの2パターンあるので $2^n$ 通りです。
出力が $0$ か $1$ かのどちらかを入力の $2^n$ パターンそれぞれに対して独立に決められるので、$n$ 変数ブール関数は $2^{2^n}$ 通り存在します。
一方で、その中から単調なブール関数を数え上げるのは非常に難しいらしく、$D(n)$ は簡単に求められないようです。
※ 0変数ブール関数
$D(0) = 2$ との記述が Wikipedia にありましたが、そもそも0変数のブール関数とは何かという話になります。
私の理解が厳密でなくて申し訳ないのですが、0変数のブール関数としては以下の2種類が考えられます。
- 入力が存在せず、出力が常に $0$ $(\ f() = 0 \ )$
- 入力が存在せず、出力が常に $1$ $(\ f() = 1 \ )$
これらいずれも入力変数が無く常に同じ値を取るので、出力が $1$ から$0$ に変わることはありません。
よって、単調という扱いになると思うので、0変数ブール関数の個数は2個です。 $(\ D(0) = 2 \ )$
デデキント数に関するニュース
2023
9番目のデデキント数 $D(9) = 286386577668298411128469151667598498812366$ が発見されたのは実は2023年です。
偶然にも、別々の二者によって4月上旬のほぼ同時期にプレプリントにて公開されました。
詳しくは以下のページをどうぞ。
[usemath] [sumaho] 今年(2023)に目にした素数・整数関連のニュースを簡潔に一覧にしました。 素数・整数のトピックは適当に不定期で確認していただけなので、内容スカスカです…。(ごめんなさい) (単に私[…]
