教材一覧
PREDICATE LOGIC

述語論理における排他的論理和

Share on twitter
Twitterで共有
Share on email
メールで共有

排他的論理和

論理式の定義より、論理式\(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) ) \quad\cdots (1)
\end{equation}において、変数\(x\)の現れは\(P\left( x\right) \)と\(Q\left( x\right) \)の2カ所の\(x\)ですが、それらはともに\(\forall \)によって束縛されています。したがって、論理式\(\left( 1\right) \)は閉論理式です。一方、論理式\begin{equation}
P\left( x\right) \quad\cdots (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) \quad\cdots (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) )
\quad\cdots (1) \\
\forall x &\in &X\ \left( \forall y\in Y\ \left( P\left( x\right) \wedge
Q\left( y\right) \right) \right) \quad\cdots (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) \quad\cdots (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 twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

排他的論理和

命題論理における排他的論理和

排他的論理和は入力された 2 つの論理式に対して、それらのどちらか一方の値だけが 1 である場合にのみ 1 を値としてとる論理式を出力する論理演算です。

対称差

対称差

集合 A,B のどちらか一方だけに属する要素からなる集合を A と B の対称差と呼びます。集合 A が命題関数 P(x) から、集合 B が命題関数 Q(x) から内包的に定義されるとき、A と B の対称差は P(x) と Q(x) のどちらか一方だけが真になるような要素 x からなる集合です。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

述語論理