直観的説明
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/11/21 02:32 UTC 版)
上記の規則群は「論理規則」と「構造規則」に分けられる。論理規則は帰結関係 ⊢ {\displaystyle \vdash } の右辺か左辺に新たな論理式を導入する。一方、構造規則はシークエントの構造を操作し、論理式の正確な形を無視する。例外として同一性の公理 (I) とカット規則 (Cut) がある。 形式化されているものの、これらの規則は古典論理的に直観的に読み解くことができる。例えば、(∧L1) 規則を見てみよう。これは、A を含む論理式の列から Δ が証明される場合は常に A∧B という(より強い)仮定からも Δ が導かれることを示している。同様に、(¬R) 規則 は Γ と A によって Δ が導かれるなら、Γ のみから Δ が真または A が偽であること(A が成り立たない)が導かれることを意味する。どの規則もこのように解釈可能である。 量化子の規則に関する直観的説明として、(∀R) 規則を見てみよう。もちろん、A[y/x] が真であるという事実だけから ∀x A が成り立つとは一般には結論できない。しかしながら、変項 y がどこにも言及されない場合(すなわち、他の論理式に影響を与えることなく自由に選べる場合)、A[y/x] は任意の y の値について成り立つと見なすことができる。他の規則も同様に解釈可能である。 これら規則を述語論理における正当な導出と見なさず、与えられた論理式について証明を構築するための手順と見ることもできる。この場合、規則を下から上に適用していく。例えば、(∧R) では、Γ と Σ という前提から A∧B が帰結されることを証明するには、それぞれ Γ から A が帰結され、Σ から B が帰結されればよい。ただし、先行条件をどのように Γ と Σ に分ければよいかは明らかではない。しかし、先行条件が有限であれば、考慮すべき組合せも有限である。これは証明論における組合せ的証明操作も示している。すなわち、A と B の両方を証明することで A∧B の証明を構築できる。 これらの規則のほとんどは、どう証明すればよいかを示しているが、カット規則だけは異なる。カット規則 (Cut) は、論理式 A が帰結となり、同時に他の帰結の前提にもなる場合、A を除いて論理的帰結関係を結合することができることを示している。証明をボトムアップで行う場合、A を具体的に何にするかという問題が生じる(横棒の下に出現しないため)。この問題はカット除去定理で扱われる。 同一性の公理 (I) もある意味で特殊である。直観的には A ならば A であるという自明なことを意味しているにすぎない。
※この「直観的説明」の解説は、「シークエント計算」の解説の一部です。
「直観的説明」を含む「シークエント計算」の記事については、「シークエント計算」の概要を参照ください。
直観的説明
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/12/01 22:33 UTC 版)
あまり平滑でない推定器(例えばヒストグラム密度推定器)は漸近的に一致させられるが、他の推定器は不連続であるか、カーネル密度推定より収束が遅い。カーネル密度推定器は、標本を一定幅の箱に入れて数えるのではなく、カーネル関数から決定されたコブを各標本に与えるものと見ることができる。つまり、「コブの総和」によって推定が形成されるため、結果として非常に滑らかになる(下図参照)。 6つのガウス曲線(赤)とそれらの総和(青)。パルツェン窓密度推定 f(x) は、この総和を6(元のガウス曲線の数)で割ることで得られる。ガウス関数の分散は 0.5 に設定されている。見ての通り、標本点が稠密にあるほど、密度推定値は大きくなる。
※この「直観的説明」の解説は、「カーネル密度推定」の解説の一部です。
「直観的説明」を含む「カーネル密度推定」の記事については、「カーネル密度推定」の概要を参照ください。
直観的説明
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/06/29 18:36 UTC 版)
Aが関数fを計算するプログラムであるとき、fA=fと定義する。たとえばAが「a=x+yを計算した後、a+zを出力する」という趣旨のプログラムであると、fA(x,y,z)=x+y+zである。ただし、Aにxを入力しても(無限ループにはまる等の理由で)有限時間で停止しない場合は、fA(x)=⊥と定義する。ここで「⊥」はプログラムが停止しない事を表す特殊な記号。 なお、2つのプログラムA、Bに対し、AとBがプログラムとしては別物であってもfAとfBが同じになる事がある事に注意されたい。たとえばBを「b=x+zを計算した後、b+yを出力する」という趣旨のプログラムとすると、Bの見掛けは前述のAのそれとは異なるが、明らかにfA(x,y,z)=fB(x,y,z)=x+y+zである。 Fを関数に関する何らかの性質とする。たとえばFは「関数fAは恒等的に0である」とか「fA(x)≧x3である」のようなものである。注意しなければならないのは、Fは関数fAに関する性質であってプログラムAに関する性質ではない事である。よってFは「プログラムAは300行以下である」のようなものであってはならない。 そして「Aが与えられたとき、fAは性質Fを満たすかを決定せよ」という問題を考える。ライスの定理は、Fが自明なものでない限り、この問題を常に正しく解く事できるプログラムは存在しない、というものである。ここで自明な性質とは、「全てのfAが満たす性質」と「いかなるfAも満たさない性質」の事である。 ライスの定理をより厳密に記述するため、記号を導入する。プログラムAにデータxを入力して実行する事をA(x)と書き、A(x)がyを出力するときy=A(x)と書く。 コンピュータではいかなるデータも0と1の数字で表し、したがってプログラム自身も0と1の数字で表せる。以下記号を簡単にする為、プログラムAを数字で表したものも、Aと書く。よって例えばプログラムA、Bに対し、「A(B)」は、「プログラムBを表す数字をbとし、Aにbを入力して実行する」の意である。 ライスの定理は、Fを自明でない任意の性質とするとき、次のようなプログラムMは存在しない、というものである。 fAがFを満たす ⇒ M(A)はYESを出力して停止する。 fAがFを満たさない ⇒ M(A)はNOを出力して停止する。 ライスの定理でFの選び方を変える事で、以下の問題が全て決定不能な事が分かる。ここで「問題XXXが決定不能」とは、「問題XXXを解くプログラムは存在しない」の意。 与えられたプログラムが全ての入力に対して 0 を返すか 与えられたプログラムが少なくとも1つの入力に対して 0 を返すか 与えられたプログラムの出力は常に10ビット以下か
※この「直観的説明」の解説は、「ライスの定理」の解説の一部です。
「直観的説明」を含む「ライスの定理」の記事については、「ライスの定理」の概要を参照ください。
直観的説明
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/21 22:48 UTC 版)
高校の教科書等の初等的な解説書ではドミノ倒しに例えて数学的帰納法を説明しているものも多い。P(n) を「n 枚目のドミノが倒れる」の意味だとすれば、上の論法は以下のようになる: 1枚目のドミノが倒れる事を示す。 任意の自然数 k に対して、「k 枚目のドミノが倒れるならば k + 1 枚目のドミノが倒れる」ことを示す。 以上の議論から全てのドミノが倒れる事が結論づけられる。 数学的帰納法が成り立つ直観的理由は以下の通りである。まず1より (a) P(1) が正しい事が分かる。次に k = 1, 2, ... に対して 2 を適用する事で、 (b) P(1) ⇒ P(2), (c) P(2) ⇒ P(3), … が分かる。(a), (b) より、P(2) が成り立ち、この事実と (c) を組み合わせる事により P(3) が従う。以下同様に P(4), P(5), …も従い、結局 3 の 全ての自然数 n に対し P(n) が成り立つ が結論づけられる。 ただし、以上の議論はあくまで数学的帰納法が成り立つ理由の直観的説明であって、1, 2 と 3 の間にはギャップがある。詳しくは後述の「数学的帰納法の形式的な取り扱い」の項目を参照されたい。
※この「直観的説明」の解説は、「数学的帰納法」の解説の一部です。
「直観的説明」を含む「数学的帰納法」の記事については、「数学的帰納法」の概要を参照ください。
- 直観的説明のページへのリンク