武蔵野個別指導塾の特徴

数理論理学と計算可能性　証明できないことを証明する｜武蔵野個別指導塾

公開 2026.10.13更新 2026.10.13武蔵野個別指導塾の特徴大学数学特集（解析・線形代数・代数・幾何・確率統計）

真理値表、量化記号、停止問題の対角線論法をたどり、完全性と不完全性が両立する理由を確かめます。計算可能性と P・NP の違いを、論理式の具体例から学べます。

数理論理学と計算可能性　証明できないことを証明する

将棋部の部室で「全部調べれば」を問い直す

将棋部の部室で、片付けかけた盤の横に小さなノートを置く場面を考えてみます。詰む手順を探している人が「この応手なら詰む」と言い、向かいの人が別の応手を指します。ひとつの成功例を見つけることと、相手がどう応じても成功すると示すことは違います。ノートの枝分かれが増えるほど、「調べた範囲では正しい」と「必ず正しい」の距離が気になってきます。

数学を教える立場から、この距離は丁寧に扱いたいところです。高校の証明でも、いくつかの整数を代入して正しかっただけでは、すべての整数について成り立つとはいえません。それでは、正しい命題を次々に見つける機械があれば、いつか数学の問題はすべて解けるのでしょうか。証明の規則まで機械に教えれば、正しい命題と誤った命題を必ず仕分けられるのでしょうか。

数理論理学は、こうした問いを、意味のはっきりした記号と規則に置き換えて調べます。計算可能性の理論は「計算手順が存在する」とは何かを定め、その手順で解ける問題と解けない問題の境界を扱います。さらに計算量の理論に進むと、手順の有無だけでなく、入力が大きくなったときに必要な時間を問います。

将棋の探索そのものから、ただちに数学全体の限界が導かれるわけではありません。それでも、候補を探す、候補を検査する、すべての場合を尽くしたと示す、という作業の違いはよい入口になります。この分野で身につけるのは、難しい言葉で限界を語る姿勢ではありません。何について、どの規則のもとで、どこまで結論したのかを明確にする読み方です。

高校の必要十分条件から真理値表へ

高校数学の「命題と条件」では、命題が真か偽かを考え、逆、裏、対偶を区別します。たとえば整数 n に対して、P を「n は 4 の倍数」、Q を「n は偶数」とします。P ならば Q は真ですが、Q ならば P は真とは限りません。n = 6 は偶数でありながら 4 の倍数ではないので、逆に対する反例です。元の命題と逆を同じものとして扱えない理由が、このひとつの数で見えます。

数式でも確かめましょう。n が 4 の倍数なら、ある整数 k を使って n = 4k と書けます。

n = 4k = 2 × (2k)

2k も整数なので、n は偶数です。ここではたくさんの倍数を調べたのではなく、任意の倍数を文字で受け取り、偶数の定義に戻しました。証明で使ったのは「4 の倍数」「偶数」という言葉の意味です。

命題論理では、その内容をいったん離れて、P、Q の真偽だけを扱います。否定を ¬P、かつを P ∧ Q、またはを P ∨ Q、ならばを P → Q と書きます。「または」は、両方が真の場合も含みます。古典論理における含意 P → Q は、P が真で Q が偽のときだけ偽です。

P	Q	P → Q	¬Q → ¬P
真	真	真	真
真	偽	偽	偽
偽	真	真	真
偽	偽	真	真

右の 2 列が一致することが、命題とその対偶が同じ真理値を持つ理由です。P が偽の行で含意が真になるのは、日常語の「だから」と少し感覚が違うかもしれません。含意は因果関係を述べる記号ではなく、「P が成り立つのに Q は成り立たない」という場合を排除する記号です。前件が成り立たなければ、その禁止した場合には当たりません。

高校の二次不等式も、この見方につながります。実数 x について x² – 3x + 2 = (x – 1)(x – 2) ですから、x² – 3x + 2 = 0 の解は x = 1 または x = 2 です。方程式を満たす条件を別の条件へ言い換えています。ただし、途中で両辺を x – 1 で割ると、x = 1 という場合を落とします。変形前後が同値なのか、一方向の含意だけなのかを確認する必要があります。

ここから大学の論理に進むと、「x がどんな対象を動くか」「ある x があるとは誰が選べるのか」まで記号に表します。高校で暗黙に置いていた整数や実数という範囲も、結論を左右する情報になります。計算が正しいことと、計算を行ってよい条件が揃っていることを分けて読むのが、最初の一歩です。

真であることと証明を持つことを分ける

まず、命題論理の充足という言葉を定義します。各命題変数に真か偽を割り当てるものを付値 v といいます。論理式 φ が付値 v のもとで真になることを v ⊨ φ と書きます。ある付値のもとで真になる論理式を充足可能といい、すべての付値のもとで真になる論理式を恒真式といいます。記号では次のように区別できます。

充足可能: ∃v (v ⊨ φ)

恒真式: ∀v (v ⊨ φ)

P ∧ Q は P と Q がともに真なら真なので充足可能ですが、恒真式ではありません。P ∨ ¬P はどちらの付値でも真なので、古典命題論理では恒真式です。P ∧ ¬P はどの付値でも偽なので充足不可能です。「一度でも成功する」と「どの場合でも成功する」を区別する量化の違いが、ここにもあります。

述語論理では、対象の性質や対象間の関係を表せます。たとえば E(x) を「x は偶数」とすれば、∀x E(x) は「すべての x が偶数」、∃x E(x) は「偶数である x が存在する」を表します。しかし、この説明には x の動く範囲が必要です。通常の一階述語論理では、構造は空でない対象の集合である領域と、定数、関数記号、関係記号の解釈からなります。自然数の構造と整数の構造とでは、同じ形の式が違う真理値を持つことがあります。

自然数を ℕ = {0, 1, 2, …} とすると、∀x ∃y (x < y) は真です。どの x に対しても y = x + 1 とすればよいからです。一方、∃y ∀x (x < y) は偽です。先にひとつの y を選んでも、x = y を代入すれば x < y は成り立ちません。量化記号の順序は、選べるものが何に依存するかを決めます。前者の y は x ごとに変えてよく、後者の y はすべての x に共通でなければなりません。

次に、形式的な証明を定めます。使用する記号、式の作り方、公理、推論規則を指定したものを形式体系と呼びます。ここでは、その公理を含む理論を T と書きます。T からの証明は、各行が論理公理または T の公理であるか、前の行から指定された推論規則で得られる、有限個の式の列です。その列の最終行が φ であるとき、T ⊢ φ と書きます。これは「T において φ が証明可能」という意味です。

たとえば、P と P → Q から Q を導く規則を使えば、前提 P → Q、Q → R、P から Q を得て、続いて R を得られます。最終行だけが正しそうかを見るのではなく、各行の根拠を有限回で点検するのが形式的な証明の特徴です。公理や規則の適用を機械的に検査できるように定めれば、候補として渡された証明の検査も機械的に行えます。

これと区別すべき記号が T ⊨ φ です。これは、T のすべての文を真にするあらゆる構造で、φ も真になることを意味します。そのような構造を T のモデルと呼びます。T ⊢ φ は記号列としての証明の存在、T ⊨ φ はモデルにおける意味の関係です。ひとつの構造で真であるという主張と、すべてのモデルで真であるという主張も混同してはいけません。

古典一階述語論理の健全性と完全性は、標準的な証明体系について、文の集合 T と文 φ に対して次の関係を述べます。

T ⊢ φ であることと T ⊨ φ であることは同値です。

証明できたものはすべてのモデルで真になるという方向が健全性で、すべてのモデルで真なら証明できるという方向が完全性です。これは、特定の自然数の構造で真である文を、ある固定した公理系ですべて証明できるという主張ではありません。この「すべてのモデル」と「意図しているひとつの構造」の区別が、完全性と不完全性を両立させます。

証明の限界と停止判定の限界を追う

理論 T が無矛盾であるとは、ある文 φ とその否定 ¬φ の両方が T から証明されることがない、ということです。また、理論が完全であるとは、その言語のどの文 φ に対しても、T ⊢ φ または T ⊢ ¬φ が成り立つことです。先ほどの「論理の完全性」は意味上の帰結と証明の対応でしたが、こちらの「理論の完全性」は個々の文を肯定か否定のどちらかに決着させられるという性質です。

第一不完全性定理を、適用範囲が見える形で述べましょう。T が自然数の加法と乗法を扱うペアノ算術を含み、公理を機械的に列挙でき、さらに ω 無矛盾であるとします。このとき、ある文 G が存在して、T ⊬ G かつ T ⊬ ¬G となります。ω 無矛盾とは、ある式 ψ(x) について、各自然数 n を表す数詞を入れた ψ(n) をすべて証明しながら、同時に ¬∀x ψ(x) を証明することがない、という条件です。通常の無矛盾性より強い条件であり、ここでは原型に沿った十分条件として採用しています。

条件が多いことには意味があります。自然数の真なる文をすべて集めれば、真偽を決着させるという意味では完全な理論になりますが、その公理全体を機械的に列挙することはできません。不完全性定理は、単に「どんなルールにも必ず穴がある」と述べているのではなく、算術を含むことと、手続きとして扱えることを同時に要求しています。

証明の核心は、式と証明を自然数で符号化し、「この数はこの文の証明を表している」という関係を算術の内部で扱うことです。そのうえで、おおよそ「この文には T における証明がない」という内容を持つ文 G を構成します。日常語で自分自身に言及するだけではなく、記号列を数へ移し、その数に関する式を作るところが数学的な仕組みです。

もし T に G の証明があれば、その具体的な有限の証明の符号を使って、T の内部でも「G の証明が存在する」と確認できます。しかし G はそれが存在しないことを述べるように作られています。したがって無矛盾性に反します。この方向が、G を証明できないことを示す要の一歩です。否定 ¬G の証明も排除するには、ここで述べた形では ω 無矛盾性を用います。「G が証明できない」から直ちに「¬G も証明できない」と飛ぶことはできません。

計算の側にも、はっきりした不可能性の定理があります。その準備として、チューリング機械を考えます。有限個の状態、有限種類のテープ記号、読み書きするヘッド、現在の状態と読んだ記号に応じて次の動作を決める有限の規則表を備えた計算モデルです。テープは必要なだけ使えるものとし、各段階では有限の動作を行います。停止状態に入れば計算が終わりますが、規則に従った動作がいつまでも続く場合もあります。

たとえば単項表記で数を表し、テープ上の 111 を数 3 と読むとします。ヘッドが左端から右へ進み、1 の上では右へ動き、初めて空白を読んだら 1 を書いて停止する規則は、1 を足す計算です。入力 111 は出力 1111 になります。最初の 3 回で既存の 1 を通過し、次の 1 回で書き込んで停止するので、この規則での遷移は 4 回です。空の入力を 0 とみなせば、1 回の遷移で 1 を書いて停止します。

停止問題は、機械の記述 M と入力 w を受け取り、「M は w 上で停止するか」に答える問題です。定理は、あらゆる M と w に対して自分自身も必ず停止し、正しく答えるチューリング機械は存在しない、というものです。個別の機械の停止を証明できないと言っているのではありません。今の加算機械のように停止を確認できるものはたくさんあります。

証明は、その万能判定機械 H が存在すると仮定して進めます。機械の有限の記述を文字列に符号化すれば、機械の記述自身を入力に渡せます。新しい機械 D は、入力 x を機械の記述として受け取り、H に「x の機械は入力 x で停止するか」と尋ねます。H が停止すると答えたら D は永久に動き続け、停止しないと答えたら D はすぐ停止するように作ります。

ここで D 自身の記述 d を D に入力します。H が停止と判定すれば、D の規則により D は停止しません。H が停止しないと判定すれば、D は停止します。どちらの答えでも H は誤るので、最初の仮定が成立しません。逆向きに動く機械を作り、その機械自身に判定を適用する一歩が決定的です。

一定時間動かして停止しなかったという観察は、この証明の代わりにはなりません。さらに待てば停止する可能性を消せないからです。停止した場合は、その時点までの有限の計算履歴が証拠になりますが、まだ停止していないことだけでは永久に停止しない証拠になりません。この非対称性は、計算実験を読むときにも役立ちます。

算術を記号として扱う発想が生んだ転換

数学の証明を明確な公理と規則に整理する試みには、複雑な議論でも、何を前提にして何を導いたかを点検できるようにする狙いがあります。ところが、証明を厳密に記述できるようにすると、その証明自体が数学の研究対象になります。数について語る式と、その式に証明があることを語る議論が結びつき、形式化の能力そのものを調べられるようになります。

ゲーデルの論文は、この転換を象徴するものです。機械的に扱える公理系と無矛盾性の条件のもとで、形式的に決定できない文が現れるという不完全性の結果は、証明の限界を体系の外から数学的に示しました（Gödel, 1931）。前節で条件を明記したのは、結果の驚きだけを切り離さないためです。扱う数の構造や公理の与え方が変われば、同じ結論をそのまま適用できるとは限りません。

不完全性は、数学の証明が信用できなくなったという意味でもありません。特定の理論で、どの文にも証明か反証があるとは限らないということです。ある未決定の文を新たな公理として加えることを考えても、適用条件を満たす体系である限り、その拡張した体系にもまた不完全性の問題が生じます。公理を加えた後の体系については、無矛盾性などの条件を改めて調べる必要があります。

一方、計算とは何かを明確にする道筋では、チューリングが、有限の規則に従う機械によって数の桁を生成する考え方を提示しました（Turing, 1937）。計算者の行動を細かい操作に分け、規則表にまとめることで、漠然とした「手順通りに計算する」を数学の対象へ移しています。機械の部品が少なくても、記述を入力として扱えるため、別の機械の計算を模倣するという考え方に進めます。

ここで「有限」という言葉が指す場所にも注意が必要です。規則表は有限ですが、計算に使う時間やテープの範囲に一律の上限を置くわけではありません。有限の規則から非常に長い計算も、停止しない計算も生まれます。手順の記述が短いことと、実行が短時間で終わることは別です。

その後の訂正論文では、元の論文の証明が訂正され、「機械が数を計算する」という定義にも小さな変更が加えられています（Turing, 1938）。これは、厳密な分野であっても、最初の表現がそのまま完成形になるとは限らないことを示す書誌上の具体例です。定義のどこを変更すると、どの証明に影響するのかを追うことも、数学を学ぶ作業に含まれます。

不完全性と停止問題には、自分自身の記述を数学的に扱うという共通点があります。ただし、前者は公理系からの証明可能性、後者はすべてのプログラムを対象とした停止判定を問います。同じ定理としてまとめるより、対象と仮定を書き分けたうえで、自己言及を厳密に実現する発想の共通性を読むと、両者の関係が見えやすくなります。

計算が終わるかと速く終わるかを分ける

情報分野への応用で、まず思い浮かぶのはプログラムの検証です。入力の条件が満たされているとき、計算後に目的の条件が満たされることを証明します。たとえば自然数 n を受け取り、変数 r を n にして、r > 0 の間は r を r – 1 に置き換える処理を考えます。r は自然数のまま各回で減るので、いつまでも繰り返すことはできません。終了時には r = 0 です。

n = 3 なら、r の変化は 3 → 2 → 1 → 0 となり、反復は 3 回です。しかし n = -1 を許して、条件を r ≠ 0 に変えると、-1 → -2 → -3 と減り続けます。入力の範囲と繰り返し条件を明記することが、正しい停止証明の一部です。停止問題が一般には解けないことと、こうした個別の処理を証明で検査できることは両立します。

次に、必ず終わることがわかった後でも、どのくらいの時間がかかるかという問題が残ります。P と NP は、有限の文字列を入力とし、はいかいいえで答える決定問題の集まりです。P は、入力の長さ n に対し、決定性チューリング機械が多項式時間で判定できる問題のクラスです。多項式時間とは、固定した定数 C と自然数 k を使って、必要な時間を C × (n + 1) の k 乗以下に抑えられることをいいます。

NP は、はいとなる入力に対し、入力長の多項式で抑えられる長さの証明書が存在し、その証明書の正しさを決定性の手順で多項式時間に検査できる問題のクラスです。より正確には、ある多項式時間の検証手順 V と多項式 p があり、入力 x が問題 L に属することが、長さ p(|x|) 以下の文字列 c で V(x, c) が受理するものが存在することと同値になる、という定義です。|x| は文字列 x の長さを表します。

NP の N は「多項式ではない」という否定ではありません。検査のしやすさを定めているのであって、解くことが必ず難しいと定めているわけではありません。P ⊆ NP です。多項式時間で答えを出せる問題なら、検証手順が証明書を使わず、自分で答えを計算すればよいからです。

具体例として、次の命題論理式を考えます。

F = (p ∨ q) ∧ (¬p ∨ r) ∧ (¬q ∨ r)

この式を真にする付値が存在するか、という問題では、p、q、r の値が証明書になります。p を真、q を偽、r を真とすると、括弧ごとは順に「真または偽」「偽または真」「真または真」なので、すべて真です。証明書を渡された側は、その代入を各括弧に入れて確かめればよく、探し直す必要はありません。

この式については全体も数えられます。r が偽なら、第 2 の括弧から p は偽、第 3 の括弧から q は偽でなければなりませんが、それでは第 1 の括弧が偽になります。したがって r は真です。r が真なら残る条件は p ∨ q だけなので、(p, q) は (真, 真)、(真, 偽)、(偽, 真) の 3 通りです。全付値は 2³ = 8 通り、そのうち 3 通りが式を満たします。

変数が n 個あれば全付値は 2ⁿ 通りです。n = 20 では 1,048,576 通りになります。ただし、全列挙の方法が指数的だからといって、別の速い方法が存在しないことまで証明したわけではありません。「いま知っている解法が遅い」と「あらゆる解法が遅い」を区別することが必要です。

P と NP の関係が重要な問いであることは、その重要性を題名に掲げた論考にも表れています（Cook, 2003）。この問いの意味は、「短い証明書を速く検査できる問題を、証明書なしでも速く判定できるか」です。ここではその等否について結論を置かず、何を比べる問題なのかを押さえます。また、多項式時間は入力長に対する増え方の基準であり、次数や係数が大きければ実用上は重い計算になります。

この考え方は、複数の条件を同時に満たす配置や割り当てを探す場面に結びつきます。候補を論理変数で表し、満たすべき条件を論理式にすれば、候補の検査と候補の探索を分けられます。論理式としての表現ができた後に、どの条件なら効率よく扱えるかを調べることが、数学から情報処理へ続く具体的な課題になります。

記号を増やす前に、依存関係を書き出す

学び始めのつまずきは、記号そのものよりも、記号の役割が途中で変わることにあります。P を命題として使っていた直後に計算量のクラス P が現れたり、「完全」という語が論理と理論に別の意味で使われたりします。ノートの冒頭で、その節での意味を短く書けば、同じ文字に異なる知識が重なるのを防げます。

証明教育を扱った研究では、形式的な論理の手法と、実際の数学の証明で使う非形式的な手法との隔たりが検討されています（Aristidou, 2020）。対象として大学生の証明に関する意見や、ギリシャおよびギリシャ系キプロスの高校での状況が扱われており、ここから日本の高校生に特定の教え方が一律に有効だとまでは言えません。授業では、すべてを最初から記号に置き換えるより、日本語で前提と結論を言い、その後で必要な量化記号を加える手順を取れます。

また、入門的な抽象代数の授業で、大学生 23 人が単射・全射について証明を書く試みを調べた研究があります（Wheeler and Champion, 2013）。研究対象はその授業の証明課題であり、数理論理学の学習全般への効果を直接示すものではありません。それでも、計算中心の課題から、自分で論証を組み立てる課題へ移るときに、完成した解答だけでなく途中の記述を読む必要があるという授業の問いにつながります。

学習の手順を具体化しましょう。第 1 に、対象の範囲を先に書きます。「任意の x」だけで止めず、「任意の自然数 x」とします。第 2 に、量化の順序を日本語へ戻します。∀x ∃y なら「x をひとつ受け取るたびに y を選ぶ」、∃y ∀x なら「共通の y を先に選ぶ」と読みます。第 3 に、主張の否定を作ります。∀x ∃y R(x, y) の否定は ∃x ∀y ¬R(x, y) です。何を示せば反例になるかが、これで明確になります。

第 4 に、証明の各行に、定義、仮定、既知の結果、推論規則のどれを使ったかを添えます。「明らか」と書いたところで、使った条件をひとつ言えるか確かめます。第 5 に、小さな場合の計算と一般の証明を別々に置きます。真理値表は命題変数が有限個ならすべての場合を尽くせますが、自然数をいくつか試すだけでは自然数全体を尽くせません。検査した範囲の性質を意識する練習です。

高校生のうちには、必要十分条件、整数の証明、数学的帰納法を使って、この手順を練習できます。数学的帰納法では、最初の場合を示すことと、任意の段階から次の段階へ進めることを分けて書きます。たくさんの具体例が並んだことを、帰納法の証明が完成したことと取り違えないようにします。高校の計算を捨てて抽象的な話に移るのではなく、使っていた論理を見えるようにする学びです。

塾で担うのは、解答の丸付けに加え、条件が抜けた場所を特定し、同じ主張を自然な言葉と記号の両方で書けるように支えることです。家庭では、お子さまが難しい用語を覚えたかより、「何を仮定したの」「その例だけで全部と言えるの」と説明を聞く時間を持てます。証明の採点を家庭へ持ち込む必要はなく、どこまで説明できて、どこで言葉が止まったかを共有できれば、次に確かめる課題が具体的になります。

ここで手が止まるなら、止まった単元まで一緒に戻ります。武蔵境の数学塾（1 対 1）／お問い合わせ

「証明できない」をめぐる3つの疑問

完全性定理があるのに、なぜ不完全性定理も成り立つのですか

完全性定理は、一階論理で T のすべてのモデルにおいて真となる文が T から証明できる、という関係です。不完全性定理は、一定の条件を満たす算術の理論 T では、証明も反証もできない文があると述べます。特定の自然数の構造で真であることを、T のすべてのモデルで真であることに置き換えてはいけません。比べている「真」の範囲を明示すると、矛盾した主張ではないとわかります。

コンピュータを速くすれば、停止問題も解けますか

停止問題の不可能性は、速度や記憶容量の不足から導いたものではありません。万能の判定手順を仮定すると、その答えに逆らう機械を構成できて矛盾することから導きます。一方、入力やプログラムの形を限定した問題では停止を判定できる場合があります。どの範囲を対象にした判定なのかが肝心です。

不完全性から、人間の思考は機械を超えるといえますか

ここで述べた定理だけから、その結論は出ません。定理の対象は、明示した条件を満たす形式体系です。人間の思考をどの体系と同一視するか、その体系が必要な条件を満たすかは別の問題です。「ある体系で証明できない」という数学的な結論を、人間一般の能力についての断定へ飛躍させない読み方が求められます。

将棋部の部室で、盤の横のノートに戻ってみましょう。「この手で勝てた」の横へ、「相手のどの応手まで調べたか」を書き足すと、議論の意味が変わります。数学でも、答えだけでなく、対象と条件と手順を書き足すことで、主張の届く範囲が見えてきます。

証明できないことを証明するという題目は、行き止まりを眺めるためのものではありません。何が有限の証拠になり、何には一般的な判定手順がなく、何は検査できても探索に時間がかかるのかを分けるためのものです。前提を明記した一行から、数学の可能性と限界を正確に読み取る学びが始まります。

あわせて読む（数学の地図・高校数学の単元解説）

参考文献

Kurt Gödel（1931）「Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I」Monatshefte für Mathematik und Physik. https://doi.org/10.1007/bf01700692
A. M. Turing（1937）「On Computable Numbers, with an Application to the Entscheidungsproblem」Proceedings of the London Mathematical Society. https://doi.org/10.1112/plms/s2-42.1.230
A. M. Turing（1938）「On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction」Proceedings of the London Mathematical Society. https://doi.org/10.1112/plms/s2-43.6.544
Stephen Cook（2003）「The importance of the P versus NP question」Journal of the ACM. https://doi.org/10.1145/602382.602398
Michael Aristidou（2020）「Is Mathematical Logic Really Necessary in Teaching Mathematical Proofs?」Athens Journal of Education. https://doi.org/10.30958/aje.7-1-5
Ann Wheeler, Joe Champion（2013）「Students’ Proofs of One-to-One and onto Properties in Introductory Abstract Algebra」International Journal of Mathematical Education in Science and Technology. https://doi.org/10.1080/0020739x.2012.756546