論理演算の定義
論理演算の定義
恒真式の例は\(P\lor\lnot P\Leftrightarrow1\)となる。
恒偽式の例は\(P\land\lnot P\Leftrightarrow0\)となる。
命題\(P\)の否定は\(\lnot P\)である。
単項演算子は2項演算子より優先順位が高いので次の命題のみを反転させる。すなわち\(\lnot P\lor Q\Leftrightarrow\left(\lnot P\right)\lor Q\)である。
2項演算子
命題\(P,Q\)の論理和は\(P\lor Q\)である。
命題\(P,Q\)の論理積は\(P\land Q\)である。
命題\(P,Q\)の包含は\(P\rightarrow Q\)である。
\[ P\rightarrow Q\Leftrightarrow\lnot P\lor Q \]
\[ P\leftarrow Q\Leftrightarrow P\lor\lnot Q \]
命題\(P,Q\)の同値は\(P\leftrightarrow Q\)である。
\begin{align*} P\leftrightarrow Q & \Leftrightarrow\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\\ & \Leftrightarrow\left(P\lor\lnot Q\right)\land\left(\lnot P\lor Q\right)\\ & \Leftrightarrow(P\rightarrow Q)\land(Q\rightarrow P) \end{align*} 同値は排他的論理積(xand)、否定排他的論理和(xnor)と同じである。
\begin{align*} P\downarrow Q & \Leftrightarrow\lnot\left(P\lor Q\right)\\ & \Leftrightarrow\lnot P\land\lnot Q \end{align*}
\begin{align*} P\uparrow Q & \Leftrightarrow\lnot\left(P\land Q\right)\\ & \Leftrightarrow\lnot P\lor\lnot Q \end{align*}
\begin{align*} P\nrightarrow Q & \Leftrightarrow\lnot\left(P\rightarrow Q\right)\\ & \Leftrightarrow P\land\lnot Q \end{align*}
\begin{align*} P\nleftarrow Q & \Leftrightarrow\lnot\left(P\leftarrow Q\right)\\ & \Leftrightarrow\lnot P\land Q \end{align*}
\begin{align*} P\nleftrightarrow Q & \Leftrightarrow\lnot\left(P\leftrightarrow Q\right)\\ & \Leftrightarrow\left(P\lor Q\right)\land\left(\lnot P\lor\lnot Q\right)\\ & \Leftrightarrow\left(P\nrightarrow Q\right)\lor\left(P\nleftarrow Q\right)\\ & \Leftrightarrow\left(P\land\lnot Q\right)\lor\left(\lnot P\land Q\right) \end{align*} 否定同値は排他的論理和(xor)、否定排他的論理積(xnand)と同じである。
(1)恒真式(恒真命題)
常に真となる式を恒真式、常に真となる命題を恒真命題といい記号\(\top\)や\(T\)や1で表す。恒真式の例は\(P\lor\lnot P\Leftrightarrow1\)となる。
(2)恒偽式(矛盾式、恒偽命題)
常に偽となる式を恒偽式、、常に偽となる命題を恒偽命題といいといい記号\(\bot\)や\(F\)や0で表す。恒偽式の例は\(P\land\lnot P\Leftrightarrow0\)となる。
(3)命題
真または偽で表されるものを命題という。(4)否定
命題の真と偽を反転させる単項演算子で記号\(\lnot\)で表す。命題\(P\)の否定は\(\lnot P\)である。
単項演算子は2項演算子より優先順位が高いので次の命題のみを反転させる。すなわち\(\lnot P\lor Q\Leftrightarrow\left(\lnot P\right)\lor Q\)である。
2項演算子
(5)論理和
2つの命題のうち少なくとも1つが真のとき真となり、いずれも偽のとき偽となる演算を論理和といい記号\(\lor\)で表す命題\(P,Q\)の論理和は\(P\lor Q\)である。
(6)論理積
2つの命題がいずれも真のとき真となり、少なくとも1つが偽のとき偽となる演算を論理積といい記号\(\land\)で表す。命題\(P,Q\)の論理積は\(P\land Q\)である。
(7)論理包含(含意、条件文)
2つの命題\(P,Q\)があり、Pが真、Qが偽のとき偽、それ以外は真となる演算を包含演算といい記号\(\rightarrow\)で表す。命題\(P,Q\)の包含は\(P\rightarrow Q\)である。
\[ P\rightarrow Q\Leftrightarrow\lnot P\lor Q \]
(8)論理逆包含
命題\(P,Q\)の逆包含は\(P\leftarrow Q\)と表され\(Q\rightarrow P\)と同じである。\[ P\leftarrow Q\Leftrightarrow P\lor\lnot Q \]
(9)同値(双条件文)
2つの命題の真偽が一致するとき真、一致しないとき偽となる演算を同値演算といい記号\(\leftrightarrow\)で表す。命題\(P,Q\)の同値は\(P\leftrightarrow Q\)である。
\begin{align*} P\leftrightarrow Q & \Leftrightarrow\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\\ & \Leftrightarrow\left(P\lor\lnot Q\right)\land\left(\lnot P\lor Q\right)\\ & \Leftrightarrow(P\rightarrow Q)\land(Q\rightarrow P) \end{align*} 同値は排他的論理積(xand)、否定排他的論理和(xnor)と同じである。
(10)否定論理和
\(P\downarrow Q\)は論理和\(P\lor Q\)の否定\(\lnot\left(P\lor Q\right)\)で、少なくとも1つが真のとき偽になり、いずれも偽のとき真になる。\begin{align*} P\downarrow Q & \Leftrightarrow\lnot\left(P\lor Q\right)\\ & \Leftrightarrow\lnot P\land\lnot Q \end{align*}
(11)否定論理積
\(P\uparrow Q\)は論理積\(P\land Q\)の否定\(\lnot\left(P\land Q\right)\)で、いずれも真のとき偽となり、少なくとも1つが偽のとき真となる。\begin{align*} P\uparrow Q & \Leftrightarrow\lnot\left(P\land Q\right)\\ & \Leftrightarrow\lnot P\lor\lnot Q \end{align*}
(12)否定論理包含(非含意)
\(P\nrightarrow Q\)は包含\(P\rightarrow Q\)の否定\(\lnot\left(P\rightarrow Q\right)\)で、Pが真、Qが偽のとき真、それ以外は偽となる。\begin{align*} P\nrightarrow Q & \Leftrightarrow\lnot\left(P\rightarrow Q\right)\\ & \Leftrightarrow P\land\lnot Q \end{align*}
(13)否定論理逆包含(逆非含意)
\(P\nleftarrow Q\)は逆包含\(P\leftarrow Q\)の否定\(\lnot\left(P\leftarrow Q\right)\)で、Qが真、Pが偽のとき真、それ以外は偽となる。\begin{align*} P\nleftarrow Q & \Leftrightarrow\lnot\left(P\leftarrow Q\right)\\ & \Leftrightarrow\lnot P\land Q \end{align*}
(14)否定同値(非同値)
\(P\nleftrightarrow Q\)は同値\(P\leftrightarrow Q\)の否定\(\lnot\left(P\leftrightarrow Q\right)\)で、真偽が一致するとき偽、一致しないとき真となる。\begin{align*} P\nleftrightarrow Q & \Leftrightarrow\lnot\left(P\leftrightarrow Q\right)\\ & \Leftrightarrow\left(P\lor Q\right)\land\left(\lnot P\lor\lnot Q\right)\\ & \Leftrightarrow\left(P\nrightarrow Q\right)\lor\left(P\nleftarrow Q\right)\\ & \Leftrightarrow\left(P\land\lnot Q\right)\lor\left(\lnot P\land Q\right) \end{align*} 否定同値は排他的論理和(xor)、否定排他的論理積(xnand)と同じである。
\(\rightarrow\)を\(\Rightarrow\)、\(\leftarrow\)を\(\Leftarrow\)、\(\leftrightarrow\)を\(\Leftrightarrow\)、\(\nrightarrow\)を\(\nRightarrow\)、\(\nleftarrow\)を\(\nLeftarrow\)、\(\nleftrightarrow\)を\(\nLeftrightarrow\)でも表す。
例えば\(e+\pi\)や\(e\pi\)は有理数か無理数か知られていないので、「\(e+\pi\)は有理数である」という命題は真偽が不明ですが命題となります。
-
命題は真か偽かどちらかであれば真偽が不明でもいい。例えば\(e+\pi\)や\(e\pi\)は有理数か無理数か知られていないので、「\(e+\pi\)は有理数である」という命題は真偽が不明ですが命題となります。
論理演算一覧
論理定数と単項演算子
\[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q & \top & \bot & P & Q & \lnot P & \lnot Q\\ \hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\ \hline 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1\\ \hline 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\\hline \end{array} \]
論理定数と2項演算子
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline P & Q & P\lor Q & P\land Q & P\rightarrow Q & P\leftarrow Q & P\leftrightarrow Q & P\downarrow Q & P\uparrow Q & P\nrightarrow Q & P\nleftarrow Q & P\nleftrightarrow Q\\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\ \hline 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\\hline \end{array} \]
論理変数と2項演算子
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline P & Q & P\lor Q & P\land Q & P\rightarrow Q & P\leftarrow Q & P\leftrightarrow Q & P\downarrow Q & P\uparrow Q & P\nrightarrow Q & P\nleftarrow Q & P\nleftrightarrow Q\\ \hline A & 0 & A & 0 & \lnot A & 1 & \lnot A & \lnot A & 1 & A & 0 & A\\ \hline A & 1 & 1 & A & 1 & A & A & 0 & \lnot A & 0 & \lnot A & \lnot A\\ \hline 0 & A & A & 0 & 1 & \lnot A & \lnot A & \lnot A & 1 & 0 & A & A\\ \hline 1 & A & 1 & A & A & 1 & A & 0 & \lnot A & \lnot A & 0 & \lnot A\\ \hline \lnot A & \lnot A & \lnot A & \lnot A & 1 & 1 & 1 & A & A & 0 & 0 & 0\\ \hline \lnot A & A & 1 & 0 & A & \lnot A & 0 & 0 & 1 & \lnot A & A & 1\\ \hline A & \lnot A & 1 & 0 & \lnot A & A & 0 & 0 & 1 & A & \lnot A & 1\\ \hline A & A & A & A & 1 & 1 & 1 & \lnot A & \lnot A & 0 & 0 & 0 \\\hline \end{array} \]
2項演算子の否定の別表記
\[ \begin{array}{|c|c|c|c|c|} \hline L & L & \lnot L & L\lnot & \lnot L\lnot\\ \hline \lor & \lor & \rightarrow & \leftarrow & \uparrow\\ \hline \land & \land & \nleftarrow & \nrightarrow & \downarrow\\ \hline \rightarrow & \lnot\lor & \lor & \uparrow & \leftarrow\\ \hline \leftarrow & \lor\lnot & \uparrow & \lor & \rightarrow\\ \hline \leftrightarrow & \leftrightarrow & \nleftrightarrow & \nleftrightarrow & \leftrightarrow\\ \hline \downarrow & \lnot\land\lnot & \nrightarrow & \nleftarrow & \land\\ \hline \uparrow & \lnot\lor\lnot & \leftarrow & \rightarrow & \lor\\ \hline \nrightarrow & \land\lnot & \downarrow & \land & \nleftarrow\\ \hline \nleftarrow & \lnot\land & \land & \downarrow & \nrightarrow\\ \hline \nleftrightarrow & \nleftrightarrow & \leftrightarrow & \leftrightarrow & \nleftrightarrow \\\hline \end{array} \]
2項演算子と論理回路
\[ \begin{array}{|c|c|} \hline P\lor Q & or\\ \hline P\land Q & and\\ \hline P\rightarrow Q & \\ \hline P\leftarrow Q & \\ \hline P\leftrightarrow Q & xnor\\ \hline P\downarrow Q & nor\\ \hline P\uparrow Q & nand\\ \hline P\nrightarrow Q & \\ \hline P\nleftarrow Q & \\ \hline P\nleftrightarrow Q & xor,xnand \\\hline \end{array} \]
論理定数と単項演算子
\[ \begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q & \top & \bot & P & Q & \lnot P & \lnot Q\\ \hline 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1\\ \hline 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ \hline 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1\\ \hline 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\\hline \end{array} \]
論理定数と2項演算子
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline P & Q & P\lor Q & P\land Q & P\rightarrow Q & P\leftarrow Q & P\leftrightarrow Q & P\downarrow Q & P\uparrow Q & P\nrightarrow Q & P\nleftarrow Q & P\nleftrightarrow Q\\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1\\ \hline 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1\\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\\hline \end{array} \]
論理変数と2項演算子
\[ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline P & Q & P\lor Q & P\land Q & P\rightarrow Q & P\leftarrow Q & P\leftrightarrow Q & P\downarrow Q & P\uparrow Q & P\nrightarrow Q & P\nleftarrow Q & P\nleftrightarrow Q\\ \hline A & 0 & A & 0 & \lnot A & 1 & \lnot A & \lnot A & 1 & A & 0 & A\\ \hline A & 1 & 1 & A & 1 & A & A & 0 & \lnot A & 0 & \lnot A & \lnot A\\ \hline 0 & A & A & 0 & 1 & \lnot A & \lnot A & \lnot A & 1 & 0 & A & A\\ \hline 1 & A & 1 & A & A & 1 & A & 0 & \lnot A & \lnot A & 0 & \lnot A\\ \hline \lnot A & \lnot A & \lnot A & \lnot A & 1 & 1 & 1 & A & A & 0 & 0 & 0\\ \hline \lnot A & A & 1 & 0 & A & \lnot A & 0 & 0 & 1 & \lnot A & A & 1\\ \hline A & \lnot A & 1 & 0 & \lnot A & A & 0 & 0 & 1 & A & \lnot A & 1\\ \hline A & A & A & A & 1 & 1 & 1 & \lnot A & \lnot A & 0 & 0 & 0 \\\hline \end{array} \]
2項演算子の否定の別表記
\[ \begin{array}{|c|c|c|c|c|} \hline L & L & \lnot L & L\lnot & \lnot L\lnot\\ \hline \lor & \lor & \rightarrow & \leftarrow & \uparrow\\ \hline \land & \land & \nleftarrow & \nrightarrow & \downarrow\\ \hline \rightarrow & \lnot\lor & \lor & \uparrow & \leftarrow\\ \hline \leftarrow & \lor\lnot & \uparrow & \lor & \rightarrow\\ \hline \leftrightarrow & \leftrightarrow & \nleftrightarrow & \nleftrightarrow & \leftrightarrow\\ \hline \downarrow & \lnot\land\lnot & \nrightarrow & \nleftarrow & \land\\ \hline \uparrow & \lnot\lor\lnot & \leftarrow & \rightarrow & \lor\\ \hline \nrightarrow & \land\lnot & \downarrow & \land & \nleftarrow\\ \hline \nleftarrow & \lnot\land & \land & \downarrow & \nrightarrow\\ \hline \nleftrightarrow & \nleftrightarrow & \leftrightarrow & \leftrightarrow & \nleftrightarrow \\\hline \end{array} \]
2項演算子と論理回路
\[ \begin{array}{|c|c|} \hline P\lor Q & or\\ \hline P\land Q & and\\ \hline P\rightarrow Q & \\ \hline P\leftarrow Q & \\ \hline P\leftrightarrow Q & xnor\\ \hline P\downarrow Q & nor\\ \hline P\uparrow Q & nand\\ \hline P\nrightarrow Q & \\ \hline P\nleftarrow Q & \\ \hline P\nleftrightarrow Q & xor,xnand \\\hline \end{array} \]
上の定義で一部証明をしておく。
(1)包含演算
\[ P\rightarrow Q\Leftrightarrow\lnot P\lor Q \](2)同値演算
\begin{align*} P\leftrightarrow Q & \Leftrightarrow\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\\ & \Leftrightarrow\left(P\lor\lnot Q\right)\land\left(\lnot P\lor Q\right)\\ & \Leftrightarrow(P\rightarrow Q)\land(Q\rightarrow P) \end{align*}(3)否定同値
\begin{align*} P\nleftrightarrow Q & \Leftrightarrow\lnot\left(P\leftrightarrow Q\right)\\ & \Leftrightarrow\left(P\lor Q\right)\land\left(\lnot P\lor\lnot Q\right)\\ & \Leftrightarrow\left(P\nrightarrow Q\right)\lor\left(P\nleftarrow Q\right)\\ & \Leftrightarrow\left(P\land\lnot Q\right)\lor\left(\lnot P\land Q\right) \end{align*}(1)
\(P\rightarrow Q\)は「\(P\)が真、\(Q\)が偽のとき偽、それ以外は真」である。これは「\(\lnot P\)が偽、\(Q\)が偽のとき偽、それ以外は真」と同じであるので、\(\lnot P\lor Q\)となる。
(2)
\(P\leftrightarrow Q\)は「\(P,Q\)の真偽が一致するとき真、一致しないとき偽」である。これは「\(P,Q\)が共に真、または共に偽のとき真、それ以外は偽」であるので、「\(P\land Q\)または\(\lnot P\land\lnot Q\)が真のとき真、\(P\land Q\)と\(\lnot P\land\lnot Q\)が共に偽のとき偽」となる。
すなわち\(\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\)となる。
\begin{align*} P\leftrightarrow Q & \Leftrightarrow\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\\ & \Leftrightarrow\left(P\lor\lnot P\right)\land\left(P\lor\lnot Q\right)\land\left(Q\lor\lnot P\right)\land\left(Q\lor\lnot Q\right)\\ & \Leftrightarrow\left(Q\lor\lnot P\right)\land\left(P\lor\lnot Q\right)\\ & \Leftrightarrow(P\rightarrow Q)\land(Q\rightarrow P) \end{align*}
(3)
\begin{align*} P\nleftrightarrow Q & \Leftrightarrow\lnot\left(P\leftrightarrow Q\right)\\ & \Leftrightarrow\lnot\left(\left(P\land Q\right)\lor\left(\lnot P\land\lnot Q\right)\right)\\ & \Leftrightarrow\left(\lnot P\lor\lnot Q\right)\land\left(P\lor Q\right) \end{align*} \begin{align*} P\nleftrightarrow Q & \Leftrightarrow\lnot\left((P\rightarrow Q)\land(Q\rightarrow P)\right)\\ & \Leftrightarrow\left(P\nrightarrow Q\right)\lor\left(P\nleftarrow Q\right)\\ & \Leftrightarrow\left(P\land\lnot Q\right)\lor\left(\lnot P\land Q\right) \end{align*}ページ情報
| タイトル | 論理演算の定義 |
| URL | https://www.nomuramath.com/wzwuty3b/ |
| SNSボタン |
論理演算の基本
\[
P\lor\left(P\land Q\right)\Leftrightarrow P
\]
優先順位を変更したものとの包含関係・同値関係
\[
P\lor\left(Q\land R\right)\Leftarrow\left(P\lor Q\right)\land R
\]
3つのうち1つを消したものとの包含関係
\[
P\lor\left(Q\land R\right)\Rightarrow P\lor Q
\]
逆・裏・対偶の定義と対偶の法則
\[
\left(P\rightarrow Q\right)\Leftrightarrow\left(\lnot P\leftarrow\lnot Q\right)
\]