アルアカ - Arcadia Academia

数学やコンピュータサイエンス、論理学などの分野で重要な「証明技術」は、命題や理論が正しいことを示すための方法論です。証明技術を使うことで、ある仮定から導かれる結論を厳密に立証することが可能になります。この記事では、TypeScriptでの実装しつつ証明技術の基礎をわかりやすく解説し、主な証明の種類とその使い方を紹介します。

サンプルコードは以下のリポジトリにあげています。

GitHub - oga114/DiscreMath-TS

Contribute to oga114/DiscreMath-TS development by creating an account on GitHub.

https://github.com

証明とは、命題や定理が正しいことを論理的に示すプロセスです。証明を行う際は、まず示したい結論を明確にし、その結論が正しいとされる条件（仮定）を出発点として、論理的な一貫性を持って結論に到達する必要があります。この一連の論理的なステップに誤りがなければ、証明は成立します。

例えば「ある数が偶数であれば、その2乗も偶数である」という命題を証明する場合、「ある数が偶数である」という仮定を元に、「その2乗も偶数である」という結論を導き出します。

証明技術にはいくつかの基本的な種類があり、それぞれが異なるアプローチで論理的な結論を導き出します。以下に代表的な証明方法を紹介します。

直接証明は、結論をそのままの形で証明する方法です。この方法では、出発点としての仮定を元に、論理的に一貫したステップを積み重ねて、目標とする結論に到達します。

たとえば、「偶数の2乗は偶数である」という命題を直接証明で示す場合、偶数を「2n」と表し、その2乗が「4n^2」となることを示すことで、2で割り切れることが分かります。こうして「偶数の2乗も偶数である」ことを論理的に証明します。

function isEven(n: number): boolean {
    return n % 2 === 0;
}

function isSquareEven(n: number): boolean {
    // 偶数である場合、その2乗も偶数であることを確認
    if (isEven(n)) {
        return isEven(n * n);
    }
    return false;
}

// 使用例
const num = 4;
console.log(`Number ${num} is even: ${isEven(num)}`); // true
console.log(`Square of ${num} is even: ${isSquareEven(num)}`); // true

間接証明、または背理法（Reductio ad Absurdum）は、結論が偽であると仮定し、その仮定が矛盾を引き起こすことを示す方法です。矛盾が生じるため、初めの仮定が偽であることがわかり、結論が真であると証明されます。

例えば、「√2は無理数である」という命題の証明では、√2が有理数であると仮定します。すると、整数a, bを用いて √2 = a/b と表せることになりますが、この仮定により数式を操作すると、aとbの最小性に矛盾が生じるため、√2は無理数であると結論づけることができます。

function doesNotContain<T>(array: T[], element: T): boolean {
    return !array.includes(element);
}

function proofByContradiction<T>(array: T[], element: T): boolean {
    if (doesNotContain(array, element)) {
        // 矛盾を導く
        console.log(`Array does not contain element ${element}.`);
        return true;
    } else {
        console.log(`Contradiction: Array contains element ${element}.`);
        return false;
    }
}

// 使用例
const arr = [1, 2, 3];
const elementToCheck = 4;
console.log(proofByContradiction(arr, elementToCheck)); // true

数学的帰納法（Mathematical Induction）は、自然数に関する命題を証明する際によく用いられる方法です。この方法は「n = 1のとき成り立つ」「n = kのとき成り立つならば、n = k + 1でも成り立つ」という二つの条件を証明することで、全ての自然数に対して命題が成り立つことを示します。

例えば、1からnまでの自然数の和が (n(n+1))/2 であることを証明する際、n = 1 のとき成り立つことを示し、次に n = k で成り立つと仮定して n = k + 1 の場合も成り立つことを示すことで、すべての自然数 n に対して成り立つことが証明されます。

function fibonacci(n: number): number {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 帰納的にフィボナッチ数列のn番目の数を計算
const n = 5;
console.log(`Fibonacci(${n}) = ${fibonacci(n)}`); // Fibonacci(5) = 5

TypeScriptの型システムも、証明技術の一部をプログラム上で表現するのに役立ちます。型によって変数や関数の入力・出力の制約を定めることで、特定の条件が必ず満たされることを保証できます。例えば、負の数が含まれない配列を表現したい場合、カスタム型を使うことができます。

type PositiveNumber = number & { __positive: true };

function createPositiveNumber(n: number): PositiveNumber | null {
    if (n > 0) {
        return n as PositiveNumber;
    }
    return null;
}

function squarePositiveNumber(n: PositiveNumber): PositiveNumber {
    return (n * n) as PositiveNumber;
}

// 使用例
const positiveNum = createPositiveNumber(5);
if (positiveNum) {
    console.log(`Square of ${positiveNum} is ${squarePositiveNumber(positiveNum)}`);
} else {
    console.log("Provided number is not positive.");
}

証明の際には、仮定と結論を明確にすることが重要です。問題の設定や命題をしっかり理解し、証明のステップを具体化するために、まずは仮定となる事柄と導きたい結論を紙に書き出して整理しましょう。

証明には「必要条件」と「十分条件」の理解が不可欠です。例えば、「Aが成立するならばBが成立する」と証明する場合、Aが成立することがBにとって十分条件ですが、逆の「Bが成立するならばAが成立する」には証明が必要です。この区別を明確にし、どちらの方向で証明するのが適切かを考えることで、証明の手順がわかりやすくなります。

証明を理解する際には、具体的な例を用いると有効です。特に、証明のステップや論理構造が複雑な場合、具体的な数字や簡単なケースを例にして証明の流れを追うと理解が深まります。

証明技術は、単に数学的な正しさを示すだけでなく、論理的な思考能力や問題解決能力の向上にも役立ちます。プログラムの正しさを検証したり、データサイエンスや機械学習の理論的な裏付けを確認する際にも応用されます。また、証明技術を身につけることで、論理的な議論や推論が求められる他の分野でも活躍できるスキルを培うことができます。

証明技術は数学や論理学の基礎であり、直接証明や間接証明、帰納法などのさまざまな手法が存在します。これらの技術を理解し、適切に使いこなせるようになることは、論理的な思考力の強化に繋がり、幅広い分野で応用可能なスキルとなります。証明技術を学ぶことで、より深く論理的な理解が得られ、自分の考えを他者に明確に示す力も身につけることができるでしょう。