あり命題論理における真偽判定問題の計算可能性について論理学,計算機科学,計算論9270通報$$$$はじめにはじめまして、mineelと申します。私は理論計算機科学等を普段勉強している学部生です。今回はタイトルの通り命題論理における真偽判定問題の計算可能性について書きました。いった記事を投稿するのは初めてで、至らない部分は多いとは思いますが多めにお願いします。記事のレベルは各分野の教科書の$10$ページ目くらいの内容を書いた程度のレベルです。面倒な部分や説明が下手な部分はあれど、難しい点は特にないので誰でも読める内容だとは思います。(ただし長いです)ただ、今回は数学的な解説記事というよりはやってみた系の記事の方が近く、今回は個人的な興味についての自己紹介のような記事になればいいなと思っています。この記事では$0$は自然数に含めるとします。~番目や~項目などと言うときは必ず$0$番目や$0$項目から始まっていることもご注意ください。※この記事はスマホからだと死ぬほど見辛いのでPCから見るのを推奨します。スマホから見るなら横にすればまだ少し見やすいです。真偽判定問題の前に軽く命題論理の用語の説明から入ります。いくつか独特な用語や記法を採用しているため、既に命題論理によくなじんでいる方も一応目は通しておおくといいかもしれません。論理式というものを定義していきます。p_1,...$とします。(加算無限個)命題変項とは、これ以上分解のできない論理式の単位のようなものだと考えていただいて大丈夫です。論理式を表す記号として$A,B,C...$を使います。B)$は「$A$ならば$B$」のイメージです。実際は論理式の形の定義を与えただけでまだ意味は考えてないです。括弧がキショすぎますが、後々括弧がある方が扱いやすいのでここでは括弧付き論理式のみ考えます。定義からわかるように$\land$や$\lor$は使わない主義で行きます。B)))$で意味的には同じになるので別に$\land$や$\lor$はなくても表現力は変わらないです。論理式の意味付けまた論理式の意味付けを恣意的に行っていきます。命題変項ごとに真偽を与える関数をここでは意味付け関数と呼ぶこととします。任意に与えられた意味付け関数に対し、その定義域を拡張して論理式に意味を与えていきます。論理式全体の集合を$Pro$とすることにします。TV$を通常の意味で使うことにします。\F(C)$この定義によって、各命題変項に対して真or偽を定めてやることで、各論理式に対しても真or偽を定めることができます。(\lnot(p_1)))$を入力としたとき出力は偽であるというようになります。問題が計算可能であるとは、その問題を解くアルゴリズムがあるということです。真偽判定問題はどうでしょうか?先ほどの例でも実演した通り、$\rightarrow$や$\lnot$を定義に沿って$(p_i)$という形が出てくるまで分解していき、最後は$TV$内における$\lnot$と$\lor$の定義に従って真偽を求めていけばそれで行けそうですね。定義するためにはいくつかの方法がありますが、ここでは再帰的関数及びNプログラムという$2$つの計算モデルを提示します。(原始)再帰的関数から見ていきます。(原始)再帰的関数とは数学的に定義された自然数上の関数です。以下のように定義しますが、定義は長いのでイメージさえ分かれば大丈夫です。\mathbb{N}$は再帰的関数である。(t))$とすればよいあまり計算論の話を深堀するつもりはないので定義の紹介にとどめておきます。イメージとしてはさまざまな関数を繰り返しによって定義しようという感じです。一応プログラムとの対応関係のイメージとして、最小解関数がプログラムで言うwhile文、すなわち、繰り返し回数が事前にわからないループに対応します。無限ループに陥り計算が止まらない可能性があるというわけです。いうわけで定義からも分かるように最小解関数のみが未定義を引き起こす要因となり、原始再帰的関数と違い再帰的関数は入力によっては未定義(=無限ループ)となる可能性を持っています。\mathbb{N}$が計算可能であるとは、$\f$が再帰的関数であるということである先ほど再帰的関数のイメージはさまざまな関数を繰り返しを用いて定義することと話したことと併せて考えると、計算不可能な関数とはとても繰り返しじゃ定義できないような関数というイメージとなります。ここで着目してほしい点が、原則として計算可能性というのはあくまで自然数上の関数にのみ定義される概念であるため、先ほどの真偽判定問題の計算可能性を判断するにはそもそも入力の論理式及び意味付け関数を自然数へとコーディングする必要があるという点です。(※補足:と私はずっと思い込んでいたのですが、チューリング機械による計算可能性の定義が「コンピュータによって計算可能」本来の姿であり、文字列の集合上の関数に対しても計算可能性は定義されます。本当に申し訳ございませんでした)ただ、その話に入る前にもう少し計算モデルの話を進めます。再帰的関数の概念は計算可能関数の数学的な性質を扱うにはとても便利な概念なのですが、もう少しプログラムチックにして直感的に扱いやすい形で計算可能関数を表現してみることにします。NプログラムNプログラムとは原始再帰的関数を用いた数学的にはラベル付き有向グラフとして定義されるプログラムです。記事の一番下の具体的なNプログラムを先に見ておけば雰囲気をつかみやすいかもしれません。詳しいことは参考文献の『計算論』(高橋)をご覧ください。Nプログラムの概念はこちらの本から拝借させていただきました。Nプログラム以下のノード及びラベル付き枝の組み合わせでできるラベル付き有向グラフをNプログラムという。Nプログラムが表す自然数上の関数も自然に定義する。\end{xy}$すなわち、Nプログラムは変数に式の値を代入する代入命令及び二つの式の値を比較する判定命令によって構成されるプログラムのようなものとなります。定義からわかる通り、Nプログラムも再帰的関数と同様に自然数の組を受け取り自然数を返す自然数上の関数となっています。重要な点が、Nプログラムで書ける関数はすべて再帰的関数であり、再帰的関数はすべてNプログラムで書ける関数であるという点です。(ここでは証明は省きます)これにより、再帰的関数の代わりに直感的に扱いやすいNプログラムを用いて計算可能性について考察することができるということとなります。ここから先ほどの真偽判定問題の計算可能性をちゃんと証明していきます。真偽判定問題の計算可能性の証明(本題)コーディングここからが本題となります。やるべきことをまとめます。1計算可能性は自然数上の関数にのみ定義されるので、真偽判定問題の入力である論理式及び意味付け関数を自然数へとコーディングする2コーディングされた自然数を受け取って、正しく$0$または$1$を返す関数をNプログラムで書くという2つのことができれば真偽判定問題の計算可能性が証明できます。コーディングの話から進めていくことにします。論理式に使われる各記号に対して自然数を割り当てるコーディング関数$\alpha$を定義します。$\alpha$によって各論理式は自然数列へと変換されます。5$これにより論理式を自然数列へと変換することができました。目標にはかなり近づいてきましたが、まだ論理式の長さによって変換後の数列の長さが異なっており扱いにくいです。そこで、自然数列をさらに一つの自然数にまとめるゲーデル関数というものを考えます。\mathbb{N}$が存在するすなわち、ゲーデル関数とは自然数列を一つの自然数へとまとめることができ、かつ一意に元の自然数列を復元できる関数ということになります。各$\G_i$をゲーデル関数$\G$の逆関数と呼びます。このゲーデル関数及び先ほどのコーディング関数を組み合わせることで、各論理式を一意に復元できる形で一つの自然数へとコーディングできるようになります。各論理式に対応する自然数をその論理式のゲーデル数と呼ぶことにします。これで論理式に対する操作や言明をその論理式ゲーデル数への操作や言明、すなわち記号ばかりだったのを、とうとうただの自然数に関する話へとすり替えることができました。数学っぽくなってきました。ところでゲーデル関数は性質だけ示してその存在はまだ示していません。そこで具体的な構成によって存在を示してみます。ゲーデル関数の構成方法は一通りでなく、おのおの好きなように実装してもらって構わないです。ここでは構成方法の一例をあげ、そのゲーデル関数を用いて話を進めていきます。(x)$は$x$番目の素数を返す関数である$\G$がゲーデル関数の性質を満たすことの証明は長くなるのでイメージだけ書きます。z$か調べればいいので事前に上限がわかる繰り返しで表現できるため原始再帰的です。(x-1)+2$は素数かと順に調べていけばわかるため原始再帰的です。繰り返し回数の上限は「$n$より大きい最小の素数は$n!+1$以下」という事実よりわかります。(y)$のべきを返す関数($x=0$なら$0$を返す)とすれば、$\G_i(x)=\pwr(x,i)$により逆関数を定義できます。(y)^2$で割り切れるか、と順に調べていき割り切れなくなるタイミングを調べればわかるので原始再帰的です。繰り返し回数の上限はx回とすれば大丈夫です。ついでに「割り切れるか」というのも証明は省きますがちゃんと原始再帰的です。意味付け関数もコーディングする必要がありますが、$\f(\alpha)$は第$i$項目が以下のようになる$0,1$からなる自然数列を返すようにコーディング関数の定義域を拡張して、それに対して上記のゲーデル関数を用いればコーディングが完了します。-1}$に限定していました以上により、1のステップは完了しました。ここから2のステップへと移っていきます。Nプログラムの構成コーディングにより真偽判定問題を自然数上の関数として定式化することができました。\mathbb{N}$によって定式化することができたということになります。故に、これから示すべきことは関数$\P$が計算可能関数であるということになります。$\P$が再帰的関数であることを直接示せればよいのですが、再帰的関数の概念は直感的に扱いにくいので、同等な概念であるNプログラムを用いることによって$\P$が計算可能であることを示していきたいと思います。証明用のNプログラムの構成の方針は以下の通りです。簡単に言えば論理式の構文木に沿って左から順にみていき、真理値を更新していく感じです。C)$なのか$(p_i)$を判断する2論理式の形をリストに記録する3論理式の形に添って部分論理式を取得する4取得した論理式について1~3を論理式の形が$(p_i)$になるまで繰り返す5$\f(p_i)$の値に沿って真理値を更新する6論理式の形を記録したリストを後ろからさかのぼり、形に添って真理値を更新していく7リストの初めまでさかのぼったら、その時の真理値を出力する順に説明していきます。与えられた論理式の形を判断する本来ならそこそこ面倒な問題だと思われますが、論理式にキショい括弧を付け続けた真価がここでついに発揮されます。コーディング関数の定義を見直してみましょう。B)$のときは$7$となっています。(B)$の第$0$項目は定義から必ず$3$となっていることがわかります。それ以外のときは$A$が$(p_i)$となります。C)$のときは第$1$項目は$3$となっていることになります。各論理式のコードの第$1$項目(=$\G_1(x)$)の値を調べればすぐに論理式の形が判断できるわけです。括弧を省略しなくてほんとよかったですね!ところで、なぜ論理式の形を知る必要があるのかということなのですが、これは論理式には合成性という、その部分論理式について調べれば全体がわかるという性質があるためになります。故に、形を判断した後はその部分論理式を取得しなければなりません。その前に手順2に移ります。論理式の形をリストに記録する記録する意義、記録をどう使うかについては後に改めて説明します。論理式の形を記録するというのは、論理式を部分論理式に分解していくときに各部分論理式の形をメモしていくというようなイメージです。ここではその記録の方法について説明をします。そもそもNプログラムにおいてはリストなど定義されておりません。リストをどう扱うのか。ここでは、$1$以上の自然数そのものをリストとして見るということをしてみることにします。具体的には、自然数を素因数分解したときのべきの部分に着目し、$2$のべきが$3$ならリストの第$0$項目は$3$、$3$のべきが$0$ならリストの第$1$項目は$0$として見るといった具合です。}$$30184=[3,0,0,3,1,0,0,...]$・$1=[0,0,...]$例からも分かる通り、自然数は無限リストとなっており上限を気にしなくてもよいのはとても便利です。格納できるのは$0$以上の自然数のみとなっております。要素の取得、挿入あたりの操作も一緒に原始再帰的関数で実装します。(削除は特に使わないので今回は無視します)まず、取得について。(L,i)$という$L$の$i$番目の要素を取得する原始再帰的関数を考えます。(L,i)=\pwr(L,i)$とすることで問題なく定義できます。($\pwr(L,i)$の定義は$L$の素因数分解において$i$番目の素数のべきを返すというものでした)続いてリストへの挿入について。\mathbb{N}$を挿入する原始再帰的関数を考えます。(L,i)$乗で割ることで挿入ができます。)$によって問題なく定義できます。(L,i,j)$も原始再帰的です。(L,i)}$となります。以上によりリストに対する要素の取得、要素の挿入が定義できました。論理式の形をリストに記録するという話でしたが、各形式の論理式に対して具体的にどんな自然数を記録すればよいのでしょうか。)=7$より$7$を記録すれば、記録を見返したときに否定形だったことがすぐ分かるので良さそうです。C)$の形)だったらどうでしょう。)=11$なので$11$を記録すればよいのでは?となりますが、実は問題があります。今回の証明の方針では論理式の構文木を"左から"見ていくという方針をとっており、含意形の論理式に対して手順3においては左の部分論理式しか取得しません。その後に、手順6においてさかのぼっていく際に含意形の記録を見つけたら右の部分論理式について見ていくという方針にしています。故に、含意形の論理式を記録する際には右側の部分論理式の情報も同時に記録する必要があるわけです。これがこの手順で論理式を記録する必要性が出てくる理由の1つとなります。そのために、含意形の記録だとわかり、なおかつすぐに右側の部分論理式の情報も得られるような記録といったら、右側の部分論理式のコードをそのまま記録するのが一番良いでしょう。実は記録用リストに記録する情報は否定形か含意形かの$2$種類の情報しか記録しません。記録が$7$と等しいか等しくないかさえ分かれば十分なので、含意形の記録の際に右側の部分論理式のコードを記録すれば問題ないというわけです。(なので正直否定形の方も$7$を記録することに本質的な意義はありません)ところで、論理式が$(p_i)$の形だったらどうするんだ、となりますが、そこは構文解析の終着点であり、そこまで着いたら記録をさかのぼるステップに入るので特に記録は必要ないです。ちなみに、まだこの段階は論理式の構文を解析してるだけの段階なので、肝心の論理式の真理値についてはまだ何も触れていません。手順5以降で真理値の更新をしていきます。(x)$が必要となります。すべて原始再帰的でなければなりません。\mathbb{N}$を実装しましょう。論理式の長さとは括弧も含めた記号の数のことを言います。(i),x)))$により定義できます。(i))\}$のような感じとなります。それでは説明に入ります。細かい部分の証明は基本省きます。原始再帰的関数の有限和及び有限積は原始再帰的です。$によって定義されます。マイナスにはならない点には注意してください。$x$に適当に$5$など入れて確認してみてください。合成なのでこれも原始再帰的です。$の定義が得られます。\mathbb{N}$も定義しましょう。(x)))$により得ることができます。$は以下のようにして得ることができます。各$\G_j$はゲーデル関数の逆関数です。x}$については後述します。イメージとしては左から順に記号を見ていって、左括弧を見たら$1$を足す、右括弧を見たら$1$を引くというようにして、合計が$0$になった時点の位置を出力するといった具合です。右括弧の数がそれまでの左括弧の数と等しくなった位置が左の部分論理式の終わりの位置という考えを利用しました。詳しく見てみると、まず、$1+\G_{i+1}(x)/3-\G_{i+1}(x)/5$の部分が、自然数$x$に対応する論理式の$i+1$番目の記号が「$($」ならば$2$、「$)$」ならば$0$、「$($」でも「$)$」でもないならば$1$を返す関数となっていることがわかります。\{1+\G_{i+1}(x)/3-\G_{i+1}(x)/5\}=i+1$となることがわかります。x}$となるわけです。x}$というのは、$z$を$0$から調べていき、括弧の中身の式が初めて成立するような$z$を返す関数となります。再帰的関数の定義にあった通常の最小解関数との違いは、$z$の探索範囲に上限があるという点です。(今回の上限は$x$)こちらも証明は省きますが、括弧の中身の式が原始再帰的ならば最小解関数も原始再帰的となります。ここでは詳しくは説明しませんが、$=$は実は原始再帰的述語と呼ばれるものであり、しっかり原始再帰的です。$全体も原始再帰的ということとなります。$を実装していきましょう。(x))))$により得られます。(x)}$となっています。(i)$のべきは元の論理式から$($と$\lnot$の$2$個分ずらしていけば否定形の部分論理式を得ることができます。残り二つについても全く同様です。非常に目が疲れるパートでしたがこれで手順3の目標は達成できたこととなります。取得した論理式について1~3を論理式の形が$(p_i)$になるまで繰り返すこれは与えられた論理式のコードを手順3で得た論理式のコードに書き換えて、同じことを繰り返すだけです。手順1で論理式の形が$(p_i)$になっていることがわかったら、手順5に進みます。$\f(p_i)$の値に沿って真理値を更新するやっと真理値に触れることができます。終わりまでもう少しです。そもそも$\f(p_i)$を求める方法を考えます。これは簡単で、意味付け関数$\f$は、第$i$項目が命題変項$p_i$の$\f$における真偽($0$または$1$)となる$0$と$1$の自然数列(のコード)として与えられるので、その第$i$項目が$\f(p_i)$ということになります。意味付け関数のコードは自然数$y$で与えられているため、$\pwr(y,i)$により命題変項$p_i$の真偽($0$または$1$)を取り出すことができます。\pwr(y,i)=1$と書けます。(i)$(=$i$番目の素数)のべきを返す関数でした。$p_i$の$i$は直接与えられるわけではありません。\mathbb{N}$から$i$を取り出さなければいけません。2)$により論理式のコード$x$から取り出すことができます。(x)=x-1$($x=0$なら$0$を返す)でした。2))=1$となることがわかります。2))$と書くことにします。($x$は入力の論理式のコード、$y$は入力の意味付け関数のコードでした)これで$\f(p_i)$を求める方法がわかりましたので、真理値を更新方法を考察していきましょう。真理値を格納する変数を$tv$とし、初期値は$0$とします。更新の方法は、元の$tv$の値に直接$\f(p_i)$の値を代入するという方法で$tv$の値を更新していきます。このように真理値を更新していけばよいのかは後に解説します。}$$tv:=\v(x,y)$とすれば大丈夫です。「$:=$」はNプログラムにおける代入命令に使われる記号で、左の変数に右の式を代入するという意味でした。論理式の形を記録したリストを後ろからさかのぼり、形に添って真理値を更新していくこの手順が真偽判定問題の答えを得るための核となる手順です。この手順で手順2において論理式の形を記録したリストを活用していくこととなります。(x)$の二種類しかありません。論理式の分解が終わり記録をさかのぼって真理値を更新していく際には、この二種類の記録に対してそれぞれどう$tv$を更新していけばよいかを考えれば十分だとわかります。リストの自然数がどちらの記録なのかは、その自然数が$7$であるかどうかを調べればわかるのでした。$7$を見たときについて。B)$という形だったとします。(x)$まで戻ってきたということは、論理式$B$の真理値の解析は終わっており、その値は$tv$に格納されている状況にあることになります。B)$の真理値を知りたかったら$tv$の値を逆転させればよいです。(1,tv)$とすることで$tv$の値を逆転させることができます。(x)$を見たときについて。C)$という形だったとします。今、論理式を分解していくときは左からみていくという方針を取っていました。(x)$まで戻ってきたということは、論理式$B$の真理値の解析は終わっており、その値は$tv$に格納されている状況にあることになります。$B$の真理値が偽だったとしましょう。C)$全体の真理値も真だということとなります。故に、もはや$C$のことなど忘れて、即座に$tv$の値を$1$に更新すればよいこととなります。$B$の真理値が真だったとしましょう。C)$全体の真理値はまだわかりません。C)$全体の真理値が完全に一致することはわかります。この場合には論理式$B$のことなど完全に忘れてもう一度$1$から論理式$C$について解析しなおせばよいわけです。与えられた論理式を$C$として手順1からやり直せばよいということとなります。$関数で上書きすればよいだけなので特に気にしなくても大丈夫です。これで真理値の更新の仕方がわかりました。ところで、手順5で今までの$tv$の値を無視して$tv$には直接$\f(p_i)$の値を代入すると説明しましたが、今までの$tv$の値を利用するタイミングというのはこの手順でリストの$\lnot$や$\rightarrow$の記録を見た時だけなので、論理式を$(p_i)$まで分解していったときは、今までの値に関係なく新しく解析中の部分論理式の真理値がわかればよいので、そのまま直接$\f(p_i)$の値を使ってもよいというためになります。リストの初めまでさかのぼったら、その時の真理値を出力する基本は書いてある通りで特に説明することもないのですが、今まで触れなかったカウンターについてここで説明します。ここでのカウンターは、その時点でリストの第何項目を見ているのかを表すカウンターとなります。リストに対する要素の取得や挿入の操作をする際には、カウンターにより位置を確認します。カウンターは手順3で部分論理式を取得した直後に$+1$し、手順6で一つさかのぼるごとに$-1$します。カウンターについての説明はこの程度です。カウンターを見て終了タイミングを把握し、その時の$tv$を取得すれば大丈夫となります。実際のNプログラム今までのことをすべて一つのNプログラムにまとめて、証明終了となります。今の私の知識では複雑なNプログラムを$TeX$で表現することが難しく、非常に見にくい図となってしまっています。\end{xy}$$L$がリストを表す自然数、$c$がカウンターを表す自然数、$\varphi$が論理式のコードを格納している自然数となっています。今までのことをまとめただけなので特に説明することもありませんが、一応二つ目のノードに関しては$L,c,\varphi$を並列に初期化していますが、実際はNプログラムに並列な計算は定義されていません。今回は逐次的に連続してこの三つの計算を行えばよく、特に順番も重要でないためこのような書き方をしました。ちなみに今更ですが裸の定数は実際は$\suc^n(\zero()):\mathbb{N}^0\rightarrow\mathbb{N}$($\suc$の$n$回合成)という定数関数で、ちゃんと原始再帰的です。これで真偽判定問題を表す関数$\P$が計算可能であることの証明完了となります。本当は構成したNプログラムが要件を満たすのか確認しなければなりませんがどうかお許しを。おわりにここまで見てくださってありがとうございました。見やすい記事とは言えないとは思いますが、楽しんでいただけたら何よりです。この記事で書いたような内容が面白いと感じたならば、理論計算機科学という分野を学んでみることをお勧めします。いうと論理学や、計算理論、圏論などを用いてプログラミング言語などについて考察していく分野だと僕は思っています。本当にありがとうございました。高評価したユーザはいませんこの記事に送られたバッジバッジはありません。バッチを贈って投稿者を応援しようバッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。バッチを贈るコメントmineel命題論理における真偽判定問題の計算可能性について。