述語論理において議論の対象となる最小概念は原子論理式です。原子論理式は命題関数を内包する概念です。原子論理式は単独で論理式とみなされます。また、原子論理式に論理演算子や量化記号を作用させて得られる式も論理式とみなされます。また、論理式に論理演算子や量化記号を作用させて得られる式も論理式です。
< 前のページ
次のページ >

原子論理式

述語論理において議論の対象となる論理的な主張や推論はいずれも、命題関数どうしを一定のルールのもとで組み合わせた式として表現されます。そのような式を論理式(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) \)である、という状況は起こり得ます。

例(原子論理式)
変数\(x,y\)の定義域\(X,Y\)はともにすべての整数からなる集合であり、以上を議論領域\(D\)とします。このとき、\begin{eqnarray*}
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\)における原子論理式です。
例(原子論理式)
変数\(a,b,C\)の定義域\(A,B,C\)はともにすべての実数からなる集合であり、以上を議論領域\(D\)とします。このとき、\begin{eqnarray*}
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\)における原子論理式です。
例(原子論理式)
変数\(f,g\)の定義域\(F,G\)はともにすべての関数からなる集合であり、以上を議論領域\(D\)とします。このとき、\begin{eqnarray*}
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\)における原子論理式とみなします。

例(原子論理式)
変数\(x,y\)の定義域\(X,Y\)はともにすべての整数からなる集合であり、以上を議論領域\(D\)とします。このとき、\begin{eqnarray*}
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\)における原子論理式です。
例(原子論理式)
変数\(a,b,C\)の定義域\(A,B,C\)はともにすべての実数からなる集合であり、以上を議論領域\(D\)とします。このとき、\begin{equation*}
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\)における原子論理式です。
例(原子論理式)
変数\(f,g\)の定義域\(F,G\)はともにすべての関数からなる集合であり、以上を議論領域\(D\)とします。このとき、\begin{equation*}
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\)で表します。

例(論理演算)
議論領域\(D\)において変数\(x\in X,y\in Y\)が定義されているとき、命題関数\(P\left( x\right) ,Q\left( y\right) ,R\left( x,y\right) \)はいずれも\(D\)における原子論理式です。値\(\overline{x}\in X,\overline{y}\in Y\)を任意に選ぶと、\(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) \)なども\(D\)における原子論理式です。個々の原子論理式は単独で\(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\)における論理式です。さらに、論理式に論理演算子を作用させたものは\(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\)で表します。

例(量化)
議論領域\(D\)において変数\(x\in X,y\in Y\)が定義されているとき、命題関数\(P\left( x\right) ,Q\left( y\right) ,R\left( x,y\right) \)はいずれも\(D\)における原子論理式です。値\(\overline{x}\in X,\overline{y}\in Y\)を任意に選ぶと、\(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) \)なども\(D\)における原子論理式です。個々の原子論理式は単独で\(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\)における論理式を以下のように再帰的に定義します。

  1. \(D\)の原子論理式は\(D\)の論理式である。
  2. \(A\)が\(D\)の論理式ならば、\(\left( \lnot A\right) \)は\(D\)の論理式である。
  3. \(A,B\)が\(D\)の論理式ならば、\(\left( A\wedge B\right) \)は\(D\)の論理式である。
  4. \(A,B\)が\(D\)の論理式ならば、\(\left( A\vee B\right) \)は\(D\)の論理式である。
  5. \(A,B\)が\(D\)の論理式ならば、\(\left( A\veebar B\right) \)は\(D\)の論理式である。
  6. \(A,B\)が\(D\)の論理式ならば、\(\left( A\rightarrow B\right) \)は\(D\)の論理式である。
  7. \(A,B\)が\(D\)の論理式ならば、\(\left( A\leftrightarrow B\right) \)は\(D\)の論理式である。
  8. \(A\)が\(D\)の論理式であり、\(x\in X\)が\(D\)の変数ならば、\(\left( \forall x\in X\ A\right) \)は\(D\)の論理式である。
  9. \(A\)が\(D\)の論理式であり、\(x\in X\)が\(D\)の変数ならば、\(\left( \exists x\in X\ A\right) \)は\(D\)の論理式である。
  10. 以上から論理式と判定されるものだけが論理式である。

論理式の例をいくつか挙げます。

例(論理式)
議論領域\(D\)において変数\(x\in X,y\in Y\)が定義されているとき、命題関数\(P\left( x,y\right) \)は原子論理式であるとともに論理式です。したがって、それに対して論理演算子を作用させた\(\lnot P\left( x,y\right) \)もまた論理式です。ちなみに、\(\left( P\left( x,y\right) \right) \)や\(\lnot \left( P\left( x,y\right) \right) \)などは論理式ではありません。
例(論理式)
議論領域\(D\)において変数\(x\in X,y\in Y,z\in Z\)が定義されているとき、命題関数\(P\left( x,y\right) ,Q\left( x\right) ,R\left( x,y,z\right) \)はいずれも\(D\)における原子論理式であるとともに論理式です。したがって、それらに論理演算子を作用させた\begin{equation*}
\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*}もまた論理式です。
例(論理式)
議論領域\(D\)において変数\(x\in X,y\in Y,z\in Z\)が定義されているとき、命題関数\(P\left( x,y\right) ,Q\left( x\right) ,R\left( x,y,z\right) \)はいずれも\(D\)における原子論理式であるとともに論理式です。したがって、それらに論理演算子を作用させた\begin{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) \)を多く含む場合には見づらいため、以下のルールのもとで括弧を省略できます。

  1. 一番外側の括弧は省略できる。
  2. 括弧を省略した結果、複数の論理演算子や量化記号が括弧によって遮られない形で存在している場合には、最初に\(\lnot ,\forall ,\exists \)を作用させ、次に\(\vee ,\wedge ,\veebar \)を作用させ、最後に\(\rightarrow ,\leftrightarrow \)を作用させる。以上のルールを踏まえた上で、論理式中のある括弧を外して新たな式を得たときに、その式における論理演算子と量化記号の作用の順番がもとの論理式の内容と整合的であるならば、その括弧を省略できる。
例(論理式の括弧の省略)
論理式\(\left( \lnot P\left( x,y\right) \right) \)の一番外側の括弧を省略すると\(\lnot P\left( x,y\right) \)を得ます。
例(論理式の括弧の省略)
論理式\(\left( \left( P\left( x,y\right) \wedge Q\left( x\right) \right) \vee R\left( x,y,z\right) \right) \)の一番外側の括弧を省略すると\(\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 Q\left( x_{1}\right) \vee R\left( x,y,z\right) \)と表すことはできません。なぜなら\(\wedge \)と\(\vee \)は作用の順番が等しいため、\(P\left( x,y\right) \wedge Q\left( x\right) \vee R\left( x,y,z\right) \)ではそれが\(\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) \)のどちらを意味するか判別できないからです。
例(論理式の括弧の省略)
論理式\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*}の一番外側の括弧を省略すると、\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*}としても問題ありません。

次回は部分論理式について学びます。

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

述語論理
アカウント
ログイン