原子論理式
述語論理において議論の対象となる論理的な主張や推論はいずれも、命題関数どうしを一定のルールのもとで組み合わせた式として表現されます。そのような式を論理式（formula）と呼びます。命題関数は論理式を構成する最小単位であるため、これを原子論理式（atomic formula）と呼ぶこともあります。また、述語論理において、個々の原子論理式は単独で論理式とみなされます。
議論領域\(D\)において定義されている変数\(x\in X\)に関する命題関数を\(P\left( x\right) \)などで表記します。変数が\(x\)であることが文脈から自明である場合、命題関数を\(P\)などで表記することもできます。ちなみに、\(P\left( x\right) \)という表記は二通りの意味で使われるため注意が必要です。「命題関数\(P\left( x\right) \)」という場合の\(P\left( x\right) \)は、それが命題関数であることを表す表記です。一方、「命題\(P\left( x\right) \)」という場合の\(P\left( x\right) \)は、定義域\(X\)に属する値\(x\)を命題関数\(P\left( x\right) \)に代入して得られる命題を表す表記です。両者を明示的に区別するために、\(X\)に属する値を\(\overline{x}\)で表し、それを命題関数\(P\left( x\right) \)に代入して得られる命題を\(P\left( \overline{x}\right) \)と表記することもできます。
命題関数が持つ変数の個数は1つである必要はありません。一般に、議論領域\(D\)において定義されている変数の中から\(n\)個の変数\(x_{1}\in X_{1},\cdots ,x_{n}\in 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) \)である、という状況は起こり得ます。
P\left( x\right) &:&x\text{は偶数である}
\\
Q\left( y\right) &:&y\text{は奇数である}
\\
R\left( x,y\right) &:&x+y\text{は偶数である} \\
S\left( x,y\right) &:&x+y\text{は奇数である}
\end{eqnarray*}などはいずれも命題関数であるため、これらは\(D\)における原子論理式です。
P\left( a,b,c\right) &:&ax^{2}+bx+c=0\text{は2つの実数解を持つ} \\
Q\left( a,b,c\right) &:&ax^{2}+bx+c=0\text{は1つの実数解を持つ} \\
R\left( a,b,c\right) &:&ax^{2}+bx+c=0\text{は実数解を持たない}
\end{eqnarray*}などはいずれも命題関数であるため、これらは\(D\)における原子論理式です。
P\left( f\right) &:&f\text{は微分可能である} \\
Q\left( g\right) &:&g\text{は微分可能である} \\
R\left( f,g\right) &:&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\)における原子論理式とみなします。
P\left( x\right) &:&x\text{は偶数である}
\\
Q\left( x,y\right) &:&x+y\text{は偶数である}
\end{eqnarray*}はともに\(D\)における原子論理式です。さらに、\begin{eqnarray*}
P\left( 1\right) &:&1\text{は偶数である}
\\
P\left( 2\right) &:&2\text{は偶数である}
\\
Q\left( 1,y\right) &:&1+y\text{は偶数である} \\
Q\left( x,3\right) &:&x+3\text{は偶数である} \\
Q\left( 2,3\right) &:&2+3\text{は偶数である}
\end{eqnarray*}なども\(D\)における原子論理式です。
P\left( a,b,c\right) :ax^{2}+bx+c=0\text{は実数解を持つ}
\end{equation*}は\(D\)における原子論理式です。さらに、\begin{eqnarray*}
P\left( 1,1,c\right) &:&x^{2}+x+c=0\text{は実数解を持つ} \\
P\left( 1,b,2\right) &:&x^{2}+bx+2=0\text{は実数解を持つ} \\
P\left( 2,1,3\right) &:&2x^{2}+x+3=0\text{は実数解を持つ}
\end{eqnarray*}なども\(D\)における原子論理式です。
P\left( f,g\right) :f\text{は}g\text{の導関数である}
\end{equation*}は\(D\)における原子論理式です。さらに、\begin{eqnarray*}
P\left( f,x^{2}+1\right) &:&f\text{は}x^{2}+1\text{の導関数である} \\
P\left( 2x,g\right) &:&2x\text{は}g\text{の導関数である} \\
P\left( 2x,x^{2}+1\right) &:&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\)で表します。
&&\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\)における論理式です。さらに、論理式に論理演算子を作用させたものは\(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\)で表します。
\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\)の論理式である。
- 以上から論理式と判定されるものだけが論理式である。
論理式の例をいくつか挙げます。
\left( P\left( x,y\right) \wedge Q\left( x\right) \right)
\end{equation*}は論理式であり、この論理式に論理演算子を作用させた\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*}もまた論理式です。
(\left( \lnot P\left( x,y\right) \right) \rightarrow \left( Q\left( x\right)
\wedge R\left( x,y,z\right) \right) )
\end{equation*}は論理式であり、この論理式に量化記号を作用させた\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*}は論理式です。さらに、この論理式に量化記号を作用させた、\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( \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*}の一番外側の括弧を省略すると、\begin{equation*}
\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) ))
\end{equation*}を得ます。\(\lnot \)は\(\rightarrow \)よりも先に作用させるルールであるため、\begin{equation*}
\forall y\in Y\ \left( \exists x\in X\ (\lnot P\left( x,y\right) \rightarrow
\left( Q\left( x\right) \wedge R\left( x,y,z\right) \right) )\right)
\end{equation*}としても問題ありません。
次回は部分論理式について学びます。
次へ進む 質問・コメントを投稿する 演習問題（プレミアム会員限定）
プレミアム会員だけが質問やコメントを投稿・閲覧できます。