排他的論理和
論理式の定義より、論理式\(A,B\)に論理演算子\(\veebar \)を作用させることで得られる\(A\veebar B\)もまた論理式です。\(\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）」という表現に対応する論理式です。
x\text{は偶数であるか奇数であるかのどちらか一方である}
\end{equation*}はどのような論理式として定式化できるでしょうか。命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ、\begin{eqnarray*}P\left( x\right) &:&x\text{は偶数である}
\\
Q\left( x\right) &:&x\text{は奇数である}
\end{eqnarray*}とおくと、先の主張は、\begin{equation*}
P\left( x\right) \veebar Q\left( x\right)
\end{equation*}という論理式として定式化されます。同様に考えると、\begin{equation*}
x\text{は偶数でないか奇数でないかのどちらか一方である}
\end{equation*}という主張は、\begin{equation*}
\lnot P\left( x\right) \veebar \lnot Q\left( x\right)
\end{equation*}という論理式として定式化されます。
Q\left( x,z\right) &:&x\text{は}z\text{と知り合いである}
\end{eqnarray*}とおくとき、\begin{eqnarray*}
P\left( x,y\right) \vee Q\left( x,z\right) &:&x\text{は}y\text{の知り合いであるか、}z\text{の知り合いであるかのどちらか一方である} \\
P\left( x,y\right) \vee \lnot Q\left( x,z\right) &:&x\text{は}y\text{の知り合いであるか、}z\text{の知り合いでないかのどちらか一方である} \\
\lnot P\left( x,y\right) \vee Q\left( x,z\right) &:&x\text{は}y\text{の知り合いでないか、}z\text{の知り合いであるかのどちらか一方である} \\
\lnot P\left( x,y\right) \vee \lnot Q\left( x,z\right) &:&x\text{は}y\text{の知り合いでないか、}z\text{の知り合いでないかのどちらか一方である}
\end{eqnarray*}などとなります。
排他的論理和の解釈
2つの論理式\(A,B\)が与えられたとき、それらの排他的論理和\(A\veebar B\)もまた論理式です。論理式の値を特定するためには何らかの解釈を与える必要があります。解釈が与えられたとき、\(A,B\)から得られる命題を\(\overline{A},\overline{B}\)でそれぞれ表記し、同じ解釈のもとで\(A\veebar B\)から得られる命題を\(\overline{A\veebar B}\)で表記します。その上で、任意の解釈のもとで\(\overline{A\veebar B}\)は命題論理の意味での\(\overline{A}\)と\(\overline{B}\)の排他的論理和であるものと定めます。つまり、解釈を任意に選んだとき、以下の真理値表
$$\begin{array}{ccc}
\hline
\overline{A} & \overline{B} & \overline{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\)が開論理式である場合や閉論理式である場合など様々なケースにおいて、それらの排他的論理和\(A\veebar B\)がどのようなものになるのかを整理するとともに具体例を提示します。
開論理式どうしの排他的論理和
変数\(x\)の自由な現れを持つ開論理式\(A\left( x\right) ,B\left(x\right) \)が与えられたとき、それらの排他的論理和\(\left( A\veebar B\right) \left( x\right) \)もまた変数\(x\)の自由な現れを持つ開論理式です。開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域（}x\text{の定義域）} \\
&&\left( b\right) \ \text{論理式}A,B\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数}x\text{の自由な現れに代入する値}\overline{x}
\end{eqnarray*}を具体的に特定する必要があります。排他的論理和の定義より、解釈としてどのようなものを選んだ場合においても、\(\left(A\veebar B\right) \left( x\right) \)から得られる命題は\(A\left( x\right) ,B\left( x\right) \)から得られる2つの命題の排他的論理和になります。つまり、\(A\left(x\right) \)から得られる命題を\(\overline{A}\left( \overline{x}\right) \)で表記し、\(B\left( x\right) \)から得られる命題を\(\overline{B}\left( \overline{x}\right) \)で表記し、\(\left( A\veebar B\right) \left(x\right) \)から得られる命題を\(\left( \overline{A\veebar B}\right) \left( \overline{x}\right) \)で表記するとき、この3つの命題の真理値の間には、以下の真理値表
$$\begin{array}{ccc}
\hline
\overline{A}\left( \overline{x}\right) & \overline{B}\left( \overline{x}\right) & \left( \overline{A\veebar B}\right) \left( \overline{x}\right)
\\ \hline
1 & 1 & 0 \\ \hline
1 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$
で表される関係が常に成り立つということです。
同じことを真理集合を用いて表現すると以下のようになります。
\overline{x}\in \phi \left( \overline{A}\right) \veebar \overline{x}\in \phi
\left( \overline{B}\right)
\end{equation*}という関係が成り立つ。
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\text{は英会話教室に通っている}
\end{equation*}と定義すると、排他的論理和\(\left( P\veebar Q\right) \left( x\right) \)は、\begin{equation*}x\text{は水泳教室か英会話教室のどちらか一方だけに通っている}
\end{equation*}となります。ある生徒\(A\)は水泳教室にのみ通っているならば、\begin{eqnarray*}A &\in &\phi \left( P\right) \\
A &\not\in &\phi \left( Q\right) \\
A &\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。別の生徒\(B\)は両方に通っているならば、\begin{eqnarray*}B &\in &\phi \left( P\right) \\
B &\in &\phi \left( Q\right) \\
B &\not\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。さらに別の生徒\(C\)はどちらにも通っていないならば、\begin{eqnarray*}C &\not\in &\phi \left( P\right) \\
C &\not\in &\phi \left( Q\right) \\
C &\not\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。任意の生徒\(x\in X\)について、\begin{equation*}x\in \phi \left( P\veebar Q\right) \Leftrightarrow x\in \phi \left( P\right)
\veebar x\in \phi \left( Q\right)
\end{equation*}という関係が成立します。
開論理式どうしが異なる変数の自由な現れを持つ場合にも同様に考えます。
変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)と、変数\(y,z\)の自由な現れを持つ開論理式\(B\left( y,z\right) \)が与えられたとき、それらの排他的論理和\(\left( A\veebar B\right) \left( x,y,z\right) \)は変数\(x,y,z\)の自由な現れを持つ開論理式です。開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域（}x,y,z\text{の定義域）} \\
&&\left( b\right) \ \text{論理式}A,B\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数}x,y,z\text{の自由な現れに代入する値}\overline{x},\overline{y},\overline{z}
\end{eqnarray*}を具体的に特定する必要があります。排他的論理和の定義より、解釈としてどのようなものを選んだ場合においても、\(\left(A\veebar B\right) \left( x,y,z\right) \)から得られる命題は\(A\left( x,y\right) ,B\left(y,z\right) \)から得られる2つの命題の排他的論理和になります。つまり、\(A\left( x,y\right) ,B\left( y,z\right) \)から得られる命題を\(\overline{A}\left( \overline{x},\overline{y}\right) ,\overline{B}\left( \overline{y},\overline{z}\right) \)でそれぞれ表記し、\(\left( A\veebar B\right) \left( x,y,z\right) \)から得られる命題を\(\left( \overline{A\veebar B}\right) \left( \overline{x},\overline{y},\overline{z}\right) \)で表記するとき、この3つの命題の真理値の間には、以下の真理値表
$$\begin{array}{ccc}
\hline
\overline{A}\left( \overline{x},\overline{y}\right) & \overline{B}\left( \overline{y},\overline{z}\right) & \left( \overline{A\veebar B}\right)\left( \overline{x},\overline{y},\overline{z}\right) \\ \hline
1 & 1 & 0 \\ \hline
1 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$
で表される関係が常に成り立つということです。
同じことを真理値表を用いて表現すると以下のようになります。証明は先の命題と同様です。
\overline{A\veebar B}\right) \Leftrightarrow \left( \overline{x},\overline{y}\right) \in \phi \left( \overline{A}\right) \veebar \left( \overline{y},\overline{z}\right) \in \phi \left( \overline{B}\right)
\end{equation*}という関係が成り立つ。
ここでは話を一般化するために、開論理式\(A\)だけが持つ変数の自由な現れ\(x\)、開論理式\(B\)だけが持つ変数の自由な現れ\(z\)、そして\(A \)と\(B\)が共有する変数の自由な現れ\(y\)がいずれも存在するケースについて考えました。実際には、\(x\)に相当する変数の自由な現れが存在しない場合（\(A\left( y\right) ,B\left( y,z\right) \)）や、\(y\)に相当する変数の自由な現れが存在しない場合（\(A\left( x\right) ,B\left( z\right) \)）や、\(z\)に相当する変数の自由な現れが存在しない場合（\(A\left( x,y\right) ,B\left(y\right) \)）など様々な状況が起こり得ます。また、\(x,y,z\)それぞれに相当する変数の自由な現れが複数存在する状況も起こり得ます。いずれの場合にも先と同様に考えます。
\end{equation*}と定義し、命題関数\(Q\left( y,z\right) \)を、\begin{equation*}y\text{と}z\text{は知り合い}
\end{equation*}と定義すると、排他的論理和\(\left( P\veebar Q\right) \left(x,y,z\right) \)は、\begin{equation*}x\text{が}y\text{の知り合いであるか、}y\text{が}z\text{の知り合いであるかのどちらか一方}
\end{equation*}となります。3人の住人からなる組\(\left( A,B,C\right) \in X\times Y\times Z\)について、彼らがお互いに知り合いであるならば、\begin{eqnarray*}\left( A,B\right) &\in &\phi \left( P\right) \\
\left( B,C\right) &\in &\phi \left( Q\right) \\
\left( A,B,C\right) &\not\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。また、\(A\)と\(B\)が知り合いであり、\(B\)と\(C\)が知り合いである一方で、\(A\)と\(C\)が知り合いでない場合には、\begin{eqnarray*}\left( A,B\right) &\in &\phi \left( P\right) \\
\left( B,C\right) &\in &\phi \left( Q\right) \\
\left( A,B,C\right) &\not\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。さらに、\(A\)と\(B\)が知り合いであり、\(B\)と\(C\)は知り合いではなく、\(A\)と\(C \)が知り合いである場合には、\begin{eqnarray*}\left( A,B\right) &\in &\phi \left( P\right) \\
\left( B,C\right) &\not\in &\phi \left( Q\right) \\
\left( A,B,C\right) &\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。任意の\(\left( A,B,C\right) \in X\times Y\times Z\)について、\begin{equation*}\left( A,B,C\right) \in \phi \left( P\veebar Q\right) \Leftrightarrow \left(
A,B\right) \in \phi \left( P\right) \veebar \left( B,C\right) \in \phi
\left( Q\right)
\end{equation*}という関係が成立します。
開論理式と閉論理式の排他的論理和
変数\(x\)の自由な現れを持つ開論理式\(A\left( x\right) \)と変数の自由な現れを持たない閉論理式\(B\)が与えられたとき、それらの排他的論理和\(\left( A\veebar B\right) \left( x\right) \)は変数\(x\)の自由な現れを持つ開論理式です。開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域（}x\text{の定義域）} \\
&&\left( b\right) \ \text{論理式}A,B\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数}x\text{の自由な現れに代入する値}\overline{x}
\end{eqnarray*}を具体的に特定する必要があります。排他的論理和の定義より、解釈としてどのようなものを選んだ場合においても、\(\left(A\veebar B\right) \left( x\right) \)から得られる命題は\(A\left( x\right) ,B\)から得られる2つの命題の排他的論理和になります。つまり、\(A\left( x\right) \)から得られる命題を\(\overline{A}\left( \overline{x}\right) \)で表記し、\(B\)から得られる命題を\(\overline{B}\)で表記し、\(\left( A\veebar B\right) \left( x\right) \)から得られる命題を\(\left( \overline{A\veebar B}\right) \left( \overline{x}\right) \)で表記するとき、この3つの命題の真理値の間には、以下の真理値表
$$\begin{array}{ccc}
\hline
\overline{A}\left( \overline{x}\right) & \overline{B} & \left( \overline{A\veebar B}\right) \left( \overline{x}\right) \\ \hline
1 & 1 & 0 \\ \hline
1 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$
で表される関係が常に成り立つということです。
\end{equation}は閉論理式ですが、以下の論理式\begin{equation}
x>0 \quad \cdots (2)
\end{equation}は開論理式です。これらの排他的論理和をとると以下の開論理式\begin{equation}
\left( \forall x\in X:x^{2}\geq 0\right) \veebar x>0 \quad \cdots (3)
\end{equation}が得られます。変数\(x\)の自由な現れに代入する値\(\overline{x}\)を適当に選ぶと、\(\left( 1\right) ,\left( 2\right) ,\left(3\right) \)から以下の3つの命題\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:x^{2}\geq 0 \\
&&\left( b\right) \ \overline{x}>0 \\
&&\left( c\right) \ \left( \forall x\in X:x^{2}\geq 0\right) \veebar
\overline{x}>0
\end{eqnarray*}が得られますが、排他的の定義より、\(\left(a\right) \)と\(\left( b\right) \)のどちらか一方が真であるならば\(\left( c\right) \)もまた真です。一方、\(\left( a\right) \)と\(\left( b\right) \)がともに真であったり、ともに偽である場合には\(\left( c\right) \)は偽です。
閉論理式どうしの排他的論理和
変数の自由な現れを持たない閉論理式\(A,B\)が与えられたとき、それらの排他的論理和\(A\veebar B\)もまた閉論理式です。閉論理式の値を特定するためには解釈、すなわち以下の2つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式}A,B\text{を構成するすべての命題関数の形状}
\end{eqnarray*}を具体的に特定する必要があります。排他的論理和の定義より、解釈としてどのようなものを選んだ場合においても、\(A\veebar B\)から得られる命題は\(A,B\)から得られる2つの命題の排他的論理和になります。つまり、\(A\)から得られる命題を\(\overline{A}\)で表記し、\(B\)から得られる命題を\(\overline{B}\)で表記し、\(A\veebar B\)から得られる命題を\(\overline{A\veebar B}\)で表記するとき、この3つの命題の真理値の間には、以下の真理値表
$$\begin{array}{ccc}
\hline
\overline{A} & \overline{B} & \overline{A\veebar B} \\ \hline
1 & 1 & 0 \\ \hline
1 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$
で表される関係が常に成り立つということです。
\exists x &\in &X:x^{3}\geq 0 \quad \cdots (2)
\end{eqnarray}はともに閉論理式です。これらの排他的論理和をとると以下の閉論理式\begin{equation}
\left( \forall x\in X:x^{2}\geq 0\right) \veebar \left( \exists x\in
X:x^{3}\geq 0\right) \quad \cdots (3)
\end{equation}が得られます。排他的論理和の定義より、\(\left( 1\right) \)と\(\left( 2\right) \)のどちらか方が真であるならば\(\left( 3\right) \)もまた真です。一方、\(\left( 1\right) \)と\(\left(2\right) \)がともに真であったり、ともに偽である場合には\(\left( 3\right) \)は偽です。
演習問題
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x>0
\end{equation*}と定義します。このとき、排他的論理和\(\left( P\veebar Q\right) \left( x\right) \)がどのような主張であるかを明らかにするとともに、\(P\left( x\right) ,Q\left( x\right) ,\left( P\veebar Q\right) \left( x\right) \)の真理集合を明らかにしてください。
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\geq 2
\end{equation*}と定義します。このとき、排他的論理和\(\left( P\veebar Q\right) \left( x\right) \)がどのような主張であるかを明らかにするとともに、\(P\left( x\right) ,Q\left( x\right) ,\left( P\veebar Q\right) \left( x\right) \)の真理集合を明らかにしてください。
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x^{2}=4
\end{equation*}と定義します。このとき、排他的論理和\(\left( P\veebar Q\right) \left( x\right) \)がどのような主張であるかを明らかにするとともに、\(P\left( x\right) ,Q\left( x\right) ,\left( P\veebar Q\right) \left( x\right) \)の真理集合を明らかにしてください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】