数学/証明
命題A⇒Bを証明するために
・対偶法:同値式を証明する方法。 ちなみに同値なものとして、¬B⇒¬Aや、¬A∨Bなどがある。
A | ¬A | B | A⇒B | ¬A∨B |
1 | 0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
・背理法:(¬A∨B)の否定式であるA∧¬Bを仮定し、矛盾を導びきだす。
ある論理式の否定である論理式を作る時は、 ∀,∃,∨,∧,命題Qを∃,∀,∧,∨,命題¬Qに置き換える。
∀ | ←→このように置き換えると否定論理式になる←→ | ∃ |
∃ | ∀ | |
∨ | ∧ | |
∧ | ∨ | |
命題Q | 命題¬Q |
命題論理は以下の記号を使って表される。
∧,∩ :論理積(かつ) ∨,∪ :論理和(または) ¬,^ :否定 (でない) ⇒,→ :導出 (ならば)
また、A⇒B then B⇒A よりA⇔B とすることも出来る
命題関数
集合 U 上で定義された命題 A(x) を考える。命題 A(x) が真となるような集合Uの要素 x の集合を、 命題関数 A(x) の真理集合といい、Aで表す。
それぞれの命題関数の真理集合は次のようになる。
命題関数 | 真理集合 |
A(x)∨B(x) | A∪B |
A(x)∧B(x) | A∩B |
¬A(x) | A^ |
A(x) ⇒ B(x) | A^∪B |
∀x∈U:A(x)⇒B(x)の成立している図
AはBの十分条件、BはAの必要条件である
Uの空間上でBの方がA以上の広い空間を持つ。このとき、全集合Uを集合A,Bと論理記号(∨,∧,¬)を使っていかにして表すか?! という問題に帰着できる。
即ち、以下の図で表すことができる。
この真理集合の考えを用いると、A⇒B の証明は視覚的に行うことができる。すなわち、
A(x) ⇒ B(x) を証明するには、A⊂B であることを確かめればよい。(記号は⊂でも⊆でもどちらでも良い)
実際に、A(x) ⇒ B(x) の真理集合は、A^∪B であり、命題がトートロジーであることから A^∪B=U に等しい。このとき、
A=A∩U=A∩(A^∪B)=(A∩A^)∪(A∩B)=A∩B⊂B から、A⊂B
逆に、A⊂B とすると、
U=A^∪A⊂A^∪B⊂U から、A^∪B=U
よって、命題 A(x) → B(x) は、トートロジーである。
例えば、全集合U:(生物)の中で、A:(人間)ならばB:(動物)である。
A,B⊂U:A⊂B
以下の4つの命題関数は同値である。
命題関数 | 読み方 | Mizarの場合 |
∀x A(x)⇒B(x) | for all x being NaturalNumber such that A(x) implies B(x) | for x being Nat st A.x implies B.x |
∀x A(x)⊂B(x) | for all x being NaturalNumber A(x) holds B(x) | for x being Nat A.x holds B.x |
∀x ¬A(x)∨B(x) | for all x being NaturalNumber such that not A(x) ∨ B(x) | for x being Nat st not A.x \/ B.x |
∀x ¬B(x)⇒¬A(x) | for all x being NaturalNumber such that not B(x) implies not A(x) | for x being Nat st not B.x implies not A.x |
裏
∃x ¬A(x)⇒¬B(x) | existence x being NaturalNumber such that not A(x) implies not B(x) | ex x being Nat st not A.x implies not B.x |
∃x A(x)∨¬B(x) | existence x being NaturalNumber such that A(x) ∨ not B(x) | ex x being Nat st A.x \/ not B.x |
トートロジー(恒真命題) tautology
真理値が全て、1(真)である命題を、トートロジーという。
A | ¬A | A⇒A | ¬A∨A |
1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 |
このように、全集合Uを埋め尽くすことが出来ればトートロジーになる。
従って、Aと¬Aを重ねると
となり、被い尽くすことが出来たので、トートロジーである。
矛盾命題 contradiction
真理値が全て、0(偽)である命題を、矛盾命題という。
A | ¬A | ¬(A⇒A) | ¬A∧A |
1 | 0 | 0 | 0 |
0 | 1 | 0 | 0 |
同様に
となり、埋めている部分が無いので、矛盾命題となる。
同値関係
1 | 反射律 | reflexivity | a~a |
2 | 対象律 | symmetry | a~b ⇒ b~a |
3 | 推移律 | transitive | (a~b & b~c) ⇒ a~c |
読み方(⇒:ならば、 &:かつ)
推移律と等価な関係
非反射関係 | irreflexivity |
非対称関係 | asymmetry |
強半順序関係 | strict partial order |
律番号 | 順序関係 | 説明 |
1,3 | 前順序(擬順序) | |
1,3 | 全擬順序 | 完全的な擬順序 |
1,2,3 | 同値関係 | 前順序に対象律が加わったもの |
1,¬2,3 | 半順序 | 前順序に反対称律が加わったもの |
1,¬2,3 | 厳密弱順序 | 強半順序関係で等価関係での比較が不可能な場合 |
¬2,3 | 全順序 | 完全関係 |
数学の証明は厳密性を保つため「一階述語論理」を使って行う。 「無限」に関する議論も「有限」と同様にして扱うことが可能となる。
∃Φ{1,2,3,4, ... ,n} このとき、以下の関係式が成り立つ ∀x Φ(x) ⇔ Φ(1)∧Φ(2)∧...∧Φ(n) ∃x Φ(x) ⇔ Φ(1)∨Φ(2)∨...∨Φ(n)
全てのxにおいて、H(x)、ならば、A(x)。 ∀x (H(x) → A(x) )
ある x が存在し、A(x)、かつ、B(x) ∃x (A(x) ∧ B(x)) ※∃の場合は、→ではなく、∧となる!
関係記号 Ψ(x,y)における同値関係
関係記号Ψ(x,y)は、集合における写像に対応している。
ただし、この場合は、ある固体領域内における要素と要素の対応関係とみるべきである。
限量記号(∀、∃)と、関係記号Ψ(x,y)を組み合わせた場合、 固体領域 (a,b) を考えてみる。この場合の対応関係は、以下の4通りである。 (a,b)、(a,a)、(b,a)、(b,b) この、Ψ(x,y)の組み合わせは以下のようになる。
∀x∀yΨ(x,y)⇔ ((a,a)∧(a,b))∧((b,a)∧(b,b))⇔(a,a)∧(a,b)∧(b,a)∧(b,b):全てのxについて、全てのyが、Ψ(x,y)において対応する
∀y∀xΨ(x,y) ⇔ ((a,a)∧(b,a)) ∧ ((a,b)∧(b,b))⇔ (a,a)∧(b,a) ∧ (a,b)∧(b,b):全てのyについて、全てのxが、Ψ(x,y)において対応する
∃x∃yΨ(x,y) ⇔ ((a,a)∨(a,b)) ∨ ((b,a)∨(b,b))⇔ (a,a)∨(a,b) ∨ (b,a)∨(b,b):あるxについて、あるyが、Ψ(x,y)において対応する
∃y∃xΨ(x,y) ⇔ ((a,a)∨(b,a)) ∨ ((a,b)∨(b,b))⇔(a,a)∨(b,a) ∨ (a,b)∨(b,b):あるyについて、あるxが、Ψ(x,y)において対応する
∀x∃yΨ(x,y) ⇔ ((a,a)∨(a,b)) ∧ ((b,a)∨(b,b))⇔ ((a,a)∨(a,b)) ∧ ((b,a)∨(b,b)):全てのxについて、あるyが、Ψ(x,y)において対応する
∃x∀yΨ(x,y) ⇔ ((a,a)∧(a,b)) ∨ ((b,a)∧(b,b))⇔ ((a,a)∧(a,b)) ∨ ((b,a)∧(b,b)):あるxについて、全てのyが、Ψ(x,y)において対応する
∀y∃xΨ(x,y) ⇔ ((a,a)∨(b,a)) ∧ ((a,b)∨(b,b))⇔ ((a,a)∨(b,a)) ∧ ((a,b)∨(b,b)):全てのyについて、あるxが、Ψ(x,y)において対応する
∃y∀xΨ(x,y) ⇔ ((a,a)∧(b,a)) ∨ ((a,b)∧(b,b))⇔ ((a,a)∧(b,a)) ∨ ((a,b)∧(b,b)):あるyについて、全てのxが、Ψ(x,y)において対応する
「二階述語論理」とは数学的帰納法、f(f(x))、などのように論理演算がそれ自身を含むものをいう。 従って自己を含む為に、その論理演算が証明可能か否かを判断できない命題が存在する。(ゲーデルの不完全定理)
数学の証明(Proof Check)はMizarという数理処理システムで行うことができる。