「ログイン済みなら閲覧できる」という仕様から、「閲覧できるならログイン済み」と判断してよいでしょうか。答えは、ほかの閲覧方法がないと分かるまでは判断できません。こうした条件の取り違えを防ぐのが論理です。記号を覚えるだけでなく、何を仮定して何を結論できるかを追えるようにします。
命題と論理結合子
命題は、真か偽かが定まる主張です。「7は奇数である」は命題ですが、「xは奇数である」はxの値や対象範囲を定める必要があります。pかつqをp∧q、pまたはqをp∨q、pではないことを¬pと書きます。通常の論理で「または」は両方が真の場合も含みます。日常語の「どちらか一方」と区別してください。
プログラムの条件にも同じ考え方が使えます。AかつBの否定は「Aでない、またはBでない」です。「Aでない、かつBでない」ではありません。例えば「成人かつ会員」に該当しない人には、成人の非会員も含まれます。否定を内側へ移すときは、ド・モルガンの法則で結合子も入れ替えます。
含意の向きを確かめる
p→qは「pならばq」を表し、pが真でqが偽の組合せでだけ偽になります。pが偽の場合、p→qは真です。これは原因と結果の説明ではなく、「pを満たす対象にqの例外がない」という条件を表すためです。p→qとq→pは別の主張です。両方を満たすときにp↔qと書きます。
p q p → q
真 真 真
真 偽 偽
偽 真 真
偽 偽 真「4の倍数なら偶数」は真ですが、逆の「偶数なら4の倍数」は6が反例です。元の主張と同値になるのは対偶の「偶数でなければ4の倍数ではない」です。逆と対偶を言葉の雰囲気で選ばず、¬q→¬pの形まで書いて確認しましょう。
すべて、少なくとも一つ、そして否定
∀x P(x)は対象のすべてでPが成り立つ主張、∃x P(x)は少なくとも一つで成り立つ主張です。∀x P(x)の否定は∃x ¬P(x)です。「すべてのリクエストが成功した」の否定は「失敗したリクエストが少なくとも一つある」であり、全件失敗までは意味しません。対象が空の場合の扱いも含め、まずxの範囲を定めます。
量化記号の順序も意味を変えます。「すべての利用者に、閲覧できるページがある」は∀u ∃p CanRead(u,p)です。「全利用者が閲覧できるページが一つある」という∃p ∀u CanRead(u,p)の方が強い条件になります。前者では利用者ごとに別のページを選べます。アクセス権やテスト条件を仕様化するときに役立つ区別です。
証明は仮定から結論までの道筋
直接証明では、仮定と定義から結論を導きます。整数nが偶数ならn=2kと書けるため、n²=4k²=2(2k²)となり、n²も偶数です。対偶を使うなら、nが奇数のときn=2k+1としてn²=2(2k²+2k)+1が奇数になることを示せます。後者から「n²が偶数ならnも偶数」が分かります。
反例は全称命題を否定するには一つで足ります。一方、100件のテスト成功は、無限にある入力すべてへの証明にはなりません。テストと証明は役割が異なります。テストは実装や実行環境の具体的な不具合を見つけ、証明は明示した仮定のもとで一般的な性質を示します。仮定が実装と合っているかは別に確認します。
理解を確かめる
「管理者なら設定を変更できる」から「管理者でなければ変更できない」を導けるか。導けません。これは逆の対偶に当たる別の主張で、一般利用者に変更権限を持つ例が反例になります。
「全要素が0以上」の否定を述べてください。「0未満の要素が少なくとも一つある」です。0以上でないことは0未満であり、0以下ではありません。
整数nについて「n²が奇数ならnが奇数」を対偶で示してください。「nが偶数ならn²が偶数」をn=2kから示せば証明できます。
この単元の概念：含意 量化記号 反例
続けて読む：値・型・制御構造・関数・モジュール