論理式\(A,B\)に論理演算子\(\veebar \)を作用させることで得られる\(A\veebar B\)もまた論理式です。\(\veebar \)は排他的論理和と呼ばれる論理演算子であり、論理式\(A\veebar B\)を\(A\)と\(B\)の排他的論理和と呼びます。

2018年11月23日:公開

排他的論理和の値

論理式の定義より、議論領域\(D\)における論理式\(A,B\)に論理演算子\(\veebar \)を作用させることで得られる\(A\veebar B\)もまた\(D\)の論理式です。\(\veebar \)は排他的論理和(exclusive disjunction)と呼ばれる論理演算子であり、論理式\(A\veebar B\)を\(A\)と\(B\)の排他的論理和(exclusive disjunction of \(A\) and \(B\))や\(A\)か\(B\)のどちらか一方(either\(\ A\) or \(B\ \)/\(\ A\) or \(B\), but not both)などと呼びます。論理式どうしの排他的論理和の値を以下のように定めます。

論理式の定義について復習する

議論領域\(D\)における論理式\(A,B\)がともに変数を持つ開論理式\begin{eqnarray*}
&&A\left( x_{1},\cdots ,x_{l},y_{1},\cdots ,y_{m}\right) \\
&&B\left( y_{1},\cdots ,y_{m},z_{1},\cdots ,z_{n}\right)
\end{eqnarray*}である場合について考えます。\(A,B\)の真理集合を\(\phi \left( A\right) \)と\(\phi \left( B\right) \)で表します。ここでは話を一般化するために\(A\)だけが持つ変数\(x_{1},\cdots ,x_{l}\)、\(B\)だけが持つ変数\(z_{1},\cdots ,z_{n}\)、そして\(A\)と\(B\)が共有する変数\(y_{1},\cdots ,y_{m}\)を導入しましたが、実際には\(A\)と\(B\)が同じ変数のみを持っていたり、同じ変数を共有しない場合なども起こり得ます。上の表現はすべての場合を包括したものになっています。

開論理式・閉論理式について復習する

開論理式\(A,B\)が上のように与えられたとき、それらの排他的論理和\(A\veebar B\)は変数\(x_{1},\cdots ,x_{l},y_{1},\cdots ,y_{m},z_{1},\cdots ,z_{n}\)を持つ開論理式\begin{equation*}
\left( A\veebar B\right) \left( x_{1},\cdots ,x_{l},y_{1},\cdots ,y_{m},z_{1},\cdots ,z_{n}\right)
\end{equation*}です。その上で、値の組\(\left( \overline{x}_{1},\cdots ,\overline{x}_{l},\overline{y}_{1},\cdots ,\overline{y}_{m},\overline{z}_{1},\cdots ,\overline{z}_{n}\right) \)が、\begin{eqnarray*}
&&\left( a\right) \ \left( \overline{x}_{1},\cdots ,\overline{x}_{l},\overline{y}_{1},\cdots ,\overline{y}_{m}\right) \in \phi \left( A\right) \\
&&\left( b\right) \ \left( \overline{y}_{1},\cdots ,\overline{y}_{m},\overline{z}_{1},\cdots ,\overline{z}_{n}\right) \in \phi \left( B\right)
\end{eqnarray*}のどちらか一方だけを満たす場合には\(A\veebar B\)の値を\(1\)と定め、それ以外の場合には\(A\veebar B\)の値を\(0\)と定めます。

続いて、議論領域\(D\)における論理式\(A,B\)について、\(A\)は変数を持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)ですが\(B\)は変数を持たない閉論理式である場合について考えます。論理式\(A,B\)がこのように与えられたとき、それらの排他的論理和\(A\veebar B\)は変数\(x_{1},\cdots ,x_{n}\)を持つ開論理式\(\left( A\veebar B\right) \left( x_{1},\cdots ,x_{n}\right) \)です。その上で、値の組\(\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right) \)が、\begin{eqnarray*}
&&\left( a\right) \ \left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right) \in \phi \left( A\right) \\
&&\left( b\right) \ B\text{の値は}1
\end{eqnarray*}のどちらか一方だけを満たす場合には\(A\veebar B\)の値を\(1\)と定め、それ以外の場合には\(A\veebar B\)の値を\(0\)と定めます。

最後に、議論領域\(D\)における論理式\(A,B\)がともに変数を持たない閉論理式である場合には、排他的論理和\(A\veebar B\)の意味は命題論理における論理和と同様です。すなわち、\(A\)と\(B\)の値のどちらか一方だけが\(1\)ならば\(A\veebar B\)の値は\(1\)であり、それ以外の場合には\(A\veebar B\)の値は\(0\)です。

例(排他的論理和)
任意の自然数を値として取り得る変数\(x,y\)に関する命題関数\begin{eqnarray*}
P\left( x,y\right) &:&x+y\leq 4 \\
Q\left( x\right) &:&x\leq 2
\end{eqnarray*}の排他的論理和\(\left( P\veebar Q\right) \left( x,y\right) \)について考えます。例えば、値の組\(\left( x,y\right) =\left( 1,1\right) \)について、\begin{eqnarray*}
P\left( 1,1\right) &:&1+1\leq 4 \\
Q\left( 1\right) &:&1\leq 2
\end{eqnarray*}となり、これらはともに真ですので\(\left( P\veebar Q\right) \left( 1,1\right) \)は偽です。また、値の組\(\left( x,y\right) =\left( 1,3\right) \)について、\begin{eqnarray*}
P\left( 1,3\right) &:&1+3\leq 4 \\
Q\left( 3\right) &:&3\leq 2
\end{eqnarray*}となり、\(P\left( 1,3\right) \)は真で\(Q\left( 3\right) \)は偽ですので\(\left( P\veebar Q\right) \left( 1,3\right) \)は真です。さらに、値の組\(\left( x,y\right) =\left( 3,3\right) \)について、\begin{eqnarray*}
P\left( 3,3\right) &:&3+3\leq 4 \\
Q\left( 3\right) &:&3\leq 2
\end{eqnarray*}となり、これらはともに偽ですので\(\left( P\veebar Q\right) \left( 3,3\right) \)は偽です。

 

排他的論理和の真理集合

変数\(x\in X\)を共有する論理式\(A\left( x\right) ,B\left( x\right) \)とそれらの排他的論理積\(\left( A\veebar B\right) \left( x\right) \)が与えられたとき、変数\(x\)に値\(\overline{x}\)を代入すれば 3 つの命題\(A\left( \overline{x}\right) ,B\left( \overline{x}\right) ,\left( A\veebar B\right) \left( \overline{x}\right) \)を得ます。排他的論理和の定義より、\(A\left( \overline{x}\right) \)と\(B\left( \overline{x}\right) \)のどちらか一方だけ\(1\)である場合には\(\left( A\veebar B\right) \left( \overline{x}\right) \)の値は\(1\)であり、それ以外の場合には\(\left( A\veebar B\right) \left( \overline{x}\right) \)の値は\(0\)です。つまり、値\(\overline{x}\)が真理集合\(\phi \left( A\right) ,\phi \left( B\right)\)のどちらか一方だけ属する場合にのみ\(\overline{x}\)は真理集合\(\phi \left( A\veebar B\right)\)に属します。

排他的論理和の値

図:排他的論理和の真理集合

変数の定義域\(X\)に属するそれぞれの値について同様の議論が成立するため、結局、\(\phi \left( A\veebar B\right) \)は\(\phi \left( A\right) \)と\(\phi \left( B\right) \)を合わせた領域から両者の交わりを除いた領域に相当します。これは上図のグレーの領域で表されます。

次回は含意の値について学びます。

次へ進む 演習問題(プレミアム会員限定)