[ ホームページ ] [ 携帯用URL ]
数学問題集「考える葦」 数学質問掲示板

わからない算数・数学の問題を質問して教えてもらいましょう。
回答できる人は積極的に回答し、みんなで教えあいましょう。
利用前に数学質問掲示板の注意事項を読んでください。
数式の書き方がわからない人は数学質問掲示板での数式の書き方を参考にして下さい。

[ EZBBS.NET | 新規作成 | ランキング | オプション ]
iモード&(絵文字)、au対応!ケータイからも返信できる無料掲示板!
名前
 E-mail 
題名
内容
   タグ有効 改行有効 等幅フォント
URL



構成的証明の正しさ 返信  引用 
名前:フランケン    日付:2018/2/15(木) 18:56
数学関連の本を読んでいて、構成的証明というものに出くわしました。
「定理の主張しているものの構成法を見せること」と書いてあるのですが、
構成法を示すだけで定理が成り立つことが証明できているのでしょうか?
それも帰納法とか使わないと証明したことにならない気がするのですが。



Re: 構成的証明の正しさ
名前:IT    日付:2018/2/15(木) 23:36
構成的証明でない例として、鳩ノ巣理論を使って「条件Aを満たすものがどこかにある。」と示す。というのがあります。

構成的証明で条件Aを満たす具体的なaの作り方を示せば、「条件Aを満たすものが存在する」のりっぱな証明になると思います。


Re: 構成的証明の正しさ
名前:IT    日付:2018/2/16(金) 0:7
たとえば,A={1,2,3,4,5,}とB={1,2,3,4,5}について
     {1+3,2+4,3+5,4+1,5+2}={4,6,8,5,7}={4,5,6,7,8}とできます.
(構成的証明)
a∈A,b∈B とする。
(1)a=1,2,..,k+1 のとき b=a+k とするとa+b=2a+k なので
a+b=k+2,k+4,....,k+2(k+1)
(2)a=k+2,...,2k+1のとき b=a-(k+1) とするとa+b=2a-(k+1) なので
a+b=k+3,k+5,...,k+2k+1
(1)と(2)を併せるとa+b はk+2からk+2(k+1)までの連続する2k+1個の整数になる。


実際に証明できるか分かりませんが、この命題を仮に、鳩ノ巣論法的な方法で証明したとすると
すべての組み合わせ(各nについては有限)を調べれば、どれかが条件を満たす。
ということですから、(構成的証明)の方が実用上優れていると言えると思います。

証明のスマートさは後者の方が優れている場合も多いと思いますが。


Re: 構成的証明の正しさ
名前:IT    日付:2018/2/16(金) 0:9
下記の部分(先にきます)が入力漏れになってました。

構成的証明があれば、そうでない証明より説得力があり、実用的と思いますが如何でしょうか?

たとえば
(命題)任意の正の奇数n=2k+1について,
A={1,2,...,n}とB={1,2,...,n}から,それぞれ1つずつ数をとって加えてできる数の集合が連続するn個の整数となるようにできます。(各数は1回だけ使用します。)


Re: 構成的証明の正しさ
名前:IT    日付:2018/2/16(金) 13:0
「数学的帰納法」は、「構成的証明法」の一種だと思います。

下記に「構成的証明」と「計算法による導出」の関係が載っています。
http://www.cs.tsukuba.ac.jp/~kam/complogic/slide2015.pdf

下記に構成的証明、非構成的証明の例が載っています。
http://www.mmm.muroran-it.ac.jp/~shi/ls1408.pdf
http://www.i.kyushu-u.ac.jp/~eiji/GraphCombinatorics/graph-combinatorics10.pdf

確率式の等価問題に関する質問 返信  引用 
名前:田中    日付:2018/2/14(水) 15:22
下記条件確率式が成立するかどうかお尋ねです。
p(A,B,C|D,E) = p(A,B,C|D) * p(A,B,C|E) ?

A,B,C,D,Eは皆確率変数です。
ただ、Dと(A,B,C)の間は非独立で、Eと(A,B,C)の間も非独立ですが、DとEの間は独立です。

宜しくお願い致します。



Re: 確率式の等価問題に関する質問
名前:Delta    日付:2018/2/14(水) 16:28
成立しないと思います。
例として2回コイントスをしてi=1,2に対し、
i回目の結果が「表」ならば、X[i]=1,「裏」ならばX[i]=0とします。
また、表が出る確率と裏が出る確率は共に1/2とします。
ここで
A=X[1]+X[2],B=X[1]X[2],C=1-(1-X[1])(1-X[2]) (X[1]=X[2]=0のときのみ0,それ以外は1),D=X[1],E=X[2]
とすると
A,B,C,D,Eは質問文の条件を満たします。
後は適当な値を代入し、等式が成り立たないことを言えばOKです。

例)P(A=1,B=0,C=1|D=1,E=0)=1,P(A=1,B=0,C=1|D=1)=1/2,P(A=1,B=0,C=1|E=0)=1/2


Re: 確率式の等価問題に関する質問
名前:田中    日付:2018/2/15(木) 7:27
Deltaさん
凄い検証実例ですね。
有難う御座いました。


Re: 確率式の等価問題に関する質問
名前:一石    日付:2018/2/15(木) 11:6
あ、正解はこれだ!
利便のために、
@ 例の確率変数A,B,Cを一つの確率eventとし、Xに記す。
A 記号D→a,E→b へ転換

即、確率変数a,bの間は独立で、a,Xの間、b,Xの間は非独立。


P(X|a,b)* P(a,b)= P(a,b|X)* P(X) = P(a|X)* P(b|X)* P(X)
そして

P(a|X)* P(b|X) = P(X|a) * P(X|b) * P(a,b) / P(X)^2


P(a|X)* P(b|X)* P(X)= P(X|a) * P(X|b) * P(a,b) / P(X)


P(X|a,b)* P(a,b) = P(X|a) * P(X|b) * P(a,b) / P(X)


P(X|a,b)* P(X) = P(X|a) * P(X|b)

元題の表現に置き換えると

P(A,B,C|D) * P(A,B,C|E) = P(A,B,C|D,E)* P(A,B,C)

即、通常

P(A,B,C|D) * P(A,B,C|E) ≦ P(A,B,C|D,E)

iff: P(A,B,C)= 1 then
P(A,B,C|D,E) = P(A,B,C|D) * P(A,B,C|E)












Re: 確率式の等価問題に関する質問
名前:一石    日付:2018/2/15(木) 11:46
より一般化へ

P(X|a) * P(X|b) *…* P(X|y) * P(X|z) = P(X) * P(X|a,b,…,y,z)
P(a,b,…,y,z | X) = P(a|X) * P(b|X) *…* P(y|X) * P(z|X) // a,b,…,y,zが互いに独立する場合

( P(X|a) * P(X|b) *…* P(X|y) * P(X|z) )/( P(a|X) * P(b|X) *…* P(y|X) * P(z|X))= (P(X|a,b,…,y,z))/(P(a,b,…,y,z | X)) P(X)




-----最近オレ的な数学発明が多いような気がする、、、(笑)


Re: 確率式の等価問題に関する質問
名前:Delta    日付:2018/2/15(木) 12:23
>P(X|a,b)* P(a,b)= P(a,b|X)* P(X) = P(a|X)* P(b|X)* P(X)

これの後半の等号が怪しい気がします...。
実際、私の提示した例で(A,B,C,D,E)=(1,0,1,1,1)とすると
(A,B,C)=(1,0,1)となるのは(D,E)=(1,0),(0,1)のときなので
P(a,b|X)* P(X)=0*1/2=0, P(a|X)*P(b|X)*P(X)=1/2*1/2*1/2=1/8 となり、等号は成立しません。

また、P(A,B,C|D) * P(A,B,C|E)=1/4, P(A,B,C|D,E)* P(A,B,C)=0 より
P(A,B,C|D) * P(A,B,C|E) ≠ P(A,B,C|D,E)* P(A,B,C) です。


Re: 確率式の等価問題に関する質問
名前:一石    日付:2018/2/15(木) 15:3
Delta さん 実験有難うございます。

>>P(X|a,b)* P(a,b)= P(a,b|X)* P(X) = P(a|X)* P(b|X)* P(X)

>これの後半の等号が怪しい気がします...。

P(a,b|X)*P(X) = P(a|X)*P(b|X)*P(X)について

証明:

P(a,b|X)*P(X) = P(a,b,X) = P(a|b,X)*P(b,X) = P(a|b,X)*P(b|X)*P(X) =
P(a|X)*P(b|X)*P(X)

注: P(a|b,X) = P(a|X) ∵ aとbは独立


Re: 確率式の等価問題に関する質問
名前:一石    日付:2018/2/15(木) 15:13

さらに新しい数学成果!

以下:a,bは独立確率変数

下記のような美しい対称性のある確率論成果を披露致します。
(全部今日午前だけの成果です 笑)

p(X,a)*p(X,b) = p(X,a,b)*p(X) → p(X,a,b) = p(X,a)*p(X,b) / p(x)
p(X|a)*p(X|b) = p(X|a,b)*p(X) → p(X|a,b) = p(X|a)*p(X|b) / p(x)

証明:

p(X|a)*p(X|b) = p(X|a,b)*p(X) (証明は3時間前出したやつ)

p(X|a)*p(X|b)*p(a,b) = p(X|a,b)*p(X)*p(a,b)
即ち
p(X,a)*p(X,b) = p(X,a,b)*p(X)


Re: 確率式の等価問題に関する質問
名前:Delta    日付:2018/2/15(木) 18:4
>注: P(a|b,X) = P(a|X) ∵ aとbは独立
aとbが独立のときに成り立つのはP(a|b)=P(a)であって、上の式は成り立ちませんよ。


Re: 確率式の等価問題に関する質問
名前:田中    日付:2018/2/15(木) 19:35

下記文献
<<Naive Bayes classifier>> From Wikipedia
https://en.wikipedia.org/wiki/Naive_Bayes_classifier
の中の中部にある以下の文とそれ以降を読んで見ていかがでしょうか。
"other feature xj for j ≠ i,given the category C.This means that"

一緒に数学定理を作りませんか。

関数? 返信  引用 
名前:横歩取り8五飛    日付:2018/2/14(水) 11:36
問い.xを1以上の整数とする。xが奇数のとき4,xが偶数のとき25を返すような関数f(x)をxを用いて表せ。ただし、f(x)=4 (x=2k-1),f(x)=25 (x=2k) (k:1以上の整数)のような回答は認めない。f(x)=(xを含んだ式)となるようにせよ。

この問題が全くわからないので教えてください!



Re: 関数?
名前:krup    日付:2018/2/14(水) 11:51
三角関数の周期性を考えてみてはいかがでしょう。


Re: 関数?
名前:由香    日付:2018/2/14(水) 15:40
基本的な事項は、xの偶奇によって差を発生させることです
三角関数とか、(−1)^x とかがありますが、偶奇でとる値の差は2しかない
差を(25−4=)21にするには何倍?
関数を一種の数列と見て、初項を4に合わせるには?


Re: 関数?
名前:IT    日付:2018/2/14(水) 19:56
お二方のヒントで解けたと思いますが、
グラフを描いて 眺めて見るのも有効な手段だと思います。


Re: 関数?
名前:横歩取り8五飛    日付:2018/2/15(木) 16:41
解けました。みなさんヒントありがとうございます。

ページ: |< << 3 4 5 6 7 8 9 10 11 12 >> >| 

無料アクセス解析

アクセス解析の決定版!無料レンタルで最大100ページ解析!

   投稿KEY
   パスワード

EZBBS.NET produced by InsideWeb