【離散数学とグラフ】命題論理
アウトプット
以下の式を真理値表で書く。
これが解けるようになるのがこの記事の目標。答えは最後に記載。
命題論理とは
chatGPTに生成してもらった。
命題論理（propositional logic）は、離散数学の一部であり、数学的な論理推論や問題解決に使用される基本的な論理体系の一つです。命題論理は、命題（proposition）や文（sentence）を扱い、それらの命題が真（true）または偽（false）であるかどうかを検討します。以下に、命題論理の基本的な要素と概念について説明します。
命題（Proposition）: 命題は真または偽である文です。具体的な命題は、特定の文脈での真偽が明確に定義されている文です。例えば、以下のような命題があります。
「太陽は東から昇ります。」（真の命題）
「2は奇数です。」（偽の命題）
論理演算子（Logical Operators）: 命題論理では、命題を組み合わせるための論理演算子が使用されます。主な論理演算子には以下のものがあります。
論理積（AND）: 命題Aと命題Bが両方とも真である場合、A AND B も真です。
論理和（OR）: 命題Aと命題Bの少なくとも一方が真である場合、A OR B も真です。
否定（NOT）: 命題Aが偽であれば、NOT A は真であり、命題Aが真であれば、NOT A は偽です。
論理式（Logical Formula）: 論理演算子を使って命題を組み合わせることで、複雑な論理式を構築できます。論理式は命題を基本要素とし、真偽値を持つ式です。例えば、次のような論理式があります。
A∧(B∨C)
¬D
真理値表（Truth Table）: 真理値表は、論理式の各命題の組み合わせに対する結果（真または偽）を示す表です。真理値表を使用して、論理式の真偽を評価できます。
論理的帰結（Logical Inference）: 命題論理は、論理的な帰結を導くために使用されます。与えられた前提条件と論理式を使って、特定の命題が真であるか偽であるかを決定することができます。
論理的等価性（Logical Equivalence）: 2つの論理式が同じ真理値を持つ場合、それらは論理的に等価であると言います。論理的等価性は、論理式を簡略化するために使用されます。
改めて命題論理とは
命題論理とは、主張(statement)が正しいか正しくないかを調べるものです。
真理値表
以下のようなtrueとfalse(もしくはtrueを1に、falseを0に置き換える)で表したテーブルを真理値表と言います。
| P | Q | P AND Q | P OR Q | P => Q | P <=> Q |
|---|---|---|---|---|---|
| F | F | F | F | T | T |
| F | T | F | T | T | F |
| T | F | F | T | F | F |
| T | T | T | T | T | T |
ANDとORはわかりやすいですよね。PとQがどっちもFだったら、ANDはFでORはFです。含意(PならばQ、PはQの必要条件、QはPの十分条件)は、PがFでQがFの時、Pが偽なのでQの真偽にかかわらず真です。同値に関してはPがFでQがFなら同値なので全体の命題はTです。
真理値表はこのような関係性を表しています。
P=>QのPが偽ならP=>Qの命題は真
筆者はこの部分で頭が混乱しました。「なぜP=>Qの命題で前提Pが偽なら、Qの真偽関係なしにP=>Qと言えるのか？」と。
わかりやすい記事が以下に書かれています。
答えとしては、Pが偽と考えると以下の同値が成り立つために、Pが偽だったら自動的にP=>Qは真になってしまうというものでした。(Pの否定orQなので、Pの否定がtrueでQの真偽は関係ない)
最初の問題を解いてみる
以下の式を真理値表で書け。
m: x => y ∨ z とします。
n: y ∧ z => x とします。
| x | y | z | y OR Z | x => y OR z | y AND z | y AND z => x | m ∨ n |
|---|---|---|---|---|---|---|---|
| F | F | F | F | T | F | T | T |
| F | F | T | T | T | F | T | T |
| F | T | F | T | T | F | T | T |
| F | T | T | T | T | T | F | T |
| T | F | F | F | F | F | T | T |
| T | F | T | T | T | F | T | T |
| T | T | F | T | T | F | T | T |
| T | T | T | T | T | T | T | T |
上記真理値ひょうの m ∨ nに注目すると、答えが全部T(0と1で考えると1)になっています。こういう時にa:m ∨ nとすると、aはtautology(命題全てがtrueになるもの)であると言います。
tautologyを表すには|=という記号を使って表せます。
参考文献
Discussion