論理と証明の基本 - Unityと数学と音楽の学習帳

論理の道具箱

偶数、奇数の四則演算の特徴

偶数×奇数＝偶数
偶数×偶数＝偶数
奇数×奇数＝奇数

偶数＋奇数＝奇数
偶数＋偶数＝偶数
奇数＋奇数＝偶数

偶数×偶数=偶数の証明

偶数： $\left\{ \forall n\in \mathbb{Z}|2n \right\}$
奇数： $\left\{ \forall n\in \mathbb{Z}|2n-1 \right\}$

命題： $\exists n\in \mathbb{Z},m={ \left( 2n \right) }^{ 2 }\Rightarrow m=2n$
この真偽を判断する。左辺を変形して整数部分を見つける
$m=\left\{ \forall l\in 2{ n }^{ 2 }\in \mathbb{Z}|2l \right\} \quad \Rightarrow \quad m=\left\{ \forall n\in \mathbb{Z}|2n \right\}$
集合として結論付ける
$\therefore true,\quad { \left( 2n \right) }^{ 2 }\subset 2n$

ド・モルガンの法則

$\overline { A\cap B } =\overline { A } \cup \overline { B } \\ \overline { A\cup B } =\overline { A } \cap \overline { B }$

例

$A={ \left\{ 6の倍数 \right\} }=\left\{ 6z|z\in { Z } \right\} =\left\{ { 6,12,18,24,30,36,42,48,54,60,66,72,78,84,\cdots } \right\}$
$B={ \left\{ 8の倍数 \right\} }=\left\{ 8z|z\in { Z } \right\} =\left\{ { { 8,16,24,32,40,48,56,64,72,80,88,96,104,112, }\cdots } \right\}$
$A\cap B=AかつB。AとBの積集合(intersection)=\left\{ 6と8の最小公倍数（LCM）の倍数 \right\} =\left\{ 24の倍数 \right\} =\left\{ 24z|z\in { Z } \right\} =\left\{ 24,48,72,\cdots \right\}$
$A\cup B=少なくともAまたはB。AとBの和集合(union)=\left\{ 6または8の倍数 \right\} =\left\{ 6,8,12,16,18,24,30,32,36,40,42,\cdots \right\}$
$\overline { A } ={ \left\{ 6の倍数の否定 \right\} }=\left\{ \neg 6z|z\in { Z } \right\} =\left\{ 1,2,3,4,5,7,8,9,10,11,13,14,15,16,17,19,20,21,22,23,25,26,27,28,29,31,32{ ,\cdots } \right\}$
$\overline { B } ={ \left\{ 8の倍数の否定 \right\} }=\left\{ \neg 8z|z\in { Z } \right\} =\left\{ 1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19,20,21,22,23,25,26,27,28,29,30,31,33{ ,\cdots } \right\}$
$\overline { A\cap B } =\overline { A } \cup \overline { B } =ド\cdot モルガンの法則より、AとBの積集合の否定=集合Aの否定と集合Bの否定の和集合$
$\overline { A\cap B } =\overline { A } \cup \overline { B } =\left\{ 24の倍数の否定 \right\} =\left\{ \neg 24z|z\in { Z } \right\} =\left\{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,26,27,28,29,30,\cdots \right\}$
$\overline { A\cup B } =\overline { A } \cap \overline { B } =ド\cdot モルガンの法則より、AとBの和集合の否定=集合Aの否定と集合Bの否定の積集合$
$\overline { A\cup B } =\overline { A } \cap \overline { B } =\left\{ 6または8の倍数の否定 \right\} =\left\{ 1,2,3,4,5,7,9,10,11,13,14,15,17,19,20,21,22,23,25,26,27,28,29,31,33{ ,\cdots } \right\}$

論理

基本的に論理は集合を扱っている。左辺と右辺、それぞれの集合の大小と包含関係を掴み真偽（true、false）を判定する事が目的となる

$p\left( x \right) \Longrightarrow q\left( x \right)$

命題（proposition）と呼ばれる、これは意味的に提案（propose）に近い。この提案に対して真偽を判定する
$p\left( x \right) ならば q\left( x \right)$ 。この場合、 $p\left( x \right)$ を仮定、 $q\left( x \right)$ は結論となる
$p\left( x \right)$ は $q\left( x \right)$ の十分条件。 $q\left( x \right)$ は $p\left( x \right)$ の必要条件となる

この命題が必要十分条件で真である場合、集合の包含関係で表すと

$\left\{ x|p\left( x \right) \right\} \subset \left\{ x|q\left( x \right) \right\}$ 　

「 $\subset$ 」はサブセットと読む。意味は集合 $\left\{ x|p\left( x \right) \right\}$ は集合 $\left\{ x|q\left( x \right) \right\}$ に含まれるとなる
（必要十分条件を満たした状態で、仮定は結論の集合に含まれる形になる）
ちなみに両方の集合が同じ大きさ、同じ要素の内容である場合「同値」（数学記号「 $\Leftrightarrow$ 」）となる

f:id:cqbosinko:20171003180528p:plain

論理の使用

参考資料：

xかつyが6の倍数でないならば、積xｙは6の倍数でない。これを論理記号で表現すると
$\overline { x\cap y } =\left\{ \neg 6z|z\in { Z } \right\} \quad \Longrightarrow \quad \overline { xy } =\left\{ \neg 6z|z\in { Z } \right\}$

$p\cap q$ は「pかつq（intersection:共通部分）」、 $\cap$ はキャップと読む。上線の　 $\overline { ～ }$ 、 $\neg$ 　は否定（not、negative）を意味する
$\Longrightarrow$ は「ならば（包含）」を表し、左辺を仮定、右辺を結論と意味づける。 $\mathbb{Z}$ は数学記号で整数を表す
「 $\in$ 」はインと読み左辺が右辺の要素であることを意味する。ここではzは任意の整数の一要素であることを表している

この仮定から導かれる結論の真偽を考えてみる。その論理が偽（false）である場合、その反例をひとつあげれば証明は完了する
この場合、x=2,y=3と仮定すればxy=6となり結論が合わない事が証明される。この命題は偽である

論理的に考える対象の集合の関係を知りたい場合、「逆」、「裏」、「対偶」を考える事が必要となる（対偶：ついになって向かい合うもの）

逆の命題。積xｙは6の倍数でないならば、xかつyが6の倍数でない。
$\overline { xy } =\left\{ \neg 6z|z\in Z \right\} \quad \Longrightarrow \quad \overline { x\cap y } =\left\{ \neg 6z|z\in Z \right\}$

裏の命題。xかつyが6の倍数ならば積xｙは6の倍数。
$x\cap y=\left\{ 6z|z\in { Z } \right\} \quad \Longrightarrow \quad xy=\left\{ 6z|z\in { Z } \right\}$

対偶の命題。積xｙは6の倍数ならばxかつyが6の倍数。
$xy=\left\{ 6z|z\in { Z } \right\} \quad \Longrightarrow \quad x\cap y=\left\{ 6z|z\in { Z } \right\}$

この場合の「逆の命題」は証明が非常に難しいが、一般に対偶はもとの命題と真偽が一致することを利用すれば「逆の命題の対偶に該当する裏の命題の証明」を使って証明が可能となる

対偶

抜粋：ベストとベターの違い

出来ない事を証明するのは実は凄く難しく、出来る事を証明する何倍も何十倍も労力がかかります。
なぜなら出来る事を証明するのは、ひったひとつの方法を示せばいいのですが、出来ない事を証明するにはあるゆる可能性を全て否定しなければなりません。

重要：対偶を利用する意味はここにある。命題の意味を反転させれば証明はひとつに絞られる

隠れた命題

6の倍数は2の倍数かつ3の倍数である。この命題は必要十分である。
このように一見、無関係に見えながら同値である命題を見つける事こそが重要だとも言える
（本質的に素数や因数分解の重要性がここに隠れている）

$x=\left\{ 6z|z\in \mathbb{Z} \right\} \quad \Leftrightarrow \quad x=\left\{ 2z\cap 3z|z\in \mathbb{Z} \right\}$

この命題の否定は

6の倍数以外は、少なくとも2の倍数以外もしくは3の倍数以外である。

$x=\left\{ \neg 6z|z\in \mathbb{Z} \right\} \quad \Leftrightarrow \quad x=\left\{ \neg 2z\cup \neg 3z|z\in \mathbb{Z} \right\}$

確認

$\neg 2z=\left\{ 1,3,5,7,9,11,13,\cdots \right\} \\ \neg 3z=\left\{ 1,2,4,5,7,8,,10,11,13,\cdots \right\} \\ \neg 2z\cup \neg 3z=\left\{ 1,2,3,4,5,7,8,9,10,11,13,\cdots \right\}$

証明の道具箱

不等式　 $p\ge q$ 　を証明するには　 $p-q\ge 0$ 　を示す

ある変数やある関数が同値であるかどうかを判定する場合、方法には二つある。係数比較法もしくは数値代入法

「 $\equiv$ 」　恒等性　恒等式で利用されることが多い

「 $=$ 」　相等性　方程式で利用されることが多い

冪等性ある操作を一回行っても複数回行っても結果が同じ。例： $0\times 0\times 0\times 0\times 0\times 0=0\quad ,\quad 1\times 1\times 1\times 1=1$ 　等

背理法

素因数分解の一意性

全ての正の整数は素数の積として一意に表せる

$\begin{matrix} 1=1 & 5=1\times 5 & 9=3^{ 2 } \\ 2=1\times 2 & 6=2\times 3 & 10=2\times 5 \\ 3=1\times 3 & 7=1\times 7 & 11=1\times 11 \\ 4={ 2 }^{ 2 } & 8=2^{ 3 } & 12={ 2 }^{ 2 }\times 3 \end{matrix}$

幾何と代数

幾何的に二つに分けられないものも代数的には二つに因数分解できる場合などがある
まっぷたつに六角形を三角形二つに分けろと言われた場合、代数的に二項式に素因数分解すればよい

f:id:cqbosinko:20171226165504p:plain

${ x }^{ 6 }-1=\left( { x }^{ 3 }+1 \right) \left( { x }^{ 3 }-1 \right)$

ここで重要な考えとは、「幾何的には分解できなくても代数的に複素平面でカタチを分解できたという事」。集合として数式で表すと

${ a }_{ n }=\left\{ x|{ x }^{ 3 }+1 \right\} =\left\{ -1,\frac { 1-\sqrt { 3 } i }{ 2 } ,\frac { 1+\sqrt { 3 } i }{ 2 } \right\} \\ b_{ n }=\left\{ x|{ x }^{ 3 }-1 \right\} =\left\{ 1,\frac { -1-\sqrt { 3 } i }{ 2 } ,\frac { -1+\sqrt { 3 } i }{ 2 } \right\}$

集合を分ける事が出来たという事は分別が付いたという事になる。証明などで別々のものとして扱えることになる

＜pocketCasでの検証計算＞
f:id:cqbosinko:20171226180655p:plain

素数

1より大きい自然数
正の約数が1と自分自身（既約性）
約数の数が常にふたつ

合成数

1より大きい自然数
素数でない

$\sqrt { 2 }$ が有理数で無い事を証明

$\sqrt { 2 } =\frac { p }{ q }$

この時p,qは既約分数であるとする。従ってp,qは互いに素、素数同士である。右辺は有理数である。この式の両辺を二乗すると

$\sqrt { 2 } =\frac { p }{ q } \quad \Rightarrow \quad 2=\frac { { p }^{ 2 } }{ q^{ 2 } } \quad \Leftrightarrow \quad 2q^{ 2 }={ p }^{ 2 }\quad \Leftrightarrow \quad 2\cdot q\cdot q={ p }\cdot p$

両辺は素因数分解で表現された合成数であるが、その構成されている素数の数が既約されているにも関わらず異なる。両辺の素因数の要素と数があっていない。従って偽になる。

素因数分解の一意性を証明

0は無批判の仮定？

そこそも完全に無なるものがあり得るかという疑問がある

1は全ての単位の祖となる

正規化の根底には全てを１に対する比として考えるみたいなものがある？
全ての単位の祖を２と考える事も可能？⇒メルセンヌ素数？