教材一覧
PREDICATE LOGIC

述語論理における論理積

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

 

論理積

論理式の定義より、論理式\(A,B\)に論理演算子\(\wedge \)を作用させることで得られる\(A\wedge B\)もまた論理式です。\(\wedge \)は論理積(logical product)と呼ばれる論理演算子であり、論理式\(A\wedge B\)を\(A\)と\(B\)の論理積(logical product of \(A\) and \(B\))と呼びます。これは「\(A\)かつ\(B\)(\(A\) and \(B\))」という表現に対応する論理式です。

例(論理積)
以下の主張\begin{equation*}
x\text{は偶数であり、なおかつ}y\text{は奇数である}
\end{equation*}はどのような論理式として定式化できるでしょうか。命題関数\(P\left( x\right) ,Q\left( y\right) \)をそれぞれ、\begin{eqnarray*}
P\left( x\right) &:&x\text{は偶数である}
\\
Q\left( y\right) &:&y\text{は奇数である}
\end{eqnarray*}とおくと、先の主張は\(P\left( x\right) \wedge Q\left( y\right) \)という論理式として定式化されます。同様に考えると、\begin{equation*}
x\text{は偶数ではなく、なおかつ}y\text{は奇数ではない}
\end{equation*}という主張は\(\lnot P\left( x\right) \wedge \lnot Q\left( y\right) \)という論理式として定式化されます。では、以下の主張\begin{equation*}
x\text{は偶数かつ}y\text{は奇数であり、なおかつ}x+y\geq 4\text{である}
\end{equation*}はどのような論理式として定式化できるでしょうか。新たな命題関数\(R\left( x,y\right) \)を、\begin{equation*}
R\left( x,y\right) :x+y\geq 4
\end{equation*}とおくと、この主張は\(\left( P\left( x\right) \wedge Q\left( y\right) \right) \wedge R\left( x,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) \wedge Q\left( x,z\right) &:&x\text{は}y\text{の知り合いであり、なおかつ}x\text{は}z\text{の知り合いである} \\
P\left( x,y\right) \wedge \lnot Q\left( x,z\right) &:&x\text{は}y\text{の知り合いだが、}x\text{は}z\text{の知り合いではない} \\
\lnot P\left( x,y\right) \wedge Q\left( x,z\right) &:&x\text{は}y\text{の知り合いではないが、}x\text{は}z\text{の知り合いである} \\
\lnot P\left( x,y\right) \wedge \lnot Q\left( x,z\right) &:&x\text{は}y\text{の知り合いではなく、なおかつ}x\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\wedge B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left( A\wedge 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*}を具体的に特定することを意味し、解釈を任意に選ぶと3つの命題\(A\left( \overline{x},\overline{y}\right) \)と\(B\left( \overline{y},\overline{z}\right) \)と\(\left( A\wedge B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が得られます。このとき、\(\left( A\wedge 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\wedge B\right) \left( \overline{x},\overline{y},\overline{z}\right) \\ \hline
1 & 1 & 1 \\ \hline
1 & 0 & 0 \\ \hline
0 & 1 & 0 \\ \hline
0 & 0 & 0 \\ \hline
\end{array}$$

表:論理積の値

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

例(論理積の解釈)
命題関数\(P\left( x\right) ,Q\left( x\right) \)はともに変数\(x\in X\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状を、\begin{eqnarray*}
&&\left( a_{1}\right) \ 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) \wedge Q\left( x\right) \)もまた変数\(x\)の自由な現れを持つ開論理式であり、その形状は、\begin{equation*}
P\left( x\right) \wedge Q\left( x\right) :x^{2}=1\wedge x>0
\end{equation*}となります。以上の3つの開論理式中の変数\(x\)の自由な現れに\(1\)を代入して得られる命題は、\begin{eqnarray*}
P\left( 1\right) &:&1^{2}=1 \\
Q\left( 1\right) &:&1>0 \\
P\left( 1\right) \wedge Q\left( 1\right) &:&1^{2}=1\wedge 1>0
\end{eqnarray*}ですが、\(P\left( 1\right) \)と\(Q\left( 1\right) \)はともに真であるため論理積の定義より\(P\left( 1\right) \wedge Q\left( 1\right) \)もまた真です。変数\(x\)の自由な現れに\(-1\)を代入して得られる命題は、\begin{eqnarray*}
P\left( -1\right) &:&\left( -1\right) ^{2}=1 \\
Q\left( -1\right) &:&-1>0 \\
P\left( -1\right) \wedge Q\left( -1\right) &:&\left( -1\right) ^{2}=1\wedge
-1>0
\end{eqnarray*}ですが、\(P\left( -1\right) \)は真で\(Q\left( -1\right) \)は偽であるため論理積の定義より\(P\left( -1\right) \wedge Q\left( -1\right) \)は偽です。
例(論理積の解釈)
命題関数\(P\left( x,y\right) \)は2つの変数\(x\in X\)と\(y\in Y\)の自由な現れを持つ開論理式であり、命題関数\(Q\left( y,z\right) \)は2つの変数\(y\in Y\)と\(z\in Z\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状を、\begin{eqnarray*}
&&\left( a_{1}\right) \ 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) \wedge Q\left( x,z\right) \)は変数\(x,y,z\)の自由な現れを持つ開論理式であり、その形状は、\begin{equation*}
P\left( x,y\right) \wedge Q\left( y,z\right) :x\text{は}y\text{の知り合い、かつ}y\text{は}z\text{の知り合い}
\end{equation*}となります。全員がお互いに知り合いであるような3人の住人\(\left( \overline{x},\overline{y},\overline{z}\right) \)を適当に選んだ上で変数\(x,y,z\)の自由な現れに代入すると、\begin{eqnarray*}
P\left( \overline{x},\overline{y}\right) &:&\overline{x}\text{と}\overline{y}\text{は知り合い} \\
Q\left( \overline{y},\overline{z}\right) &:&\overline{y}\text{と}\overline{z}\text{は知り合い} \\
P\left( \overline{x},\overline{y}\right) \wedge Q\left( \overline{y},\overline{z}\right) &:&\overline{x}\text{は}\overline{y}\text{の知り合い、かつ}\overline{y}\text{は}\overline{z}\text{の知り合い}
\end{eqnarray*}という3つの命題が得られますが、\(P\left( \overline{x},\overline{y}\right) \)と\(Q\left( \overline{y},\overline{z}\right) \)はともに真であるため論理積の定義より\(P\left( \overline{x},\overline{y}\right) \wedge 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\)の現れはいずれも\(\forall \)によって束縛されています。したがって、論理式\(\left( 1\right) \)は閉論理式です。一方、論理式\begin{equation}
P\left( x\right) \quad \cdots (2)
\end{equation}は変数\(x\)の自由な現れを持つ開論理式です。\(\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) \wedge P\left( x\right) \quad \cdots (3)
\end{equation}となりますが、\(\lnot P\left( x\right) \)と\(Q\left( x\right) \)における\(x\)の現れは\(\forall \)によって束縛されている一方で、\(P\left( x\right) \)における\(x\)は自由な表れであるため\(\left( 3\right) \)は開論理式です。議論領域\(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\ (\lnot P\left( \overline{x}\right)
\wedge Q\left( \overline{x}\right) ) \\
&&\left( b\right) \ P\left( \overline{x}\right) \\
&&\left( c\right) \ \left( \forall x\in X\ \left( \lnot P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \right) \right) \wedge 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) \)もまた偽です。

 

論理積の真理集合

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

例(論理積の真理集合)
命題関数\(P\left( x\right) ,Q\left( x\right) \)はともに変数\(x\in X\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ、\begin{eqnarray*}
&&\left( a_{1}\right) \ 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*}で与えられているものとします。このとき、\begin{equation*}
P\left( x\right) \wedge Q\left( x\right) :x^{2}=1\wedge x>0
\end{equation*}となります。\(P\)と\(Q\)の真理集合は、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ -1,1\right\} \\
\phi \left( Q\right) &=&\left\{ 1,2,3,\cdots \right\}
\end{eqnarray*}であるため、論理積の定義より、\begin{equation*}
\phi \left( P\wedge Q\right) =\left\{ 1\right\}
\end{equation*}となります。
例(論理積の真理集合)
命題関数\(P\left( x,y\right) \)は2つの変数\(x\in X\)と\(y\in Y\)の自由な現れを持つ開論理式であり、命題関数\(Q\left( y,z\right) \)は2つの変数\(y\in Y\)と\(z\in Z\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状がそれぞれ、\begin{eqnarray*}
&&\left( a_{1}\right) \ 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*}で与えられているものとします。このとき、\begin{equation*}
P\left( x,y\right) \wedge Q\left( y,z\right) :x\text{は}y\text{の知り合い、かつ}y\text{は}z\text{の知り合い}
\end{equation*}となります。\(A,B,C\)の3人がお互いに知り合いであるならば、\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) &\in &\phi \left( P\wedge 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) &\in &\phi \left( P\wedge 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) &\not\in &\phi \left( P\wedge Q\right)
\end{eqnarray*}となります。
例(論理積の真理集合)
命題関数\(P\left( x,y\right) \)は2つの変数\(x,y\)の自由な現れを持つ開論理式であり、命題関数\(Q\left( y,z\right) \)は2つの変数\(y,z\)の自由な現れを持つ開論理式です。このとき、論理式\begin{equation*}
\lnot P\left( x,y\right) \wedge \lnot Q\left( y,z\right)
\end{equation*}は3つの変数\(x,y,z\)の自由な現れを持つ開論理式です。議論領域\(D\)と関数\(P,Q\)の形状を適当に指定すると、変数\(x,y,z\)の自由な現れに代入する任意の値の組\(\left( \overline{x},\overline{y},\overline{z}\right) \)について、\begin{eqnarray*}
\left( \overline{x},\overline{y},\overline{z}\right) \in \phi \left( \lnot
P\wedge \lnot Q\right) &\Leftrightarrow &\left( \overline{x},\overline{y}\right) \in \phi \left( \lnot P\right) \wedge \left( \overline{y},\overline{z}\right) \in \phi \left( \lnot Q\right) \quad \because \wedge \text{の定義} \\
&\Leftrightarrow &\left( \overline{x},\overline{y}\right) \not\in \phi
\left( P\right) \wedge \left( \overline{y},\overline{z}\right) \not\in \phi
\left( Q\right) \quad \because \lnot \text{の定義}
\end{eqnarray*}という関係が成り立ちます。つまり、命題\(\lnot P\left( \overline{x},\overline{y}\right) \wedge \lnot Q\left( \overline{y},\overline{z}\right) \)が真であることと、命題\(P\left( \overline{x},\overline{y}\right) \)と命題\(Q\left( \overline{y},\overline{z}\right) \)がともに偽であることは必要十分です。

次回は論理和の解釈について学びます。

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

関連知識

論理積

命題論理における論理積

論理積∧は入力された論理式 A, B に対して、それらの値がともに 1 である場合にのみ 1 を値としてとる論理式 A∧B を出力する論理演算です。

共通部分

共通部分

集合 A,B の双方に属する要素からなる集合を A と B の共通部分と呼びます。集合 A が命題関数 P(x) から、集合 B が命題関数 Q(x) からそれぞれ内包的に定義されるとき、A と B の共通部分は 2 つの命題 P(x), Q(x) がともに真になるような要素 x からなる集合です。

DISCUSSION

質問とコメント

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

述語論理