練習問題

偽の仮定からは任意の命題が証明できる事実に納得できず、\(P\) が偽のとき \(P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q\) は偽であるべきだと考える人がいるかもしれない。しかしこのとき、\(\operatorname{\text{\footnotesize IMPLIES}}\) は特定の論理結合子と同じ真理値表を持つことになる。どの論理結合子か？

あなたが受講中の講義では教科書が指定されており、近いうちに期末試験がある。命題 \(P\), \(Q\), \(R\) を次のように定める:

次の文章を \(P\), \(Q\), \(R\) と論理結合子 \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize NOT}}\), \(\operatorname{\text{\footnotesize IMPLIES}}\) を使った命題論理式に書き換えよ:

1. 講義の成績は A だったが、教科書の練習問題を全て解いたわけではない。

2. 教科書の練習問題を全て解き、期末試験の点数は A で、講義の成績は A だった。

3. 講義の成績で A を取るには、期末試験で A の点数を取る必要がある。

4. 期末試験の点数は A だったが、教科書の練習問題を全て解いたわけではない。それでも、講義の成績は A だった。

数学者が学生に向かって「関数が連続でないなら、それは微分可能でない」と言った。\(C\) を命題「考えている関数が連続」、\(D\) を命題「考えている関数が微分可能」と定めると、数学者の発言の唯一の適切な解釈は次の命題論理式で表される:

これを同値変形すれば次の命題論理式となる:

一方で、母親が息子に向かって「宿題をしないなら、テレビを見てはいけない」といったとする。\(H\) を命題「宿題をする」、\(T\) を命題「TV を見ることができる」と定めると、母親の発言の常識的な解釈は次の命題論理式で表される:

これを同値変形すれば次の命題論理式となる:

「 \(\cdots\) なら \(\cdots\) 」という形をした二つの発言が異なる形の命題論理式で表現される理由を説明せよ。

正整数 \(n\) を受け取って、\(n\) 個の命題変数を持つ真理値表の最初の \(n\) 列を出力する手続きを説明せよ。出力される \(n\) 列は \(n\) 個の命題変数に対する値の割り当てからなる必要がある。例えば \(n = 2\) のとき、出力は次のようになる:

解答は文章でも、Python や Java といった使い慣れた言語で書かれた単純なプログラムでも構わない。プログラムを答える場合は、出力例を解答に含めること。

不注意な Samサム は命題 \(P\) を証明しようとしている。彼は関連する命題 \(Q\), \(R\) を定義し、次の三つの含意を証明した:

そして彼は次のように論じた:

1. 次の二つの命題論理式の真理値表を作成せよ:

   \[ (P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q) \ \operatorname{\text{\footnotesize AND}} \ (Q \ \operatorname{\text{\footnotesize IMPLIES}}\ R) \ \operatorname{\text{\footnotesize AND}} \ (R \ \operatorname{\text{\footnotesize IMPLIES}}\ P) \tag{\(\ast\)} \]
   \[ P \ \operatorname{\text{\footnotesize AND}} \ Q \ \operatorname{\text{\footnotesize AND}} \ R \tag{\(\ast\ast\)} \]

   その真理値表を使って、\((\ast)\) が \(\textbf{T}\) となり \((\ast\ast)\) が \(\textbf{F}\) となるような \(P\), \(Q\), \(R\) に対する真理値の割り当てを見つけよ。

2. 不注意な Sam に真理値表を見せたところ、彼は「なるほど。\(P\), \(Q\), \(R\) が全て真とは言えないことは理解できたよ。でも、さっきの議論のどこが間違っていたのか分からないんだ。助けてくれない？」と言った。Sam の議論のどこがどのように間違っているか説明せよ。

デジタル回路設計で述語論理が利用されるときは、\(\textbf{T}\) を \(1\) で表し、\(\textbf{F}\) を \(0\) で表す慣習がある。簡単な例として \(2\) ビットの半加算器 (half-adder) の回路を考えよう。この回路は \(3\) 個のバイナリ入力 \(a_{1}\), \(a_{0}\), \(b\) と \(3\) 個のバイナリ出力 \(c\), \(s_{1}\), \(s_{0}\) を持つ。\(2\) ビットワード \(a_{1}a_{0}\) は \(0\) 以上 \(3\) 以下の整数 \(k\) の二進表現、\(3\) ビットワード \(cs_{1}s_{0}\) は整数 \(k + b\) の二進表現である。出力の第 \(3\) ビット \(c\) は最後のキャリー繰り上がりビット (carry bit) と呼ばれる。

例えば \(k\) と \(b\) が両方 \(1\) のとき、\(a_{1}a_{0}\) は \(\texttt{01}\) となり、出力 \(cs_{1}s_{0}\) は \(1 + 1 = 2\) の \(3\) 桁二進表現 \(\texttt{010}\) となる。

また、最後のキャリービット \(c\) が \(1\) となるのは入力の \(3\) ビットが全て \(1\) のとき、つまり \(k = 3\) かつ \(b = 1\) のときに限る。このとき \(cs_{1}s_{0}\) は \(3 + 1 = 4\) の二進表現 \(\texttt{100}\) となる。

\(2\) ビットの半加算器の入力と出力の関係は次の論理式で表される:

1. 上記の \(2\) ビット半加算器の構成を一般化することで、\(n+1\) ビット半加算器の構成を説明せよ。\(n+1\) ビット半加算器は \(n + 1\) 個の入力 \(a_{n}\), \(\ldots\), \(a_{1}\), \(a_{0}\), \(b\) と \(n + 2\) 個の出力 \(c\), \(s_{n}\), \(\ldots\), \(s_{1}\), \(s_{0}\) を持つ。この設定の下で、\(0 \leq i \leq n + 1\) のそれぞれに対して \(s_{i}\) と \(c_{i}\) を表す単純な論理式を示せ。ただし \(c_{i}\) は \(i + 1\) 桁目へのキャリーであり、\(c = c_{n+1}\) が成り立つ。

2. \(n + 1\) ビットのバイナリで表現された整数 \(a_{n} \ldots a_{1} a_{0}\) と \(b_{n} \ldots b_{1} b_{0}\) の和の各桁の値およびキャリーに対する同様の定義を示せ。

   デジタル回路として視覚化すると、この加算器は大量の \(1\) ビット半加算器から構成されていると分かる。この回路は人間が紙と鉛筆で足し算を計算するときの方法を模倣しており、現在の桁へのキャリーから次の桁のキャリーを計算する。そのため最後のキャリーを計算するには、最初のキャリーが全ての桁を通って最後まで伝わる必要がある。こういった設計を持つ回路をリップルキャリー (ripple-carry) 加算器と呼ぶ。リップルキャリー加算器は理解・記憶しやすく、実行される演算も最小限で済む。しかし、出力の上位桁と最後のキャリービットの値は \(n\) に比例する時間が経過しないと決定しない。

3. \((b)\) で示した加算器の定義に含まれる論理結合子の個数を種類ごとにまとめよ。

問題 3.6 で見たように、\(n+1\) ビット半加算器と呼ばれるデジタル回路は \(n + 1\) 個の入力

と、\(n + 2\) 個の出力

を持つ。

\(n+1\) ビット半加算器の入力と出力の関係は次の通りである。\(0\) または \(1\) が並んだ列 \(a_{n}\), \(\ldots\), \(a_{1}\), \(a_{0}\) を \(n+1\) ビットの整数の二進表現と解釈し、その整数を \(k\) とする。このとき、\(0\) または \(1\) が並んだ列 \(c\), \(s_{n}\), \(\ldots\), \(s_{1}\), \(s_{0}\) は整数 \(k + b\) の \(n+2\) 桁二進表現である。

例えば \(n = 2\) で \(a_{2}a_{1}a_{0}\) が \(\texttt{101}\) だと仮定する。\(\texttt{101}\) を二進表現として解釈すると \(k = 5\) が分かる。さらに \(b\) が \(\texttt{1}\) だとすれば、出力は \(5 + 1 = 6\) の \(4\) 桁二進表現である必要がある。つまり、出力 \(cs_{2}s_{1}s_{0}\) は \(\texttt{0110}\) となる。

半加算器には様々な設計が知られている。最も分かりやすい設計は問題 3.6 で触れた「リップルキャリー」半加算器である。この問題では並列設計 (parallel-design) あるいはルックアヘッドキャリー (look-ahead carry) と呼ばれる半加算器の設計を考える。この設計では、上位桁においてキャリーを \(0\) としたときの値と \(1\) としたときの値が並列に計算される。そしてキャリーの値が下位桁から伝わると、事前に計算した値が素早く選択される。

\(n+1\) ビット半加算器の並列設計に関する問題を通して、このアイデアを見ていこう。

並列設計の半加算器は \(\texttt{add1}\) モジュール (\(\texttt{add1}\)-module) と呼ばれる並列設計回路から構成される。\(\texttt{add1}\) モジュールの入力と出力の関係は半加算器の特殊ケースであり、半加算器の入力 \(b\) を \(1\) に固定すると \(\texttt{add1}\) モジュールの関係となる。つまり、\(n+1\) ビット \(\texttt{add1}\) モジュールは \(n+1\) 個のバイナリ入力

と、\(n+2\) 個のバイナリ出力

を持つ。\(a_{n} \ldots a_{1}a_{0}\) を \(n+1\) 桁二進表現として解釈した整数を \(k\) とするとき、\(cp_{n}\ldots p_{1}p_{0}\) は整数 \(k+1\) の \(n+2\) 桁二進表現である。

例えば \(1\) ビット \(\texttt{add1}\) モジュールは入力 \(a_{0}\) と出力 \(c\), \(p_{0}\) を持ち、次の関係が成り立つ:

リップルキャリーの設計では、規模を倍にした \(2(n + 1)\) ビット半加算器が出力を生成するのにかかる時間は \(n+1\) ビット半加算器の倍になる。これに対して並列設計の \(\texttt{add1}\) モジュールでは、規模が倍になっても出力が生成されるまでの時間がほとんど変わらない。この理由を理解しよう。

\(2(n + 1)\) 入力の \(\texttt{add1}\) モジュールの入力を

として、出力を

とする。図 \(\text{3.1}\) に示すように、\(2(n+1)\) ビット \(\texttt{add1}\) モジュールは \(n+1\) ビット \(\texttt{add1}\) モジュールを二つ並列に動作させる。

\(2(n + 1)\) ビット \(\texttt{add1}\) モジュールの具体的な動作は次の通りである。一つ目 (図中右) の \(\texttt{add1}\) モジュールは入力の下位 \(n + 1\) ビット \(a_{n}\), \(\ldots\), \(a_{1}\), \(a_{0}\) を受け取り、出力の下位桁 \(p_{n}\), \(\ldots\), \(p_{1}\), \(p_{0}\) とキャリー \(c_{(1)}\) を出力する。二つ目 (図中左) の \(\texttt{add1}\) モジュールは入力の上位 \(n+1\) ビット \(a_{2n+1}\), \(\ldots\), \(a_{n+2}\), \(a_{n+1}\) を受け取り、中間結果 \(r_{n}\), \(\ldots\), \(r_{1}\), \(r_{0}\) とキャリー \(c_{(2)}\) を出力する。

1. \(2(n+1)\) ビット \(\texttt{add1}\) モジュールのキャリー \(c\) を、二つの \(n+1\) ビット \(\texttt{add1}\) モジュールのキャリー \(c_{(1)}\), \(c_{(2)}\) のみを使って表せ。

2. \(2(n+1)\) ビット \(\texttt{add1}\) モジュールの定義を完成させよ。つまり、\(1 \leq i \leq n + 1\) に対する \(p_{n+i}\) を表す命題論理式を示せ。\(p_{n+i}\) を表す命題論理式は変数として \(a_{n+i}\), \(r_{i-1}\), \(c_{(1)}\) のみを含むべきである。

3. \(n+1\) ビット \(\texttt{add1}\) モジュールを使って \(n+1\) ビット並列設計半加算器を作る方法を説明せよ。つまり、\(a_{i}\), \(p_{i}\), \(b\) だけを変数として使って半加算器の出力 \(s_{i}\) を表す命題論理式を示せ。

4. デジタル回路の遅延 (latency) とは、入力から出力までの任意のパスが通るゲートの最大個数を言う。問題 3.6 で見たリップルキャリー半加算器の回路では、入力から出力 \(c\) (最後のキャリービット) までのパスに \(2n\) 個のゲートを通過するものが存在する。これに対して、並列設計半加算器はリップルキャリー半加算器より指数的に高速である。\(n\) ビット \(\texttt{add1}\) モジュールの入力から出力までの任意のパスに含まれる論理結合子の個数を数えることで、この事実を確認せよ。\(n\) は \(2\) の冪だと仮定して構わない。

1. この主張は真理値表を使って証明できる。この方法を使うとき、書くことになる真理値表の行数を答えよ。

2. 真理値表を使わずに、\(P\) の真理値に関する場合分けを使って主張を証明せよ。

\(n\) ビット \(\texttt{AND}\) 回路は入力 \(a_{0}\), \(a_{1}\), \(\ldots\), \(a_{n-1}\) と出力 \(c\) を持ち、次の関係が成り立つ:

\(n\) ビット \(\texttt{AND}\) 回路を設計する方法はいくつかある。直列設計 (serial design) とは、\(n - 1\) 個の \(\texttt{AND}\) ゲートを横に並べた単純な設計を言う。それぞれの \(\texttt{AND}\) の入力は回路の入力 \(a_{i}\) と、一つ前の \(\texttt{AND}\) ゲートの出力である (図 \(\text{3.2}\))。

これとは異なる樹状設計 (tree design) も考えられる。樹状設計の \(1\) ビット \(\texttt{AND}\) 回路は \(c ::= a_{0}\) である。議論を簡単にするため \(n\) が \(2\) の冪と仮定するとき、\(n > 1\) に対する樹状設計の \(n\) ビット \(\texttt{AND}\) 回路は、樹状設計の \(n/2\) ビット \(\texttt{AND}\) 回路を二つ用意して、それらの出力を \(\texttt{AND}\) ゲートに入力し、その \(\texttt{AND}\) ゲートの出力を \(c\) とした回路である (図 \(\text{3.3}\))。樹状設計の \(4\) ビット \(\texttt{AND}\) 回路を図 \(\text{3.4}\) に示す。

1. 直列設計の \(n\) ビット \(\texttt{AND}\) 回路には通常の \(2\) ビット \(\texttt{AND}\) ゲートがいくつ必要か？

2. デジタル回路の「速さ」を表す指標に遅延 (latency) がある。遅延は入力から出力までの任意のパスに含まれるゲートの最大個数と定義される。樹状設計の \(n\) ビット \(\texttt{AND}\) 回路が直接設計より指数的に高速であることを遅延の計算を通して示せ。

3. \(n\) が \(2\) の冪だと仮定する。樹状設計の \(n\) ビット \(\texttt{AND}\) 回路に \(n-1\) 個の \(\texttt{AND}\) ゲートが含まれると示せ。

正しい選択肢を選べ:

1. 「命題論理式 \(P\) が充足可能」と「\(P\) の否定が ( \(\cdots\) )」は同値である。

   • 充足可能でない

   • 充足可能

   • 恒真

   • 恒真でない

2. 「命題論理式 \(P\) が恒真」と「\(P\) の否定が ( \(\cdots\) )」は同値である。

   • 恒真でない

   • 恒真

   • 充足可能

   • 充足可能でない

3. 「命題論理式 \(F\), \(G\) が同値」と「( \(\cdots\) )」は同値である。

   • \(F \ \operatorname{\text{\footnotesize IFF}}\ G\) が真

   • \(F \ \operatorname{\text{\footnotesize IFF}}\ \operatorname{\text{\footnotesize NOT}} (G)\) が恒真でない

   • \(F \ \operatorname{\text{\footnotesize XOR}}\ G\) が充足可能

   • \(F \ \operatorname{\text{\footnotesize XOR}}\ G\) が充足可能でない

次に示す命題論理式が

• 恒真 (\(V\))

• 恒真でないが充足可能 (\(S\))

• 充足可能でない (\(N\))

のどれかを答えよ。恒真でないが充足可能な命題論理式に対しては、それが真になる真理値割り当てを示せ。

真理値表を使って、次の二つの命題論理式の同値性を確認せよ:

次の二つの命題論理式が同値だと示せ:

真理値表を使って、\(\operatorname{\text{\footnotesize AND}}\) に対する \(\operatorname{\text{\footnotesize OR}}\) の分配律を証明せよ。つまり、次の関係を示せ:

次の命題論理式は恒真である:

1. 紙とペンだけを持った (コンピューターを持たない) 一人の人間が真理値表を使って上記の事実を確認するには大変な手間がかかる理由を説明せよ。

2. \(A\) の真理値に関する場合分けを使うことで、上記の事実を証明せよ。

1. 真理値表を使って、次の命題論理式が恒真だと示せ:

   \[ (P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q) \ \operatorname{\text{\footnotesize OR}}\ (Q \ \operatorname{\text{\footnotesize IMPLIES}}\ P) \]

2. \(P\), \(Q\) を命題論理式とする。\(P\) と \(Q\) が同値なとき、かつそのときに限って恒真になる命題論理式 \(R\) を答えよ。ただし、\(R\) は \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\), \(\operatorname{\text{\footnotesize NOT}}\), \(P\), \(Q\) だけから構成されなければならない (それぞれ複数回使って構わない)。

3. 命題論理式が充足可能 (satisfiable) とは、それが真になるような命題変数への真理値割り当て ── 環境 (environment) ── が存在することを言う。次の関係が成り立つ理由を説明せよ:

   \[ P \text{ が恒真なのは } \operatorname{\text{\footnotesize NOT}} (P) \text{ が充足可能でないとき、かつそのときに限る。} \]

4. \(k\) 個の命題論理式 \(P_{1}\), \(\ldots\), \(P_{k}\) が無矛盾 (consistent) とは、ある環境で \(P_{1}\), \(\ldots\), \(P_{k}\) が全て真になることを言う。\(P_{1}\), \(\ldots\), \(P_{k}\) が無矛盾でないとき、かつそのときに限って恒真になる命題論理式 \(S\) を答えよ。

この問題¹では次の仕様が充足可能かどうかを調べる:

1. もしファイルシステムがロックされていないなら...

   1. 新しいメッセージはキューに積まれる。

   2. 新しいメッセージはメッセージバッファに送信される。

   3. システムは正常動作している。逆に、システムが正常動作しているなら、ファイルシステムはロックされていない。

2. 新しいメッセージがキューに積まれないとき、それはメッセージバッファに送信される。

3. 新しいメッセージはメッセージバッファに送信されない。

次の設問に答えよ:

1. 次に示す四つの命題変数を使って、上記の五つの文章を命題論理式に変換せよ:

   \[ \begin{aligned} L &::= \text{ファイルシステムはロックされている} \\ Q &::= \text{新しいメッセージはキューに積まれる} \\ B &::= \text{新しいメッセージはメッセージバッファに送信される} \\ N &::= \text{システムは正常動作している} \\ \end{aligned} \]

2. 仕様が全て真になるような命題変数 \(L\), \(Q\), \(B\), \(N\) に対する真理値割り当てを示すことで、仕様の集合が充足可能だと示せ。

3. \(\text{(b)}\) で示した割り当ては仕様を充足させる唯一の割り当てだと示せ。

命題論理式で利用できる論理結合子は半ダースほどあるものの、実際には \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\), \(\operatorname{\text{\footnotesize NOT}}\) があれば十分である。この三つの論理結合子を使えば、他の論理結合子を簡単に表現できる。例えば、\(A \ \operatorname{\text{\footnotesize IMPLIES}}\ B \) は \(\operatorname{\text{\footnotesize NOT}} (A) \ \operatorname{\text{\footnotesize OR}}\ B \) と同値である。つまり命題論理式に含まれる全ての \(\operatorname{\text{\footnotesize IMPLIES}}\) は \(\operatorname{\text{\footnotesize NOT}}\) と \(\operatorname{\text{\footnotesize OR}}\) を使った命題論理式で置き換えられる。

1. \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\), \(\operatorname{\text{\footnotesize NOT}}\) だけを論理結合子に用いる、\(A \ \operatorname{\text{\footnotesize IFF}}\ B\) および \(A \ \operatorname{\text{\footnotesize XOR}}\ B\) と同値な命題論理式をそれぞれ示せ。

2. \(\operatorname{\text{\footnotesize AND}}\) さえ必要ない理由を説明せよ。

3. \(\operatorname{\text{\footnotesize NAND}}\) を使えば、他の全ての論理結合子を作れることを示せ。\(A \ \operatorname{\text{\footnotesize NAND}}\ B\) は \(\operatorname{\text{\footnotesize NOT}} (A \ \operatorname{\text{\footnotesize AND}} \ B)\) と定義される。

五つの命題変数を持つ次の命題論理式 \(P\) を考える:

\(P\) は二つの \(\operatorname{\text{\footnotesize AND}}\) 節からなる DNF である。

1. \(P\) と同値な完全 DNF を答えよ。どのように見つけたか説明せよ。

   ヒント: 重要な部分を残して、重要でない部分は省略して真理値表の書くことはできないか？ 真理値表を全く書かずに答えが得られないか？

2. \(P\) と同値な完全 CNF を \(C\) とする。\(C\) を単純化して任意の二つの \(\operatorname{\text{\footnotesize OR}}\) 節が同値でないようにしたとき、その命題論理式には \(\operatorname{\text{\footnotesize OR}}\) 節がいくつ含まれるか？ その答えが正しい理由を簡単に説明せよ。ただし、\(C\) および \(C\) を単純化した命題論理式が持つ \(\operatorname{\text{\footnotesize OR}}\) 節を一つでも実際に求めてはいけない。

論理結合子 \(\operatorname{\text{\footnotesize NOR}}\) の定義を次に示す:

\(P\) を任意の命題論理式とする ── \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize IMPLIES}}\), \(\operatorname{\text{\footnotesize XOR}}\) といった通常の論理結合子が含まれていても構わない。このとき、論理結合子として \(\operatorname{\text{\footnotesize NOR}}\) だけを含む \(P\) と同値な命題論理式が存在する。その理由を説明せよ。

\(P\) を命題論理式とする。\(\overline{\mathstrut P}\) の DNF から \(P\) の CNF を直接得る簡単な方法を説明せよ。

ヒント: De Morgan の法則を適用すれば仕事の大半は終わる。一般的なケースに進む前に、自分で選んだ具体例に対して操作を適用してみるとよい。

命題変数として \(A\), \(B\), \(C\), \(D\) だけを含む命題論理式 \(P\) がある。\(A\), \(B\), \(C\), \(D\) に対する真理値割り当てと、そのときの \(P\) の値を次の真理値表にまとめる。\(P\) の DNF と CNF を答えよ。

命題論理式 \(P\) を次のように定める:

1. 第 3.4.2 項で示した同値公理を使って、\(P\) を同値な DNF に変形せよ。

2. 第 3.4.2 項で示した同値公理を使って、\(P\) を同値な CNF に変形せよ。

回路 SAT (circuit-SAT) 問題とは、\(1\) ビットの出力を持つデジタル回路が与えられたときに、その回路の出力が \(\textbf{T}\) となるような入力が存在するかどうかを判定する問題である。

回路 SAT の効率的解法があれば、命題論理式に対する通常の SAT (第 3.5 節)に対する効率的解法を構築できる。具体的には次の通りである。考えている命題論理式 \(F\) の値を計算する回路 \(C_{F}\) を構築すれば \(F\) の充足可能性が分かる: \(F\) が充足可能なのは、\(C_{F}\) に出力が \(\textbf{T}\) となる入力が存在するとき、かつそのときに限る。\(F\) から \(C_{F}\) を構築する処理も難しくない: \(F\) に含まれるそれぞれの論理結合子を二値ゲートで表現していけばよい。つまり回路 SAT を効率的に解く手続きがあれば、SAT を効率的に解く手続きが得られる。

逆に、与えられた回路 \(C\) から「同値」な命題論理式 \(E_{C}\) を構築する単純な再帰的手続きも存在する。ここで回路と命題論理式が同値とは、変数に対する任意の真理値割り当てにおいて \(E_{C}\) の値と \(C\) の唯一の出力が一致することを言う。ただし問題が一つある: 一般に、構築される \(E_{C}\) が \(C\) より「指数的に」大きくなる可能性がある。SAT と回路 SAT が同程度に難しい問題であることを示したいとき、問題の変換に指数的な時間がかかると、問題を変換するそもそもの目的「一方の問題の効率的な解法を仮定してもう一方の問題を効率的に解く」が達成できなくなってしまう。

しかし、回路 \(C\) と同値な命題論理式 \(E_{C}\) ではなく、回路 \(C\) と充足同値 (equisatisfiable) な命題論理式 \(F_{C}\) なら効率的に構築できる。つまり、\(C\) の出力を \(\textbf{T}\) にする入力が存在するとき、かつそのときに限って \(F_{C}\) を充足させる真理値割り当ても存在するような命題論理式 \(F_{C}\) である (\(F_{C}\) は \(C\) と同じ変数を持つ必要さえない)。その上で、\(C\) から \(F_{C}\) を構築する処理にかかる時間は \(C\) の大きさと同程度でなくてはならない。特に、\(F_{C}\) と \(C\) は同程度の大きさである必要がある。

\(F_{C}\) を構築する手続きのアイデアは次の通りである。二値ゲートから構成される \(1\) 出力の回路 \(C\) が与えられたとき、\(C\) に含まれるワイヤのそれぞれに異なる変数を割り当てる。このとき \(C\) に含まれるゲートのそれぞれについて、その入力と出力の関係を表す命題論理式が存在する。例えば、ある \(\texttt{AND}\) ゲートの入力ワイヤに割り当てられた変数が \(P\), \(Q\) で、出力ワイヤに割り当てられた変数が \(R\) なら、この \(\texttt{AND}\) ゲートの入力と出力の関係は次の命題論理式によって表される:

1. 任意の回路 \(C\) が与えられたとする。\(C\) が何らかの入力に対して \(\textbf{T}\) を出力するとき、かつそのときに限って充足可能となり、加えて大きさが \(C\) に含まれるワイヤの個数に比例する命題論理式 \(F_{C}\) を構築する簡単な方法を説明せよ。

2. SAT を効率的に解く手続きからは回路 SAT を効率的に手続きが得られると結論付けよ。

3CNF (3-conjunctive normal form) とは、任意の \(\operatorname{\text{\footnotesize OR}}\) 節が \(3\) 個以下のリテラル (命題変数もしくは命題変数の否定) からなる CNF を言う。命題論理式 \(F\) が充足可能かどうかを判定する問題は一般に難しいのに対して、次の条件を満たす命題論理式 \(\mathcal{C}(F)\) はどんなときでも簡単に構築できる:

• 3CNF

• 各命題変数の使用回数は \(F\) における使用回数の \(24\) 倍以下

• \(F\) が充足可能なとき、かつそのときに限って充足可能

\(\mathcal{C}(F)\) と \(F\) が同値である必要はない点に注意してほしい。第 3.4.1 項で見たように、\(F\) を同値な CNF に変換する方法は存在し、その CNF の充足可能性は \(F\) の充足可能性と同値になる。しかし、\(F\) と同値な最小の CNF は \(F\) より \(24\) 倍ではなく指数的に大きくなる可能性がある。さらに、\(F\) と同値な 3CNF が存在しない場合もある。

\(\mathcal{C}(F)\) の構築する手続きの基本的なアイデアは「\(F\) に含まれる論理結合子ごとに新しい命題変数を導入する」である。例えば \(F\) を次の命題論理式とする:

\(F\) に含まれる \(4\) 個の命題論理式に対応する新しい命題変数 \(X_{1}\), \(X_{2}\), \(O\), \(A\) を次のように導入する:

それぞれの論理結合子には対応する部分論理式が存在する。論理結合子に対応する命題変数とその部分論理式を \(\operatorname{\text{\footnotesize IFF}}\) で結んだ命題論理式は、新しい命題変数に対する制約となる。例えば上の例からは、次の四つの制約が得られる:

1. これらの制約と \(O\) を \(\operatorname{\text{\footnotesize AND}}\) で結んだ命題論理式の充足可能性が命題論理式 \(\text{(3.33)}\) の充足可能性と同値である理由を説明せよ。

2. この方法で構築される任意の制約は、それぞれの命題論理式を最大でも \(24\) 回しか使わない 3CNF と同値である理由を説明せよ。

3. ここまでの結果を使って、任意の命題論理式 \(F\) から \(\mathcal{C}(F)\) を構築する方法を簡単に説明せよ (詳細を完全に詰める必要はない ── 大まかな説明で十分である)。

次の命題を考える:

1. \(\forall x\, \exists y.\ 2x - y = 0\)
2. \(\forall x\, \exists y.\ x - 2y = 0\)
3. \(\forall x.\ x < 10 \ \operatorname{\text{\footnotesize IMPLIES}}\ (\forall y.\ y < x \ \operatorname{\text{\footnotesize IMPLIES}}\ y < 9)\)
4. \(\forall x\, \exists y.\ (y > x \ \operatorname{\text{\footnotesize AND}} \ \exists z.\ y + z = 100)\)

議論領域が次の集合であるとき、偽である命題はどれかそれぞれ答えよ:

1. 非負整数全体の集合

2. 整数全体の集合

3. 実数全体の集合

\(Q(x,y)\) を次の述語と定める:

\(x\) の議論領域は学校の生徒全体の集合、\(y\) の議論領域は今までに放映されたクイズ番組全体の集合とする。

次の文章と同値な述語論理式はどれかを答えよ:

1. \(\forall x\, \forall y.\ \operatorname{\text{\footnotesize NOT}} (Q(x, y))\)
2. \(\exists x\, \exists y.\ \operatorname{\text{\footnotesize NOT}} (Q(x, y))\)
3. \(\operatorname{\text{\footnotesize NOT}} (\forall x\, \forall y.\ \operatorname{\text{\footnotesize NOT}} (Q(x, y)))\)
4. \(\operatorname{\text{\footnotesize NOT}} (\exists x\, \exists y.\ \operatorname{\text{\footnotesize NOT}} (Q(x, y)))\)

述語 \(P(x)\), \(Q(x)\), \(R(x)\), \(S(x)\) を次のように定める:

\(x\) の議論領域は全ての生物とする。

1. 量化子、論理結合子、そして述語 \(P(x)\), \(Q(x)\), \(R(x)\), \(S(x)\) を使って次の命題を表現せよ:

   1. ピザが好きなサルはいない。

   2. \(23\) 世紀生まれでピザが好きでない人間はいない。

   3. 6.042 の TA は全員サルである。

   4. 6.042 の TA に \(23\) 世紀生まれの人間はいない。

2. \(\text{(a)}\) の \(\text{(iv)}\) は \(\text{(i)}\), \(\text{(ii)}\), \(\text{(iii)}\) から論理的に従うか？ 従うなら証明を、従わないなら反例を示せ。

3. 日本語に変換せよ:

   \[ \forall x.\ (R(x) \ \operatorname{\text{\footnotesize OR}}\ S(x)) \ \operatorname{\text{\footnotesize IMPLIES}}\ Q(x) \]

4. 日本語に変換せよ:

   \[ (\exists x.\ R(x) \ \operatorname{\text{\footnotesize AND}} \ \operatorname{\text{\footnotesize NOT}} (Q(x))) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall x.\ (P(x) \ \operatorname{\text{\footnotesize IMPLIES}}\ S(x)) \]

反例モデルを見つけることで、次の命題が恒真でないと示せ:

次の命題が恒真でないと示す反例モデルを見つけよ:

反例モデルを定義すれば十分である。その正しさを証明する必要はない。

反例モデルを見つけることで、次の命題が恒真でないと示せ:

反例モデルを定義すれば十分である。その正しさを証明する必要はない。

次の命題の中で恒真なものを答えよ。恒真でないものに対しては反例モデルを示せ。

1. \(\exists x\, \exists y.\ P(x, y) \ \operatorname{\text{\footnotesize IMPLIES}}\ \exists y\, \exists x.\ P(x, y)\)
2. \(\forall x\, \exists y.\ P(x, y) \ \operatorname{\text{\footnotesize IMPLIES}}\ \exists y\, \forall x.\ P(x, y)\)
3. \(\exists x\, \forall y.\ P(x, y) \ \operatorname{\text{\footnotesize IMPLIES}}\ \forall y\, \exists x.\ P(x, y)\)
4. \(\operatorname{\text{\footnotesize NOT}} (\exists x.\ S(x)) \ \operatorname{\text{\footnotesize IFF}}\ \forall x.\ \operatorname{\text{\footnotesize NOT}} (S(x))\)

1. 次の命題論理式が恒真だと示せ:

   \[ (P \ \operatorname{\text{\footnotesize IMPLIES}}\ Q) \ \operatorname{\text{\footnotesize OR}}\ (Q \ \operatorname{\text{\footnotesize IMPLIES}}\ P) \]

2. \(\text{(a)}\) で示した恒真な命題論理式からは「含意を示すには、逆の含意が偽だと示せばよい」と分かる²。例えば、初等的な解析学からは次の命題が偽だと分かる:

   ある関数が連続なら、その関数は微分可能である。

   よって、その逆は真だと分かる:

   ある関数が微分可能なら、その関数は連続である。

   この命題は実際に正しい。

   だが、ちょっと待ってほしい！ 次の含意は間違いなく偽である:

   ある関数が微分可能なら、その関数は連続でない。

   ここから、その逆が真にならなければならないと分かる:

   ある関数が連続でないなら、その関数は微分可能である。

   しかし、この命題は明らかに偽である。

   ということは、これまでの議論のどこかに間違いがある。どこが間違っているか説明せよ。

あるメディア王は、ニュース番組だけを放映するテレビネットワークのアイデアを持っている。そのネットワークは LNN (Logic News Network) と呼ばれ、各番組は議論領域の定義といくつかの述語論理式を伝える。こうすれば起こったことを正確に伝えられると彼は考えた。例えば、番組は次のように始まる:

1. 続いて次の述語論理式が伝えられたとする。それぞれ日本語に翻訳せよ:

   1. \(\footnotesize\operatorname{\text{\scriptsize NOT}} (D(\text{Ben}) \ \operatorname{\text{\scriptsize OR}}\ D(\text{David})) \ \operatorname{\text{\scriptsize IMPLIES}}\ (L(\text{Albert}, \text{Ben}) \ \operatorname{\text{\scriptsize AND}} \ L(\text{Ben}, \text{Albert}))\)
   2. \(\footnotesize \forall x.\ ((x = \text{Claire} \ \operatorname{\text{\scriptsize AND}} \ \operatorname{\text{\scriptsize NOT}} (L(x, \text{Emily}))) \ \operatorname{\text{\scriptsize OR}}\ (x \neq \text{Claire} \ \operatorname{\text{\scriptsize AND}} \ L(x, \text{Emily}))) \\[5pt] \ \operatorname{\text{\scriptsize AND}} \ \\[5pt] \forall x.\ ((x = \text{David} \ \operatorname{\text{\scriptsize AND}} \ L(x, \text{Claire})) \ \operatorname{\text{\scriptsize OR}}\ (x \neq \text{David} \ \operatorname{\text{\scriptsize AND}} \ \operatorname{\text{\scriptsize NOT}} (L(x, \text{Claire}))))\)
   3. \(\footnotesize \operatorname{\text{\scriptsize NOT}} (D(\text{Claire})) \ \operatorname{\text{\scriptsize IMPLIES}}\ (G(\text{Albert}, \text{Ben}) \ \operatorname{\text{\scriptsize AND}} \ \exists x.\ G(\text{Ben}, x))\)
   4. \(\footnotesize \forall x\, \exists y\, \exists z.\ (y \neq z) \ \operatorname{\text{\scriptsize AND}} \ L(x, y) \ \operatorname{\text{\scriptsize AND}} \ \operatorname{\text{\scriptsize NOT}} (L(x, z))\)

2. 「\(\text{Claire}\) 以外の全員は \(\text{Emily}\) が好きだ」を表す、量化子 (\(\forall\), \(\exists\)) が含まれない述語論理式を示せ。今考えている議論領域では、任意の述語論理式は量化子を使われない同値な述語論理式に書き換えられる。その理由を説明せよ。前問までの述語論理式をそういった形に書き変えると、述語論理式はどれくらい大きくなるか？

次に示す述語論理式について、議論領域が \(\mathbb{N}\) (非負整数 \(0\), \(1\), \(2\), \(\ldots\) 全体の集合)、\(\mathbb{Z}\) (整数全体の集合)、\(\mathbb{Q}\) (有理数全体の集合)、\(\mathbb{R}\) (実数全体の集合)、\(\mathbb{C}\) (複素数全体の集合) のとき真かどうかをそれぞれ答えよ。自明でないものには簡単な説明を加えよ。

この問題では、ビット列に関する命題を論理式に変換することを考える。議論領域は有限長のビット列 \(\lambda\), \(0\), \(1\), \(00\), \(01\), \(11\), \(000\), \(001\), \(\ldots\) 全体の集合とする (\(\lambda\) は空文字列を表す)。変換後の論理式は通常の論理記号 (等号 \(=\) を含む) と変数、そして \(0\), \(1\) を表す記号 \(\texttt{0}\), \(\texttt{1}\) から構成される。

\(\texttt{0}\), \(\texttt{1}\) と変数からなる \(\texttt{01}x\texttt{0}y\) のような文字列は、記号が表す文字と変数が表すビット列の連結を表すと定める。例えば \(x\) が \(\texttt{011}\) で \(y\) が \(\texttt{1111}\) のとき、\(\texttt{01}x\texttt{0}y\) の値はビット列 \(\texttt{0101101111}\) である。

ビット列に関する命題と、それを表す論理式の例をいくつか次に示す。ここに示した命題は解答で使って構わない。

1. 次の命題を論理式で表せ:

   1. \(x\) は同じ文字列が三つ並んだ文字列である。

   2. \(x\) は \(0\) だけを含む偶数長の文字列である。

   3. \(x\) は \(0\) だけもしくは \(1\) だけを含む文字列である。

   4. \(x\) は何らかの整数 \(k \geq 0\) に対する \(2^{k} + 1\) のバイナリ表現である。

2. \(\operatorname{\text{\footnotesize NO-1S}}(x)\) の異なる定義を示す。少しトリッキーだが、この方がシンプルに書ける:

   \[ \operatorname{\text{\footnotesize PREFIX}}(x, \texttt{0}x) \tag{\(\ast\)} \]

   \((\ast)\) は \(x\) が \(0\) だけからなる文字列のときに限って真になる。その理由を説明せよ。

この問題では、議論領域が \(\mathbb{N}\) の述語論理式を考える。通常の論理記号に加えて、次の三項述語 \(A\), \(M\) を使えるとする:

例えば、「\(n\) が \(0\) に等しい」を意味する述語論理式 \(\operatorname{\text{\footnotesize ZERO}}(n)\) は次のように定義できる:

\(\operatorname{\text{\footnotesize ZERO}}\) が定義されたので、以降の議論 (および解答) では \(\operatorname{\text{\footnotesize ZERO}}\) を利用して構わない。さらに、\(\operatorname{\text{\footnotesize ZERO}}\) を使うと \(m > n\) を意味する述語論理式 \(\operatorname{\text{\footnotesize GREATER}}\) を定義できる:

以降の議論 (および解答) では \(\operatorname{\text{\footnotesize GREATER}}\) も利用して構わない。

次の命題を表す述語論理式を答えよ。解答は定義が示された記号だけを含むべきである。

1. 「\(m = n\)」を意味する \(\operatorname{\text{\footnotesize EQUAL}}(m, n)\)

2. 「\(n = 1\)」を意味する \(\operatorname{\text{\footnotesize ONE}}(n)\)

3. \(n = i \cdot (m \cdot j + k^{2})\)

4. 「\(p\) は素数」を意味する \(\operatorname{\text{\footnotesize PRIME}}(p)\)

5. 「\(n = 2\)」を意味する \(\operatorname{\text{\footnotesize TWO}}(n)\)

\(\text{(e)}\) の結果を拡張すると、\(\operatorname{\text{\footnotesize THREE}}(n)\), \(\operatorname{\text{\footnotesize FOUR}}(n)\), \(\operatorname{\text{\footnotesize FIVE}}(n)\), \(\ldots\) も同様に定義できる。

6. 「\(n\) は偶数」を意味する \(\operatorname{\text{\footnotesize EVEN}}(n)\)

7. [Goldbachゴールドバッハ の予想] \(4\) 以上の任意の偶数は二つの素数の和として表現できる。

8. [Fermatフェルマー の最終定理] 三項述語 \(X\) を次のように定義する:

   \[ X(k, m, n) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ k = m^{n} \]

   \(n > 2\) のとき、次の等式を満たす正の整数 \(x\), \(y\), \(z\) が存在しない:

   \[ x^{n} + y^{n} = z^{n} \]

9. [双子素数予想] \(2\) だけ離れた素数の組は無限に存在する。

次の述語および命題を、数学的な論理式を使って表現せよ。議論領域は非負整数全体の集合 \(\mathbb{N}\) とする。通常の論理結合子、変数、量化子に加えて、加算、乗算、等号の記号、そして非負整数定数 (\(0\), \(1\), \(\ldots\)) を使って構わない。ただし指数記号 (\(x^{y}\) など) は使ってはいけない。例えば、次の二つの述語論理式はいずれも「\(n\) は偶数」を表現する:

1. \(m\) は \(n\) の約数である。

2. \(n\) は素数である。

3. \(n\) は素数の冪である。

次の文章を述語論理式に変換せよ:

議論領域はクラスの生徒全員の集合とする。述語は次の二つだけを使ってよい:

• 「\(x\) と \(y\) は等しい」を意味する等号 \(x = y\)

• 「\(x\) は \(y\) にメールを送信した」を意味する \(E(x, y)\)

1. 次の文章を述語論理式に変換せよ:

   ある生徒は \(n\) 人以下のクラスメイトにしかメールを送っていない (自分は送信相手にカウントしない)。

   議論領域はクラスの生徒全員の集合とする。述語は次の二つだけを使ってよい:

   • 「\(x\) と \(y\) は等しい」を意味する等号 \(x = y\)

   • 「\(x\) は \(y\) にメールを送信した」を意味する \(E(x, y)\)

2. 次の文章を述語論理式に変換するとき、\(\text{(a)}\) の解答をどう利用できるか説明せよ。

   1. ある生徒はメールを \(n\) 人以上のクラスメイトに送った (自分は送信相手にカウントしない)。

   2. ある生徒はメールをちょうど \(n\) 人のクラスメイトに送った (自分は送信相手にカウントしない)。

多くのプログラミング言語では、異なる関数の引数の名前が同じでも問題は起こらず、「ローカル」な引数の名前はいつでも変更できる。述語論理式でも同じことが言える。

例えば、述語論理式 \(\forall x.\ P(x)\) に含まれる「ローカル」な変数の名前を書き換えると \(\forall y.\ P(y)\) になり、書き換え前後の二つの述語論理式は同値である。他にも、

は次と同値である:

こうすると述語論理式 \(\text{(3.34)}\) に含まれる二つの \(\forall x\) が互いに無関係な事実がはっきりする。

このように変数の名前を書き換えていくと、任意の述語論理式を全ての変数名が一種類の使われ方しかしない同値な述語論理式へと変換できる。具体的に定義すると、述語論理式 \(P\) が一意変数規則 (unique variable convention) を満たすとは、次の条件を満たすことを言う:

• 任意の変数 \(x\) について、\(x\) の量化は一回以下である。つまり、\(P\) には \(\forall x\) と \(\exists x\) の一方が一度だけ含まれるか、そうでなければ両方とも含まれない。

• \(\forall x.\ F\) または \(\exists x.\ F\) の形をした部分述語論理式があるとき、\(P\) に含まれる \(x\) は全て \(F\) に含まれる。

例えば述語論理式 \(\text{(3.34)}\) は \(\forall x\) を二つ含むので一意変数規則を満たさない。一方で述語論理式 \(\text{(3.34)}\) は一意変数規則を満たす。

もう一つ例を示す:

述語論理式 \(\text{(3.36)}\) は一意変数規則を満たさない。なぜなら、\(x\) が三回 (順に \(\forall x\), \(\exists x\), \(\exists x\) と) 量化されるからである。また、もう一つの規則も破っている。例えば、部分述語論理式 \(\exists y.\ P(x) \ \operatorname{\text{\footnotesize AND}} \ Q(y)\) 以外の部分で量化されていない \(y\) が使われている。

任意の述語論理式には、一意変数規則を満たす同値な述語論理式が存在することが言える。 \(\text{(3.34)}\) に含まれる \(x\) の一つを \(y\) に変更して \(\text{(3.35)}\) にしたのと同じ操作と行えばよい。

述語論理式 \(\text{(3.36)}\) に含まれる変数を変更することで得られる、一意変数規則を満たす同値な述語論理式を示せ。変数の変更を可能な限り少なくすること。

一意変数規則を満たす形式に述語論理式を変換する一般的な手続きは問題 7.32 で考える。

述語論理式が冠頭形 (prenex form) とは、全ての量化子が先頭に付いていることを言う。例えば、次の述語論理式は冠頭形である:

任意の述語論理式には同値な冠頭形の述語論理式が存在することが言える。述語論理式 \(P\) を冠頭形に変換する秘密のレシピを次に示す:

1. \(P\) に含まれる変数を、問題 3.41 で定義した一意変数規則が満たされるように変更する。

2. 量化される部分述語論理式で使われる全ての論理結合子を \(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\), \(\operatorname{\text{\footnotesize NOT}}\) だけを使って書き換える。

3. 量化子に対する De Morgan の法則 (第 3.6.5 項) を使って、否定を量化子の「内側」に移動させる。

4. 入れ子になった量化子の順序を保ちながら、全ての量化子を述語論理式の先頭に移動させる。例えば \(\forall y\) で始まる部分述語論理式の中に \(\exists x\) が含まれるなら、量化子を先頭に移動させるとき \(\forall y\) は \(\exists x\) より前に配置されなければならない。

この手法を使って、次の述語論理式の冠頭形を見つけよ:

\(\tilde{\mathbf{0}}\) を定数記号、\(\textbf{next}\) と \(\textbf{prev}\) を一引数の関数記号とする。

これらの記号に対する任意のモデルは、議論領域の要素を点として視覚化できる。モデルは \(\tilde{\mathbf{0}}\) を何らか点 \(e_{0}\) として解釈する必要がある。さらに、\(\textbf{next}\) と \(\textbf{prev}\) を議論領域から議論領域への全域関数 \(nextf\) および \(prevf\) として解釈する必要がある。この二つの関数は点 \(e\) から \(nextf(e)\) へ向かう \(\textbf{next}\) のラベルが付いた矢印、および点 \(e\) から \(prevf(e)\) へ向かう \(\textbf{prev}\) のラベルが付いた矢印で視覚化できる。

この問題では記号 \(\tilde{\mathbf{0}}\), \(\textbf{next}\), \(\textbf{prev}\) だけを用いた述語論理式の集合であって条件「それらの述語論理式を全て満たす任意のモデルは、非負整数全体の集合 \(\mathbb{N}\) のコピーを含む」を満たすものを考える。モデルが「\(\mathbb{N}\) のコピーを含む」とは、議論領域に \(0\), \(1\), \(\ldots\) に対応する要素が存在し、それらの要素に対して \(nextf\) が「\(+1\)」として振る舞い、\(prevf\) が「\(-1\)」として振る舞うことを言う。このように振る舞う \(nextf\) を後者関数 (successor) と呼び、\(prevf\) を前者関数 (predecessor) と呼ぶ。

さらに正確に言えば、モデルに含まれる \(\mathbb{N}\) のコピーは \(e_{0}\) から始まる相異なる要素の無限列を持ち、隣り合う要素が \(\textbf{next}\) のラベルが付いた矢印で結ばれる:

このとき \(nextf\) は後者関数となる。さらに、\(\textbf{next}\) のラベルが付いた矢印の終点から始点に向かう逆向きの \(\textbf{prev}\) のラベルが付いた矢印が存在すれば、\(prevf\) は後者関数として振る舞う:

ここには示されていないものの、\(e_{0}\) から \(e_{0}\) に向かう \(\textbf{prev}\) のラベルが付いたループ矢印が存在する。これは非負整数を考えるとき \(0\) から \(1\) を引いても値は変化しないと定める慣習に対応する。

この条件は次の単純な述語論理式で表せる:

述語論理式 \(\text{(3.38)}\) は、任意の点 \(e\) から \(\textbf{prev}\) 矢印をたどって進んだ後、さらに \(\textbf{prev}\) 矢印をたどって進むと \(e\) に戻ることを意味する。もちろん、この操作は複数の \(\textbf{next}\) 矢印の終点となる \(e\) が存在するとき不可能となる。

図 \(\text{(3.37)}\) に示された要素 \(e_{0}\), \(e_{1}\), \(\ldots\) の述語論理式による表現を専門用語で数項 (numeral) と呼ぶ。つまり、\(e_{0}\) の数項は \(\tilde{\mathbf{0}}\) であり、\(e_{n}\) の数項は \(\tilde{\mathbf{0}}\) に \(\textbf{next}\) を \(n\) 回適用した結果である。例えば \(e_{3}\) の数項は次の述語論理式となる:

以降の議論では \(e_{n}\) の数項を \(\tilde{n}\) と表記する。例えば \(\tilde{3}\) は述語論理式 \(\text{(3.39)}\) を表す。

ただ、述語論理式 \(\text{(3.38)}\) だけで \(\mathbb{N}\) のコピーが得られるわけではない。例えば、全ての数項が同じ値である状況を防ぐ規則が存在しない。言い換えれば、\(\textbf{next}(\tilde{\textbf{0}}) = \tilde{\textbf{0}}\) と述語論理式 \(\text{(3.38)}\) は矛盾しない (頭の中で確認してみよ)。\(\textbf{next}\) 矢印の始点と終点が同じになってはいけないと定めればいいと思うかもしれないが、そうしても二つの数項が互いの \(nextf\) となる状況は防げない。つまり、モデルが次の関係を満たす可能性がある:

こういった \(\textbf{next}\) 矢印による長さ \(2\) のループを禁止したとしても、長さ \(3\) のループが依然として存在できる:

もちろん他の長さについても同様である。ただ幸い、この問題はいずれにせよ必要となる条件によって解決される: \(\tilde{\mathbf{0}}\) の解釈 \(e_{0}\) を整数 \(0\) のように振る舞わせる条件である。

1. \(\tilde{\mathbf{0}}\) の値は後者関数の値とならない事実を表現する述語論理式を答えよ。また、\(\tilde{\mathbf{0}}\) から \(1\) を引いても値が変化しないと定める慣習を表現する述語論理式を答えよ。

述語論理式 \(\text{(3.38)}\) と \(\text{(a)}\) で答えた述語論理式が満たされるとき、数項は \(\mathbb{N}\) のコピーとして (図 \(\text{3.37}\) のように) 振る舞う。この事実を確認するには、数項が全て異なると示せばよい。

2. 述語論理式 \(\text{(3.38)}\) と \(\text{(a)}\) の解答を満たす任意のモデルにおいて、任意の異なる二つの数項が異なる値を持つ理由を説明せよ。

   ヒント: 「矢印」を使わずに述語論理式 \(\text{(3.38)}\) の意味を説明する。整列原理を使った解答も考えられる。

これで述語論理式 \(\text{(3.38)}\) と \(\text{(a)}\) の解答を満たす任意のモデルは \(\mathbb{N}\) のコピーだと分かった。

議論領域が \(\mathbb{N}\) のとき真になる論理式と、恒真 ── 任意の議論領域で真になる ── の論理式を最初は混同してしまうかもしれない。両者の違いを理解するために、モデルが述語論理式 \(\text{(3.38)}\) と \(\text{(a)}\) の解答を満たす場合でも、そのモデルが \(\mathbb{N}\) のコピーだけから構成されるとは限らない事実は確認しておくに値する。

例えば、モデルは \(\mathbb{N}\) のコピーを二つ含む可能性がある。ただ、この可能性は簡単に除去できる: それぞれの \(\mathbb{N}\) のコピーには \(0\) に対応する要素 (\(nextf\) 値とならない要素) が含まれるので、そういった要素は一つしか存在してはいけないと定めればよい。

3. 任意のモデルが \(\mathbb{N}\) のコピーを一つだけ持つことを保証するための追加の条件を表現する述語論理式を答えよ。

\(\text{(c)}\) の解答を追加したとしても、モデルが \(\mathbb{N}\) のコピー以外に奇妙な特徴を持った「蛇足」を持つ可能性は残される。

4. 述語論理式 \(\text{(3.38)}\) および \(\text{(a)}\), \(\text{(b)}\) の解答を満たすモデルであって、次の述語論理式も満たすものを示せ:

   \[ \exists x.\ x = \textbf{next} (x) \tag{3.40}\]

5. [スキップ可] 述語論理式 \(\text{(3.38)}\) および \(\text{(a)}\), \(\text{(b)}\) の解答を満たす任意のモデルで次の述語論理式が真になると示せ:

   \[ \forall x \neq \tilde{\textbf{0}}.\ \textbf{next}(\textbf{prev}(x)) = x \tag{3.41}\]

次の議論領域を順に考える:

次に示す述語論理式が初めて真になる議論領域を答えよ。全ての議論領域で偽になる場合は「\(\textbf{none}\)」と答えよ。それぞれの解答が正しい理由を簡単に説明すること。

1. \(\forall x\, \exists y.\ y = 3x\)
2. \(\forall x\, \exists y.\ 3y = x\)
3. \(\forall x\, \exists y.\ y^{2} = x\)
4. \(\forall x\, \exists y.\ y < x\)
5. \(\forall x\, \exists y.\ y^{3} = x\)
6. \(\forall x\, \exists y.\ y^{3} = x\)
7. \(\forall x \neq 0.\ \exists y, z.\ y \neq z \ \operatorname{\text{\footnotesize AND}} \ y^{2} = x = z^{2}\)

次の述語論理式は恒真でない:

述語論理式 \(\text{(3.42)}\) に対する反例モデルを次の中から全て選べ。解答が反例モデルである理由を簡単に説明せよ。

1. 議論領域 \(\mathbb{Q}\) と述語 \(P(x, y) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ y \cdot x = 1\)

2. 議論領域 \(\mathbb{R}\) と述語 \(P(x, y) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ y < x\)

3. 議論領域 \(\mathbb{R}\ \backslash \left\{0\right\}\) と述語 \(P(x, y) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ y \cdot x = 2\)

4. 議論領域「ビット列全体の集合 (空文字列を含む)」と述語 \(P(x, y) \ \ \overset{\text{def}}{\longleftrightarrow}\ \ yxy = x\)

ある講義を受講する学生 (の一部) が左から右に一列に並んでいる。列には \(2\) 人以上の学生が含まれると仮定する。次の述語を述語論理式に変換せよ。議論領域は講義を受講する学生全体の集合として、量化子 \(\forall\), \(\exists\) と全ての論理結合子 (\(\operatorname{\text{\footnotesize AND}}\), \(\operatorname{\text{\footnotesize OR}}\), \(\operatorname{\text{\footnotesize NOT}}\), \(\ldots\)) を使ってよい。述語としては次の二つだけを使うこと:

• 「\(x\) と \(y\) は等しい」を意味する等号 \(x = y\)

• 「列の中で \(x\) は \(y\) の左にいる」を意味する \(F(x, y)\): 例えば、列が「\(\text{cba}\)」のとき \(F(c, a)\) と \(F(c, b)\) は真になる。任意の生徒は自身より左にいるとはみなされず、\(F(x, x)\) は常に偽となる。

例えば、述語「\(x\) の後ろには \(2\) 人以上の学生がいる」は次の述語論理式で表現できる:

それぞれの解答では以前の設問に対する解答を (解けていなくても) 使ってよい。例えば \(\text{(c)}\) の解答では \(\operatorname{inline}(x)\) と \(\operatorname{first}(x)\) を使って構わない。

1. 「学生 \(x\) は列に含まれる」を意味する \(\text{inline}(x)\)

   ヒント: 列には少なくとも \(2\) 人の学生が含まれるので、\(\text{inline}(x)\) は「\(x\) の右または左に誰かがいる」を意味する。

2. 「学生 \(x\) は列の先頭である」を意味する \(\operatorname{first}(x)\)

3. 「学生 \(x\) は学生 \(y\) の右隣にいる」を意味する \(\operatorname{isnext}(x, y)\)

   ヒント: \(x\) と \(y\) の間には誰もいない。

4. 「\(x\) は列の先頭から \(2\) 番目である」を意味する \(\operatorname{second}(x)\)

この問題では非負整数 \(\mathbb{N}\) に関する述語論理式であって述語として \(\leq\) のみを含み、定数を一切含まないものを考える。

例えば、この条件の下で等号は次のように定義できる:

条件を満たす定義が示された述語は以降で使って構わない。例えば \(>\) は \(=\) を使って次のように定義できる:

次の述語を条件が満たされる述語論理式に変換せよ:

1. \(x = 0\)
2. \(x = y + 1\)

   ヒント: この関係が成り立つとき、\(y\) より大きい全ての整数は \(x\) 以上である。

3. \(x = 3\)

述語として等号だけを含む述語論理式を純粋等号 (pure euality) と呼ぶ。例えば

は純粋等号であり、「議論領域が単元集合である」を意味する³。また、次の述語論理式も純粋等号である:

これは「議論領域の要素数が \(2\) 以下である」を意味する。

一方、次の述語論理式は \(\geq\) を含むので純粋等号でない⁴:

次の述語を意味する純粋等号な述語論理式を示せ:

1. 議論領域の要素数がちょうど \(2\) である。

2. 議論領域の要素数がちょうど \(3\) である。

1. 非負整数に関する述語 \(R(n)\) が無限に多く (inifinitely often, i.o.) 真になるとは、\(R(n)\) が真になる \(n \in \mathbb{N}\) が無限に存在することを意味する。

   「\(R(n)\) は無限に多く真になる」は次の形をした述語論理式で表せる:

   \[ \mathbf{Q_{1}}\, \mathbf{Q_{2}}.\ R(n) \]

   ここで \(\mathbf{Q_{1}}\), \(\mathbf{Q_{2}}\) は量化子であり、次のいずれかである:

   \[ \begin{aligned} & \forall n, && \exists n, && \forall n \geq n_{0}, && \exists n \geq n_{0}, \\ & \forall n_{0}, && \exists n_{0}, && \forall n_{0} \geq n, && \exists n_{0} \geq n \end{aligned} \]

   述語論理式の議論領域は非負整数全体の集合とする。\(\mathbf{Q_{1}}\), \(\mathbf{Q_{2}}\) はどの量化子か答えよ。

2. 非負整数に関する述語 \(S(n)\) がほとんどいたるところで (almost everywhere, a.e.) 真になるとは、\(S(n)\) が偽になる \(n \in \mathbb{N}\) が有限個しか存在しないことを意味する。 「ほとんどいたるところで \(S(n)\) は真である」は次の形をした述語論理式で表せる:

   \[ \mathbf{Q_{3}}\, \mathbf{Q_{4}}.\ R(n) \]

   議論領域は非負整数全体の集合で、\(\mathbf{Q_{3}}\), \(\mathbf{Q_{4}}\) は上に示した量化子のいずれかである。どの量化子か答えよ。

\(f: \mathbb{N} \to \mathbb{R}\) を実数の値を取る全域関数とする。\(f\) の極限点 (limit point) とは、実数 \(r \in \mathbb{R}\) であって \(f(n)\) が \(r\) に近い値を無限に多く取るものを言う。ここで「\(r\) に近い値」は任意に選んだ \(\varepsilon\) に対して \(r\) からの距離が \(\varepsilon\) 以下である値を意味する。

\(r\) が \(f\) の極限点である事実は次の形の述語論理式で表せる:

ここで \(\mathbf{Q_{0}}\), \(\mathbf{Q_{1}}\), \(\mathbf{Q_{2}}\) は量化子であり、それぞれ次のいずれかである:

ただし \(n\), \(n_{0}\) の議論領域は非負整数全体の集合、\(\varepsilon\) の議論領域は実数全体の集合とする。\(\mathbf{Q_{0}}\), \(\mathbf{Q_{1}}\), \(\mathbf{Q_{2}}\) はどの量化子か答えよ。

\(f: \mathbb{R} \to \mathbb{R}\) を実数の値を取る全域関数とする。実数 \(r \in \mathbb{R}\) に対して、\(x\) が \(r\) に近づくときの \(f(x)\) の極限 (limit) とは、実数 \(a \in \mathbb{R}\) であって、\(x\) を \(r\) に十分近づければ \(f(x)\) と \(a\) の差を好きなだけ小さくできるものを言う。

この条件は次の形の述語論理式で表せる:

ここで \(\mathbf{Q_{0}}\), \(\mathbf{Q_{1}}\), \(\mathbf{Q_{2}}\) は量化子 \(\forall\) または \(\exists\) であり、\(\alpha\), \(\beta\) は \(\delta\) または \(\varepsilon\) である。それぞれどの記号か答えよ。