論理演算の基本

by nomura · 2022年11月14日

論理和と論理積の演算の基本
\(P,Q,R\)を命題変数とする。

結合律

(1)

\[ P\lor\left(Q\lor R\right)\Leftrightarrow\left(P\lor Q\right)\lor R \]

(2)

\[ P\land\left(Q\land R\right)\Leftrightarrow\left(P\land Q\right)\land R \]
交換律

(3)

\[ P\lor Q\Leftrightarrow Q\lor P \]

(4)

\[ P\land Q\Leftrightarrow Q\land P \]
冪等律

(5)

\[ P\lor P\Leftrightarrow P \]

(6)

\[ P\land P\Leftrightarrow P \]
二重否定(反射律)

(7)

\[ \lnot\lnot P\Leftrightarrow P \]
吸収律

(8)

\[ P\lor\left(P\land Q\right)\Leftrightarrow P \]

(9)

\[ P\land\left(P\lor Q\right)\Leftrightarrow P \]
吸収律の片方が否定形

(10)

\[ P\lor\left(\lnot P\land Q\right)\Leftrightarrow P\lor Q \]

(11)

\[ P\land\left(\lnot P\lor Q\right)\Leftrightarrow P\land Q \]
分配律

(12)

\[ P\land\left(Q\lor R\right)\Leftrightarrow\left(P\land Q\right)\lor\left(P\land R\right) \]

(13)

\[ P\lor\left(Q\land R\right)\Leftrightarrow\left(P\lor Q\right)\land\left(P\lor R\right) \]
ド・モルガンの法則

(14)論理和の否定

\[ \lnot\left(P\lor Q\right)\Leftrightarrow\lnot P\land\lnot Q \]

(15)論理積の否定

\[ \lnot\left(P\land Q\right)\Leftrightarrow\lnot P\lor\lnot Q \]
否定

(16)

\[ \lnot0\Leftrightarrow1 \]

(17)

\[ \lnot1\Leftrightarrow0 \]
零元

(18)偶然式

\[ P\lor0\Leftrightarrow P \]

(19)恒偽式

\[ P\land0\Leftrightarrow0 \]
単位元

(20)恒真式

\[ P\lor1\Leftrightarrow1 \]

(21)偶然式

\[ P\land1\Leftrightarrow P \]
相補律

(22)同一律

\[ P\Leftrightarrow P \]

(23)排中律

\[ P\lor\lnot P\Leftrightarrow1 \]

(24)矛盾律

\[ P\land\lnot P\Leftrightarrow0 \]

-

論理式は恒真式・恒偽式・偶然式の3つに分けられる。
恒真式は常に真となる論理式。
恒偽式は常に偽となる論理式。
偶然式は真にも偽にもなる論理式。
偶然式は事実式や整合式ともいう。

-

相補律は同一律・排中律・矛盾律の3つからなる。
同一律は\(P\)は\(P\)であるという法則である。
排中律は\(P\)または\(\lnot P\)は必ず真になるという法則である。
矛盾律は\(P\)と\(\lnot P\)が同時に真になることはないという法則である。

(1)

\begin{align*} P\lor\left(Q\lor R\right) & \Leftrightarrow\begin{cases} Q\lor R & P\leftrightarrow\bot\\ \top & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow\begin{cases} \left(P\lor Q\right)\lor R & P\leftrightarrow\bot\\ \left(P\lor Q\right)\lor R & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow\left(P\lor Q\right)\lor R \end{align*}

(2)

\begin{align*} P\land\left(Q\land R\right) & \Leftrightarrow\lnot\lnot\left(P\land\left(Q\land R\right)\right)\\ & \Leftrightarrow\lnot\left(\lnot P\lor\left(\lnot Q\lor\lnot R\right)\right)\\ & \Leftrightarrow\lnot\left(\left(\lnot P\lor\lnot Q\right)\lor\lnot R\right)\\ & \Leftrightarrow\left(P\land Q\right)\land R \end{align*}

(2)-2

\begin{align*} P\land\left(Q\land R\right) & \Leftrightarrow\begin{cases} \bot & P\leftrightarrow\bot\\ Q\lor R & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow\begin{cases} \left(P\land Q\right)\land R & P\leftrightarrow\bot\\ \left(P\land Q\right)\land R & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow\left(P\land Q\right)\land R \end{align*}

(3)

\begin{align*} P\lor Q & \Leftrightarrow\begin{cases} 0 & \left(P\leftrightarrow0\right)\land\left(Q\leftrightarrow0\right)\\ 1 & \left(P\leftrightarrow1\right)\lor\left(Q\leftrightarrow1\right) \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \left(Q\leftrightarrow0\right)\land\left(P\leftrightarrow0\right)\\ 1 & \left(Q\leftrightarrow1\right)\lor\left(P\leftrightarrow1\right) \end{cases}\\ & \Leftrightarrow Q\lor P \end{align*}

(4)

\begin{align*} P\land Q & \Leftrightarrow\begin{cases} 0 & \left(P\leftrightarrow0\right)\lor\left(Q\leftrightarrow0\right)\\ 1 & \left(P\leftrightarrow1\right)\land\left(Q\leftrightarrow1\right) \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \left(Q\leftrightarrow0\right)\lor\left(P\leftrightarrow0\right)\\ 1 & \left(Q\leftrightarrow1\right)\land\left(P\leftrightarrow1\right) \end{cases}\\ & \Leftrightarrow Q\land P \end{align*}

(5)

\begin{align*} P\lor P & \Leftrightarrow\begin{cases} 0\lor0 & P\leftrightarrow0\\ 1\lor1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 1 & P \end{cases}\\ & \Leftrightarrow P \end{align*}

(6)

\begin{align*} P\land P & \Leftrightarrow\begin{cases} 0\land0 & P\leftrightarrow0\\ 1\land1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 1 & P \end{cases}\\ & \Leftrightarrow P \end{align*}

(7)

\begin{align*} \lnot\lnot P & \Leftrightarrow\begin{cases} \lnot\lnot0 & P\leftrightarrow0\\ \lnot\lnot1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 1 & P \end{cases}\\ & \Leftrightarrow P \end{align*}

(8)

\begin{align*} P\lor\left(P\land Q\right) & \Leftrightarrow\begin{cases} P & Q\leftrightarrow\bot\\ P & Q\leftrightarrow\top \end{cases}\\ & \Leftrightarrow P \end{align*}

(9)

\begin{align*} P\land\left(P\lor Q\right) & \Leftrightarrow\begin{cases} P & Q\leftrightarrow\bot\\ P & Q\leftrightarrow\top \end{cases}\\ & \Leftrightarrow P \end{align*}

(10)

\begin{align*} P\lor\left(\lnot P\land Q\right) & \Leftrightarrow\left(P\lor\lnot P\right)\land\left(P\lor Q\right)\\ & \Leftrightarrow P\lor Q \end{align*}

(11)

\begin{align*} P\land\left(\lnot P\lor Q\right) & \Leftrightarrow\left(P\land\lnot P\right)\lor\left(P\land Q\right)\\ & \Leftrightarrow P\land Q \end{align*}

(12)

\begin{align*} P\land\left(Q\lor R\right) & \Leftrightarrow\begin{cases} \bot & P\leftrightarrow\bot\\ Q\lor R & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow\begin{cases} \left(P\land Q\right)\lor\left(P\land R\right) & P\leftrightarrow\bot\\ \left(P\land Q\right)\lor\left(P\land R\right) & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow(P\land Q)\lor(P\land R) \end{align*}

(13)

\begin{align*} P\lor\left(Q\land R\right) & \Leftrightarrow\lnot\lnot\left(P\lor\left(Q\land R\right)\right)\\ & \Leftrightarrow\lnot\left(\lnot P\land\left(\lnot Q\lor\lnot R\right)\right)\\ & \Leftrightarrow\lnot\left(\left(\lnot P\land\lnot Q\right)\lor\left(\lnot P\land\lnot R\right)\right)\\ & \Leftrightarrow\left(P\lor Q\right)\land\left(P\lor R\right) \end{align*}

(13)-2

\begin{align*} P\lor\left(Q\land R\right) & \Leftrightarrow\begin{cases} Q\land R & P\leftrightarrow\bot\\ \top & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow\begin{cases} \left(P\lor Q\right)\land\left(P\lor R\right) & P\leftrightarrow\bot\\ \left(P\lor Q\right)\land\left(P\lor R\right) & P\leftrightarrow\top \end{cases}\\ & \Leftrightarrow(P\lor Q)\land(P\lor R) \end{align*}

(14)

\begin{align*} \lnot\left(P\lor Q\right) & \Leftrightarrow\begin{cases} 1 & P\leftrightarrow0\land Q\leftrightarrow0\\ 0 & P\nleftrightarrow0\lor Q\nleftrightarrow0 \end{cases}\\ & \Leftrightarrow\begin{cases} 1 & \lnot P\land\lnot Q\\ 0 & \lnot\left(\lnot P\land\lnot Q\right) \end{cases}\\ & \Leftrightarrow\lnot P\land\lnot Q \end{align*}

(14)-2

\(\lnot\left(P\lor Q\right)\)は「\(P,Q\)のうち、どちらかが真のとき真、両方偽のとき偽」の否定である。
これは「\(P,Q\)のうち、どちらかが真のとき偽、両方偽のとき真」と同じであり、「\(\lnot P,\lnot Q\)のうち、どちらかが偽のとき偽、両方真のとき真」となる。
すなわち、\(\lnot P\land\lnot Q\)となる。

(15)

\begin{align*} \lnot\left(P\land Q\right) & \Leftrightarrow\lnot\left(\lnot\left(\lnot P\right)\land\lnot\left(\lnot Q\right)\right)\\ & \Leftrightarrow\lnot\lnot\left(\left(\lnot P\right)\lor\left(\lnot Q\right)\right)\\ & \Leftrightarrow\lnot P\lor\lnot Q \end{align*}

(15)-2

\(\lnot\left(P\land Q\right)\)は「\(P,Q\)のうち、両方真のとき真、どちらかが偽のとき偽」の否定である。
これは「\(P,Q\)のうち、両方真のとき偽、どちらかが偽のとき真」と同じであり、「\(\lnot P,\lnot Q\)のうち、両方偽のとき偽、どちらかが真のとき真」となる。
すなわち、\(\lnot P\lor\lnot Q\)となる。

(16)

明らかである。

(17)

明らかである。

(18)

\begin{align*} P\lor0 & \Leftrightarrow\begin{cases} 0 & P\leftrightarrow0\\ 1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 1 & P \end{cases}\\ & \Leftrightarrow P \end{align*}

(19)

\begin{align*} P\land0 & \Leftrightarrow\begin{cases} 0 & P\leftrightarrow0\\ 0 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 0 & P \end{cases}\\ & \Leftrightarrow0 \end{align*}

(20)

\begin{align*} P\lor1 & \Leftrightarrow\begin{cases} 1 & P\leftrightarrow0\\ 1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 1 & \lnot P\\ 1 & P \end{cases}\\ & \Leftrightarrow1 \end{align*}

(21)

\begin{align*} P\land1 & \Leftrightarrow\begin{cases} 0 & P\leftrightarrow0\\ 1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 1 & P \end{cases}\\ & \Leftrightarrow P \end{align*}

(22)

明らかである。

(23)

\begin{align*} P\lor\lnot P & \Leftrightarrow\begin{cases} 0\lor\lnot0 & P\leftrightarrow0\\ 1\lor\lnot1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0\lor1 & \lnot P\\ 1\lor0 & P \end{cases}\\ & \Leftrightarrow\begin{cases} 1 & \lnot P\\ 0 & P \end{cases}\\ & \Leftrightarrow1 \end{align*}

(24)

\begin{align*} P\land\lnot P & \Leftrightarrow\begin{cases} 0\land\lnot0 & P\leftrightarrow0\\ 1\land\lnot1 & P\leftrightarrow1 \end{cases}\\ & \Leftrightarrow\begin{cases} 0\land1 & \lnot P\\ 1\land0 & P \end{cases}\\ & \Leftrightarrow\begin{cases} 0 & \lnot P\\ 0 & P \end{cases}\\ & \Leftrightarrow0 \end{align*}

否定論理和・否定論理積・包含・否定包含・同値・否定同値の基本
\(P,Q\)を命題変数とする。

否定論理和の基本

(1)偶然式

\[ 0\downarrow P\Leftrightarrow\lnot P \]

(2)恒偽式

\[ 1\downarrow P\Leftrightarrow0 \]

(3)偶然式

\[ P\downarrow0\Leftrightarrow\lnot P \]

(4)恒偽式

\[ P\downarrow1\Leftrightarrow0 \]

(5)偶然式

\[ P\downarrow P\Leftrightarrow\lnot P \]

(6)恒偽式

\[ P\downarrow\lnot P\Leftrightarrow0 \]
否定論理積の基本

(7)恒真式

\[ 0\uparrow P\Leftrightarrow1 \]

(8)偶然式

\[ 1\uparrow P\Leftrightarrow\lnot P \]

(9)恒真式

\[ P\uparrow0\Leftrightarrow1 \]

(10)偶然式

\[ P\uparrow1\Leftrightarrow\lnot P \]

(11)偶然式

\[ P\uparrow P\Leftrightarrow\lnot P \]

(12)恒真式

\[ P\uparrow\lnot P\Leftrightarrow1 \]
包含の基本

(13)恒真式

\[ 0\rightarrow P\Leftrightarrow1 \]

(14)偶然式

\[ 1\rightarrow P\Leftrightarrow P \]

(15)偶然式

\[ P\rightarrow0\Leftrightarrow\lnot P \]

(16)恒真式

\[ P\rightarrow1\Leftrightarrow1 \]

(17)恒真式

\[ P\rightarrow P\Leftrightarrow1 \]

(18)偶然式

\[ P\rightarrow\lnot P\Leftrightarrow\lnot P \]
否定包含の基本

(19)恒偽式

\[ 0\nrightarrow P\Leftrightarrow0 \]

(20)偶然式

\[ 1\nrightarrow P\Leftrightarrow\lnot P \]

(21)偶然式

\[ P\nrightarrow0\Leftrightarrow P \]

(22)恒偽式

\[ P\nrightarrow1\Leftrightarrow0 \]

(23)恒偽式

\[ P\nrightarrow P\Leftrightarrow0 \]

(24)偶然式

\[ P\nrightarrow\lnot P\Leftrightarrow P \]
同値の基本

(25)偶然式

\[ P\leftrightarrow0\Leftrightarrow\lnot P \]

(26)偶然式

\[ P\leftrightarrow1\Leftrightarrow P \]

(27)恒真式

\[ P\leftrightarrow P\Leftrightarrow1 \]

(28)恒偽式

\[ P\leftrightarrow\lnot P\Leftrightarrow0 \]
否定同値の基本

(29)偶然式

\[ P\nleftrightarrow0\Leftrightarrow P \]

(30)偶然式

\[ P\nleftrightarrow1\Leftrightarrow\lnot P \]

(31)恒偽式

\[ P\nleftrightarrow P\Leftrightarrow0 \]

(32)恒真式

\[ P\nleftrightarrow\lnot P\Leftrightarrow1 \]

(1)

\begin{align*} 0\downarrow P & \Leftrightarrow\lnot0\land\lnot p\\ & \Leftrightarrow1\land\lnot p\\ & \Leftrightarrow\lnot P \end{align*}

(2)

\begin{align*} 1\downarrow P & \Leftrightarrow\lnot1\land\lnot P\\ & \Leftrightarrow0\land\lnot P\\ & \Leftrightarrow0 \end{align*}

(3)

\begin{align*} P\downarrow0 & \Leftrightarrow\lnot P\land\lnot0\\ & \Leftrightarrow\lnot P\land1\\ & \Leftrightarrow\lnot P \end{align*}

(4)

\begin{align*} P\downarrow1 & \Leftrightarrow\lnot P\land\lnot1\\ & \Leftrightarrow\lnot P\land0\\ & \Leftrightarrow0 \end{align*}

(5)

\begin{align*} P\downarrow P & \Leftrightarrow\lnot P\land\lnot P\\ & \Leftrightarrow\lnot P \end{align*}

(6)

\begin{align*} P\downarrow\lnot P & \Leftrightarrow\lnot P\land P\\ & \Leftrightarrow0 \end{align*}

(7)

\begin{align*} 0\uparrow P & \Leftrightarrow\lnot0\lor\lnot P\\ & \Leftrightarrow1\lor\lnot P\\ & \Leftrightarrow1 \end{align*}

(8)

\begin{align*} 1\uparrow P & \Leftrightarrow\lnot1\lor\lnot P\\ & \Leftrightarrow0\lor\lnot P\\ & \Leftrightarrow\lnot P \end{align*}

(9)

\begin{align*} P\uparrow0 & \Leftrightarrow\lnot P\lor\lnot0\\ & \Leftrightarrow\lnot P\lor1\\ & \Leftrightarrow1 \end{align*}

(10)

\begin{align*} P\uparrow1 & \Leftrightarrow\lnot P\lor\lnot1\\ & \Leftrightarrow\lnot P\lor0\\ & \Leftrightarrow\lnot P \end{align*}

(11)

\begin{align*} P & \uparrow P\Leftrightarrow\lnot P\lor\lnot P\\ & \Leftrightarrow\lnot P \end{align*}

(12)

\begin{align*} P\uparrow\lnot P & \Leftrightarrow\lnot P\lor P\\ & \Leftrightarrow1 \end{align*}

(13)

\begin{align*} 0\rightarrow P & \Leftrightarrow\lnot0\lor P\\ & \Leftrightarrow1\lor P\\ & \Leftrightarrow1 \end{align*}

(14)

\begin{align*} 1\rightarrow P & \Leftrightarrow\lnot1\lor P\\ & \Leftrightarrow0\lor P\\ & \Leftrightarrow P \end{align*}

(15)

\begin{align*} P\rightarrow\bot & \Leftrightarrow\lnot P\lor0\\ & \Leftrightarrow\lnot P \end{align*}

(16)

\begin{align*} P\rightarrow\top & \Leftrightarrow\lnot P\lor1\\ & \Leftrightarrow P\lor1\\ & \Leftrightarrow1 \end{align*}

(17)

\begin{align*} P\rightarrow P & \Leftrightarrow\lnot P\lor P\\ & \Leftrightarrow1 \end{align*}

(18)

\begin{align*} P\rightarrow\lnot P & \Leftrightarrow\lnot P\lor\lnot P\\ & \Leftrightarrow\lnot P \end{align*}

(19)

\begin{align*} 0\nrightarrow P & \Leftrightarrow\lnot\left(0\rightarrow P\right)\\ & \Leftrightarrow0 \end{align*}

(20)

\begin{align*} 1\nrightarrow P & \Leftrightarrow\lnot\left(1\rightarrow P\right)\\ & \Leftrightarrow\lnot P \end{align*}

(21)

\begin{align*} P\nrightarrow0 & \Leftrightarrow\lnot\left(P\rightarrow0\right)\\ & \Leftrightarrow P \end{align*}

(22)

\begin{align*} P\nrightarrow1 & \Leftrightarrow\lnot\left(P\rightarrow1\right)\\ & \Leftrightarrow0 \end{align*}

(23)

\begin{align*} P\nrightarrow P & \Leftrightarrow\lnot\left(P\rightarrow P\right)\\ & \Leftrightarrow0 \end{align*}

(24)

\begin{align*} P\nrightarrow\lnot P & \Leftrightarrow\lnot\left(P\rightarrow\lnot P\right)\\ & \Leftrightarrow P \end{align*}

(25)

\begin{align*} P\leftrightarrow0 & \Leftrightarrow\left(\lnot P\land\lnot0\right)\lor\left(P\land0\right)\\ & \Leftrightarrow\left(\lnot P\land1\right)\lor\left(P\land0\right)\\ & \Leftrightarrow\lnot P\lor0\\ & \Leftrightarrow\lnot P \end{align*}

(26)

\begin{align*} P\leftrightarrow1 & \Leftrightarrow\left(\lnot P\land\lnot1\right)\lor\left(P\land1\right)\\ & \Leftrightarrow\left(\lnot P\land0\right)\lor\left(P\land1\right)\\ & \Leftrightarrow0\lor P\\ & \Leftrightarrow P \end{align*}

(27)

\begin{align*} P\leftrightarrow P & \Leftrightarrow\left(\lnot P\land\lnot P\right)\lor\left(P\land P\right)\\ & \Leftrightarrow\lnot P\lor P\\ & \Leftrightarrow1 \end{align*}

(28)

\begin{align*} P\leftrightarrow\lnot P & \Leftrightarrow\left(\lnot P\land P\right)\lor\left(P\land\lnot P\right)\\ & \Leftrightarrow0\lor0\\ & \Leftrightarrow0 \end{align*}

(29)

\begin{align*} P\nleftrightarrow0 & \Leftrightarrow\left(\lnot P\lor\lnot0\right)\land\left(P\lor0\right)\\ & \Leftrightarrow1\land P\\ & \Leftrightarrow P \end{align*}

(30)

\begin{align*} P\nleftrightarrow1 & \Leftrightarrow\left(\lnot P\lor\lnot1\right)\land\left(P\lor1\right)\\ & \Leftrightarrow\lnot P\land1\\ & \Leftrightarrow\lnot P \end{align*}

(31)

\begin{align*} P\nleftrightarrow P & \Leftrightarrow\left(\lnot P\lor\lnot P\right)\land\left(P\lor P\right)\\ & \Leftrightarrow\lnot P\land P\\ & \Leftrightarrow0 \end{align*}

(32)

\begin{align*} P\nleftrightarrow\lnot P & \Leftrightarrow\left(\lnot P\lor P\right)\land\left(P\lor\lnot P\right)\\ & \Leftrightarrow1\land1\\ & \Leftrightarrow1 \end{align*}

ページ情報

タイトル	論理演算の基本
URL	https://www.nomuramath.com/zpavbueo/
SNSボタン

論理演算子の移項

\[ \left(P\land R\right)\rightarrow Q\Leftrightarrow P\rightarrow\left(Q\lor\lnot R\right) \]

逆・裏・対偶の定義と対偶の法則

\[ \left(P\rightarrow Q\right)\Leftrightarrow\left(\lnot P\leftarrow\lnot Q\right) \]

量化記号(全称命題・存在命題)の分配

\[ \exists x\left(P\left(x\right)\lor Q\left(x\right)\right)\Leftrightarrow\exists xP\left(x\right)\lor\exists xQ\left(x\right) \]

論理演算同士の関係

\begin{align*} P\lor Q & \Leftrightarrow\lnot P\uparrow\lnot Q\\ & \Leftrightarrow\lnot P\rightarrow Q\\ & \Leftrightarrow P\leftarrow\lnot Q\\ & \Leftrightarrow\lnot\left(\lnot P\land\lnot Q\right)\\ & \Leftrightarrow\lnot\left(P\downarrow Q\right)\\ & \Leftrightarrow\lnot\left(\lnot P\nrightarrow Q\right)\\ & \Leftrightarrow\lnot\left(P\nleftarrow Q\right) \end{align*}