論理演算の定義

論理演算の定義

(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\)は有理数である」という命題は真偽が不明ですが命題となります。

論理演算一覧

論理定数と単項演算子

\[ \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ボタン