計算理論・ラムダ計算の問題

難易度 3大学院入試の専門科目の標準レベル大学院数学計算理論・ラムダ計算

変数 $x_{1}, x_{2}, x_{3}, x_{4}$ を用いる論理式を、次の規則で帰納的に定める。

各 $x_{i}$ $(1 \leq i \leq 4)$ は論理式である。
$φ, ψ$ が論理式ならば、 $\neg φ$ 、 $(φ \land ψ)$ 、 $(φ \lor ψ)$ も論理式である。

定数記号 $0, 1$ は用いない。論理式に $x_{1}, x_{2}, x_{3}, x_{4}$ を代入すると、写像 ${0, 1}^{4} \to {0, 1}$ が定まる。現れない変数には依存しない関数とみなす。

各変数 $x_{i}$ の出現回数がどれも高々 $1$ 回である論理式を、リードワンス論理式とよぶ。写像 $f : {0, 1}^{4} \to {0, 1}$ のうち、あるリードワンス論理式で表されるものの個数を求めよ。

この問題で使うもの

条件つきブール関数の数え上げ（説明と入口の問題）

この問題を解けるようになるまで（30 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

否定を葉まで押し下げ、同種のゲートをまとめた「標準木」を考えます。そのうえで、異なる標準木が異なる関数を表すこと、使われる変数にはすべて本質的に依存することを確かめましょう。

ヒント 2

根が $\land$ の標準木の個数を $A_{k}$ とします。根の子への葉の分割を考えると、各子はリテラル（2 通り）か根が $\lor$ の木（ $A_{m}$ 通り）なので、 $A_{k}$ が分割の和として漸化的に求まります。

ヒント 3

$A_{2} = 4$ 、 $A_{3} = 32$ となるので、ちょうど $2, 3$ 変数を使う関数はそれぞれ $8, 64$ 個です。あとは $A_{4}$ を分割の型 $1 + 1 + 1 + 1, 2 + 1 + 1, 2 + 2, 3 + 1$ ごとに数え、使う変数の選び方を掛けて合計します。

答えと解説

答えを見る

1144

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

1. 標準形への変形

ド・モルガンの法則を使うと、否定はすべて葉（変数）まで押し下げられる。変数の出現回数は変わらない。さらに $\land, \lor$ の結合律・交換律を使い、同じ種類のゲートが親子で続くときはまとめる。すると任意のリードワンス論理式は、次の形の標準木で表せる。

葉は互いに異なる変数のリテラル（ $x_{i}$ か $\neg x_{i}$ ）である。
内部節点は $\land$ か $\lor$ で、子は $2$ 個以上、子の順序は区別しない。
親子の内部節点は種類が交互になる。

2. 使われる変数にはすべて本質的に依存する

リードワンス論理式は、そこに現れる変数すべてに本質的に依存する（したがって定数関数ではない）。これは帰納法で示せる。

$φ \land ψ$ では、 $φ$ と $ψ$ の変数は互いに素で、 $ψ$ は定数でない。そこで $ψ = 1$ となるように $ψ$ の変数を固定すれば、 $φ$ の変数への依存がそのまま残る。
$\lor$ のときは $ψ = 0$ となるように固定すればよい。 $\neg$ のときは明らかである。

3. 標準木は関数から一意に復元できる

異なる標準木は異なる関数を表すことを示す。

*(a) 2 変数の最小共通祖先の種類が $f$ から決まる。* 変数 $x, y$ が葉にあるとする。他の変数を固定して $x, y$ の両方が本質的になるようにすると、 $f$ の制限は次の形になる。
$ℓ_{x} \circ ℓ_{y} (ℓ_{x}, ℓ_{y} はリテラル)$
ここで $\circ$ は $x, y$ の葉の最小共通祖先のゲートである。理由は次のとおり。最小共通祖先の両側の部分木は $ℓ_{x}, ℓ_{y}$ か定数に退化し、他の兄弟は定数になる。 $x, y$ がともに本質的なら、兄弟の定数は中立元でなければならない。また、そのような固定は 2. の議論により存在する。 $\land$ 型の関数は値 $1$ を $1$ 点でとり、 $\lor$ 型は $3$ 点でとるので、両者は区別できる。よって $\circ$ の種類は $f$ だけから決まる。

*(b) 木の構造が決まる。* (a) により、各変数対について「最小共通祖先が $\land$ か $\lor$ か」が分かる。根が $\land$ なら、根の子の部分木の変数集合は、「 $\lor$ で結ばれる」という関係のグラフの連結成分と一致する（異なる子にまたがる対はすべて $\land$ で結ばれるからである）。これを再帰的に繰り返せば木の形が決まる。

*(c) リテラルの符号が決まる。* 葉の符号は、 $f$ がその変数について単調増加か単調減少かで決まる。

したがって、ちょうど $k$ 個の変数を使うリードワンス関数の個数は、それらの変数をラベルとする標準木の個数に等しい。

4. 標準木の数え上げ

$k$ 個のラベル付き葉をもつ標準木のうち、根が $\land$ のものの個数を $A_{k}$ $(k \geq 2)$ とする。 $\land, \lor$ を入れ替えれば根が $\lor$ のものも $A_{k}$ 個ある。

根が $\land$ のとき、各子は「リテラル」（ $2$ 通り）か「根が $\lor$ の木」（ $A_{m}$ 通り）である。そこで $B_{1} = 2$ 、 $B_{m} = A_{m}$ $(m \geq 2)$ とおくと、
$A_{k} = 葉の集合の 2 個以上のブロックへの分割 \sum ブロック \prod B_{∣ ブロック ∣} .$

$A_{2} = B_{1}^{2} = 4$
$A_{3} = B_{1}^{3} + 3 B_{2} B_{1} = 8 + 24 = 32$
$A_{4}$ は分割の型ごとに数える。
$1 + 1 + 1 + 1$ ： $16$
$2 + 1 + 1$ ： $6$ 通り $\times 4 \cdot 2 \cdot 2 = 96$
$2 + 2$ ： $3$ 通り $\times 16 = 48$
$3 + 1$ ： $4$ 通り $\times 32 \cdot 2 = 256$

よって $A_{4} = 16 + 96 + 48 + 256 = 416$ 。

ちょうど $k$ 変数を使う関数の個数を $T_{k}$ とすると、
$T_{1} = 2, T_{2} = 2 A_{2} = 8, T_{3} = 2 A_{3} = 64, T_{4} = 2 A_{4} = 832.$

5. 合計

2. により、使う変数の集合が異なれば関数も異なる。また定数関数は表せない。よって求める個数は
$(1 4) T_{1} + (2 4) T_{2} + (3 4) T_{3} + (4 4) T_{4} = 8 + 48 + 256 + 832 = 1144.$

別解

リードワンス論理式で表される関数のうち、ちょうど $n$ 個の指定した変数すべてに本質的に依存するものの個数を $a_{n}$ とする。定数記号がないので、少なくとも 1 つの変数に依存する関数だけが対象になる。

$a_{n}$ の求め方。 $n \geq 2$ のとき、リードワンス関数は最上位が ∧ 型か ∨ 型のどちらかである。否定を取ると ∧ 型と ∨ 型が入れ替わるので、∧ 型は $a_{n} /2$ 個になる。

∧ 型の関数は、変数を互いに素な 2 個以上のブロックに分け、各ブロックの関数の積で表される。各ブロックの関数は、最上位が ∧ 型でないものでなければならない。そのようなブロック関数の個数を $c_{m} = a_{m} - a_{m} /2 = a_{m} /2$ （ $m \geq 2$ ）とおく。 $m = 1$ では $c_{1} = a_{1} = 2$ （ $x, \neg x$ ）である。

$a_{1} = 2$ 、 $c_{1} = 2$ 。
$n = 2$ : 分割は ${1, 1}$ のみで、 $c_{1}^{2} = 4$ 個。よって $a_{2} = 8$ 、 $c_{2} = 4$ 。これは 2 変数に依存する 14 個の関数から XOR と XNOR を除いた数と一致する。
$n = 3$ : 分割 ${2, 1}$ が 3 通りで $3 \cdot 4 \cdot 2 = 24$ 、分割 ${1, 1, 1}$ は $2^{3} = 8$ 。合計 32 個なので $a_{3} = 64$ 、 $c_{3} = 32$ 。
$n = 4$ : 分割 ${3, 1}$ は 4 通りで $4 \cdot 32 \cdot 2 = 256$ 。分割 ${2, 2}$ は 3 通りで $3 \cdot 16 = 48$ 。分割 ${2, 1, 1}$ は 6 通りで $6 \cdot 4 \cdot 4 = 96$ 。分割 ${1, 1, 1, 1}$ は $16$ 。合計 416 個なので $a_{4} = 832$ 。

全体の個数。 依存する変数の部分集合ごとに数える。

$(1 4) \cdot 2 + (2 4) \cdot 8 + (3 4) \cdot 64 + 832 = 8 + 48 + 256 + 832 = 1144$

検算。 $a_{2} = 8$ は直接数えた結果と一致する。また、 $a_{3} = 64$ は 3 変数の「分解可能な」関数の個数として知られる値と整合している。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる