トートロジー【形式論理学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時点) 楽天で購入

真理関数から論理式を決定すること【形式論理学7】

数学の学び直しのための記事です． 本記事では，真理関数(真理表)から論理式を決定する方法について解説します． 真理関数から論理式を決定する方法 二つの原子式からなる命題\(X\)の真理関数(真理表)から\(X\)の論理式を決定する方法を考え...

efcharistoblog.com

2023.02.13