排他的論理和の解釈

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

排他的論理和

論理式の定義より、論理式\(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)」という表現に対応する論理式です。

例(排他的論理和)
以下の主張\begin{equation*}
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*}とおくと、先の主張は\(P\left( x\right) \veebar Q\left( x\right) \)という論理式として定式化されます。同様に考えると、\begin{equation*}
x\text{は偶数でないか奇数でないかのどちらか一方である}
\end{equation*}という主張は\(\lnot P\left( x\right) \veebar \lnot Q\left( y\right) \)という論理式として定式化されます。
例(排他的論理和)
命題関数\(P\left( x,y\right) ,Q\left( x,z\right) \)がそれぞれ、\begin{eqnarray*}
P\left( x,y\right) &:&x\text{は}y\text{と知り合いである} \\
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*}などとなります。

 

排他的論理和の解釈

論理式\(A\)が変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)であり、論理式\(B\)が変数\(y,z\)の自由な現れを持つ開論理式\(B\left( y,z\right) \)であるものとします。ここでは話を一般化するために\(A\)だけが持つ変数の自由な現れ\(x\)、\(B\)だけが持つ変数の自由な現れ\(z\)、そして\(A\)と\(B\)が共有する変数の自由な現れ\(y\)について考えていますが、実際には、\(A\)と\(B\)が共通の変数の自由な現れだけを持っていたり、逆に、共通の変数の自由な現れを持たない場合も起こり得ます。また、\(x,y,z\)それぞれに相当する変数の自由な現れが複数存在する場合も以下の議論と同様の議論が成り立ちます。また、論理式\(A,B\)が変数の自由な現れを持たない場合、それは閉論理式であることを意味しますが、その場合にも以下の議論と同様の議論が成り立ちます。

繰り返しになりますが、論理式\(A\)が変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)であり、論理式\(B\)が変数\(y,z\)の自由な現れを持つ開論理式\(B\left( y,z\right) \)であるものとします。このとき、\(A\)と\(B\)の排他的論理和\(A\veebar B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left( A\veebar B\right) \left( x,y,z\right) \)であるものと定めます。開論理式を解釈することとは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}
\end{eqnarray*}を具体的に特定することを意味し、解釈を任意に選ぶと3つの命題\(A\left( \overline{x},\overline{y}\right) \)と\(B\left( \overline{y},\overline{z}\right) \)と\(\left( A\veebar B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が得られます。このとき、\(\left( A\veebar B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)を\(A\left( \overline{x},\overline{y}\right) \)と\(B\left( \overline{y},\overline{z}\right) \)の排他的論理和と同一視します。つまり、これらの命題の真理値の間には、以下の真理値表で表される関係が成り立つということです。
$$\begin{array}{ccc}
\hline
A\left( \overline{x},\overline{y}\right) & B\left( \overline{y},\overline{z}\right) & \left( 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}$$

表:排他的論理和の値

開論理式と閉論理式の排他的論理和や、閉論理式どうしの排他的論理和についても同様に考えます。

例(排他的論理和の解釈)
命題関数\(P\left( x\right) ,Q\left( x\right) \)はともに変数\(x\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ、\begin{eqnarray*}
&&\left( a_{1}\right) \ \text{変数}x\text{の定義域}X\text{はすべての整数からなる集合} \\
&&\left( b_{1}\right) \ P\left( x\right) :x^{2}=1 \\
&&\left( b_{2}\right) \ Q\left( x\right) :x>0
\end{eqnarray*}で与えられているものとします。排他的論理和\(P\left( x\right) \veebar Q\left( x\right) \)もまた変数\(x\)の自由な現れを持つ開論理式であり、その形状は、\begin{equation*}
P\left( x\right) \veebar Q\left( x\right) :x^{2}=1\veebar x>0
\end{equation*}となります。例えば、値\(x=1\)については、\begin{eqnarray*}
P\left( 1\right) &:&1^{2}=1 \\
Q\left( 1\right) &:&1>0
\end{eqnarray*}はともに真であるため、排他的論理和の定義より、\begin{equation*}
P\left( 1\right) \veebar Q\left( 1\right) :1^{2}=1\veebar 1>0
\end{equation*}は偽です。また、値\(x=-1\)については、\begin{eqnarray*}
P\left( -1\right) &:&\left( -1\right) ^{2}=1 \\
Q\left( -1\right) &:&-1>0
\end{eqnarray*}となりますが、\(P\left( -1\right) \)は真で\(Q\left( -1\right) \)は偽であるため、排他的論理和の定義より、\begin{equation*}
P\left( 1\right) \veebar Q\left( 1\right) :\left( -1\right) ^{2}=1\veebar
-1>0
\end{equation*}は真です。
例(排他的論理和の解釈)
命題関数\(P\left( x,y\right) \)は変数\(x,y\)の自由な現れを持つ開論理式であり、命題関数\(Q\left( y,z\right) \)は変数\(y,z\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ、\begin{eqnarray*}
&&\left( a_{1}\right) \ \text{変数}x,y,z\text{の定義域}X,Y,Z\text{はいずれもある町の住人} \\
&&\left( b_{1}\right) \ P\left( x,y\right) :x\text{と}y\text{は知り合いである} \\
&&\left( b_{2}\right) \ Q\left( y,z\right) :y\text{と}z\text{は知り合いである}
\end{eqnarray*}で与えられているものとします。排他的論理和\(P\left( x,y\right) \veebar Q\left( x,z\right) \)は変数\(x,y,z\)の自由な現れを持つ開論理式であり、その形状は、\begin{equation*}
P\left( x,y\right) \veebar Q\left( y,z\right) :x\text{は}y\text{の知り合い}\veebar y\text{は}z\text{の知り合い}
\end{equation*}となります。全員がお互いに知り合いであるような3人の住人\(\left( \overline{x},\overline{y},\overline{z}\right) \)を適当に選んだとき、命題\(P\left( \overline{x},\overline{y}\right) \)と命題\(Q\left( \overline{y},\overline{z}\right) \)はともに真であるため、排他的論理和の定義より、命題\(P\left( \overline{x},\overline{y}\right) \veebar Q\left( \overline{y},\overline{z}\right) \)は偽です。また、\(\overline{y}\)が\(\overline{x}\)と\(\overline{z}\)のどちらか一方とのみ知り合いであるような3人の住人\(\left( \overline{x},\overline{y},\overline{z}\right) \)を適当に選んだとき、命題\(P\left( \overline{x},\overline{y}\right) \)と命題\(Q\left( \overline{y},\overline{z}\right) \)の一方は真で他方は偽であるため、排他的論理和の定義より、命題\(P\left( \overline{x},\overline{y}\right) \veebar Q\left( \overline{y},\overline{z}\right) \)は真です。
例(排他的論理和の解釈)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする論理式\begin{equation}
\forall x\in X\ (\lnot P\left( x\right) \wedge Q\left( x\right) ) \tag{1}
\end{equation}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)ですが、それらはともに\(\forall \)によって束縛されています。したがって、論理式\(\left( 1\right) \)は閉論理式です。一方、論理式\begin{equation}
P\left( x\right) \tag{2}
\end{equation}は変数\(x\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ具体的に与えられているものとします。このとき、\(\left( 1\right) \)と\(\left( 2\right) \)の排他的論理和は、\begin{equation}
\left( \forall x\in X\ \left( \lnot P\left( x\right) \wedge Q\left( x\right)
\right) \right) \veebar P\left( x\right) \tag{3}
\end{equation}となります。\(\lnot P\left( x\right) \)と\(Q\left( x\right) \)における\(x\)の現れは束縛されている一方で、\(P\left( x\right) \)における\(x\)は自由な表れです。したがって\(\left( 3\right) \)は開論理式です。変数\(x\)の自由な現れに代入する値\(\overline{x}\)を適当に選ぶと、\(\left( 1\right) \)より命題\(\forall x\in X\ (\lnot P\left( x\right) \wedge Q\left( x\right) )\)が、\(\left( 2\right) \)より命題\(P\left( \overline{x}\right) \)が得られます。仮にこれらの値がともに\(1\)であるとき、排他的論理和の定義より、\(\left( 3\right) \)より得られる命題\begin{equation*}
\left( \forall x\in X\ \left( \lnot P\left( x\right) \wedge Q\left( x\right)
\right) \right) \veebar P\left( \overline{x}\right)
\end{equation*}の値は\(0\)です。
例(排他的論理積の解釈)
変数\(x\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)を被演算子とする以下の2つの論理式\begin{eqnarray}
\forall x &\in &X\ (\lnot P\left( x\right) \wedge Q\left( x\right) )
\tag{1} \\
\forall x &\in &X\ \left( \forall y\in Y\ \left( P\left( x\right) \wedge
Q\left( y\right) \right) \right) \tag{2}
\end{eqnarray}はともに閉論理式です(確認してください)。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ具体的に与えられているものとします。このとき、\(\left( 1\right) \)と\(\left( 2\right) \)の排他的論理和は、\begin{equation}
\left( \forall x\in X\ (\lnot P\left( x\right) \wedge Q\left( x\right)
)\right) \veebar \left( \forall x\in X\ \left( \forall y\in Y\ \left(
P\left( x\right) \wedge Q\left( y\right) \right) \right) \right) \tag{3}
\end{equation}となりますが、これもまた閉論理式です。仮に、与えられた解釈において\(\left( 1\right) \)と\(\left( 2\right) \)の値がともに\(1\)であるならば、排他的論理和の定義より、その解釈において\(\left( 2\right) \)の値は\(0\)です。また、別の解釈において\(\left( 1\right) \)の値と\(\left( 2\right) \)の値がともに\(0\)であるならば、排他的論理和の定義より、その解釈において\(\left( 2\right) \)の値は\(0\)です。

 

排他的論理和の真理集合

繰り返しになりますが、論理式\(A\)が変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)であり、論理式\(B\)が変数\(y,z\)の自由な現れを持つ開論理式\(B\left( y,z\right) \)であるとき、これらの排他的論理和\(A\veebar B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left( A\veebar B\right) \left( x,y,z\right) \)となります。今、開論理式の解釈の中でも、議論領域と、論理式を構成するすべての命題関数の形状を指定すれば、\(A\)の真理集合\(\phi \left( A\right) \)と\(B\)の真理集合\(\phi \left( B\right) \)、そして\(A\veebar B\)の真理集合\(\phi \left( A\veebar B\right) \)がそれぞれ得られます。さらに、変数の自由な現れに代入する値\(\left( \overline{x},\overline{y},\overline{z}\right) \)を任意に選ぶと、\begin{eqnarray*}
\left( \overline{x},\overline{y},\overline{z}\right) \in \phi \left(
A\veebar B\right) &\Leftrightarrow &\left( A\veebar B\right) \left(
\overline{x},\overline{y},\overline{z}\right) \text{は真}\quad
\because \phi \text{の定義} \\
&\Leftrightarrow &A\left( \overline{x},\overline{y}\right) \text{は真}\veebar B\left( \overline{y},\overline{z}\right) \text{は真}\quad \because \veebar \text{の定義} \\
&\Leftrightarrow &\left( \overline{x},\overline{y}\right) \in \phi \left(
A\right) \veebar \left( \overline{y},\overline{z}\right) \in \phi \left(
B\right) \quad \because \phi \text{の定義}
\end{eqnarray*}すなわち、\begin{equation*}
\left( \overline{x},\overline{y},\overline{z}\right) \in \phi \left(
A\veebar B\right) \Leftrightarrow \left( \overline{x},\overline{y}\right)
\in \phi \left( A\right) \veebar \left( \overline{y},\overline{z}\right) \in
\phi \left( B\right)
\end{equation*}という関係が成り立ちます。つまり、\(\left( \overline{x},\overline{y},\overline{z}\right) \)が\(A\veebar B\)の真理集合の要素であることと、\(\left( \overline{x},\overline{y}\right) \)が\(A\)の真理集合の要素であるか\(\left( \overline{y},\overline{z}\right) \)が\(B\)の真理集合の要素であるかのどちらか一方であることは必要十分です。

例(排他的論理和の真理集合)
命題関数\(P\left( x\right) ,Q\left( x\right) \)はともに変数\(x\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ、\begin{eqnarray*}
&&\left( a_{1}\right) \ \text{変数}x\text{の定義域}X\text{はすべての整数からなる集合} \\
&&\left( b_{1}\right) \ P\left( x\right) :x^{2}=1 \\
&&\left( b_{2}\right) \ Q\left( x\right) :x^{2}=4
\end{eqnarray*}で与えられているとき、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ -1,1\right\} \\
\phi \left( Q\right) &=&\left\{ -2,2\right\}
\end{eqnarray*}であるため、論理和の定義より、\begin{equation*}
\phi \left( P\veebar Q\right) =\left\{ -2,-1,1,2\right\}
\end{equation*}となります。
例(排他的論理和の真理集合)
命題関数\(P\left( x,y\right) \)は変数\(x,y\)の自由な現れを持つ開論理式であり、命題関数\(Q\left( y,z\right) \)は変数\(y,z\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状を選んだ上で、そこでの\(P,Q\)の真理集合を\(\phi \left( P\right) ,\phi \left( Q\right) \)で表します。排他的論理式\(\lnot P\left( x,y\right) \veebar \lnot Q\left( y,z\right) \)は変数\(x,y,z\)の自由な現れを持つ開論理式であり、その真理集合を\(\phi \left( \lnot P\veebar \lnot Q\right) \)で表します。このとき、それぞれの値の組\(\left( \overline{x},\overline{y},\overline{z}\right) \)について、\begin{eqnarray*}
\left( \overline{x},\overline{y},\overline{z}\right) \in \phi \left( \lnot
P\veebar \lnot Q\right) &\Leftrightarrow &\left( \overline{x},\overline{y}\right) \in \phi \left( \lnot P\right) \veebar \left( \overline{y},\overline{z}\right) \in \phi \left( \lnot Q\right) \quad \because \vee \text{の定義} \\
&\Leftrightarrow &\left( \overline{x},\overline{y}\right) \not\in \phi
\left( P\right) \veebar \left( \overline{y},\overline{z}\right) \not\in \phi
\left( Q\right) \quad \because \lnot \text{の定義}
\end{eqnarray*}が成り立ちます。したがって、それぞれの\(\left( \overline{x},\overline{y},\overline{z}\right) \)において、命題\(P\left( \overline{x},\overline{y}\right) \)と命題\(Q\left( \overline{y},\overline{z}\right) \)のどちらか一方が偽の場合にのみ、命題\(\left( \lnot P\veebar \lnot Q\right) \left( \overline{x},\overline{y},\overline{z}\right) \)は真になります。

 

排他的論理和と否定・論理積・論理和の関係

論理式\(A\)が変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)であり、論理式\(B\)が変数\(y,z\)の自由な現れを持つ開論理式\(B\left( y,z\right) \)であるものとします。今、開論理式の解釈の中でも、議論領域と、論理式を構成するすべての命題関数の形状をした上で、変数の自由な現れに代入する値\(\left( \overline{x},\overline{y},\overline{z}\right) \)を任意に選ぶと、排他的論理和の言い換えより、\begin{equation*}
A\left( \overline{x},\overline{y}\right) \veebar B\left( \overline{y},\overline{z}\right) \Leftrightarrow \left( A\left( \overline{x},\overline{y}\right) \wedge \lnot B\left( \overline{y},\overline{z}\right) \right) \vee
\left( \lnot A\left( \overline{x},\overline{y}\right) \wedge B\left(
\overline{y},\overline{z}\right) \right)
\end{equation*}という関係が成り立つため、\begin{equation*}
\left( A\veebar B\right) \left( \overline{x},\overline{y},\overline{z}\right) \Leftrightarrow \left( \left( A\wedge \lnot B\right) \vee \left(
\lnot A\wedge B\right) \right) \left( \overline{x},\overline{y},\overline{z}\right)
\end{equation*}すなわち、\begin{equation*}
\phi \left( A\veebar B\right) =\phi \left( \left( A\wedge \lnot B\right)
\vee \left( \lnot A\wedge B\right) \right)
\end{equation*}が成り立ちます。つまり、任意の解釈において、排他的論理和\(A\veebar B\)の値は論理式\(\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \)の値と常に一致するということです。この事実は、排他的論理和\(\veebar \)は否定\(\lnot \)と論理積\(\wedge \)と論理和\(\vee \)から間接的に定義可能であることを意味します。したがって、否定、論理積、そして論理和さえ定義されていれば、排他的論理和を新たな論理演算として定義する必要はありません。とは言え、排他的論理和を独立した論理演算として定義しておくと何かと便利ですので、以降でも引き続き\(\veebar \)を採用します。

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

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

述語論理
アカウント
ログイン