教材一覧
PREDICATE LOGIC

述語論理における含意

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

含意

論理式の定義より、論理式\(A,B\)に論理演算子\(\rightarrow \)を作用させることで得られる\(A\rightarrow B\)もまた論理式です。\(\rightarrow\)は含意(implication)と呼ばれる論理演算子であり、論理式\(A\rightarrow B\)を\(A\)から\(B\)への含意(implication from \(A\) to \(B\))と呼びます。これは「\(A\)ならば\(B\)(if \(A\) then \(B\))」という表現に対応する論理式です。含意\(A\rightarrow B\)を構成する\(A\)を前件(antecedent)や前提(premise)、仮定(assumption)などと呼び、\(B\)を後件(consequent)や結論(conclusion)などと呼びます。

例(含意)
以下の主張\begin{equation*}
x\text{が}4\text{の倍数ならば、}x\text{は偶数である}
\end{equation*}はどのような論理式として定式化できるでしょうか。命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ、\begin{eqnarray*}
P\left( x\right) &:&x\text{は}4\text{の倍数である} \\
Q\left( x\right) &:&x\text{は偶数である}
\end{eqnarray*}とおくと、先の主張は\(P\left( x\right) \rightarrow Q\left( x\right) \)という論理式として定式化されます。同様に考えると、\begin{equation*}
x\text{が}4\text{の倍数でないならば、}x\text{は偶数ではない}
\end{equation*}という主張は\(\lnot P\left( x\right) \rightarrow \lnot Q\left( x\right) \)という論理式として定式化されます。
例(含意)
以下の主張\begin{equation*}
x\text{と}y\text{が知り合いであり、}y\text{と}z\text{が知り合いならば、}x\text{と}z\text{は知り合いである}
\end{equation*}はどのような論理式として定式化できるでしょうか。以下の命題関数\begin{eqnarray*}
P\left( x,y\right) &:&x\text{と}y\text{は知り合いである} \\
Q\left( y,z\right) &:&y\text{と}z\text{は知り合いである} \\
R\left( x,z\right) &:&x\text{と}z\text{は知り合いである}
\end{eqnarray*}を定義すると、先の主張は、\begin{equation*}
\left( P\left( x,y\right) \wedge Q\left( y,z\right) \right) \rightarrow
R\left( x,z\right)
\end{equation*}という論理式として定式化されます。

 

含意の解釈

論理式\(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\rightarrow B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left( A\rightarrow 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\rightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が得られます。このとき、\(\left( A\rightarrow 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\rightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \\ \hline
1 & 1 & 1 \\ \hline
1 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
0 & 0 & 1 \\ \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) \rightarrow Q\left( x\right) \)もまた変数\(x\)の自由な現れを持つ開論理式であり、その形状は、\begin{equation*}
P\left( x\right) \rightarrow Q\left( x\right) :x^{2}=1\rightarrow 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) \rightarrow Q\left( 1\right) :1^{2}=1\rightarrow 1>0
\end{equation*}は真です。また、値\(x=0\)については、\begin{eqnarray*}
P\left( 0\right) &:&0^{2}=1 \\
Q\left( 0\right) &:&0>0
\end{eqnarray*}はともに偽であるため、含意の定義より、\begin{equation*}
P\left( 0\right) \rightarrow Q\left( 0\right) :0^{2}=1\rightarrow 0>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) \rightarrow Q\left( -1\right) :\left( -1\right)
^{2}=1\rightarrow -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) \rightarrow Q\left( x,z\right) \)は変数\(x,y,z\)の自由な現れを持つ開論理式であり、その形状は、\begin{equation*}
P\left( x,y\right) \rightarrow Q\left( y,z\right) :x\text{が}y\text{の知り合いならば、}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) \rightarrow 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) \rightarrow 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) \rightarrow 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) \rightarrow P\left( \overline{x}\right)
\end{equation*}の値は\(1\)です。
例(含意の解釈)
変数\(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) \rightarrow \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) \)の値は\(1\)です。また、別の解釈において\(\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\rightarrow B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left( A\rightarrow B\right) \left( x,y,z\right) \)となります。今、開論理式の解釈の中でも、議論領域と、論理式を構成するすべての命題関数の形状を指定すれば、\(A\)の真理集合\(\phi \left( A\right) \)と\(B\)の真理集合\(\phi \left( B\right) \)、そして\(A\rightarrow B\)の真理集合\(\phi \left( A\rightarrow B\right)\)がそれぞれ得られます。さらに、変数の自由な現れに代入する値\(\left( \overline{x},\overline{y},\overline{z}\right) \)を任意に選ぶと、\begin{eqnarray*}
\left( \overline{x},\overline{y},\overline{z}\right) \in \phi \left(
A\rightarrow B\right) &\Leftrightarrow &\left( A\rightarrow B\right) \left(
\overline{x},\overline{y},\overline{z}\right) \text{は真}\quad
\because \phi \text{の定義} \\
&\Leftrightarrow &A\left( \overline{x},\overline{y}\right) \text{は真}\rightarrow B\left( \overline{y},\overline{z}\right) \text{は真}\quad \because \rightarrow \text{の定義} \\
&\Leftrightarrow &\left( \overline{x},\overline{y}\right) \in \phi \left(
A\right) \rightarrow \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\rightarrow B\right) \Leftrightarrow \left( \overline{x},\overline{y}\right) \in \phi \left( A\right) \rightarrow \left( \overline{y},\overline{z}\right) \in \phi \left( B\right)
\end{equation*}という関係が成り立ちます。つまり、\(\left( \overline{x},\overline{y},\overline{z}\right) \)が\(A\rightarrow B\)の真理集合の要素であることは、\(\left( \overline{x},\overline{y}\right) \)が\(A\)の真理集合の要素でないか、または\(\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{は}1\text{以上}9\text{以下の整数からなる集合} \\
&&\left( b_{1}\right) \ P\left( x\right) :x\leq 3 \\
&&\left( b_{2}\right) \ Q\left( x\right) :x\text{は偶数}
\end{eqnarray*}で与えられているとき、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ 1,2,3\right\} \\
\phi \left( Q\right) &=&\left\{ 2,4,6,8\right\}
\end{eqnarray*}であるため、含意の定義より、\begin{equation*}
\phi \left( P\rightarrow Q\right) =\left\{ 2,4,5,6,7,8,9\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) \rightarrow Q\left( y,z\right) \)は変数\(x,y,z\)の自由な現れを持つ開論理式であり、その真理集合を\(\phi \left( \lnot P\rightarrow 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\rightarrow Q\right) &\Leftrightarrow &\left( \overline{x},\overline{y}\right) \in \phi \left( \lnot P\right) \rightarrow \left( \overline{y},\overline{z}\right) \in \phi \left( Q\right) \quad \because \rightarrow
\text{の定義} \\
&\Leftrightarrow &\left( \overline{x},\overline{y}\right) \not\in \phi
\left( P\right) \rightarrow \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) \)が真であるか、または命題\(P\left( \overline{x},\overline{y}\right) \)は偽で命題\(Q\left( \overline{y},\overline{z}\right) \)が偽である場合、命題\(\left( \lnot P\rightarrow 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) \rightarrow B\left( \overline{y},\overline{z}\right) \Leftrightarrow \lnot A\left( \overline{x},\overline{y}\right) \vee B\left( \overline{y},\overline{z}\right)
\end{equation*}という関係が成り立つため、\begin{equation*}
\left( A\rightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \Leftrightarrow \left( \lnot A\vee B\right) \left( \overline{x},\overline{y},\overline{z}\right)
\end{equation*}すなわち、\begin{equation*}
\phi \left( A\rightarrow B\right) =\phi \left( \lnot A\vee B\right)
\end{equation*}が成り立ちます。つまり、任意の解釈において、含意\(A\rightarrow B\)の値は論理式\(\lnot A\vee B\)の値と常に一致するということです。この事実は、含意\(\rightarrow \)は否定\(\lnot \)と論理和\(\vee \)から間接的に定義可能であることを意味します。したがって、否定と論理和さえ定義されていれば、含意を新たな論理演算として定義する必要はありません。とは言え、含意を独立した論理演算として定義しておくと何かと便利ですので、以降でも引き続き\(\rightarrow \)を採用します。

次回は同等と呼ばれる論理演算について解説します。

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

関連知識

同等

論理演算の言い換え

含意、同等、排他的論理和はいずれも否定、論理積、論理和を用いて間接的に定義可能です。

含意

命題論理における含意

含意 → は入力された論理式 A,B に対して、A と B の値がともに 1 である場合には 1 を値としてとり、A の値が 0 の場合には B の値によらず常に 1 を値としてとる論理式 A→B を出力する論理演算です。

DISCUSSION

質問とコメント

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

述語論理