教材一覧
教材一覧
教材検索
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*}とおくと、先の主張は、\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*}という論理式として定式化されます。

例(排他的論理和)
命題関数\(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\)と\(B\)の排他的論理和\(A\veebar B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left(A\veebar B\right) \left( x,y,z\right) \)であるものと定めます。開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A,B\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}\left(
\overline{x},\overline{y},\overline{z}\right)
\end{eqnarray*}を具体的に特定する必要があります。解釈を任意に選んだ上で、\(A\left( x,y\right) \)から得られる命題を\(A\left( \overline{x},\overline{y}\right) \)で、\(B\left( y,z\right) \)から得られる命題を\(B\left( \overline{y},\overline{z}\right) \)で、\(\left( A\veebar B\right) \left( x,y,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) \)の(命題論理における意味での)排他的論理和であるものと定めます。つまり、これら3つの命題の真理値の間には、以下の真理値表
$$\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}$$

表:排他的論理和の値

で表される関係が成り立つものと定めるということです。任意の解釈において同様に考えます。

開論理式である\(A\left( x,y\right) \)と\(B\left( y,z\right) \)に対して、議論領域および\(A\left( x,y\right) \)と\(B\left( y,z\right) \)を構成するすべての命題関数の形状が具体的に与えられている状況を想定します。あとは変数\(x,y,z\)の自由な現れに代入する値\(\overline{x},\overline{y},\overline{z}\)を指定すれば\(A\left( x,y\right) \)から命題\(A\left( \overline{x},\overline{y}\right) \)が得られ、\(B\left( y,z\right) \)から命題\(B\left( \overline{y},\overline{z}\right) \)が得られ、さらに排他的論理和\(\left( A\veebar B\right) \left( x,y,z\right) \)から命題\(\left( A\veebar B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が得られます。\(A\left( \overline{x},\overline{y}\right) \)が真になるような値の組\(\left( \overline{x},\overline{y}\right) \)からなる集合が\(A\left( x,y\right) \)の真理集合\(\phi \left(A\right) \)であり、\(B\left( \overline{y},\overline{z}\right) \)が真になるような値の組\(\left( \overline{y},\overline{z}\right) \)からなる集合が\(B\left( y,z\right) \)の真理集合\(\phi \left( B\right) \)であり、\(\left( A\veebar B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が真になるような値の組\(\left( \overline{x},\overline{y},\overline{z}\right) \)からなる集合が\(\left(A\veebar B\right) \left( x,y,z\right) \)の真理集合\(\phi \left( A\veebar B\right) \)です。排他的論理和の定義より、任意の値の組\(\left( \overline{x},\overline{y},\overline{z}\right) \in X\times Y\times Z\)に対して、\begin{equation*}\left( A\veebar B\right) \left( \overline{x},\overline{y},\overline{z}\right) \text{は真}\Leftrightarrow A\left( \overline{x},\overline{y}\right) \text{と}B\left( \overline{y},\overline{z}\right)
\text{のどちらか一方が真}
\end{equation*}という関係が成り立ちますが、真理集合を用いてこれを表現すると、\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\)の真理集合の要素であるかそのどちらか一方であることを意味します。

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

例(排他的論理和の解釈)
変数\(x\)の定義域\(X\)はある小学校の生徒からなる集合であるものとします。命題変数\(P\left( x\right) \)を、\begin{equation*}x\text{は水泳教室に通っている}
\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*}となります。ある生徒\(x=A\)は水泳教室にのみ通っているならば、\begin{eqnarray*}A &\in &\phi \left( P\right) \\
A &\not\in &\phi \left( Q\right) \\
A &\not\in &\phi \left( P\veebar Q\right)
\end{eqnarray*}が成り立ちます。別の生徒\(x=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*}が成り立ちます。さらに別の生徒\(x=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\)の定義域\(X\)はすべての整数からなる集合であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x^{2}=1
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x>0
\end{equation*}と定義すると、これらの真理集合は、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ 1,-1\right\} \\
\phi \left( Q\right) &=&\left\{ 1,2,3,\cdots \right\}
\end{eqnarray*}となります。一方、排他的論理和\(\left( P\veebar Q\right)\left( x\right) \)は、\begin{equation*}x^{2}=1\text{または}x>0\text{のどちらか一方}
\end{equation*}であり、その真理集合は、\begin{equation*}
\phi \left( P\veebar Q\right) =\left\{ -1,2,3,\cdots \right\}
\end{equation*}となります。任意の整数\(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,z\)は共通の定義域\(X\)を持っており、これはある街の住人からなる集合であるものとします。命題関数\(P\left( x,y\right) \)を、\begin{equation*}x\text{と}y\text{は知り合い}
\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人の住人\(A,B,C\in X\)について、彼らがお互いに知り合いであるならば、\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*}が成り立ちます。任意の\(A,B,C\in X\)について、\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\in X\)に関する命題関数\(P\left( x\right) ,Q\left( x\right) \)から以下の論理式\begin{equation}\forall x\in X:\left( \lnot P\left( x\right) \wedge Q\left( x\right) \right)
\quad \cdots (1)
\end{equation}を定義します。これと命題関数\begin{equation}
P\left( x\right) \quad \cdots (2)
\end{equation}の排他的論理和をとると、以下の論理式\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}を得ます。\(\left( 1\right) \)は閉論理式である一方、\(\left( 2\right) \)と\(\left( 3\right) \)は変数\(x\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状を適当に定めた上で、変数\(x\)の自由な現れに代入する値\(\overline{x}\)を適当に選ぶと、\(\left( 1\right),\left( 2\right) ,\left( 3\right) \)から以下の3つの命題\begin{eqnarray*}&&\left( a\right) \ \forall x\in X:\left( \lnot P\left( x\right) \wedge
Q\left( x\right) \right) \\
&&\left( b\right) \ P\left( \overline{x}\right) \\
&&\left( c\right) \ \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{eqnarray*}を得ます。排他的論理和の定義より、\(\left(a\right) \)と\(\left( b\right) \)のどちらか一方が真であるならば\(\left( c\right) \)は真です。一方、\(\left( a\right) \)と\(\left( b\right) \)がともに真である場合やともに偽である場合には\(\left( c\right) \)は偽です。

 

演習問題

問題(排他的論理和)
変数\(x\)の定義域\(X\)はすべての自然数からなる集合であるものとします。命題関数\(P\left(x\right) \)を、\begin{equation*}x<5
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\geq 2
\end{equation*}と定義します。このとき、\(P\left( x\right) \)および\(Q\left(x\right) \)およびそれらの排他的論理和\(\left( P\veebar Q\right) \left(x\right) \)の真理集合をそれぞれ求めてください。
解答を見る

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

問題(排他的論理和)
変数\(x\)の定義域\(X\)はすべての整数からなる集合であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x^{2}=1
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x^{2}=4
\end{equation*}と定義します。このとき、\(P\left( x\right) \)および\(Q\left(x\right) \)およびそれらの排他的論理和\(\left( P\veebar Q\right) \left(x\right) \)の真理集合をそれぞれ求めてください。
解答を見る

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

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

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

質問とコメント

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

RELATED KNOWLEDGE

関連知識

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

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

対称差
対称差

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

述語論理