数理論理学・集合論の問題

真理値を $0<1$ で順序づけ、真理値割り当てを $\{0,1{\}}^3$ の元と見て成分ごとの順序を入れる。

表せる関数の特徴づけ. $\wedge ,\vee$ は単調なので、この形の論理式が表すブール関数 $f:\{0,1{\}}^3\to \{0,1\}$ はすべて単調（$a\le b\Rightarrow f(a)\le f(b)$）である。また、すべて $0$ の割り当てでは値 $0$、すべて $1$ の割り当てでは値 $1$ をとるので、定数関数ではない。

逆に、定数でない単調関数 $f$ は表せる。$f$ が真になる割り当てのうち極小なものに対応する変数の集合を $S_1,\dots ,S_k$ とすると、$f$ は単調なので $$f=\underset{j=1}{\overset{k}{\bigvee }}\underset{i\in S_j}{\bigwedge }{x}_i$$ と書ける。$f$ が恒等的に $0$ でないので $k\ge 1$、恒等的に $1$ でないので（すべて $0$ の割り当てで偽なので）各 $S_j$ は空でなく、これは $\wedge ,\vee$ と変数だけの論理式である。

よって、同値類の個数は「定数でない単調ブール関数の個数」に等しい。

数え上げ. 定数でない単調関数は、極小な真の集合の族、すなわち $\{1,2,3\}$ の空でない部分集合からなる空でない反鎖（どの 2 つも包含関係にない族）と 1 対 1 に対応する。これを数える。
- $\{1,2,3\}$ のみ: $1$ 個（$x_1\wedge x_2\wedge x_3$）
- 2 元集合だけからなる反鎖: $\{12\},\{13\},\{23\}$ の空でない部分族で $2^3-1=7$ 個
- 1 元集合だけからなる反鎖: 同様に $7$ 個
- 1 元集合と 2 元集合を両方含む反鎖: 1 元集合 $\{i\}$ と、$i$ を含まない 2 元集合 1 つの組だけが可能（1 元集合を 2 つ含むと、それらと交わらない 2 元集合はない）。$3$ 個（たとえば $x_1\vee (x_2\wedge x_3)$）

合計 $1+7+7+3=18$。（定数関数 $2$ 個を加えた $20$ が 3 変数の単調ブール関数の個数（デデキント数）である。）

答えは $18$ である。

$\wedge ,\vee$ だけで作られる論理式が表す真理値関数は単調（$x_i$ を増やすと値が減らない）である。逆に、3 変数の単調ブール関数のうち定数でないものは、すべて $\wedge ,\vee$ のみの式で表せる（主加法標準形: 極小真ベクトルに対する $\bigwedge$ の $\bigvee$。定数関数 $\top ,\perp$ は変数の式としては作れない）。

3 変数の単調ブール関数の個数は Dedekind 数 $M(3)=20$。内訳は反鎖（極小真ベクトルの集合）で数えると、空 (恒偽)、$\{\varnothing \}$ (恒真) を含めて 20 個。

論理式は少なくとも 1 つの変数を含むので、恒偽 ($\perp$) と恒真 ($\top$) の 2 つは表せない。実際、$\wedge ,\vee$ のみの式はすべての変数を真にすれば真、すべて偽にすれば偽になる。残りの 18 個は、反鎖が空でも $\{\varnothing \}$ でもないもの。

確認: 反鎖の個数を大きさ別に数えると、1 要素: 非空部分集合 7 個、2 要素: 反鎖となる対 (3 個の 1 元集合から 3 通り、3 個の 2 元集合から 3 通り、1 元と無関係な 2 元 3 通り) 9 個、3 要素: 3 つの 1 元集合 1 個、3 つの 2 元集合 1 個で 2 個。計 $7+9+2=18$（空集合と $\{\varnothing \}$ を除く）。ただし 1 要素の反鎖で空集合を要素とするものは除いたので $\{\varnothing \}$ は含めず、1 要素の数は非空部分集合 7 個。よって 18 個。

答えは 18。