トートロジー【形式論理学6】

数学の学び直しのための記事です．

本記事では，トートロジーについて考察します．

トートロジー
トートロジー・恒偽命題と原子命題の結合
トートロジーと恒偽命題を用いた論理式の変形
参考文献

トートロジー

トートロジーとは，原子命題の真偽に関わらず，真理値が\(1\)となる命題です．

恒真命題ともいい，命題記号として\(\top\)を用います．

トートロジーは恒に真ですので，法則とみなせます．

以下に主なトートロジーを紹介します．

➀　\(A \Rightarrow A\)　(同一律)

➁　\(A \Leftrightarrow A\)　(同一律)

➂　\(A \land A \Leftrightarrow A\)　(冪等律)

④　\(A \lor A \Leftrightarrow A\)　(冪等律)

⑤　\(\lnot \lnot A \Leftrightarrow A\)　(二重否定)

⑥　\(A \Rightarrow B \Leftrightarrow \lnot B \Rightarrow \lnot A\)　(対偶)

⑦　\(A \land B \Leftrightarrow B \land A\)　(交換律)

⑧　\(A \lor B \Leftrightarrow B \lor A\)　(交換律)

⑨　\((A \land B) \land C \Leftrightarrow A \land (B \land C)\)　(結合律)

⑩　\((A \lor B) \lor C \Leftrightarrow A \lor (B \lor C)\)　(結合律)

⑪　\(A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)\)　(分配律)

⑫　\(A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)\)　(分配律)

⑬　\(A \land (A \lor B) \Leftrightarrow A\)　(消去律)

⑭　\(A \lor (A \land B) \Leftrightarrow A\)　(消去律)

⑮　\(\lnot (A \land \lnot A)\)　(矛盾律)

⑯　\(A \lor \lnot A\)　(排中律)

⑰　\(\lnot (A \land B) \Leftrightarrow \lnot A \lor \lnot B\)　(ド・モルガンの法則)

⑱　\(\lnot (A \lor B) \Leftrightarrow \lnot A \land \lnot B\)　(ド・モルガンの法則)

⑲　\(A \Rightarrow B \Leftrightarrow \lnot A \lor B\)　(条件法)

⑳　\(A \Rightarrow B \Leftrightarrow \lnot (A \land \lnot B)\)　(条件法)

㉑　\(\lnot (A \Rightarrow B) \Leftrightarrow A \land \lnot B\)

㉒　\(A \land B \Leftrightarrow \lnot (\lnot A \lor \lnot B)\)

㉓　\(A \lor B \Leftrightarrow \lnot (\lnot A \land \lnot B)\)

㉔　\(A \land B \Leftrightarrow \lnot (A \Rightarrow \lnot B)\)

㉕　\(A \lor B \Leftrightarrow \lnot A \Rightarrow B\)

㉖　\((A \Leftrightarrow B) \Leftrightarrow (A \Rightarrow B) \land (B \Rightarrow A)\)　(同値の定義)

㉗　\((A \Rightarrow B) \land A \Rightarrow B\)　(前件肯定式)

㉘　\((A \Rightarrow B) \land \lnot B \Rightarrow \lnot A\)　(後件否定式)

㉙　\((A \Rightarrow B) \land (B \Rightarrow C) \Rightarrow (A \Rightarrow C)\)　(推移律)

原子命題の真偽に関わらず，真理値が\(0\)になる命題を恒偽命題といいます．

恒偽命題の記号として\(\bot\)を用います．

例えば，\(A \land \lnot A\)は恒偽命題です．

トートロジーを否定したものは恒偽命題になります．

トートロジー・恒偽命題と原子命題の結合

トートロジーと一般の原子命題の結合について考察してみましょう．

\(\top \land A\)はどうなるでしょうか？

真理表を用いて考えます．

\(\top\)	\(A\)	\(\top \land A\)
1	1	1
1	0	0

つまり，\(\top \land A \Leftrightarrow A\)となります．

同様にして，

\(\top \lor A \Leftrightarrow \top\)

\(\top \Rightarrow A \Leftrightarrow A\)

\(A \Rightarrow \top \Leftrightarrow \top\)

となります．

恒偽命題\(\bot\)については，

\(\bot \land A \Leftrightarrow \bot\)

\(\bot \lor A \Leftrightarrow A\)

\(\bot \Rightarrow A \Leftrightarrow \top\)

\(A \Rightarrow \bot \Leftrightarrow \lnot A\)

となります．

ただし，\(\bot \Rightarrow A\)は無内容であるため，\(\bot\)が条件節となることは避けるべきと考えます．

トートロジーと恒偽命題を用いた論理式の変形

以上のトートロジーや恒偽命題を利用して，複雑な論理式を簡単にしてみましょう．

例1　\((A \Rightarrow \lnot B) \land A\)

方針としては，条件法を連言や選言に置き換えると考えやすいです．

また，上式で\(A\)同士を作用させることになると予想すると，上式はより簡単になるだろうと考えられます．

\(P \Rightarrow Q \Leftrightarrow \lnot P \lor Q\)を利用します．

\((A \Rightarrow \lnot B) \land A\)

\(\Leftrightarrow (\lnot A \lor \lnot B) \land A\)

ここでは分配法則\((P \lor Q) \land R \Leftrightarrow (P \land R) \lor (Q \land R)\)を用いることができます．

\((\lnot A \lor \lnot B) \land A \Leftrightarrow (\lnot A \land A) \lor (\lnot B \land A)\)

\(\lnot P \land P \Leftrightarrow \bot\)であり(矛盾律)，\(\bot \lor Q \Leftrightarrow Q\)を用いることができます．

\((\lnot A \land A) \lor (\lnot B \land A)\)

\(\Leftrightarrow \bot \lor (\lnot B \land A)\)

\(\Leftrightarrow \lnot B \land A\)

つまり，\((A \Rightarrow \lnot B) \land A \Leftrightarrow \lnot B \land A\)となります．

例2　\((A \Rightarrow B) \Rightarrow (A \land B)\)

この場合も，条件法を選言に置き換えるパターンで行きましょう．

\((A \Rightarrow B) \Rightarrow (A \land B)\)

\(\Leftrightarrow (\lnot A \lor B) \Rightarrow (A \land B)\)

\(\Leftrightarrow \lnot (\lnot A \lor B) \lor (A \land B)\)

\(\lnot\)を括弧の中に作用させる場合には，ド・モルガンの法則\(\lnot(P \lor Q) \Leftrightarrow (\lnot P \land \lnot Q)\)を利用します．

\( \lnot (\lnot A \lor B) \lor (A \land B)\)

\(\Leftrightarrow (A \land \lnot B) \lor (A \land B)\)

ここでは，分配法則\((P \land Q) \lor R \Leftrightarrow (P \lor R) \land (Q \lor R)\)を利用します．

\( (A \land \lnot B) \lor (A \land B)\)

\(\Leftrightarrow (A \lor (A \land B)) \land (\lnot B \lor (A \land B)) \)

前半部では消去律\(P \lor (P \land Q) \Leftrightarrow P\)が使えます．

後半部は分配法則です．

\( (A \lor (A \land B)) \land (\lnot B \lor (A \land B)) \)

\(\Leftrightarrow A \land ((\lnot B \lor A) \land (\lnot B \lor B))\)

ここで，\(\lnot P \lor P \Leftrightarrow \top\)でした(排中律)．

また，\(Q \land \top \Leftrightarrow Q\)も利用します．

\( A \land ((\lnot B \lor A) \land (\lnot B \lor B))\)

\(\Leftrightarrow A \land ((\lnot B \lor A) \land \top)\)

\(\Leftrightarrow A \land (\lnot B \lor A)\)

\(\Leftrightarrow A\)

最後に消去律を利用しました．

このように，トートロジーや恒偽命題を利用して論理式を簡単にできる場合があります．

参考文献

形式論理学に関する参考文献を以下に挙げます．

アフィリエイト広告です．

野矢茂樹著，『論理学』

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

論理学 [ 野矢茂樹 ]
価格：2860円（税込、送料無料) (2023/2/3時点)

楽天で購入

長岡亮介著，『論理学で学ぶ数学』

総合的研究論理学で学ぶ数学ーー思考ツールとしてのロジック【電子書籍】[ 長岡亮介 ]
価格：2024円 (2023/2/3時点)

楽天で購入

赤攝也著，『現代数学概論』

現代数学概論【電子書籍】[ 赤攝也 ]
価格：1320円 (2023/2/3時点)

楽天で購入