「木は2部グラフである。」
これを証明して欲しいのです。
出来れば背理法で。
よろしくお願いします。

A 回答 (2件)

お気に召さない?


自明すぎて困っちゃうんですが、そうだな、木のノードが奇数番目と偶数番目に分けられる。つまりノードに赤と青の色を付けて、どの辺も一端が赤、他端が青のノードを繋ぐようにできる。

どれでも良いから一つノードを選んで赤にする。
これに辺1本で繋がっている全てのノードを青にする。
青のノードに辺1本で繋がっている全てのノードを赤にする。

これを繰り返せば、木は連結しているから全てのノードに色が付きます。
次に、木はループがないから、一度赤がついたノードは何度色を塗っても赤ですし、青がついたノードは青。

これなら証明っぽいですか?
    • good
    • 0

2部グラフ:ノードを二つの部分集合A,Bに分けて、どの辺も一端をAに他端をBに持つようにできること。



木が2部グラフであることは、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明。

背理法?
木が2部グラフでないとすると、ノードが根元から数えて偶数番目のものと奇数番目のものに分ければ自明であることと矛盾する。QED
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q三次関数の証明(背理法)

任意の相異なる4点(x1, y1), (x2, y2), (x3, y3), (x4, y4) を通る3次関数が2つ存在すると仮定した上で背理法により実際はただ1つしかそんざいしないということを証明してみてください!お願いします!

Aベストアンサー

任意の相異なる4点(x1, y1), (x2, y2), (x3, y3), (x4, y4) を通る3次関数が2つ存在すると仮定し、f1(x), f2(x)とおく。
f1(x)≠f2(x)
ここで、g(x) = f1(x) - f2(x) とする。
g(x) は3次以下の関数である。
(3次関数の差は、3次以下の関数でなければならない。)

また、f1(x1) = f2(x1), f1(x2) = f2(x2), f1(x3) = f2(x3), f1(x4) = f2(x4)より、
g(x1) = g(x2) = g(x3) = g(x4) = 0

因数定理より、
g(x) = (x - x1)(x - x2)(x - x3)(x - x4)h(x)
とかける。 (ここで、h(x)は多項式)
しかし、もし、h(x) ≠ 0 ならば、右辺の次数は明らかに4次以上である。

ゆえに、 h(x) ≡ 0 でなければならず、
(h(x) ≡ 0 でなければ、左辺と右辺の次数が合わなくなります。左辺3次以下、右辺4次以上)

g(x) = (x - x1)(x - x2)(x - x3)(x - x4)h(x) ≡ 0
結局、g(x) = f1(x) - f2(x) ≡ 0 より、
f1(x) ≡ f2(x)
これは仮定に矛盾する。
つまり、任意の相異なる4点(x1, y1), (x2, y2), (x3, y3), (x4, y4) を通る3次関数はただ1つである。

証明風に書いてみました。どうでしょうか。

任意の相異なる4点(x1, y1), (x2, y2), (x3, y3), (x4, y4) を通る3次関数が2つ存在すると仮定し、f1(x), f2(x)とおく。
f1(x)≠f2(x)
ここで、g(x) = f1(x) - f2(x) とする。
g(x) は3次以下の関数である。
(3次関数の差は、3次以下の関数でなければならない。)

また、f1(x1) = f2(x1), f1(x2) = f2(x2), f1(x3) = f2(x3), f1(x4) = f2(x4)より、
g(x1) = g(x2) = g(x3) = g(x4) = 0

因数定理より、
g(x) = (x - x1)(x - x2)(x - x3)(x - x4)h(x)
とかける。 (ここで、h(x)は多項式)
しか...続きを読む

Q背理法を用いた、整数問題の証明

a,b,cは整数とし、a^2+b^2=c^2とする。a,bのうち、少なくとも1つは3の倍数であることを証明せよ。
 という問題について質問します。

a,bはともに3の倍数でないと仮定する。
このとき、a=3n+1,b=3m+1(n,mは整数)とおく。
a^2=3(3n^2+2n)+1
b^2=3(3m^2+2m)+1
ただし、3n^2+2n,3m^2+2mは整数。
よってa^2,b^2を3で割った余りはともに1である。


a^2+b^2=3(3n^2+2n)+1+3(3m^2+2m)+1
=3(3n^2+2n+3m^2+2m)+2
3n^2+2n+3m^2+2mは整数である。
したがって、a^2+b^2を3で割った余りは2である。

一方、cが3の倍数のとき、c^2は3で割り切れ、
cが3の倍数でないとき、c^2を3で割った余りは1である。
すなわちc^2を3で割った余りは0か1である。


よって、a^2+b^2=c^2において、
左辺は3で割ったときの余りが2、右辺は3で割ったときの余りが0か1
であるから矛盾する。
ゆえに、背理法よりa^2+b^2=c^2ならば、a,bのうち、少なくとも1つは3の倍数である。

このように解答したのですが、※と※の間の部分に対して数学の先生から、不十分というコメントを書かれてしまいました。

どこが不十分なのか分かる方がいらっしゃいましたら、教えていただけないでしょうか。
よろしくお願いします!

a,b,cは整数とし、a^2+b^2=c^2とする。a,bのうち、少なくとも1つは3の倍数であることを証明せよ。
 という問題について質問します。

a,bはともに3の倍数でないと仮定する。
このとき、a=3n+1,b=3m+1(n,mは整数)とおく。
a^2=3(3n^2+2n)+1
b^2=3(3m^2+2m)+1
ただし、3n^2+2n,3m^2+2mは整数。
よってa^2,b^2を3で割った余りはともに1である。


a^2+b^2=3(3n^2+2n)+1+3(3m^2+2m)+1
=3(3n^2+2n+3m^2+2m)+2
3n^2+2n+3m^2+2mは整数である。
したがって、a^2+b^2を3で割った余りは2であ...続きを読む

Aベストアンサー

上の解答は,「a,bがともに3で割ると1余る」だけは証明して
いますが,「a,bの一方が余り1,他方が余り2」,「a,bがともに
余り2」の場合が抜けています。また,強いて言えば
  >左辺は3で割ったときの余りが2、
  >右辺は3で割ったときの余りが0か1
の部分も理由説明が抜けています。

本質的な部分は正しいので,不足分だけ補えばよいでしょう。
ただ,同じようなことを何度も書くのは大変なので,まず
一般に平方数を3で割ると余りはどうなるかを最初に述べておく
とよいでしょう。
   (3m)^2 = 3(3m^2),
   (3n±1)^2 = 9n^2±6n+1 = 3(3n^2±2n)+1
より,3の倍数の平方は3の倍数,3で割り切れないものの平方
は3で割ると1余るとまとめることができます。
(余りが2のときは 3n+2 としてもよいのですが,
3n-1 としておくと上のように少ない労力で済みます。)
あとは,aもbも3の倍数でないならa^2,b^2はともに3で割ると
1余るからa^2+b^2を3で割ると2余り,c^2は3で割ると余りは
0または1となる(最初に一般論をまとめておくと改めて示す
必要はなくなる)から,・・・・・・(以下略)

ちなみに・・・

>3(3n^2+2n+3m^2+2m)+2の平方根が整数でなければならない
余りで矛盾しているので,平方根が整数であろうとなかろうと
成り立たないことには変わりないので,この議論は不要です。

>背理法なんだから、a, b, c すべてが 3 の倍数でないと仮定
>すれば良い
a,bが3の倍数でないときcも3の倍数でないことは証明が必要です。
3104akaさんの答案通り,「a,bはともに3の倍数でないと仮定する」
でよいと思います。

上の解答は,「a,bがともに3で割ると1余る」だけは証明して
いますが,「a,bの一方が余り1,他方が余り2」,「a,bがともに
余り2」の場合が抜けています。また,強いて言えば
  >左辺は3で割ったときの余りが2、
  >右辺は3で割ったときの余りが0か1
の部分も理由説明が抜けています。

本質的な部分は正しいので,不足分だけ補えばよいでしょう。
ただ,同じようなことを何度も書くのは大変なので,まず
一般に平方数を3で割ると余りはどうなるかを最初に述べておく
とよいでしょう。
...続きを読む

Q背理法を用いた対数の証明問題

「log_(10) 2 (底が10です)は無理数である。」

を背理法をで証明したいのですがやり方がわかりません。

どなたかわかる方いましたら教えてください。

Aベストアンサー

有理数だと仮定すると log_(10) 2=n/m (m と n は互いに素の整数、mはZeroでない)とおける。
これは 10^n/m=2
つまり 10^n=2^m とおける。

ここで左辺を素因数分解すると 2^n×5^nとなり
右辺と左辺で二通りの違った素因数分解できることになり矛盾している。
よって有理数ではない。

素因数分解の一意性を使うところが味噌

Q√2を無理数と言える証明(背理法以外で)

現在、√2を無理数だと証明する方方には、矛盾から考える背理法と言うのがあります。というか、自分がそれしか知らないのかもしれません。
今学校で、√2の正体について追究しています。
背理法についてまとめた人はたくさんいるので…。
√2を無理数だと証明する方法、ありませんか?

Aベストアンサー

凄い研究やってるんですね。楽しそうです。

「帰謬法」は「背理法」の別名です。Pという命題を証明しようとするとき、「Pでない」と仮定して矛盾を導くんですね。正確に言えば、適当な命題Aについて
「PでないならばAである」と「PでないならばAでない」を証明して、これらから「Pである」と結論します。ご質問の場合、
P: √2は無理数である
を証明しようという訳ですけど、
・√2って何か。「x^2 = 2 を満たす正の数x」
これは良いでしょう。では、
●無理数って何か。「有理数でない数」「どんな整数nについてもnxが整数にならないような数x」「小数展開したときに、循環小数にならないような数」

 いずれも「××でないもの」と定義されています。だから帰謬法が有効です。すなわち、『「××でない数」ではない』は『××である数』と同じですから、
「√2は有理数である」と仮定する。
「或る整数nが存在してn√2が整数である」と仮定する。
「√2を小数展開したときに、循環小数になる」と仮定する。
などから出発して、矛盾を導く。

○良く知られた帰謬法による証明は:
「√2は有理数である」と仮定する。
すると整数n,mが存在して「m>0かつ √2 = n/mかつn/mは既約分数」を満たす。
(√2)^2 = 2
であるから
(n/m)^2=2
よって
n^2 = 2(m^2)
従ってnは偶数である。すなわち
n=2k
を満たす整数kが存在する。ゆえに
4(k^2) = 2(m^2)
2(k^2) = m^2
従ってmは偶数である。
だからn,mは共に偶数であり、n/mは既約分数ではない。これは矛盾である。
つまり『「√2は有理数である」ならば矛盾である。』が証明された。
ゆえに「√2は有理数でない」が証明された。

●ほかの証明方法と言いますと、
○対偶を使う。
 「xが√2ならばxは有理数でない」の対偶は「xが有理数ならば、xは√2でない」です。
 つまり、「どんな有理数xも x^2=2 を満たさない」ことを示せば良い。
○ジレンマ(場合分け)を使う。適当な命題Aを見つけて、
 「Aならば√2は有理数でない」および「Aでないならば√2は有理数でない」
 の両方を証明できたら、「√2は有理数でない」が言えます。
○三段論法を使う。適当な命題Aを見つけて、
 「xがAならばxは有理数でない」および「√2はAである」
 の両方を証明できたら、「√2は有理数でない」が言えます。
○数学的帰納法(累積帰納法)を使う。例えば
 Q(m) : 「どんな整数nについてもn/mは√2ではない。」
 とするとき、
 「Q(1)である」と
 「自然数mがm>1のとき、『自然数jがm>j≧1を満たすならQ(j)である』ならばQ(m)である」
 を証明する。
などが考えられます。しかしながら、これらの代替え案も皆、どこかで「××でない」を言わねばならないのは同じで、ここのところで帰謬法を使っちゃいます。具体的に見てみましょう。

●上記の帰謬法による証明を、対偶「xが有理数ならば、xは√2でない」の証明に変えるのは簡単です。
「x^2=2を満たす有理数xがある」と仮定する。
すると整数n,mが存在して「m>0かつx= n/m かつ n/mは既約分数」を満たす。
仮定により(n/m)^2=2だからnもmも偶数である。(ここの詳細は既に、帰謬法の例で見ました。)
だからn,mは共に偶数であり、n/mは既約分数ではない。これは矛盾である。
以上から、『「x^2=2を満たす有理数xがある」ならば矛盾』が証明できた。
ゆえに「xが有理数ならば、xはx^2=2を満たさない」つまり、「xが有理数ならば、xは√2でない」が証明できた。
 やっぱりこれも帰謬法を含んでいます。

●帰納法にしてみましょう。ついでにジレンマの例も見てみましょう。
Q(m) : 「どんな整数nについてもn/mは√2ではない。」
とするとき、「Q(1)である」と「自然数mがm>1のとき、『自然数jがm>j≧1を満たすならQ(j)である』ならばQ(m)である」を証明します。
Q(1) : 「どんな整数nについてもnは√2ではない。」
  すなわち「√2は整数でない」を証明する問題です。これをジレンマで証明しましょう。
  つまり
    A: 整数nがn≦1のとき、nは√2ではない。
    B: 整数nがn≧2のとき、nは√2ではない。
  を証明すれば、Q(1) が言えたことになります。
  Aは√2の定義から明らかです。Bは数学的帰納法を使って簡単に証明できます。
自然数mがm>1のとき。『自然数jがm>j≧1を満たすならQ(j)である』と仮定する。
  この仮定の下で、ジレンマを使いましょう。
  C:「n/m≠√2であるならばn/m≠√2である」
  D:「n/m=√2であるならばn/m≠√2である」
  この両方を証明すれば、Q(j)であることが証明されます。
  Cの証明:トートロジーです。n/m≠√2と仮定すればn/m≠√2。
  Dの証明:
    n/m=√2であるとすると、(既に見たように)nもmも偶数であることが分かる。
    従って、n/mは既約でない。すなわちh/j = n/m, m>j≧1を満たす整数h,jが存在する。
    仮定『自然数jがm>j≧1を満たすならQ(j)である』によりh/jは√2ではない。
    ゆえにn/m≠√2。
  ゆえに、Q(m):「どんな整数nについてもn/mは√2ではない。」が証明された。
以上から、どんな自然数mについてもQ(m)であることが示された。

★ここでは帰謬法が使われていない! でもジレンマを使っています。
 ジレンマは、「AならばPである」と「AでないならばPである」から「Pである」を導く推論ですが、上の例ではAの所にPを代入して、「PならばPである」と「PでないならばPである」から「Pである」を導く、という形で使いました。前者は自明であり、実質「PでないならばPである」を証明するだけです。
 一方、帰謬法は「PでないならばAである」と「PでないならばAでない」から「Pである」を証明します。Aの所にPを代入すると、「PでないならばPである」と「PでないならばPでない」を証明することになり、後者は自明ですから、実質「PでないならばPでない」を証明するだけです。つまり、ジレンマと帰謬法はA=Pとしたときには同じものになる訳です。
 言い換えれば、帰謬法をジレンマの形に化けさせて使うことができます。これはズルですよね。

●どうにも、帰謬法が止まりません。じゃあ、もっと他の方法は?
√2を計算するには近似値g[0] = 2 からスタートして、
g[n]=g[n-1] /2+1/g[n-1]
を繰り返し計算する方法があります。(てゆーかー、今作りました)
ε[n] = g[n]-√2
と定義すると、n=1,2,....について(2-√2)≧ε[n-1] , (1/√2-1/2)ε[n-1]>ε[n] ≧0, g[n]>√2が成り立つことは簡単に証明できます。ここで、0<(1/√2-1/2)<1だから、ε[n]は0に単調に収束し、従って、g[n]は√2に単調に収束します。計算方法から、g[n] (n=0,1,2,....)はどれも有理数であることは明らかです。
同様に、h[0]=0、h[n]=2-2/(h[n-1]+2) は√2に、h[0]<h[1]<....<√2と単調に収束する有理数の列です。だから、
h[n]<√2<g[n]
である。こうして、√2は「x^2=2の解」なんて抽象的なものではなく、幾らでも正確に計算できる具体的なアルゴリズムで記述されるようになりました。でも、「h[n]とg[n]の間」という範囲に入る有理数は、nをどんなに増やしてもなお無限個あります。そのどれもが√2ではない、ということを証明しなくてはならない。つまり、ここまで絞り込んでも、結局「××ではないもの」というパターンからは逃れられません。

●では、「帰謬法を使ってはいけない」というルールの数学を考えたとき、√2が有理数でないことを証明できなくなるんでしょうか?
 帰謬法とは「Aでないならば矛盾である。ゆえにAである」ということですけど、「Aでないならば矛盾である」を証明するのを禁じる理由はありません。だから『「Aでないならば矛盾である(=「Aでない」は成り立たない)」から「ゆえにAである」と言ってはいけない』と決めるしかない。つまり「帰謬法を使ってはいけない」ってのは、
排中律:「どんな命題Aも、AであるかAでないかのどちらかである。」を使ってはいけない
ということに他なりません。(だからジレンマも対偶も使えません。)さらに言い換えれば、「『Aである』が成り立たない」と「Aでない」とは別の事を意味している、という論理体系です。
 これは非常に制限が強い。たとえば、
 「2=√2ではない」の証明:2はx^2=2を満たさない。
というのが証明になっているかどうか。詳しく考えますと
  2=√2と仮定する。
  √2の定義から、(√2)^2=2である。仮定により2^2=2である。
  一方2^2=4だから、2=4である。
  これは矛盾である。だから「2=√2ならば矛盾」が示された。
  ゆえに「2=√2ではない」。
というわけで、帰謬法が(こっそり)使われている。

●きちんと定式化してみましょう。
 「排中律を禁止する体系Xでは『√2が有理数でない』ことは証明できない。」を証明せよ
という問題です。これは、数学の体系を対象とした数学、すなわち超数学の命題です。証明せよと言っているこの証明は排中律を禁止する体系Xの中で行われるのではなく、従って排中律を使うことができます。体系Xではどんな推論が許されているのか(無論、排中律が定理として導かれるような推論規則は全部禁止です)をきちんと調べておかないと、この問題は解決できないでしょう。そもそも有理数とその四則演算を定義するまでの段階で排中律を使っていないかどうかのチェックをしなくては意味がありません。大仕事ですね。
 もっと一般化して
 「排中律を禁止する体系Xでは『xが命題A(x)を満たさない』ことは証明できない」ようなAとはどんなものか
という問題と捉えることができます。どんな命題なら『xが命題A(x)を満たさない』が証明でき、どんな命題ならできないか。

凄い研究やってるんですね。楽しそうです。

「帰謬法」は「背理法」の別名です。Pという命題を証明しようとするとき、「Pでない」と仮定して矛盾を導くんですね。正確に言えば、適当な命題Aについて
「PでないならばAである」と「PでないならばAでない」を証明して、これらから「Pである」と結論します。ご質問の場合、
P: √2は無理数である
を証明しようという訳ですけど、
・√2って何か。「x^2 = 2 を満たす正の数x」
これは良いでしょう。では、
●無理数って何か。「有理数でない数」「どんな整数nに...続きを読む

Q背理法の定理を排中律から証明できません。

よろしくお願い致します。

先ず、
Pを命題とし、「→」は含意を表す。
Pが真→¬Pは偽
Pが偽→¬Pは真
Pが否定の否定が真ならばPは真
Pが否定の否定が偽ならばPは偽
Pが真であるか,またはPの否定が真であるかのいずれかである.

が成立しているとします。

これらから背理法が正しい事を証明したくと思ってます。

先ず、「矛盾」の定義はP∧¬Pが真となる事です。
ですから
P→Qが

(P→¬Q)∧¬(P→¬Q)
の真偽が等しくならなければ背理法が正しい証明法とはいえません。
つまり、
P→Qを示したい((P→Q)=true)時、代わりに
((P→¬Q)∧¬(P→¬Q))=true
を示す事である。
しかし、
((P→¬Q)∧¬(P→¬Q))は
(¬P)∨(¬Q)∧¬(¬P∨¬Q)と書け、更に
¬(P∧Q)∧(P∧Q)
でこれは自動的に恒偽命題となってしまい、
P→Qと真偽が一致しません。
とい事はP→Qを示すのに背理法
((P→¬Q)∧¬(P→¬Q))=trueが使えなくなってしまいます。

一体、何処を勘違いしていますでしょうか?

よろしくお願い致します。

先ず、
Pを命題とし、「→」は含意を表す。
Pが真→¬Pは偽
Pが偽→¬Pは真
Pが否定の否定が真ならばPは真
Pが否定の否定が偽ならばPは偽
Pが真であるか,またはPの否定が真であるかのいずれかである.

が成立しているとします。

これらから背理法が正しい事を証明したくと思ってます。

先ず、「矛盾」の定義はP∧¬Pが真となる事です。
ですから
P→Qが

(P→¬Q)∧¬(P→¬Q)
の真偽が等しくならなければ背理法が正しい証明法とはいえません。
つまり、
P→Qを示...続きを読む

Aベストアンサー

あ~, P→Q を背理法で証明するってことね.
これをどう証明するかというと
「P ∧ ¬Q を仮定すると矛盾が生じるので P→Q」のはずなので, これを式に書くと
((P∧¬Q)→(R∧¬R))→(P→Q)
か?
例えば, 「√2 が有理数でない」ことを背理法で証明する (中学校レベルの) 方法だと,
「x^2 = 2 ならば x は有理数でない」なので, P = 「x^2 = 2」, Q = 「x は有理数でない」とおけます.
で, x = m/n (m, n は整数で互いに素) とおくときの「互いに素」が R となって, これらを使うと
((P∧¬Q∧R)→¬R)→(P→Q)
あれ? 上と式が違う (苦笑). 証明中では (P∧¬Q∧R)→R を使う (最後に「互いに素と仮定したのに」といっているので) ので,
((P∧¬Q∧R)→(R∧¬R))→(P→Q)
なのかなぁ? もしくは (「互いに素」までを含めて有理数とすれば)
((P∧¬Q)→Q)→(P→Q) あるいは ((P∧¬Q)→(Q∧¬Q))→(P→Q)
という論理で証明しているみたいです. うお, 以外と複雑.

あ~, P→Q を背理法で証明するってことね.
これをどう証明するかというと
「P ∧ ¬Q を仮定すると矛盾が生じるので P→Q」のはずなので, これを式に書くと
((P∧¬Q)→(R∧¬R))→(P→Q)
か?
例えば, 「√2 が有理数でない」ことを背理法で証明する (中学校レベルの) 方法だと,
「x^2 = 2 ならば x は有理数でない」なので, P = 「x^2 = 2」, Q = 「x は有理数でない」とおけます.
で, x = m/n (m, n は整数で互いに素) とおくときの「互いに素」が R となって, これらを使うと
((P∧¬Q∧R)→¬R)→(P→Q)
あれ? 上...続きを読む


人気Q&Aランキング

おすすめ情報