アルアカ - Arcadia Academia

論理（Logic）は、数学やコンピュータサイエンスの基礎であり、正確な推論や証明を行うための重要なツールです。特に命題論理と述語論理は、情報工学や離散数学において基本的な役割を果たします。この記事では、論理の基本概念とその応用について解説します。

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

GitHub - oga114/DiscreMath-TS

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

https://github.com

サンプルの実装は、DiscreMath-TSのsrc/predicateLogic/propositionalLogic.ts参照。

エンジニアにとってnotやandのような論理演算とTrueやFalseは馴染み深いものですが、なんとなく使ってしまっていることも多いと思います。私もそうでした。命題論理を学ぶことでより深く理解していきましょう！

命題論理は、真（True）か偽（False）のいずれかの値を持つ命題（Proposition）を扱う論理体系です。命題論理では、複雑な論理的命題を単純な命題の組み合わせとして表現し、論理演算を用いてそれらを操作します。

• 命題（Proposition）:

  真偽を持つ文や表現。例えば、「今日は晴れです」は真偽が明確に定まるため、命題として扱えますが、「今日は楽しい」は主観的なので命題にはなりません。

  真偽というと複雑に思えますが、正しいのか正しくないのかはっきりできることじゃないと命題として扱えないということです。

• 論理演算:

  複数の命題を組み合わせるために用いる演算子。主な論理演算には以下があります。

  • 否定（NOT, ¬）: 命題の真偽を反転させる。例: ¬A（Aが真なら偽、Aが偽なら真）
  • 論理積（AND, ∧）: 2つの命題が両方とも真である場合に真。例: A ∧ B
  • 論理和（OR, ∨）: どちらか一方、または両方が真であれば真。例: A ∨ B
  • 排他的論理和（XOR, ⊕）: どちらか一方が真の場合に真。例: A ⊕ B
  • 含意（IF-THEN, →）: Aが真ならばBも真である。例: A → B

論理演算は、複数の命題を組み合わせたり、命題の真偽を操作するために使われる演算です。以下に主な論理演算をTypeScriptで実装しながら解説します。

// 各種論理演算を定義する関数

// 否定（NOT）
function not(A: boolean): boolean {
  return !A;
}

// 論理積（AND）
function and(A: boolean, B: boolean): boolean {
  return A && B;
}

// 論理和（OR）
function or(A: boolean, B: boolean): boolean {
  return A || B;
}

// 排他的論理和（XOR）
function xor(A: boolean, B: boolean): boolean {
  return A !== B;
}

// 含意（IF-THEN, A → B）
function implies(A: boolean, B: boolean): boolean {
  return !A || B;
}

これらの関数を使って論理演算の基本的な動作を確認します。

const A = true;
const B = false;

console.log("NOT A:", not(A)); // false
console.log("A AND B:", and(A, B)); // false
console.log("A OR B:", or(A, B)); // true
console.log("A XOR B:", xor(A, B)); // true
console.log("A → B:", implies(A, B)); // false

• NOT: not(A)は、Aの真偽を反転させます。
• AND: and(A, B)は、AとBの両方が真であれば真になります。
• OR: or(A, B)は、AかBのどちらかが真であれば真になります。
• XOR: xor(A, B)は、AとBが異なる場合に真となります。
• IF-THEN (含意): implies(A, B)は、Aが真ならばBも真である、という条件を表します。

含意は他の論理演算に比べ、直観的に理解しにくいことがあります。A → Bの解釈は、「Aが成り立つならば、Bも成り立つ」という意味です。このため、Aが成り立たない（偽）場合は、Bがどうであっても含意全体は真とされます。

「もし雨が降ったら地面が濡れる」という命題A → Bを考えます。この命題が成り立つためには、雨（A）が降った場合にのみ、地面（B）が濡れている必要があります。しかし、雨が降らない場合（Aが偽）には、地面が濡れていようが乾いていようが、この命題は成立していると見なされます。

// 雨が降ったら地面が濡れる (A → B)
const rain = true; // 雨が降っている
const groundWet = false; // 地面が濡れていない

const statement = implies(rain, groundWet);
console.log("If it rains, the ground is wet:", statement); // false

上記では、rainがtrue（雨が降っている）でgroundWetがfalse（地面が濡れていない）ため、命題は偽になります。

「雨が降ったら地面が濡れる」の例を、rainがfalse（雨が降っていない）とした場合で確認します。

const rain2 = false; // 雨が降っていない
const groundWet2 = false; // 地面が濡れていない

const statement2 = implies(rain2, groundWet2);
console.log("If it rains, the ground is wet (rain is false):", statement2); // true

ここでは、rain2がfalse（雨が降っていない）ため、groundWet2がどうであっても命題全体はtrueと解釈されます。このように、A（条件）が偽の場合、含意全体は常に真となるのが含意の特徴です。

命題論理の基本的な推論は真理値表によって整理されます。真理値表は、命題やその組み合わせのすべての真偽の組み合わせと、それに対する結果の真偽を示した表です。これにより、論理式がどのような状況で真または偽になるかを確認できます。

否定（NOT, ¬）とは、命題の真偽を反転させる操作のことです。命題 AAA が「真（T）」であれば、その否定 ¬A¬A¬A は「偽（F）」となり、逆に AAA が「偽（F）」ならば、¬A¬A¬A は「真（T）」になります。

真偽表で表すと以下の通りです：

このように、否定記号（¬）は、命題の真偽を反転させる単純な論理操作です。

論理積（AND, ∧）は、2つの命題が両方とも真である場合にのみ真となる論理演算です。どちらか一方でも偽であれば、論理積 A∧BA ∧ BA∧B は偽となります。

真偽表で表すと以下のようになります：

このように、A と B の両方が真（T）の場合にのみ、A∧B が真（T）になります。

論理和（OR, ∨）は、どちらか一方、または両方が真であれば真となる論理演算です。AまたはBの少なくとも一方が真の場合、論理和 A∨BA ∨ BA∨B は真になります。

真偽表で表すと以下のようになります：

このように、AもBも両方とも偽（F）の場合のみ、A∨BA ∨ BA∨B は偽（F）となり、それ以外の場合は真（T）となります。

排他的論理和（XOR, ⊕）は、どちらか一方が真であり、かつ両方が同時に真ではない場合に真となる論理演算です。つまり、AとBが異なる真偽を持つときのみ、A⊕BA ⊕ BA⊕B が真になります。

真偽表で表すと以下のようになります：

このように、AとBの片方のみが真（T）の場合に限り、A⊕BA ⊕ BA⊕B が真（T）となります。両方が真または両方が偽の場合、A⊕BA ⊕ BA⊕B は偽（F）です。

含意 A→BA → BA→B の真偽表を「T（真）」と「F（偽）」で表すと以下のようになります。

// 命題論理の基本演算

// AND演算: 両方がtrueの場合にのみtrueを返す
function and(a: boolean, b: boolean): boolean {
  return a && b;
}

// OR演算: 少なくとも片方がtrueならtrueを返す
function or(a: boolean, b: boolean): boolean {
  return a || b;
}

// NOT演算: 入力がtrueならfalseを、falseならtrueを返す
function not(a: boolean): boolean {
  return !a;
}

// XOR演算（排他的論理和）: 異なる場合にtrueを返す
function xor(a: boolean, b: boolean): boolean {
  return a !== b;
}

// 含意演算 (A → B): AがtrueでBがfalseの場合にのみfalseを返す
function implies(a: boolean, b: boolean): boolean {
  return !a || b;
}

// サンプルの論理値
// AとBの値を変更して試してみましょう
const A = true;
const B = false;

// 論理式の例: (AかつB)または¬A
const result = or(and(A, B), not(A));

// 各演算の出力
console.log("AND (A, B):", and(A, B));
console.log("OR (A, B):", or(A, B));
console.log("NOT A:", not(A));
console.log("XOR (A, B):", xor(A, B));
console.log("A implies B:", implies(A, B));
console.log("(AかつB)または¬A:", result);

サンプルの実装は、DiscreMath-TSのsrc/predicateLogic/predicateLogic.ts参照。

述語論理は、命題論理を拡張したもので、変数や量化子（Quantifiers）を使って命題をより柔軟に表現するための方法です。述語論理により、特定の対象についての一般的な命題を表現し、複雑な条件や関係を扱うことができます。

以下のコード例では、述語や量化子の概念をTypeScriptで表現しています。

// 型定義
type Person = {
  name: string;
  isStudent: boolean;
};

// 述語（Predicate）
function isStudent(person: Person): boolean {
  return person.isStudent;
}

// サンプルデータ
const people: Person[] = [
  { name: "Alice", isStudent: true },
  { name: "Bob", isStudent: true },
  { name: "Charlie", isStudent: false }
];

• 述語（Predicate）:

  ここでisStudent関数が述語として機能します。この述語は、特定のPersonが「学生であるか」を判断し、その結果としてtrueかfalseを返します。述語は、特定の対象に対してその性質が成り立つかどうかを示す役割を持っています。

• 全称量化子（For all, ∀）と存在量化子（There exists, ∃）:

  以下のコードでは、forAllとexists関数が全称量化子と存在量化子の役割を果たします。

// 全称量化子（For all）
function forAll<T>(array: T[], predicate: (item: T) => boolean): boolean {
  return array.every(predicate);
}

// 存在量化子（There exists）
function exists<T>(array: T[], predicate: (item: T) => boolean): boolean {
  return array.some(predicate);
}

// 使用例
const allAreStudents = forAll(people, isStudent); // 全員が学生か
const someAreStudents = exists(people, isStudent); // 1人でも学生がいるか

console.log("All are students:", allAreStudents); // false
console.log("There exists a student:", someAreStudents); // true

1. 全称量化子の例

   forAll関数は、配列のすべての要素に対してisStudent述語が成り立つかをチェックしています。上の例では、「全員が学生か」を判定し、falseを返します。つまり、全てのPersonが学生であるわけではないことを示しています。

2. 存在量化子の例

   exists関数は、配列の少なくとも1つの要素に対してisStudent述語が成り立つかを判定しています。ここでは「1人でも学生がいるか」をチェックし、trueを返します。つまり、少なくとも1人は学生であることを示しています。

このように述語論理を使うと、ある条件が「すべての対象に成り立つのか」や「少なくとも1つの対象に成り立つのか」といった命題を簡単に表現できます。述語論理はデータベースクエリ、プログラム検証、論理証明など、特定の条件が成り立つかを確認する様々な場面で役立ちます。

論理の推論においては、推論規則が使われます。これにより、いくつかの既知の命題から新しい命題を導き出すことが可能です。代表的な推論規則には、以下のようなものがあります。

• Modus Ponens（肯定的推論）:

  「Aが真で、A → Bが真であれば、Bも真である」という推論。

  例: 「雨が降れば道が濡れる」という含意が真で、実際に雨が降っているならば、道が濡れていると推論できます。

• Modus Tollens（否定的推論）:

  「A → Bが真で、Bが偽であれば、Aも偽である」という推論。

  例: 「雨が降れば道が濡れる」という含意が真で、道が濡れていないならば、雨は降っていないと推論できます。

命題論理や述語論理は、プログラムの正しさを証明する形式的検証や、デジタル回路設計、データベースクエリ、人工知能など、情報工学の多くの分野で応用されています。特に、コンピュータプログラムにおける条件分岐やループ、制約の論理的な表現に役立ちます。

論理（Logic）は、命題論理と述語論理に分かれ、情報工学や離散数学の基礎概念を構成しています。これらを学ぶことで、プログラムの設計や証明、デジタル回路、データベース操作などの分野で、論理的な思考を応用できるようになります。