原子論理式
述語論理において議論の対象となる論理的な主張や推論はいずれも命題関数どうしを一定のルールのもとで組み合わせた式として表現されます。そのような式を論理式（formula）と呼びます。命題関数は論理式を構成する最小単位であるため、これを原子論理式（atomic formula）と呼ぶこともあります。述語論理において個々の原子論理式は単独で論理式とみなされます。
議論領域\(D\)において定義されている変数\(x\)に関する命題関数を\(P\left(x\right) \)などで表記します。変数が\(x\)であることが文脈から自明である場合、命題関数\(P\left(x\right) \)を\(P\)と表記することもできます。ちなみに、\(P\left( x\right) \)という表記は二通りの意味で使われるため注意が必要です。「命題関数\(P\left( x\right) \)」という場合の\(P\left( x\right) \)は、それが命題関数であることを表す表記です。一方、「命題\(P\left( x\right) \)」という場合の\(P\left( x\right) \)は、定義域\(X\)に属する値\(x\)を命題関数\(P\)に代入して得られる命題を表す表記です。両者を明示的に区別するために、\(X\)に属する値を\(\overline{x}\)で表し、それを命題関数\(P\)に代入して得られる命題を\(P\left( \overline{x}\right) \)と表記することもできます。
命題関数が持つ変数の個数は1つである必要はありません。一般に、議論領域\(D\)において定義されている変数の中から\(n\)個の変数\(x_{1},\cdots ,x_{n}\)を任意に選んだとき、それらを変数とする命題関数を\(P\left( x_{1},\cdots ,x_{n}\right) \)などで表記します。
異なる命題関数が同じ変数を持つとは限りません。議論領域\(D\)において定義されている変数\(x_{1},x_{2},x_{3}\)を選んだとき、ある命題関数\(P\)は\(x_{1}\)と\(x_{2}\)を変数として持つ関数\(P\left( x_{1},x_{2}\right) \)であり、別の関数\(Q\)は\(x_{2}\)と\(x_{3}\)を変数として持つ関数\(Q\left( x_{2},x_{3}\right) \)であり、さらに別の関数\(R\)は\(x_{3}\)を変数として持つ関数\(R\left( x_{3}\right) \)である、という状況は起こり得ます。
&&y\text{は奇数} \\
&&x+y\text{は偶数} \\
&&x+y\text{は奇数}
\end{eqnarray*}などはいずれも命題関数であるため、これらは\(D\)における原子論理式です。
ax^{2}+bx+c &=&0\text{は1つの実数解を持つ} \\
ax^{2}+bx+c &=&0\text{は実数解を持たない}
\end{eqnarray*}などはいずれも命題関数であるため、これらは\(D\)における原子論理式です。
&&g\text{は微分可能である} \\
&&f\text{は}g\text{の導関数である}
\end{eqnarray*}などはいずれも命題関数であるため、これらは\(D\)における原子論理式です。
議論領域\(D\)における命題関数\(P\left( x_{1},\cdots ,x_{n}\right) \)が与えられたとき、その変数\(x_{1},\cdots ,x_{n}\)の中から特定の変数\(x_{1},\cdots ,x_{m}\ \left( m\leq n\right) \)を任意に選び、さらにそれらの変数の値\(\overline{x}_{1},\cdots ,\overline{x}_{m}\)を任意に選びます。これを命題関数\(P\left( x_{1},\cdots ,x_{n}\right) \)の該当する変数に代入して得られる\(P\left( \overline{x}_{1},\cdots ,\overline{x}_{m},x_{m+1},\cdots ,x_{n}\right) \)を便宜的に\(\bar{P}\)で表します。\(m<n \)の場合、\(\bar{P}\)は値が代入されていない変数\(x_{m+1},\cdots ,x_{n}\)を持つ命題関数\(P\left( \overline{x}_{1},\cdots ,\overline{x}_{m},x_{m+1},\cdots ,x_{n}\right) \)であり、これもまた\(D\)における原子論理式とみなします。\(m=n\)の場合、\(\bar{P}\)は変数を持たない命題\(P\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right) \)ですが、これも\(D\)における原子論理式とみなします。
&&x+y\text{は偶数である}
\end{eqnarray*}はともに\(D\)における原子論理式です。さらに、変数\(x,y\)の少なくとも一方に何らかの値を代入して得られる、\begin{eqnarray*}&&1\text{は偶数である} \\
&&2\text{は偶数である} \\
&&1+y\text{は偶数である} \\
&&x+3\text{は偶数である} \\
&&2+3\text{は偶数である}
\end{eqnarray*}なども\(D\)における原子論理式です。
\end{equation*}は\(D\)における原子論理式です。さらに、変数\(a,b,c\)の少なくとも一つに何らかの値を代入して得られる、\begin{eqnarray*}x^{2}+x+c &=&0\text{は実数解を持つ}
\\
x^{2}+bx+2 &=&0\text{は実数解を持つ} \\
2x^{2}+x+3 &=&0\text{は実数解を持つ}
\end{eqnarray*}なども\(D\)における原子論理式です。
\end{equation*}は\(D\)における原子論理式です。さらに、変数\(f,g\)の少なくとも一方に何らかの値を代入して得られる、\begin{eqnarray*}&&f\text{は}x^{2}+1\text{の導関数である} \\
&&2x\text{は}g\text{の導関数である} \\
&&2x\text{は}x^{2}+1\text{の導関数である}
\end{eqnarray*}なども\(D\)における原子論理式です。
繰り返しになりますが、述語論理において、個々の原子論理式は単独で論理式とみなされます。つまり、議論領域\(D\)における命題関数や、そこから上のようにして生成される命題関数や命題などはいずれも議論領域\(D\)における論理式とみなされます。
論理演算
述語論理では、議論領域\(D\)における原子論理式\(P,Q,\cdots \)に対して行う操作を表す記号\(\lnot ,\wedge ,\vee,\veebar ,\rightarrow ,\leftrightarrow \)を導入した上で、これらを原子論理式に作用させることで新たな論理式を作り出します。
具体的には、議論領域\(D\)における原子論理式\(P,Q\)を任意に選んだとき、\(P\)に\(\lnot \)を作用させることで得られる論理式を\(\lnot P\)で表し、\(P\)と\(Q\)に\(\wedge \)を作用させることで得られる論理式を\(P\wedge Q\)で表します。さらに、\(P\)と\(Q\)に\(\vee \)を作用させることで得られる論理式を\(P\vee Q\)で表し、\(P\)と\(Q\)に\(\veebar \)を作用させることで得られる論理式を\(P\veebar Q\)で表します。また、\(P\)と\(Q\)に\(\rightarrow \)を作用させることで得られる論理式を\(P\rightarrow Q\)で表し、\(P\)と\(Q\)に\(\leftrightarrow \)を作用させることで得られる論理式を\(P\leftrightarrow Q\)で表します。
述語論理では議論領域\(D\)における原子論理式に論理演算子を作用させることで論理式を生成するだけでなく、そのようにして生成された論理式\(A,B,\cdots \)に対して再び論理演算子を作用させて得られる式もまた\(D\)における論理式とみなします。
具体的には、議論領域\(D\)における論理式\(A,B\)を任意に選んだとき、\(A\)に\(\lnot \)を作用させることで得られる論理式を\(\lnot A\)で表し、\(A\)と\(B\)に\(\wedge \)を作用させることで得られる論理式を\(A\wedge B\)で表します。さらに、\(A\)と\(B\)に\(\vee \)を作用させることで得られる論理式を\(A\vee B\)で表し、\(A\)と\(B\)に\(\veebar \)を作用させることで得られる論理式を\(A\veebar B\)で表します。また、\(A\)と\(B\)に\(\rightarrow \)を作用させることで得られる論理式を\(A\rightarrow B\)で表し、\(A\)と\(B\)に\(\leftrightarrow \)を作用させて得られる論理式を\(A\leftrightarrow B\)で表します。
\end{equation*}はいずれも\(D\)における原子論理式であるため論理式でもあります。変数\(x,y\)に代入する値\(\overline{x},\overline{y}\)を任意に選んだとき、\begin{equation*}P\left( \overline{x}\right) ,\ Q\left( \overline{y}\right) ,\ R\left(
\overline{x},y\right) ,\ R\left( x,\overline{y}\right) ,\ R\left( \overline{x},\overline{y}\right)
\end{equation*}などはいずれも\(D\)における原子論理式であるため論理式でもあります。原子論理式に論理演算子を作用させたものは\(D\)における論理式であるため、例えば、\begin{eqnarray*}&&\lnot P\left( x\right) \\
&&P\left( x\right) \wedge Q\left( \overline{y}\right) \\
&&R\left( x,y\right) \rightarrow \left( Q\left( y\right) \vee P\left(
\overline{x}\right) \right)
\end{eqnarray*}などはいずれも\(D\)における論理式です。論理式に論理演算子を作用させたものは論理式であるため、例えば、\begin{eqnarray*}&&\left( \lnot P\left( x\right) \right) \veebar \left( P\left( x\right)
\wedge Q\left( \overline{y}\right) \right) \\
&&\left( \lnot R\left( x,y\right) \rightarrow \left( Q\left( y\right) \vee
P\left( \overline{x}\right) \right) \right) \wedge \left( P\left( x\right)
\wedge Q\left( \overline{y}\right) \right)
\end{eqnarray*}などはいずれも\(D\)における論理式です。
量化
述語論理では論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)とは別の演算子\(\forall ,\exists \)を導入した上で、これらを議論領域\(D\)における原子論理式へ作用させて得られる式もまた\(D\)における論理式とみなします。具体的には、議論領域\(D\)における原子論理式\(P\)と変数\(x\in X\)をそれぞれ任意に選んだとき、\(P\)に\(\forall \)を作用させることで得られる論理式を\(\forall x\in X:P\)で表します。同様に、\(P\)に\(\exists \)を作用させることで得られる論理式を\(\exists x\in X:P\)で表します。
記号\(\forall \)は all ないし any の頭文字である A を逆さにしたものであり、これを全称記号（universal quantifier）や全称量化記号などと呼びます。一方、記号\(\exists \)は exist の頭文字である E を逆さにしたものであり、これを存在記号（existential quantifier）や存在量化記号などと呼びます。全称記号と存在記号を総称して量化記号（quantifier）や限定記号などと呼び、原子論理式に量化記号を作用させることを量化（quantification）と呼びます。原子論理式を量化して得られる論理式の意味については後ほど解説します。
議論領域\(D\)における原子論理式に論理演算子や量化記号を作用させると\(D\)における論理式が生成されますが、そうして得られた論理式を量化させることで得られる式もまた\(D\)における論理式とみなします。具体的には、議論領域\(D\)における論理式\(A\)と変数\(x\in X\)をそれぞれ任意に選んだとき、\(A\)に\(\forall \)を作用させることで得られる論理式を\(\forall x\in X:A\)で表し、\(A\)に\(\exists \)を作用させることで得られる論理式を\(\exists x\in X:A\)で表します。
\end{equation*}が定義されているものとします。これらは\(D\)における原子論理式です。変数\(x,y\)に代入する値\(\overline{x},\overline{y}\)を任意に選んだとき、\begin{equation*}P\left( \overline{x}\right) ,\ Q\left( \overline{y}\right) ,\ R\left(
\overline{x},y\right) ,\ R\left( x,\overline{y}\right) ,\ R\left( \overline{x},\overline{y}\right)
\end{equation*}などはいずれも\(D\)における原子論理式であるため論理式でもあります。原子論理式に量化記号を作用させたものも\(D\)における論理式であるため、例えば、\begin{eqnarray*}\forall x &\in &X:P\left( x\right) \\
\forall y &\in &Y:Q\left( y\right) \\
\forall y &\in &Y:R\left( x,y\right)
\end{eqnarray*}などは\(D\)における論理式です。論理式に論理演算子を作用させたものは\(D\)における論理式であるため、例えば、\begin{eqnarray*}\forall x &\in &X:\left( \lnot P\left( x\right) \right) \\
\forall y &\in &X:\left( \forall y\in Y:R\left( x,y\right) \right) \\
\forall x &\in &X:\left( R\left( x,y\right) \rightarrow \left( Q\left(
y\right) \vee P\left( \overline{x}\right) \right) \right)
\end{eqnarray*}などは\(D\)における論理式です。
論理式の再帰的定義
繰り返しになりますが、述語論理において原子論理式は単独で論理式とみなされます。また、原子論理式に論理演算子や量化記号を作用させることで得られる式も論理式とみなされます。また、論理式に論理演算子や量化記号を作用させることで得られる式も論理式です。
以上を踏まえた上で、議論領域\(D\)における論理式を以下のように再帰的に定義します。
- \(D\)の原子論理式は\(D\)の論理式である。
- \(A\)が\(D\)の論理式ならば、\(\left( \lnot A\right) \)は\(D\)の論理式である。
- \(A,B\)が\(D\)の論理式ならば、\(\left( A\wedge B\right) \)は\(D\)の論理式である。
- \(A,B\)が\(D\)の論理式ならば、\(\left( A\vee B\right) \)は\(D\)の論理式である。
- \(A,B\)が\(D\)の論理式ならば、\(\left( A\veebar B\right) \)は\(D\)の論理式である。
- \(A,B\)が\(D\)の論理式ならば、\(\left( A\rightarrow B\right) \)は\(D\)の論理式である。
- \(A,B\)が\(D\)の論理式ならば、\(\left( A\leftrightarrow B\right) \)は\(D\)の論理式である。
- \(A\)が\(D\)の論理式であり、\(x\in X\)が\(D\)の変数ならば、\(\left( \forall x\in X:A\right) \)は\(D\)の論理式である。
- \(A\)が\(D\)の論理式であり、\(x\in X\)が\(D\)の変数ならば、\(\left( \exists x\in X:A\right) \)は\(D\)の論理式である。
- 以上から論理式と判定されるものだけが論理式である。
論理式の例をいくつか挙げます。
\end{equation*}は論理式です。さらに、この論理式をもう1つの論理式\(R\left( x,y,z\right) \)に論理演算子\(\vee \)を作用させた、\begin{equation*}\left( \left( P\left( x,y\right) \wedge Q\left( x\right) \right) \vee
R\left( x,y,z\right) \right)
\end{equation*}もまた論理式です。
\wedge R\left( x,y,z\right) \right) )
\end{equation*}は論理式であり、この論理式に量化記号\(\exists \)を作用させた、\begin{equation*}(\exists x\in X:(\left( \lnot P\left( x,y\right) \right) \rightarrow \left(
Q\left( x\right) \wedge R\left( x,y,z\right) \right) ))
\end{equation*}は論理式です。さらに、この論理式に量化記号\(\forall \)を作用させた、\begin{equation*}\left( \forall y\in Y:(\exists x\in X:(\left( \lnot P\left( x,y\right)
\right) \rightarrow \left( Q\left( x\right) \wedge R\left( x,y,z\right)
\right) ))\right)
\end{equation*}もまた論理式です。
論理式中の括弧の省略
上の最後の例のように、定義にもとづいて生成された論理式が括弧\(\left( \ \right) \)を多く含む場合には見づらいため、以下のルールのもとで括弧を省略できます。
- 一番外側の括弧は省略できる。
- 括弧を省略した結果、複数の論理演算子や量化記号が括弧によって遮られない形で存在している場合には、最初に\(\lnot ,\forall,\exists \)を作用させ、次に\(\vee ,\wedge ,\veebar \)を作用させ、最後に\(\rightarrow ,\leftrightarrow \)を作用させる。以上のルールを踏まえた上で、論理式中のある括弧を外して新たな式を得たときに、その式における論理演算子と量化記号の作用の順番がもとの論理式の内容と整合的であるならば、その括弧を省略できる。
\left( \lnot P\left( x,y\right) \right)
\end{equation*}の一番外側の括弧は省略できるため、これを、\begin{equation*}
\lnot P\left( x,y\right)
\end{equation*}とすることができます。
\left( \left( P\left( x,y\right) \wedge Q\left( x\right) \right) \vee
R\left( x,y,z\right) \right)
\end{equation*}の一番外側の括弧は省略できるため、これを、\begin{equation*}
\left( P\left( x,y\right) \wedge Q\left( x\right) \right) \vee R\left(
x,y,z\right)
\end{equation*}とすることができます。ちなみに、この論理式を、\begin{equation*}
P\left( x,y\right) \wedge Q\left( x_{1}\right) \vee R\left( x,y,z\right)
\end{equation*}とすることができません。なぜなら\(\wedge \)と\(\vee \)は作用の順番が等しいため、上のような形で括弧を外してしまうと、これが以下の2つ\begin{eqnarray*}&&\left( P\left( x,y\right) \wedge Q\left( x\right) \right) \vee R\left(
x,y,z\right) \\
&&P\left( x,y\right) \wedge \left( Q\left( x\right) \vee R\left(
x,y,z\right) \right)
\end{eqnarray*}のどちらの意味であるか判別できないからです。
\left( \forall y\in Y:\left( \exists x\in X:\left( \left( \lnot P\left(
x,y\right) \right) \rightarrow \left( Q\left( x\right) \wedge R\left(
x,y,z\right) \right) \right) \right) \right)
\end{equation*}の一番外側の括弧は省略できるため、これを、\begin{equation*}
\forall y\in Y:\left( \exists x\in X:\left( \left( \lnot P\left( x,y\right)
\right) \rightarrow \left( Q\left( x\right) \wedge R\left( x,y,z\right)
\right) \right) \right)
\end{equation*}とすることができます。\(\lnot \)は\(\rightarrow \)よりも先に作用させるルールであるため、\begin{equation*}\forall y\in Y:\left( \exists x\in X:\left( \lnot P\left( x,y\right)
\rightarrow \left( Q\left( x\right) \wedge R\left( x,y,z\right) \right)
\right) \right)
\end{equation*}としても問題ありません。
部分論理式
命題関数\(P\left( x,y\right) ,Q\left( x\right) \)に関する以下の式\begin{equation}\forall x\in X:\left( \lnot P\left( x,y\right) \wedge Q\left( x\right)
\right) \quad \cdots (1)
\end{equation}が論理式であることを順番に確認します。まず、命題関数は論理式とみなされるため、\begin{equation}
P\left( x,y\right) ,\ Q\left( x\right) \quad \cdots (2)
\end{equation}はいずれも論理式です。\(P\left( x,y\right) \)が論理式であるならば、それに論理演算子\(\lnot \)をさせて得られる、\begin{equation}\lnot P\left( x,y\right) \quad \cdots (3)
\end{equation}は論理式です。\(Q\left( x\right) \)と\(\lnot P\left( x,y\right) \)が論理式であるならば、それらに論理演算子\(\wedge \)を作用させて得られる、\begin{equation}\lnot P\left( x,y\right) \wedge Q\left( x\right) \quad \cdots (4)
\end{equation}は論理式です。したがってこれに量化記号\(\forall \)を作用