原子論理式
述語論理では議論に先立ち議論領域\begin{equation*}
D
\end{equation*}を設定する必要があります。つまり、議論の対象となるすべての変数と、それらの定義域を設定する必要があるということです。
述語論理における議論の最小単位は命題関数です。議論に先立って議論領域\(D\)を設けることは、\(D\)において定義されている変数に関する命題関数だけが議論の対象になり得ることを意味します。ただし、それぞれの命題関数は、議論領域\(D\)において定義されているすべての変数を自身の変数として持つ必要はありません。議論領域\(D\)が定義する変数の中の特定の変数だけを自身の変数として持つ命題関数や、変数を1つも持たない命題関数なども考察対象となります。逆に、議論領域\(D\)において定義されていない変数を自身の変数として持つ命題関数は議論の対象になりません。
1つの変数\(x\)に関する命題関数を表す記号として、アルファベットの大文字を用いて、\begin{equation*}P\left( x\right) ,Q\left( x\right) ,\cdots
\end{equation*}などを利用します。命題関数\(P\left( x\right) \)の変数\(x\)の定義域が\(X\)であることを明示したい場合には、\begin{equation*}P\left( x\right) \quad \left( x\in X\right)
\end{equation*}と表記します。
有限\(n\)個の変数に関する命題関数を表す記号として、アルファベットの大文字を用いて、\begin{equation*}P\left( x_{1},\cdots ,x_{n}\right) ,Q\left( x_{1},\cdots ,x_{n}\right)
,\cdots
\end{equation*}などを利用します。命題関数\(P\left( x_{1},\cdots ,x_{n}\right) \)の変数\(x_{1},\cdots ,x_{n}\)の定義域が\(X_{1},\cdots ,X_{n}\)であることを明示したい場合には、\begin{equation*}P\left( x_{1},\cdots ,x_{n}\right) \quad \left( x_{1}\in X_{1},\cdots
,x_{n}\in X_{n}\right)
\end{equation*}または、\begin{equation*}
P\left( x_{1},\cdots ,x_{n}\right) \quad \left( \left( x_{1},\cdots
,x_{n}\right) \in X_{1}\times \cdots \times X_{n}\right)
\end{equation*}などと表記します。
述語論理において議論の対象となる主張はいずれも命題関数どうしを一定のルールのもとで組み合わせることにより得られる式として表現されます。そのような式を論理式（formula）と呼びます。以下では論理式という概念を形式的に定義します。
まず、述語論理において個々の命題関数は単独で論理式とみなされます。このような事情もあり、命題関数のことを原子論理式（atomic formula）と呼ぶこともできます。
&&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\)における命題関数\begin{equation*}P\left( x_{1},\cdots ,x_{n}\right)
\end{equation*}が与えられた状況において、変数\(x_{1},\cdots ,x_{n}\)の中から特定の変数\(x_{1},\cdots ,x_{m}\ \left( m\leq n\right) \)を任意に選びます。その上で、これらの変数\(x_{1},\cdots ,x_{m}\)に具体的な値\(\overline{x}_{1},\cdots ,\overline{x}_{m}\)を代入すれば、残りの変数\(x_{m+1},\cdots ,x_{n}\)に関する命題関数\begin{equation*}P\left( \overline{x}_{1},\cdots ,\overline{x}_{m},x_{m+1},\cdots
,x_{n}\right)
\end{equation*}が得られます。これもまた\(D\)における原子論理式とみなします。特に、\(m=n\)の場合には、すべての変数\(x_{1},\cdots ,x_{n}\)に具体的な値\(\overline{x}_{1},\cdots ,\overline{x}_{n}\)を代入することとなるため、変数を持たない命題\begin{equation*}P\left( \overline{x}_{1},\cdots ,\overline{x}_{n}\right)
\end{equation*}が得られます。これもまた\(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\)の少なくとも1つに具体的な値を代入することにより得られる以下の主張\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 \)に対して行う操作を表す記号\begin{equation*}\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow
\end{equation*}を導入した上で、これらを原子論理式に作用させることにより新たな論理式を作り出します。これらの記号を論理演算子（logical operators）や論理結合子（logical connectives）などと呼び、論理演算子が表す操作を論理演算（logical operation）と呼びます。
それぞれの論理演算子の意味は後ほど解説することとして、まずは論理式という概念を形式的に定義します。
議論領域\(D\)における原子論理式\(P\)に論理演算子\(\lnot \)を作用させることにより得られる論理式を、\begin{equation*}\lnot P
\end{equation*}で表記し、これを\(P\)の否定（negation of \(P\)）と呼びます。
議論領域\(D\)における原子論理式\(P,Q\)に論理演算子\(\wedge \)を作用させることにより得られる論理式を、\begin{equation*}P\wedge Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の論理積（logical productof \(P\) and \(Q\)）と呼びます。
議論領域\(D\)における原子論理式\(P,Q\)に論理演算子\(\vee \)を作用させることにより得られる論理式を、\begin{equation*}P\vee Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の論理和（logical productof \(P\) and \(Q\)）と呼びます。
議論領域\(D\)における原子論理式\(P,Q\)に論理演算子\(\veebar \)を作用させることにより得られる論理式を、\begin{equation*}P\veebar Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の排他的論理和（exclusive disjunction of \(P\) and \(Q\)）と呼びます。
議論領域\(D\)における原子論理式\(P,Q\)に論理演算子\(\rightarrow \)を作用させることにより得られる論理式を、\begin{equation*}P\rightarrow Q
\end{equation*}で表記し、これを\(P\)から\(Q\)への含意（implication from \(P\) to \(Q\)）と呼びます。
議論領域\(D\)における原子論理式\(P,Q\)に論理演算子\(\leftrightarrow \)を作用させることにより得られる論理式を、\begin{equation*}P\leftrightarrow Q
\end{equation*}と表記し、これを\(P\)と\(Q\)の同等（equivalent of \(P\) and \(Q\)）と呼びます。
これらの論理式の意味については後ほど解説します。
&&Q\left( y\right) \\
&&R\left( x,y\right)
\end{eqnarray*}はいずれも\(D\)における原子論理式であるため論理式でもあります。変数\(x,y\)がとり得る具体的な値\(\overline{x},\overline{y}\)を任意に選んだとき、\begin{eqnarray*}&&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{eqnarray*}などはいずれも\(D\)における原子論理式であるため論理式でもあります。原子論理式に論理演算子を作用させたものは\(D\)における論理式であるため、\begin{eqnarray*}&&\lnot P\left( x\right) \\
&&P\left( x\right) \wedge Q\left( \overline{y}\right) \\
&&P\left( \overline{x}\right) \vee R\left( \overline{x},\overline{y}\right)
\\
&&Q\left( \overline{y}\right) \rightarrow R\left( x,\overline{y}\right)
\end{eqnarray*}などはいずれも\(D\)における論理式です。
原子論理式に量化記号を作用させた式は論理式
述語論理では論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)の他にも以下の2つの演算子\begin{equation*}\forall ,\exists
\end{equation*}を導入した上で、これらを議論領域\(D\)における原子論理式へ作用させることにより新たな論理式を作り出します。
記号\(\forall \)は all ないし any の頭文字である A を逆さにしたものであり、これを全称記号（universal quantifier）や全称量化記号などと呼びます。記号\(\exists \)は exist の頭文字であるEを逆さにしたものであり、これを存在記号（existential quantifier）や存在量化記号などと呼びます。全称記号と存在記号を総称して量化記号（quantifier）や限定記号などと呼び、原子論理式に量化記号を作用させることを量化（quantification）と呼びます。
量化記号の意味については後ほど解説することとして、まずは論理式という概念を形式的に定義します。
議論領域\(D\)における原子論理式\(P\)と変数\(x\in X\)が与えられたとき、\(P\)に\(\forall \)を作用させることにより得られる論理式を、\begin{equation*}\forall x\in X:P
\end{equation*}で表記し、これを全称命題（universal proposition）と呼びます。
議論領域\(D\)における原子論理式\(P\)と変数\(x\in X\)が与えられたとき、\(P\)に\(\exists \)を作用させることにより得られる論理式を、\begin{equation*}\exists x\in X:P
\end{equation*}で表記し、これを存在命題（existential proposition）と呼びます。
これらの論理式の意味については後ほど解説します。
&&Q\left( y\right) \\
&&R\left( x,y\right)
\end{eqnarray*}が与えられているものとします。これらは\(D\)における原子論理式です。変数\(x,y\)がとり得る具体的な値\(\overline{x},\overline{y}\)を任意に選んだとき、\begin{eqnarray*}&&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{eqnarray*}などはいずれも\(D\)における原子論理式であるため論理式でもあります。原子論理式に量化記号を作用させたものも\(D\)における論理式であるため、\begin{eqnarray*}\forall x &\in &X:P\left( x\right) \\
\forall x &\in &X:P\left( \overline{x}\right) \\
\forall x &\in &X:Q\left( y\right) \\
\forall y &\in &Y:Q\left( y\right) \\
\forall y &\in &Y:R\left( x,y\right) \\
\forall x &\in &X:R\left( x,\overline{y}\right)
\end{eqnarray*}などはいずれも\(D\)における論理式です。
論理式に論理演算子と量化記号を作用させた式は論理式
述語論理では議論領域\(D\)における原子論理式\(P,Q,\cdots \)に対して論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)や量化記号\(\forall ,\exists \)を作用させることにより論理式を生成するだけでなく、そのようにして生成された論理式\(A,B,\cdots \)に対して再び論理演算子\(\lnot ,\wedge ,\vee ,\veebar,\rightarrow ,\leftrightarrow \)や量化記号\(\forall ,\exists \)を作用させることによる得られる式もまた論理式とみなします。
それぞれの論理演算子および量化記号の意味は後ほど解説することとして、まずは論理式という概念を形式的に定義します。
議論領域\(D\)における論理式\(A\)に論理演算子\(\lnot \)を作用させることにより得られる論理式を、\begin{equation*}\lnot A
\end{equation*}で表記し、これを\(A\)の否定（negation of \(A\)）と呼びます。
議論領域\(D\)における論理式\(A,B\)に論理演算子\(\wedge \)を作用させることにより得られる論理式を、\begin{equation*}A\wedge B
\end{equation*}で表記し、これを\(A\)と\(B\)の論理積（logical productof \(A\) and \(B\)）と呼びます。
議論領域\(D\)における論理式\(A,B\)に論理演算子\(\vee \)を作用させることにより得られる論理式を、\begin{equation*}A\vee B
\end{equation*}で表記し、これを\(A\)と\(B\)の論理和（logical productof \(A\) and \(B\)）と呼びます。
議論領域\(D\)における論理式\(A,B\)に論理演算子\(\veebar \)を作用させることにより得られる論理式を、\begin{equation*}A\veebar B
\end{equation*}で表記し、これを\(A\)と\(B\)の排他的論理和（exclusive disjunction of \(A\) and \(B\)）と呼びます。
議論領域\(D\)における論理式\(A,B\)に論理演算子\(\rightarrow \)を作用させることにより得られる論理式を、\begin{equation*}A\rightarrow B
\end{equation*}で表記し、これを\(A\)から\(B\)への含意（implication from \(A\) to \(B\)）と呼びます。
議論領域\(D\)における論理式\(A,B\)に論理演算子\(\leftrightarrow \)を作用させることにより得られる論理式を、\begin{equation*}A\leftrightarrow B
\end{equation*}と表記し、これを\(A\)と\(B\)の同等（equivalent of \(A\) and \(B\)）と呼びます。
議論領域\(D\)における論理式\(A\)と変数\(x\in X\)が与えられたとき、\(A\)に\(\forall \)を作用させることにより得られる論理式を、\begin{equation*}\forall x\in X:A
\end{equation*}と表記し、これを全称命題（universal proposition）と呼びます。
議論領域\(D\)における論理式\(A\)と変数\(x\in X\)が与えられたとき、\(A\)に\(\exists \)を作用させることにより得られる論理式を、\begin{equation*}\exists x\in X:A
\end{equation*}と表記し、これを存在命題（existential proposition）と呼びます。
これらの論理式の意味については後ほど解説します。
&&Q\left( y\right) \\
&&R\left( x,y\right)
\end{eqnarray*}が与えられているものとします。これらは\(D\)における原子論理式です。変数\(x,y\)がとり得る具体的な値\(\overline{x},\overline{y}\)を任意に選んだとき、\begin{eqnarray*}&&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{eqnarray*}などはいずれも\(D\)における原子論理式であるため論理式でもあります。原子論理式に量化記号を作用させたものも\(D\)における論理式であるため、\begin{eqnarray*}\forall x &\in &X:P\left( x\right) \\
\forall x &\in &X:P\left( \overline{x}\right) \\
\forall x &\in &X:Q\left( y\right) \\
\forall y &\in &Y:Q\left( y\right) \\
\forall y &\in &Y:R\left( x,y\right) \\
\forall x &\in &X:R\left( x,\overline{y}\right)
\end{eqnarray*}などはいずれも\(D\)における論理式です。論理式に論理演算子や量化記号を作用させたものも\(D\)における論理式であるため、
\begin{gather*}
\left( \forall x\in X:P\left( x\right) \right) \rightarrow P\left( \overline{x}\right) \\
\exists x\in X:\left( P\left( x\right) \wedge Q\left( x\right) \right) \\
\left( \forall x\in X:P\left( x\right) \right) \rightarrow \left( \forall
x\in X:R\left( x,\overline{y}\right) \right)
\end{gather*}などはいずれも\(D\)における論理式です。
論理式の再帰的定義
繰り返しになりますが、述語論理において原子論理式\(P,Q,\cdots \)は単独で論理式とみなされます。また、原子論理式に論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)や量化記号\(\forall ,\exists \)を作用させることで得られる式\(A,B,\cdots \)も論理式とみなされます。また、そのようにして得られた論理式\(A,B,\cdots \)に論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)や量化記号\(\forall ,\exists \)を作用させることで得られる式も論理式です。
以上を踏まえた上で、議論領域\(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*}もまた論理式です。ちなみに、\begin{gather*}
\left( P\left( x,y\right) \right) \\
\lnot \left( P\left( x,y\right) \right)
\end{gather*}などは論理式ではありません。なぜなら、これらが論理式であることを認めるルールは存在しないからです。
\end{equation*}もまた論理式です。以上の事実とルール4より、\begin{equation}
\left( \left( P\left( x,y\right) \wedge Q\left( x\right) \right) \vee
R\left( x,y,z\right) \right) \quad \cdots (1)
\end{equation}もまた論理式です。括弧の位置から明らかであるように、最初に論理積\(\left( P\left( x,y\right) \wedge Q\left( x\right) \right) \)をとった上で、この論理積\(\left( P\left( x,y\right)\wedge Q\left( x\right) \right) \)と残された命題関数\(R\left( x,y,z\right) \)の論理和をとることにより得られる論理式が\(\left( 1\right) \)です。同様の理由により、\begin{equation}\left( P\left( x,y\right) \wedge \left( Q\left( x\right) \vee R\left(
x,y,z\right) \right) \right) \quad \cdots (2)
\end{equation}もまた論理式です。括弧の位置から明らかであるように、最初に論理和\(\left( Q\left( x\right) \vee R\left( x,y,z\right) \right) \)をとった上で、この論理和\(\left( Q\left(x\right) \vee R\left( x,y,z\right) \right) \)と残された命題関数\(P\left( x,y\right) \)の論理積をとることにより得られる論理式が\(\left( 2\right) \)です。\(\left( 1\right) \)と\(\left(2\right) \)では括弧の位置が異なるため、これらを異なる論理式として区別する必要があります。
\wedge R\left( x,y,z\right) \right) )
\end{equation*}は論理式です。以上の事実とルール9より、\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*}は論理式です。以上の事実とルール8より、\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) \)が論理式であるならば、これに否定を作用させることにより得られる、\begin{equation}\lnot P\left( x,y\right) \quad \cdots (3)
\end{equation}は論理式です。\(Q\left( x\right) \)と\(\lnot P\left( x,y\right) \)が論理式であるならば、これらに論理積を作用させることにより得られる、\begin{equation}\lnot P\left( x,y\right) \wedge Q\left( x\right) \quad \cdots (4)
\end{equation}は論理式です。したがってこれに量化記号\(\forall \)を作用させることにより得られる、\begin{equation*}\forall x\in X:\left( \lnot P\left( x,y\right) \wedge Q\left( x\right)
\right)
\end{equation*}は論理式ですが、これは\(\left( 1\right) \)に他なりません。以上で確認が完了しました。
論理式\(\left( 1\right) \)を生成する過程において登場した論理式\(\left( 2\right) ,\left( 3\right),\left( 4\right) \)に\(\left( 1\right) \)自身を加えたものを、もとの論理式\(\left( 1\right) \)の部分論理式（subformula）と呼びます。つまり、論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。また、論理式自身をその論理式の部分論理式とみなします。
部分論理式を以下のように再帰的に定義します。
- 論理式\(A\)自身は\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)を用いて\(\left( \lnot B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式でもある。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\wedge C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\vee C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\veebar C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\rightarrow C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\leftrightarrow C\right) \)の形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)と変数\(x\in X\)を用いて\(\left( \forall x\in X:B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)と変数\(x\in X\)を用いて\(\left( \exists x\in X:B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式である。
\end{equation*}の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\begin{array}{cc}
\hline
論理式 & 部分論理式 \\ \hline
P\left( x\right) & P\left( x\right) \\ \hline
\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) \\
\hline
\end{array}$$
\end{equation*}の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\begin{array}{cc}
\hline
論理式 & 部分論理式 \\ \hline
P\left( x\right) & P\left( x\right) \\ \hline
Q\left( x\right) & Q\left( x\right) \\ \hline
\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) \\
\hline
\lnot P\left( x\right) \wedge Q\left( y\right) & P\left( x\right) ,\ \lnot P\left( x\right) ,\ Q\left( x\right) ,\ \lnot P\left( x\right) \wedge Q\left( y\right) \\ \hline
\end{array}$$
\end{equation*}の部分論理式を特定します。下の表の左側の列には論理式が、右側の列にはその部分論理式が記されています。
$$\begin{array}{cc}
\hline
論理式 & 部分論理式 \\ \hline
P\left( x\right) & P\left( x\right) \\ \hline
\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) \\
\hline
\forall x\in X:\lnot P\left( x\right) & P\left( x\right) ,\ \lnot P\left( x\right) ,\ \forall x\in X:\lnot P\left( x\right) \\ \hline
\end{array}$$
演習問題
\end{equation*}は論理式でしょうか。論理式である場合には括弧を外してください。
y\right) \vee \left( \lnot R\left( x,y\right) \right) \right) \right)
\end{equation*}は論理式でしょうか。論理式である場合には括弧を外してください。
\end{equation*}は論理式でしょうか。論理式である場合には括弧を外してください。
x,y\right) \right) \right) \wedge \left( \forall y\in Y:Q\left( y\right)
\right) \right)
\end{equation*}は論理式でしょうか。論理式である場合には括弧を外してください。
\right)
\end{equation*}は論理式でしょうか。論理式である場合には括弧を外してください。
\right)
\end{equation*}の部分論理式をすべて特定してください。
R\left( x,y\right) \right)
\end{equation*}の部分論理式をすべて特定してください。
\wedge \forall y\in Y:Q\left( y\right)
\end{equation*}の部分論理式をすべて特定してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】