述語論理における推論規則

推論

既知の事柄を前提（premise）とした上で、未知の事柄に関する結論（conclusion）を導き出すことを推論（inference）と呼びます。より正確には、推論とは、前提に相当する有限個の論理式\(A_{1},\cdots ,A_{n}\)と、結論に相当する論理式\(B\)からなる表現\begin{equation*} A_{1},\cdots ,A_{n}\ \therefore \ B
\end{equation*}として定式化されます。これを推論式（inference formula）とも呼びます。以降では推論式とそれが表す推論を区別せずに、両者を推論と呼ぶこともあります。

前提を持たず結論\(B\)だけを持つ推論については、それを、\begin{equation*} \therefore \ B
\end{equation*}と表現します。

妥当な推論：推論規則

論理式\(A_{1},\cdots ,A_{n},B\)に関する推論\begin{equation*} A_{1},\cdots ,A_{n}\ \therefore \ B
\end{equation*}が与えられた状況において、前提\(A_{1},\cdots ,A_{n}\)がすべて真であるような任意の解釈において結論\(B\)が必ず真になることが保証される場合、推論は妥当である（valid）と言い、そのことを、\begin{equation*} A_{1},\cdots ,A_{n}\ \models \ B
\end{equation*}と表現します。その上で、これを推論規則（inference rule）と呼びます。また、推論規則を構成する結論\(B\)を\(A_{1},\cdots ,A_{n}\)の論理的帰結（logical consequence）と呼びます。

述語論理では、論理式の真偽が議論領域や命題関数の解釈、量化などにも依存するため、真理値表だけを用いて妥当性を判定できるとは限りません。その代わり、前提が真となる任意の解釈について結論も真になることを確認します。

前提を持たず結論\(B\)だけを持つ推論\begin{equation*} \therefore \ B
\end{equation*}が妥当であることを、\begin{equation*}
\models \ B
\end{equation*}と表現します。これは、論理式\(B\)が恒真式であることを意味します。

推論が妥当であることの定義は以上の通りですが、これはどのような意味を持っているのでしょうか。繰り返しになりますが、前提\(A_{1},\cdots ,A_{n}\)と結論\(B\)に関する推論が妥当であること、すなわち、以下の推論規則\begin{equation} A_{1},\cdots ,A_{n}\ \models \ B \quad \cdots (1)
\end{equation}が成り立つこととは、\(A_{1},\cdots ,A_{n}\)がすべて真であるような任意の解釈において\(B\)も必ず真になることを意味します。したがって、推論規則\(\left( 1\right) \)が得られた場合、具体的な解釈のもとで\(A_{1},\cdots ,A_{n}\)がいずれも真であるならば、その解釈において\(B\)もまた真になることが保証されます。

推論規則を別の形で理解することもできます。前提\(A_{1},\cdots ,A_{n}\)と結論\(B\)に関する推論が妥当であること、すなわち、以下の推論規則\begin{equation} A_{1},\cdots ,A_{n}\ \models \ B \quad \cdots (1)
\end{equation}が成り立つことが分かっている状況を想定します。では、ある解釈のもとで\(B\)が偽である場合、推論規則\(\left( 1\right) \)が成立するという事実から何らかの有益な事実を導き出せるでしょうか。ある解釈のもとで\(B\)が偽である場合、その解釈のもとでは\(A_{1},\cdots ,A_{n}\)の中の少なくとも1つが偽であることが保証されます。なぜなら、仮にその解釈のもとで\(A_{1},\cdots ,A_{n}\)がすべて真である場合、推論規則\(\left( 1\right) \)より\(B\)が真であることが導き出され、これは\(B\)が偽であることと矛盾するからです。

妥当ではない推論

前提\(A_{1},\cdots ,A_{n}\)がすべて真であるとともに結論\(B\)が偽であるような解釈が存在する場合、その推論は妥当ではない（invalid）と言い、そのことを、 \begin{equation*}
A_{1},\cdots ,A_{n}\ \not\models \ B
\end{equation*}と表記します。

前提\(A_{1},\cdots ,A_{n}\)がすべて真である一方で結論\(B\)が偽になる解釈を反例（counterexample）と呼びます。推論が妥当でないこととは、その推論に反例が存在することを意味します。逆に、反例が存在しない場合、その推論は妥当です。

前提を持たず結論\(B\)だけを持つ推論が妥当でないことを、 \begin{equation*}
\not\models\ B
\end{equation*}と表記します。これは\(B\)が恒真式ではないことを意味します。

推論規則を導く方法

推論の妥当性を示す方法はいくつか存在します。1つ目の方法は、すべての前提\(A_{1},\cdots ,A_{n}\)が真である任意の解釈を選び、その解釈のもとで結論\(B\)も真になることを示す方法です。

推論の妥当性を示すための2つ目の方法は、前提\(A_{1},\cdots ,A_{n}\)と結論\(B\)から以下の論理式 \begin{equation*}
\bigwedge_{i=1}^{n}A_{i}\rightarrow B
\end{equation*}を構成した上で、これが恒真式であること、すなわち、
\begin{equation*}
\bigwedge_{i=1}^{n}A_{i}\Rightarrow B
\end{equation*}が成り立つことを示すというものです。なぜなら、この恒真式が成立することと、前提\(A_{1},\cdots ,A_{n}\)と結論\(B\)に関する推論が妥当であることは必要十分だからです。

推論の妥当性を示すための3つ目の方法は、前提\(A_{1},\cdots ,A_{n}\)を出発点として妥当な推論規則を用いて結論を次々に導出し、最終的に当初の推論の結論\(B\)を導出するというものです。これは証明（proof）と呼ばれる手続きですが、これについては後ほど詳しく解説することにして、次回からは証明において役に立つ推論規則をいくつか提示します。
 

演習問題