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

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

本記事では，真理関数(真理表)から論理式を決定する方法について解説します．

真理関数から論理式を決定する方法

二つの原子式からなる命題\(X\)の真理関数(真理表)から\(X\)の論理式を決定する方法を考えます．

例として，下記の真理表で表される論理式\(X\)を考えます．

\(A\)	\(B\)	\(X\)
1	1	1
1	0	1
0	1	0
0	0	1

\(X\)は\(A\)と\(B\)が共に真のとき真ですので，\(A \land B\)を含みます．

\(X\)は\(A\)が真，\(B\)が偽のとき真ですので，\(A \land \lnot B\)を含みます．

\(X\)は\(A\)と\(B\)が共に偽のとき真ですので，\(\lnot A \land \lnot B\)を含みます．

以上より，\(X \Leftrightarrow (A \land B) \lor (A \land \lnot B) \lor (\lnot A \land \lnot B)\)となります．

あとは上式を簡単にします．

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

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

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

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

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

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

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

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

\(\Leftrightarrow B \Rightarrow A\)

以上の同値変形で，分配律・消去律・排中律・トートロジーの性質を利用しています．

二つの原子命題の結合で表される分子命題の真理関数

例えば，下記の真理関数を\(1101\)と書くことにします．

\(A\)	\(B\)	\(X\)
1	1	1
1	0	1
0	1	0
0	0	1

二つの原子命題の結合で表される分子命題の真理関数は，\(0\)か\(1\)の四つの並びですので，\(2^4=16\)通りとなります．

試みにすべて求めてみますと，下記の表の通りになります．

\(1111 \dots \top\)	\(1110 \dots A \lor B\)	\(1101 \dots B \Rightarrow A\)	\(1100 \dots A\)
\(1011 \dots A \Rightarrow B\)	\(1010 \dots B\)	\(1001 \dots A \Leftrightarrow B\)	\(1000 \dots A \land B\)
\(0111 \dots \lnot A \lor \lnot B\)	\(0110 \dots A \Leftrightarrow \lnot B\)	\(0101 \dots \lnot B\)	\(0100 \dots A \land \lnot B\)
\(0011 \dots \lnot A\)	\(0010 \dots \lnot A \land B\)	\(0001 \dots \lnot A \land \lnot B\)	\(0000 \dots \bot\)

二つの原子命題からなる分子命題は，どんなに複雑なものでも，変形して必ず上記の\(16\)通りの論理式に直せるわけですね．

しかも，例えば\(0111\)の命題\(\lnot A \lor \lnot B\)は，全体を否定すると\(0\)と\(1\)が反転しますので，\(1000\)の命題\(A \land B\)と同値になります．

ということは，とりあえず \(1111\)から\(1000\)を覚えておけばOKということですね．

すると，命題は\(\top, A \lor B, B \Rightarrow A, A, A \Rightarrow B, B, A \Leftrightarrow B, A \land B\)となり，これまでみてきた基本的な結合子でことたりる，というわけです．

それ以外は，上記の命題に否定\(\lnot\)を作用させれば得られます．

参考文献

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

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

野矢茂樹著，『論理学』

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

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

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

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

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

シェファーの棒記号【形式論理学8】

論理学を学ぶ記事です． 本記事では，シェファーの棒記号について説明します． シェファーの棒記号 下記の論理式\(X\)を考えます． \(A\)\(B\)\(X\)110101011001 この論理式を\(X \Leftrightarrow ...

efcharistoblog.com

2023.02.19