背景

• たまに間違って理解していたり、理解が浅かったりする概念のメモ
• 特に人とディスカッションをしていたりする時に概念が曖昧だと混乱の元

条件

命題と条件と前提

• 命題
  • 真か偽かを決められる文
  • 例：「Aさんは東京に住んでいる」「2は偶数である」
• 条件
  • ある結論・目的・状態が成り立つための要件や前提
  • 多くの場合、命題として表せる。ただし、別の命題との関係の中で「必要条件」「十分条件」などの役割を持つ
• 複合命題
  • 複数の命題を、否定・かつ・または・ならばなどで組み合わせた命題
  • 例：$P \Rightarrow Q$ は、「$P$ ならば $Q$」という複合命題
• 前提
  • 議論や推論を始める際に、ひとまず正しいものとして置く命題・仮定
  • 前提から、結論を導く
• 前提条件
  • ある物事や計画を成り立たせるために、あらかじめ満たしておくべき条件や事実の事

十分条件と必要条件とは

• 十分条件と必要条件は、「ある条件が、別の条件に対してどれくらい足りているか／欠かせないか」を表す言葉
• 義務教育でも習うし、ビジネスでもよく使う言葉である

十分条件と必要条件の例

わかりやすい例として、次の命題を考える。

東京に住んでいるなら、日本に住んでいる。

$$ P \Rightarrow Q $$

ここで、以下とする。

• $P$ ：東京に住んでいる
• $Q$ ：日本に住んでいる

このとき、条件は以下になる。

• 「東京に住んでいる」は「日本に住んでいる」の十分条件
• 「日本に住んでいる」は「東京に住んでいる」の必要条件

「東京に住んでいる」だけで「日本に住んでいる」と言えるため、前者は後者の十分条件になる。

また、「東京に住んでいる」ためには、少なくとも「日本に住んでいる」必要があるため、後者は前者の必要条件になる。

十分条件と必要条件の言い換え

わかりやすくいうと次：

• 十分条件（=充足条件）
  • それを満たせば、目的の条件を満たすことが保証される条件
  • 日常語に寄せると、「それがあれば足りる」条件
• 必要条件（=必須条件）
  • 目的の条件を満たすために、必ず満たしていなければならない条件
  • 日常語に寄せると、「それがないと成り立たない」条件

対偶は正しい

$$ P \Rightarrow Q $$

が正しいとき、常に正しいのはその対偶。

$$ \neg Q \Rightarrow \neg P $$

つまり、以下は正しい。

日本に住んでいないなら、東京に住んでいない。

裏と逆はUnknown

さっきの例だと、裏と逆は以下になる。

裏:

$$ \neg P \Rightarrow \neg Q $$

東京に住んでいないなら、日本に住んでいない。

逆:

$$ Q \Rightarrow P $$

日本に住んでいるなら、東京に住んでいる。

つまり、一方、元の命題が正しくても、逆や裏が正しいとは限らない。

ちなみに、逆と裏は互いに同値になる。

$$ Q \Rightarrow P \Leftrightarrow \neg P \Rightarrow \neg Q $$

まとめの例

前提として、PとQの条件を次のように定義する。

$$ P=\text{難しい課題が解ける} $$ $$ Q=\text{簡単な課題が解ける} $$

そして「難しい課題が解けるなら、簡単な課題も解ける」の（複合）命題を以下を定義する。

$$ P \Rightarrow Q $$

上記を認めるなら、整理はこうなる。

• 難しい課題が解ける ⇒ 簡単な課題も解ける
  • → True（元の命題）
• 簡単な課題が解けない ⇒ 難しい課題は解けない
  • → True（対偶）
• 簡単な課題が解ける ⇒ 難しい課題が解ける
  • → Falseとは限らない／一般には導けない（逆）
• 難しい課題が解けない ⇒ 簡単な課題も解けない
  • → Falseとは限らない／一般には導けない（裏）

最後はむしろ、次のような人が反例となる。

簡単な課題は解けるが、難しい課題は解けない。

また、対偶に対して反例っぽく見える例があるとしたら、それは対偶への反例ではなく、そもそもの前提の命題が間違っていることとなる。

証明

天使の証明（肯定命題の証明）

• 天使の証明とは、あるものが「存在する」ことを証明する簡単さを指す。
• 「一例で足りる存在証明」を、便宜上形式的に“天使の証明”と呼んでいる
• オレオレ定義の造語で、標準的な用語ではないので注意

悪魔の証明（否定命題の証明）

悪魔の証明とは、あるものが「存在しない」ことを証明する難しさを指す。

たとえば、次の二つを比べる。

• 宇宙人はいる
• 宇宙人はいない

「宇宙人はいる」を証明するには、確実な宇宙人の存在を一例示せばよい。

$$ \exists x, xは宇宙人である $$

一方で、「宇宙人はいない」を証明するには、宇宙全体を調べるか、宇宙人が存在すると論理的に矛盾することを示す必要がある。

$$ \forall x, xは宇宙人ではない $$

宇宙のように範囲が広く、すべてを観測できない対象では、不存在を証明することは特に難しい。

悪魔の証明の意味

悪魔の証明は単に「範囲が広いと証明できない」という意味ではなく、次のように捉えるとよい。

存在を示すには一例で足りることが多いが、不存在を示すには対象範囲全体の確認や、論理的な不可能性の証明が必要になる。

ただし、定義上ありえないものについては、不存在を論理的に証明できる。

例：

四角い円は存在しない。

これは「円」と「四角形」の定義が両立しないため。

量化子とは

「すべて」や「少なくとも一つ」といった表現は、論理では量化子で表す。

• $\forall$：すべての
• $\exists$：少なくとも一つ存在する

また、量化子が対象にする範囲を対象範囲（定義域）という。

量化子の例

たとえば、$U$ を宇宙に存在する対象全体とし、$A(x)$ を「$x$ は宇宙人である」とする。

その時、「宇宙人がいる」は、次のように書ける。

$$ \exists x \in U,\ A(x) $$

• これは「宇宙のどこかに、宇宙人であるものが少なくとも一つ存在する」という意味
• 一方、「宇宙人はいない」は次のように書ける

$$ \forall x \in U,\ \neg A(x) $$

これは「宇宙に存在するすべての対象について、宇宙人ではない」という意味。

量化子の証明方法

この二つでは、確認しなければならない範囲が異なる。

• $\exists$
  • 一つでも確実な例を見つければよい
• $\forall$
  • 対象範囲の任意の対象について成り立つことを示す必要がある
  • 注意
    • 有限の場合は、一つ一つ調べる事もOK
    • 無限の場合は、対象を個別に全部調べなくても、すべてに通用する一般的な根拠を示せば証明ともなる
  • たとえば「すべての偶数の二乗は偶数」は、すべての偶数を調べなくても証明できる。

そのため、対象範囲が広いほど、「存在しない」という主張を経験的に証明するのは難しくなる。

量化子の証明の難易度

量化子を使った証明の難易度は範囲が関係する。

例:

• 部屋の中

  この部屋（R）に宇宙人はいない。 $$ \forall x \in R,\ \neg A(x) $$

• 宇宙の中

  宇宙（U）に宇宙人はいない。 $$ \forall x \in U,\ \neg A(x) $$

宇宙が難しい理由:

• 部屋であれば範囲が限られているため、確認できる可能性がある
• 一方、宇宙全体を対象にすると、すべてを調べ切ることが難しい

量化子の否定

また、否定を取ると量化子は入れ替わる。

$$ \neg \left( \exists x,\ A(x) \right) \Leftrightarrow \forall x,\ \neg A(x) $$

「宇宙人がいる、ということはない」は、「すべての対象は宇宙人ではない」と同じ意味になる。

逆に、

$$ \neg \left( \forall x,\ A(x) \right) \Leftrightarrow \exists x,\ \neg A(x) $$

「すべての対象が宇宙人である、とは限らない」は、「宇宙人ではない対象が少なくとも一つある」と言い換えられる。

まとめ

• 天使は対象範囲を広げて、悪魔は対象範囲を狭めると確率的に存在の証明がしやすい
• ただし、存在を示す場合でも、挙げた一例が本当に条件を満たすことまで示す必要がある
• 相手が間違った証明をしていると言いたければ、反例を一つ出せばいい
• 元の命題が正しくても、その逆と裏が正しいとは限らないので注意
• 反例が出たときは、対象範囲・前提・結論を見直し、必要に応じて条件を追加したり、主張の範囲を限定したりする
• もしくは、カレーが食べたい vs. ラーメンが食べたい => カレーラーメンを食べる（アウフヘーベン）みたいな、主張のmixもできる