さらにもっともっと初歩的、基本的なことの質問：ねこ騙し数学：SSブログ

	ブログをはじめるログイン

ものすごく初歩的なことの質問｜数列の収束の復習２ブログトップ

さらにもっともっと初歩的、基本的なことの質問　[ひとこと言わねば] [編集]

さらにもっともっと初歩的、基本的なことの質問

「pならばq」は論理記号で書くと、

だにゃ。

という記号もあるけれど、この記号では埒が明かない！！

対して、「pならばq」の対偶は「qでないならばpでない」で、これを論理記号であらわすと、

となる。

これを変形すると、

となるので、「pならばq」とその対偶「qでないならばpでない」の真偽は一致する。

つまり、この２つの命題は同値だ。

「pならばq」の真偽表

の真偽表

「pならばq」の対偶の真偽表

なお、ここで使われている記号を説明すると、記号「¬」は命題の否定「ない」を表し、「∧」は「かつ」、論理積（連言）を表すにゃ。そして、「∨」は「または」、論理和（選言）を表すケロ。

高校の数学では、「pである」の否定はと上に「バー」を引いて表しすことが多いと思うけれど、大学の数学や論理学ではこの記号はあまり使わずに、「¬」を使うにゃ。

まぁ、「pならばq」を、高校数学風に

などと書いてもいいけれど・・・。

なお、ド・モルガンの法則をつかうと、「pならばq」は

になるにゃ。

この流儀を使うならば、

と、「qでないならばpでない」と「pならばq」の真偽が一致することを示すことができる。

命題「pならばq」を直接証明することが難しいとき、この命題と同値の対偶「qでないならばpでない」を証明し、それをもって「pならばq」の証明にすることはよくあることだにゃ。というか、「pならばq」と「qでないならばpでない」は同じ命題！！

このことは高校の数学で習ったと思う。

では、お前らに訊くにゃ。

命題「pならばq」を背理法をもちいて証明するとき、お前らはどうしているにゃ。

「¬」や「∧」なんて難しい記号を使わずに書いてもよし、こうした論理記号を使ってもよし、

お前ら、ネムネコにコッソリ教えるケロ。

なぜ、それで証明になるのか、この理由もあわせて、コメント欄に書いてネムネコのもとに送信するにゃ。

「質問内容が抽象的（曖昧か？）で、何を言っているかわからない」というヒトは、次の問題にチャレンジするケロ。

問　命題「x>1ならばx²>1」が真であることを背理法を用いて示せ。

この問を解くと、自分がどのような論理を使っているかがわかるのかもしれない。

そして、この問題を解けないとしたら、背理法がどのようななものであるかをまったく理解できていないのかもしれないケロね。

ところで、論理でいう矛盾って何だにゃ、どんな意味だにゃ。

この定義を知っているケロか？

いったい、何と何が矛盾しているにゃ。

そして、それは論理学でいう「矛盾」と一致しているケロか？

この曲の間に、これらの問に答えられないかもしれないので、さらにBGMを♪

１０時間あれば、足りるだろう(^^)

2018-11-29 22:07 nice!(2) コメント(2)

nice! 2

　続きです・・・。余計わけわかんなくなるかも知れないけど(^^;)。

【背理法と対偶関係】
　再び蒸し返しますか(^^;)。背理法と対偶関係は同じだと。ただし両者は厳密には違います。

　以下、命題理論を手短にまとめます。ネコ先生は意味論っぽくまとめてますが（真理表）、自分は構文論的に行きます。そういうので学んだのと、そうやった方が多少とも代数的になると思うので。ただしここで醸すのは論理の雰囲気だけです。ここで論理を知ろうとは思わないで下さいね(^^;)。

　論理は本来、数学で証明すべきものではないとも言えます。数学を始める以前に、それはやっとくべきものなのだと。なので以下で述べる事は、ある意味全て公理と考えてもらっても、そんなに間違いではないと思います。その最たるものが、

C1（三段論法）
　Ａ，Ｂを命題とする。ＡとＡ⇒Ｂが成立するなら、Ｂが成立。

です。Cの略記号（たぶんフランス語）は、推論法則を表します（法則だから公理みたいなもの(^^;)）。
　命題とはそこで扱う対象の間に成り立つ関係の事です（真偽は問わない）。命題を関係式と総称する本もあります。Ａが成り立つ事を、Ａが真と言う時もあります。
　論理記号を導入します。「否定」を「～」，「または」を「ou」，「かつ」を「et」で表します。これらを用いるのは趣味です。自分がなれてるのと、IME辞書で出やすいので(^^;)。

定義1.
　(～Ａ)ouＢを、Ａ⇒Ｂで略記する。

　これは含意の定義ですが、ここではその実際上の意味（意味論）は述べません。
　定義とは、省略記法の事です。ただそれだけです。例えば「Ａと(～Ａ)ouＢが成立するなら、Ｂが成立」を略記号⇒で表したのがC1です。この程度だと省略記法を用いてもあんまり変わりませんが、長い関係式では略記を使わないと、記述にメリハリがつかなくなり訳わかんなくなります。構文論と言っても、最後は意味ですからね(^^;)。

　次の4つを、命題理論のシェマと言います。実際上は命題理論の公理なんですが、論理は数学を始める以前のものだという立場から、公理って言わないんだと思います。

　　(S1) (ＡouＡ)⇒Ａは真。
　　(S2) Ａ⇒(ＡouＢ)は真。
　　(S3) (ＡouＢ)⇒(ＢouＡ)は真。
　　(S4) (Ａ⇒Ｂ)⇒((ＣouＡ)⇒(ＣouＢ))は真。

定義2.
　Ａet(～Ａ)が成り立つとき、その理論は矛盾すると言われる。

C2（連言の分離法則）
　(ＡetＢ)⇒Ａと(ＡetＢ)⇒Ｂは真。

　定義2.とC2から既に、次のC3を導けます。

C3（矛盾法則）
　ある理論が矛盾すれば、その理論において全ての命題は真である。
［超数学的証明］
　「超」をカッコつけて冠するのは、数学での証明でないという意識です(^^;)。

　理論が矛盾すればその理論においては少なくとも一つの命題Ａで、Ａet(～Ａ)が成り立つ。C2とC1からＡと～Ａが真。～Ａが真なら(S2)より、

　　～Ａと(～Ａ)⇒((～Ａ)ouＢ)が真．

　定義1.を使うと、

　　～Ａと(～Ａ)⇒(Ａ⇒Ｂ)が真．

　C1より、

　　Ａ⇒Ｂは真．

　Ａも真だったので再びC1で、

　　ＡとＡ⇒Ｂが真．

　従ってＢが真。
　よって矛盾する理論においては、任意の命題Ｂが真。
［超証明終］

　たびたび［超数学的証明］や［超証明］と書くのはさすがに恥ずかしいので(^^;)、以降は（証明）と略記します。自分は数学の証明は［証明］で区別します。
　C3は、どんな理論であれ矛盾してはアカンよ、と言ってます。矛盾したら理論は、いっきょに論証能力を失います。逆の意味で注目すべき結果が次ですが、ほとんど注目されません(^^;)。

C4（命題が真である事の構文論的定式化）
　Ｂが真なら、任意の仮定Ａに対して、Ａ⇒Ｂが成り立つ。
（証明）
　1) (S2)より、Ｂ⇒(Ｂou(～Ａ))は真。
　2) (S3)より、(Ｂou(～Ａ))⇒((～Ａ)ouＢ)は真。
　3) Ｂが真だから、1)とC1よりＢou(～Ａ)は真。
　4) Ｂou(～Ａ)が真なら、2)とC1より(～Ａ)ouＢは真。
　5) (～Ａ)ouＢとは、定義1.よりＡ⇒Ｂの事。従ってＡ⇒Ｂは真。
（証明終）

　ある理論において命題Ｂが真とわかってしまったら、どんな仮定を立てようとＢが真である事実は変わらない、とC4は言ってます。正しい結論は、推論過程に無関係という事です
　C3とC4は命題理論、別名論理的理論の存在論的意義を表していると思います。「存在論」などと安易に使うと、プロゲラさんに怒られそうですが(^^;)。
　このように論理的証明は鬱陶しいです。鬱陶しいですが論理は、究極のバカチョン方式とも言えます。C1と(S1)～(S4)という一定の規則に従いさえすれば、仮定が真なら真と考えられる結果を必ず出せます。鬱陶しいが故に証明過程を検証できず、数々の詐欺の温床にもなる訳ですが(^^;)。

　Cが「推論法則」の略記号という事には、象徴的な意味合いがあります。論理は命題の真偽には踏み込まないのです。例えば(S1)～(S4)の原始命題Ａ，Ｂ，Ｃの真偽に関わらず「(S1)～(S4)で表される関係は正しいのだ」というのが、命題理論のシェマの立場です。要するに論理とは、「推論の正しさだけ」を保証するものです。その典型が、次の「演繹法則」です。

C5（補助仮定の方法、または演繹法則）
　ある理論でＡを仮定したときＢが真なら、Ａを仮定しない元の理論でＡ⇒Ｂが成り立つ。

　これの（証明）は行いませんが、C5を頻繁に利用して理論は、成り立つべき関係式（命題）を無限に増殖させて行きます。C5を使って背理法を（証明）します(^^)。背理法は帰謬法とも言われるようです。

C6（帰謬法もしくは背理法）
　ある理論で～Ａを仮定したとき矛盾するなら、～Ａを仮定しない元の理論でＡが成り立つ。
（証明）
　1) ～Ａを仮定したときある理論が矛盾するなら、C3より、～Ａを仮定した理論では任意の命題が真だからＡが真。
　2) 演繹法則C5より～Ａを仮定しない理論では、(～Ａ)⇒Ａが成り立つ。
　3) (S4)より、((～Ａ)⇒Ａ)⇒((Ａou(～Ａ))⇒(ＡouＡ))は真。
　4) 2)とC1から、(Ａou(～Ａ))⇒(ＡouＡ)は真。
　5) （証明）はしませんが、C1と(S1)～(S4)を地道に運用すると、Ａou(～Ａ)が真である事を示せる。
　6) 5)と3)とC1から、(ＡouＡ)は真。
　7) (ＡouＡ)が真なら、(S1)から(ＡouＡ)⇒Ａなので、Ａが真。
　8) この結論は2)以降、～Ａを仮定しない理論の中で得られたものだから、Ａは元の理論で成り立つ。
（証明終）

　いやぁ～、鬱陶しい！。でもC6の効用として、次の自明でなければならない関係を導けます。

C7（二重否定法則）
　(～～Ａ)⇒Ａは真。
（証明）
　～～Ａを仮定し、Ａを導けば良い。そこで～Ａを仮定すると、これは矛盾。帰謬法C6よりＡが成り立つ。従って補助仮定の方法C5より、(～～Ａ)⇒Ａは真。
（証明終）

　C7は納得できました？。たぶん納得できないと思うんですが、C7が妥当な理由は、結局はC3とC4の論理的拘束結果にあると思えます。だから論理という究極のバカチョン方式としては、なに一つ悪い事はしてないのですが、もう自分で感覚的に納得するしかないとも思えます(^^;)。
　じつはC1と(S1)～(S4)の地道な運用により、Ａ⇒(～～Ａ)が導けます。よってC7によって、二重否定則：Ａ⇔(～～Ａ)が完成されます。

　対偶関係も同様です。地道な運用で、(Ａ⇒Ｂ)⇒((～Ｂ)⇒(～Ａ))が導けるので、次のC8で対偶則は完成です：(Ａ⇒Ｂ)⇔((～Ｂ)⇒(～Ａ))。

C8（対偶関係）
　((～Ｂ)⇒(～Ａ))⇒(Ａ⇒Ｂ)は真。
（証明）
　1) 演繹法則C5を念頭に(～Ｂ)⇒(～Ａ)を仮定し、Ａ⇒Ｂを導く。
　2) 同様にC5を念頭にＡ⇒Ｂを導くために、Ａを仮定し背理法を用いる。
　3) ～Ｂを仮定すると、(～Ｂ)⇒(～Ａ)から～Ａが成り立つが、これは矛盾。
　4) 従って帰謬法C6よりＢが成り立つ。
　5) 2)～5)に演繹法則C5を適用すると、Ａ⇒Ｂが成り立つ。
　6) 1)，5)に再びC5を適用すると、((～Ｂ)⇒(～Ａ))⇒(Ａ⇒Ｂ)が成り立つ。
（証明終）

　ここまでの話をまとめると、背理法，帰謬法は証明の方法（推論法則）であって、対偶関係はそこから導かれる命題関係です。ただし対偶関係も推論法則ですから、それを利用した証明の方法もあり得る訳です。それを仮に対偶法と呼ぶと、(～Ｂ)⇒(～Ａ)からＡ⇒Ｂを導き矛盾を利用した証明法ではないので、背理法ではないという話にもなります。でもこの話、虚しくないですか？。じっさいC7もC8の（証明）にも、背理法C6が重要なポイントとして現れます。

　背理法C6と二重否定則C7との関係を考えてみます。～Ａを仮定したとき矛盾するとすれば、～Ａでは変だって事です。なので正しいのは、～Ａのさらなる否定～～Ａであろうと。それは(～～Ａ)⇔ＡであるＡだったと。これを集合論的に解釈する事も可能です。
　命題Ａの妥当する外延集合をaで表します。aの定義から、aに対して～Ａが妥当すると仮定したら矛盾です。aの補集合も～aで表す事にすれば、～Ａが妥当するのはaの定義から～aでなければならないからです。従ってＡが妥当するのは、～～a＝a。
　対偶関係も同様に扱えます。Ａ，Ｂの妥当する外延集合をa，bとすれば、Ａ⇒Ｂはa⊂bという意味になります。a⊂bを補集合で考えれば、～b⊂～a。～b⊂～aは(～Ｂ)⇒(～Ａ)と同じです。
　集合論的に解釈すれば、背理法と二重否定則が同じ状況を語っているのはほぼ明らかです。そこには補集合の関係がありました。対偶関係にも補集合の関係が本質的です。という事は、対偶関係C8を先に認めれば、背理法C6を逆に導けるだろうと予想できます。

C6'（帰謬関係もしくは背理関係）
　対偶関係C8のもとでＡを仮定した時、～Ｂを仮定してＡと矛盾するなら、Ａ⇒ＢがＡを仮定しない理論で成り立つ。
（証明）
　1) Ａを仮定する。
　2) さらに仮定～Ｂを追加する。
　3) 仮定～Ｂを追加すればＡと矛盾するから、定義2.より～Ａが真。
　4) 2)，3)に演繹法則C5を適用し、～Ｂを仮定しない理論で(～Ｂ)⇒(～Ａ)が真。
　5) 対偶関係C8より、Ａ⇒Ｂが真。
　6) 1)，5)に演繹法則C5を適用し、Ａを仮定しない理論でＡ⇒(Ａ⇒Ｂ)が真。
　7) 再びＡを仮定すれば、ＡとＡ⇒(Ａ⇒Ｂ)が真だから、Ａ⇒Ｂが真。
　8) 仮定ＡのもとでＡ⇒Ｂが真なら、Ｂが真。
　9) 7)，8)に再度演繹法則C5を適用すれば、Ａを仮定しない理論でＡ⇒Ｂが成り立つ。
（証明終）

　上記が普通にやってる背理法ではないですか？。

［例題］
　Ａ⇒Ｂを示せ。
［解法-1］
　Ａが成り立つとき～Ｂを仮定すれば、(～Ｂ)⇒(～Ａ)なので～Ａも成り立つ。従って矛盾。
　Ａ⇒Ｂでなければならない。
［解法-2］
　(～Ｂ)⇒(～Ａ)が成り立つ。対偶をとれば、Ａ⇒Ｂ。

　［解法-1］と［解法-2］のどこが違うんですか？。

by ddtddtddt (2018-12-02 11:30)