命題論理と証明：ステップごとの解答つき練習問題

1命題と結合子

命題は、真か偽のどちらかである文で、たとえば「7 は素数である」です。p や q のような文字で表し、真理値を 1（真）または 0（偽）で表します。

結合子を使うと、小さな論理式から大きな論理式をつくれます：

• ¬p（p でない）は値を反転させます。
• p ∧ q（かつ）は、両方が 1 のときだけ 1 です。
• p ∨ q（または）は、両方が 0 のときだけ 0 です。これは包含的な「または」で、両方が真でもかまいません。
• p → q（p ならば q）は、p = 1 かつ q = 0 のときだけ 0 です。
• p ↔ q（p と q は同値）は、p と q が同じ値のとき 1 です。

含意に戸惑う学生は多いです：p が偽のとき、q が何であっても p → q は真です。「雨が降ったら傘を持つ」という約束が破られるのは、雨の日に傘を持たないときだけです。

2真理値表

真理値表は、変数の真理値のすべての組み合わせを一覧にしたものです。異なる変数が n 個あれば 2ⁿ 行になります：2 変数なら 4 行、3 変数なら 8 行、4 変数なら 16 行です。同じ変数が 2 回現れても、1 つと数えます。

内側から順に進めます。部分式ごとに列を用意すると、新しい列では、すでにある列に結合子を 1 つ適用するだけで済みます。

1. 変数を並べ、2ⁿ 通りの組み合わせをすべて書きます。最初はすべて 1 です。
2. 部分式ごとに列を加えます。最も内側のものから始めます。
3. 各列を、その主結合子の規則で埋めます。
4. 最後の列から答えを読み取ります：1 を数えるか、問われている行を探します。

3例題

すべてのステップをたどりましょう。開く前に次のステップを予想してみましょう。

4同値と証明法

2 つの論理式の真理値表の列がまったく同じとき、それらは同値（≡）です。すべての行で 1 になるものが恒真式（トートロジー）、すべての行で 0 になるものが矛盾（恒偽式）、どちらでもないものが充足可能な非恒真式です。

よく使う法則：

これらの法則が証明法の土台です。p → q の対偶による証明は、同値な ¬q → ¬p を代わりに証明します。背理法による証明は、含意が成り立たなくなる唯一の場合である p ∧ ¬q を仮定し、不可能なことを導きます。

注意：逆 q → p と裏 ¬p → ¬q は、p → q と同値ではありません。

5量化子と妥当な論証

定義域上の変数に対して、∀x P(x) は「すべての x について P が成り立つ」、∃x P(x) は「少なくとも 1 つの x について P が成り立つ」を意味します。否定すると量化子が入れ替わります：

否定を 1 段階ずつ内側へ移します。内側では命題論理の法則を使います。たとえば ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)) で、「すべての P が Q であるわけではない」は「ある P は Q でない」を意味します。

論証は、すべての前提が 1 であるどの行でも結論が 1 のとき、妥当です。代表的な妥当な形は、肯定式（p → q、p、よって q）、否定式（p → q、¬q、よって ¬p）、仮言三段論法（p → q、q → r、よって p → r）です。

すべての前提が 1 で結論が 0 の行は反例です。後件肯定（p → q、q、よって p）は妥当ではありません：p = 0、q = 1 の行が反例です。

6よくある間違い

• p が偽のとき、p → q を偽としてしまう。p → q が偽になるのは、p = 1 かつ q = 0 のときだけです。
• 行数を求めるときに、繰り返し現れる変数を 2 回数えてしまう。
• 対偶 ¬q → ¬p を、逆 q → p や裏 ¬p → ¬q と混同する。
• ∀x P(x) の否定を ∀x ¬P(x) としてしまう：量化子は ∃ に変えなければなりません。
• ¬(p ∧ q) を ¬p ∧ ¬q と書いてしまう：ド・モルガンの法則では結合子も入れ替わります。

7試験問題の例

• やさしい：真理値表。行数を求める、論理式が真になる行を数える、論理式を真または偽にする 1 行をクリックする、といった問題です。
• ふつう：同値と証明法。論理式が恒真式・矛盾・そのどちらでもないもののどれかを判断する、同値な論理式を選ぶ、対偶による証明や背理法で示すべき主張を選ぶ、といった問題です。
• むずかしい：量化子と論証。量化された文を否定する、前提から導かれる結論を選ぶ、妥当でない論証の反例の行をクリックする、4 変数の表で真の行を数える、といった問題です。