論理演算の基本
論理和と論理積の演算の基本
\(P,Q,R\)を命題変数とする。
結合律
交換律
冪等律
二重否定(反射律)
吸収律
吸収律の片方が否定形
分配律
ド・モルガンの法則
否定
零元
単位元
相補律
\(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\)を命題変数とする。
否定論理和の基本
否定論理積の基本
包含の基本
否定包含の基本
同値の基本
否定同値の基本
\(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ボタン |
LK推論規則での包含関係
\[
\left(P\rightarrow Q\right)\land\left(R\rightarrow S\right)\Rightarrow\left(P\lor R\right)\rightarrow\left(Q\land S\right)
\]
論理演算子の移項
\[
\left(P\land R\right)\rightarrow Q\Leftrightarrow P\rightarrow\left(Q\lor\lnot R\right)
\]
分配法則一覧
\[
P\lor\left(Q\land R\right)\Leftrightarrow\left(P\lor Q\right)\land\left(P\lor R\right)
\]
逆・裏・対偶の定義と対偶の法則
\[
\left(P\rightarrow Q\right)\Leftrightarrow\left(\lnot P\leftarrow\lnot Q\right)
\]