命題・反例と全称・存在量化
条件付きの主張が偽になる場合と、「すべて」「少なくとも一つ」の違いを学びます。
説明
「4の倍数ならば偶数である」のように、条件Pが成り立つときにQも成り立つという主張を、含意と呼びます。Pが真なのにQが偽の例が一つでもあれば、その主張は成り立ちません。このような例が反例です。
このモジュールでは、整数の一覧から反例を探します。まず正しい主張と、その条件を逆にした主張を比較します。次に「すべての対象が条件を満たす」と「条件を満たす対象が少なくとも一つある」を計算し、対象の範囲を変えると結論も変わることを確認します。有限個の確認と、すべての整数についての証明は別のものとして扱います。
1調べる整数の範囲
まず0〜8を対象にします。割った余りが0なら、その整数の倍数です。
numbers = list(range(9))対象を0〜8にする; [(n, n % 4 == 0, n % 2 == 0整数・4の倍数・偶数) for n in numbers対象範囲の全整数]各行は整数、4の倍数か、偶数かの順です。0も4×0なので4の倍数に含まれます。
2命題が偽になる行を探す
「4の倍数ならば偶数」の反例は、4の倍数なのに偶数でない整数です。
[n for n in numbers候補の整数 if n % 4 == 0 and n % 2 != 04の倍数であり偶数でないもの]空のリストです。この範囲には反例がありません。整数全体でも成り立つことは、n=4kならn=2×(2k)と書けるため、偶数であると説明できます。有限の一覧に反例がないだけで一般的な証明が済むわけではありません。
3条件を逆にすると別の主張になる
今度は「偶数ならば4の倍数」という逆の主張です。偶数なのに4の倍数でない整数を探します。
[n for n in numbers候補の整数 if n % 2 == 0 and n % 4 != 0偶数であり4の倍数でないもの]2と6が反例です。元の主張が正しくても、その逆が正しいとは限りません。
4含意の真理値表
PならばQが偽になるのは、Pが真でQが偽の場合だけです。これはnot P or Qという論理式で表せます。
from itertools import product全組合せを作る機能; [(p, q, (not p) or qPならばQ) for p, q in product((False, True), repeat=2)PとQの全4組]True/Falseの行だけがFalseです。PがFalseの行では「Pが真なのにQが偽」という違反が起きないため、含意はTrueと定義します。これはPの発生がQの原因であるという意味ではありません。
5元の主張と同じ意味になる対偶
PならばQの対偶は、not Qならばnot Pです。ここでは「偶数でないなら4の倍数でない」に当たります。
[(n, (n % 4 != 0) or (n % 2 == 0)4の倍数なら偶数, (n % 2 == 0) or (n % 4 != 0)奇数なら4の倍数でない) for n in numbers0〜8について確認]各行の二つの結果は一致します。元の含意と対偶は同じ真偽になり、条件を単に逆にした主張とは異なります。
6「すべて」と「少なくとも一つ」
allは対象のすべてが真ならTrue、anyは少なくとも一つが真ならTrueになります。0〜8が偶数かを調べます。
all(n % 2 == 0 for n in numbers)すべて偶数か, any(n % 2 == 0 for n in numbers)偶数が少なくとも一つあるかすべて偶数ではないのでFalse、偶数は存在するのでTrueです。主張に「すべて」が付くか「一つでも」が付くかで、必要な条件が変わります。
7対象を偶数だけに絞った場合
対象範囲を、最初の一覧にある偶数だけへ絞ります。
evens = [n for n in numbers if n % 2 == 0]対象を偶数に限定; evens, all(n % 2 == 0 for n in evens)対象一覧と全称判定対象は0、2、4、6、8になり、すべて偶数という判定もTrueです。同じ条件式でも、何を対象にしているかで結論が変わります。
8対象が一つもない場合
空の対象集合に対する「すべて」と「存在」を調べます。
empty = []対象を空にする; all(n > 0 for n in empty)正でない反例があるか, any(n > 0 for n in empty)正の数が存在するかallはTrue、anyはFalseです。「すべてが正」は反例となる要素がないのでTrueですが、正の数が一つ存在するとはいえません。空集合で全称命題が真になることを空虚な真と呼びます。
9存在して、しかも全件が条件を満たす場合
全称判定だけでは、対象が空であることを除外できません。対象が存在することも要件なら、別の条件として加えます。
[(values, bool(values) and all(n > 0 for n in values)空でなく、すべて正の数) for values in ([], [1, 2], [0, 2])三つの対象集合]空リストはFalse、1と2はTrue、0と2はFalseです。「一件以上ある」と「全件が正」という二つの条件をANDで要求しています。
10「すべて」の否定は反例の存在
「すべて偶数ではない」は、「偶数でない整数が少なくとも一つある」という意味です。二つの式を比較します。
not all(n % 2 == 0 for n in numbers)すべて偶数、という主張を否定, any(n % 2 != 0 for n in numbers)偶数でない要素が存在どちらもTrueです。「すべて偶数ではない」を「すべて奇数である」と読むと意味が変わります。否定が全体に掛かるのか、各要素に掛かるのかを式で確認できます。
まとめ
PならばQの反例は、Pが真でQが偽の例です。逆の主張は一般には同じ意味になりませんが、対偶は同じ真偽になります。
全称や存在の判定では対象範囲を明らかにします。対象が空でもallはTrueになるので、存在自体が必要なら、その条件も加えます。
操作履歴と解説を振り返れます。
Python 3
numbers = list(range(9)); [(n, n % 4 == 0, n % 2 == 0) for n in numbers][(0, True, True), (1, False, False), (2, False, True), (3, False, False), (4, True, True), (5, False, False), (6, False, True), (7, False, False), (8, True, True)]
[n for n in numbers if n % 4 == 0 and n % 2 != 0][]
[n for n in numbers if n % 2 == 0 and n % 4 != 0][2, 6]
from itertools import product; [(p, q, (not p) or q) for p, q in product((False, True), repeat=2)][(False, False, True), (False, True, True), (True, False, False), (True, True, True)]
[(n, (n % 4 != 0) or (n % 2 == 0), (n % 2 == 0) or (n % 4 != 0)) for n in numbers][(0, True, True), (1, True, True), (2, True, True), (3, True, True), (4, True, True), (5, True, True), (6, True, True), (7, True, True), (8, True, True)]
all(n % 2 == 0 for n in numbers), any(n % 2 == 0 for n in numbers)(False, True)
evens = [n for n in numbers if n % 2 == 0]; evens, all(n % 2 == 0 for n in evens)([0, 2, 4, 6, 8], True)
empty = []; all(n > 0 for n in empty), any(n > 0 for n in empty)(True, False)
[(values, bool(values) and all(n > 0 for n in values)) for values in ([], [1, 2], [0, 2])][([], False), ([1, 2], True), ([0, 2], False)]
not all(n % 2 == 0 for n in numbers), any(n % 2 != 0 for n in numbers)(True, True)
演習完了