含意 (→) を AND/OR/NOT で表現
含意 (→) を AND/OR/NOT で表現
このレッスンで分かること
- 論理学には「ならば」を表す
→という記号があります- 含意の重要な性質は、
aがFalseのときはbの値に関わらずa → bがTrueになるという点です- 2 入力なので 4 通り
含意 (→) を AND/OR/NOT で表現 とは
論理学の含意 a → b を AND/OR/NOT の組み合わせで実装し、0/1 で返す関数を作ります。「a ならば b」の真偽の不思議さも体感します。
論理学には「ならば」を表す → という記号があります。a → b は日本語で「a ならば b」と読み、命題論理の基本演算の 1 つです。前提 a が True のときに帰結 b も True なら全体は True、a が True なのに b が False なら全体は False というルールです。AND OR NOT の組み合わせで作れるので、新しい記号というよりは「合成ゲート」だと考えるとスッキリ理解できます。
含意の重要な性質は、a が False のときは b の値に関わらず a → b が True になるという点です。これは「前提が成り立たない場合、結論については何も主張していない」と解釈できます。日常感覚では「雨が降った → 傘を持つ」が偽になるのは、雨が降ったのに傘を持たないときだけ、という感じです。雨が降らない日はそもそもこの命題が問題にならないので、便宜上 True 扱いになるのです。
含意の難所は「前提が False のときは全部 True」。この
空虚な真 (vacuous truth)がプログラマーの第一関門。
真理値表
2 入力なので 4 通り。表を覚えると速いです。
| a | b | a → b |
|---|---|---|
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
表を眺めると、a → b は NOT a OR b と同じ結果になっていることが分かります。これが含意を AND/OR/NOT で表現する公式です。
プレーンテキスト
a → b = (NOT a) OR bこの等価式は、論理学の証明や SAT ソルバー、Prolog などで頻繁に登場します。たとえば「在庫がない → 注文不可」は、NOT 在庫がない OR 注文不可 と書き換えられ、これは「在庫がある OR 注文不可」と同じ意味になります。
Python
def impl(a, b):
return (not a) or b
print(impl(False, False)) # True
print(impl(True, False)) # False
print(impl(True, True)) # True等価変形を可視化
図のポイント (テキスト併記)
NOT a OR bを回路で書くと、上のようなフローになります
NOT a OR b を回路で書くと、上のようなフローになります。論理回路の世界では OR ゲートの 1 つの入力に NOT ゲートを通すだけで含意が作れる、というシンプルな構造です。これは半導体設計から SQL の CHECK 制約まで応用範囲がとても広い等価式です。
「
NOT a OR b」というたった 1 行の式が、論理学の「ならば」のすべてを表現します。
含意の言い換え
含意にはいくつかの言い換えがあります。
対偶 (contraposition)はa → bと(NOT b) → (NOT a)が等価なこと。証明テクニックとして有名です。逆 (converse)はb → aで、これは元と同値ではないので注意。裏 (inverse)は(NOT a) → (NOT b)で、これも元と同値ではありません。
Python
# 対偶も同じ結果になる
def contra(a, b):
return impl(not b, not a)
print(impl(True, False)) # False
print(contra(True, False)) # False (同じ)つまり「雨が降った → 傘を持つ」の対偶は「傘を持たない → 雨が降らなかった」で、論理的には等価です。証明問題で「対偶を使う」と楽になるケースの裏側には、この等価変形があります。
対偶は元と等価。逆と裏は等価ではない。混同しないように注意。
よくある間違い
1 つめは、a → b を b → a だと思ってしまうケースです。これは「逆」であり、元と同値ではありません。2 つめは、前提が False のときに直感に反して結果が True になることに戸惑うケース。「空虚な真」と呼ばれる現象で、論理学の入り口でつまずきやすい部分です。3 つめは、Python で a >>= b を含意演算子だと勘違いするケース。Python には含意専用の記号がなく、not a or b と書くのが定石です。
Python
# 前提が False のとき、何を b に渡しても True
print(impl(False, True)) # True
print(impl(False, False)) # True (空虚な真)やってみよう
2 つの真偽値を 0/1 で表した a b を受け取り、a → b の結果を 0 か 1 で返す関数 implication(a, b) を実装します。実装は (NOT a) OR b を素直に書くだけで OK です。a = 1, b = 0 のときだけ 0 (False)、それ以外の 3 通りは 1 (True) を返せば正解です。比較演算で書くなら (a != 1) or (b == 1) と書いて int に変換するアプローチもありです。
よくある質問
Q. a → b と b → a の違いは何ですか？
A. a → b（含意）と b → a（逆）は論理的に等価ではありません。「雨が降る → 地面が濡れる」が真でも、「地面が濡れる → 雨が降った」は必ずしも真ではありません。本文の真理値表を使って 4 通りを比較すると、a=True, b=False のとき a → b は False ですが、b → a は True になり、結果が異なることが確認できます。
Q. 空虚な真はなぜ「真」扱いになるのですか？
A. 含意 a → b は「a が成立したとき、必ず b も成立する」という約束です。a が最初から False ならその約束が破られる機会がないため、約束は守られたと見なす、というのが論理学の取り決めです。これを空虚な真（vacuous truth）と呼びます。日常言語では違和感を感じますが、数学の証明や仕様記述では非常に便利な性質です。
Q. Python に含意専用の演算子がないのはなぜですか？
A. not a or b という一般演算子の組み合わせで完全に表現できるため、専用記号を追加するメリットが薄いからです。>> は右シフト演算子として既に使われており、含意への転用は混乱を招きます。実務でも含意が単独で頻出するケースは少なく、not a or b をそのまま書くのが Python の慣習です。
次のレッスン
次は ド・モルガンの法則 に進みましょう。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 含意 (→) の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 含意 (→) とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- (NOT a) OR b と等価な処理を実装する
- a が 0 のときは b に関わらず 1 を返す
- a が 1 かつ b が 0 のときだけ 0 を返す
入出力例
test-cases.txt
implication(0, 0) → 1
implication(0, 1) → 1
implication(1, 0) → 0
implication(1, 1) → 1