論理式の排他的論理和
論理式の定義より、論理式\(A,B\)に論理演算子\(\veebar \)を作用させることにより得られる、\begin{equation*}A\veebar B
\end{equation*}もまた論理式です。\(\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）などと呼びます。
Q &:&\text{加藤は嘘をついている}
\end{eqnarray*}とおくと、「鈴木と加藤はともに嘘をついている」は、\begin{equation*}
P\wedge Q
\end{equation*}として、「鈴木と加藤はともに嘘をついていない」は、\begin{equation*}
\lnot P\wedge \lnot Q
\end{equation*}としてそれぞれ定式化されるため、言明全体は、\begin{equation*}
\left( P\wedge Q\right) \veebar \left( \lnot P\wedge \lnot Q\right)
\end{equation*}と定式化されます。
Q &:&\text{妻が働く}
\end{eqnarray*}とおくとき、\begin{eqnarray*}
P\wedge \lnot Q &:&\text{夫が働き妻が働かない} \\
\lnot P\wedge Q &:&\text{夫が働かず妻が働く}
\end{eqnarray*}となり、さらに、\begin{equation*}
\left( P\wedge \lnot Q\right) \veebar \left( \lnot P\wedge Q\right) :\text{夫が働き妻が働かないか、夫が働かず妻が働くかのどちらか一方}
\end{equation*}となります。
排他的論理和の解釈
排他的論理和\(A\veebar B\)の値は\(A\)と\(B\)の値に依存しますが、その対応規則を以下の真理値表によって定義します。
$$\begin{array}{ccc}
\hline
A & B & A\veebar B \\ \hline
1 & 1 & 0 \\ \hline
1 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$
つまり、排他的論理和\(\veebar \)は入力された論理式\(A,B\)に対して、それらのどちらか一方の値だけが\(1\)である場合にのみ\(1\)を値としてとる論理式\(A\veebar B\)を出力する論理演算です。残りの場合、すなわち\(A\)と\(B\)がともに\(1\)である場合や\(A\)と\(B\)がともに\(0\)である場合、\(A\veebar B\)の値は\(0\)です。
論理和\(A\vee B\)が真になるためには\(A\)と\(B\)の少なくとも一方が真であればよく、\(A\)と\(B\)がともに真である場合にも\(A\vee B\)は真になります。一方、排他的論理和\(A\veebar B\)が真になるのは、\(A\)と\(B\)のどちらか一方だけが真のときに限られます。\(A\)と\(B\)がともに真である場合、\(A\veebar B\)は真ではありません。以上が排他的論理和と論理和の違いです。
$$\begin{array}{ccc}
\hline
P & Q & P\veebar Q \\ \hline
1 & 1 & 0 \\ \hline
1 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$
$$\begin{array}{cccccc}
\hline
P & T & F & P\veebar T & P\veebar F & T\veebar F \\ \hline
1 & 1 & 0 & 0 & 1 & 1 \\ \hline
0 & 1 & 0 & 1 & 0 & 1 \\ \hline
\end{array}$$
$$\begin{array}{ccccc}
\hline
P & Q & R & P\veebar Q & \left( P\veebar Q\right) \veebar R \\ \hline
1 & 1 & 1 & 0 & 1 \\ \hline
1 & 1 & 0 & 0 & 0 \\ \hline
1 & 0 & 1 & 1 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 \\ \hline
0 & 1 & 1 & 1 & 0 \\ \hline
0 & 1 & 0 & 1 & 1 \\ \hline
0 & 0 & 1 & 0 & 1 \\ \hline
0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$
が成り立ちます。
$$\begin{array}{ccccccc}
\hline
P & Q & \lnot P & \lnot Q & P\veebar Q & \lnot P\veebar Q & P\veebar \lnot Q \\ \hline
1 & 1 & 0 & 0 & 0 & 1 & 1 \\ \hline
1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 1 & 0 & 0 \\ \hline
0 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline
\end{array}$$
が成り立ちます。
$$\begin{array}{ccccccc}
\hline
P & Q & R & \lnot P & \lnot R & \lnot P\wedge Q & \left( \lnot P\wedge Q\right) \veebar \lnot R \\ \hline
1 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline
1 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline
1 & 0 & 1 & 0 & 0 & 0 & 0 \\ \hline
1 & 0 & 0 & 0 & 1 & 0 & 1 \\ \hline
0 & 1 & 1 & 1 & 0 & 1 & 1 \\ \hline
0 & 1 & 0 & 1 & 1 & 1 & 0 \\ \hline
0 & 0 & 1 & 1 & 0 & 0 & 0 \\ \hline
0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \hline
\end{array}$$
が成り立ちます。
排他的論理和と否定・論理積・論理和の関係
論理式\(A,B\)を任意に選んだとき、以下の真理値表が得られます。
$$\begin{array}{cccccc}
\hline
A & B & A\veebar B & A\wedge \lnot B & \lnot A\wedge B & \left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \\ \hline
1 & 1 & 0 & 0 & 0 & 0 \\ \hline
1 & 0 & 1 & 1 & 0 & 1 \\ \hline
0 & 1 & 1 & 0 & 1 & 1 \\ \hline
0 & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$
上の真理値表より、排他的論理和\(A\veebar B\)の値は論理式\begin{equation*}\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right)
\end{equation*}の値と常に一致します。この事実は、排他的論理和\(\veebar \)は否定\(\lnot \)と論理積\(\wedge \)と論理和\(\vee \)から間接的に定義可能であることを意味します。したがって、否定、論理積、そして論理和さえ定義されていれば、排他的論理和を新たな論理演算として定義する必要はありません。とは言え、排他的論理和を独立した論理演算として定義しておくと何かと便利であるため、本稿ではこのまま\(\veebar \)を採用します。
演習問題
- 君が卵を買いに行くか、卵抜きのチャーハンになるかのどちらかだ。
- 加藤と鈴木のどちらか一方が不在である。
- 聡はオフィスかジムのどちらかにいる。
- すべての整数は\(2\)で割り切れるか、割り切れるわけではないかのどちらか一方である。
Q &:&\text{鈴木は在宅中である}
\end{eqnarray*}とおいた場合、ある人は先の言明を、\begin{equation*}
\left( P\wedge \lnot Q\right) \vee \left( Q\wedge \lnot P\right)
\end{equation*}と定式化しましたが、別の人は、\begin{equation*}
P\veebar Q
\end{equation*}と定式化しました。どちらが正しいか、理由とともに答えてください。
$$\begin{array}{ccccccc}
\hline
P & Q & T & F & P\wedge Q & \left( P\wedge Q\right) \veebar T & \left( P\wedge Q\right) \veebar F \\ \hline
1 & 1 & 1 & 0 & & & \\ \hline
1 & 0 & 1 & 0 & & & \\ \hline
0 & 1 & 1 & 0 & & & \\ \hline
0 & 0 & 1 & 0 & & & \\ \hline
\end{array}$$
$$\begin{array}{ccccccc}
\hline
P & Q & T & F & P\veebar Q & \left( P\veebar Q\right) \veebar T
& \left( P\veebar Q\right) \veebar F \\ \hline
1 & 1 & 1 & 0 & & & \\ \hline
1 & 0 & 1 & 0 & & & \\ \hline
0 & 1 & 1 & 0 & & & \\ \hline
0 & 0 & 1 & 0 & & & \\ \hline
\end{array}$$
\veebar A_{3}\right) \veebar \cdots \right) \veebar A_{n-1}\right) \veebar
A_{n}\right)
\end{equation*}が真であることが必要十分であることを\(n\)に関する数学的帰納法を用いて証明してください。
