論理学で使う用語一覧

(1)論理演算子・論理結合子

0項演算子である命題定数や1項演算子である否定\(\lnot\)と2項演算子\(\land,\lor,\rightarrow,\leftarrow,\leftrightarrow,\uparrow,\downarrow,\nrightarrow,\nleftarrow,\nleftrightarrow\)や3項演算子などの演算子を論理演算子・論理結合子といいます。
ただし、量化子と括弧は含みません。
また、論理結合子は2項演算子以外も含みます。

(2)命題

真偽が決まっている記号列を命題という。

(3)素論理式

原子式と論理演算子と括弧で表される式を素論理式といいます。
命題変数\(P\)や述語式\(P\left(x\right)\)や論理積\(P\left(x\right)\land Q\left(y\right)\)などは素論理式です。
量化子は使ってはいけません。

(4)論理式

文法的に正しい記号列を論理式という。
素論理式と量化子で表される式のことです。
\(x\)によって真偽の値の異なる\(P\left(x\right)\)は命題ではありませんが、文法的に正しい記号列なので論理式となります。
命題や素論理式は論理式となります。

(5)命題論理

命題変数と論理演算子と括弧を用いて表される論理式を命題論理という。

(6)述語論理

述語式と論理演算子と量化子と括弧を用いて表される論理式を述語論理という。
述語論理は1階述語論理から高階述語論理を全て含みますが、1階述語論理に限定することもあります。
また、述語論理ならば論理式ですが論理式でも述語論理とは限りません。
例えば、様相論理では\(P\)が必然ならば\(Q\)は可能であるというのは論理式で\(\square P\rightarrow\diamondsuit Q\)と表すことができますが、これは述語論理ではありません。

(7)\(n\)階述語論理

量化子を個体変数にのみ作用させることができる述語論理を1階述語論理といいます。
1階述語論理では量化子を述語や関数に使うことはできません。
量化子を個体変数と述語や関数に作用させることができる述語論理を2階述語論理といいます。
例えば量化子を述語\(P\)に作用させると、\(x=y\Leftrightarrow\forall P,P\left(x\right)\leftrightarrow P\left(y\right)\)のようになり、これはライプニッツの等価原理です。
また、数学的帰納法は\(\forall P,\left(\left(P\left(0\right)\land\forall k\in\mathbb{N}_{0},P\left(k\right)\rightarrow P\left(k+1\right)\right)\rightarrow\forall n\in\mathbb{N}_{0},P\left(n\right)\right)\)と表すことができます。
1階述語論理では変数は個体変数\(x\)となり、原子式\(P\left(x\right)\)の\(P\)は固定で\(x\)は可変なので\(\forall xP\left(x\right)\)は論理式となります。
2階述語論理では変数は個体変数\(x\)と2階の変数である述語変数\(P\)となり、原子式\(P\left(x\right)\)の\(P\)と\(x\)は可変なので、\(\forall P\forall xP\left(x\right)\)は論理式となります。
ここで1階述語論理の変数は個体変数\(x\)であり、2階述語論理の変数は個体変数\(x\)と述語変数\(P\)であり、述語変数\(P\)は個体変数\(x\)を引数にとり述語式\(P\left(x\right)\)になる。
3階述語論理の変数は個体変数\(x\)と2階の変数である述語変数\(P\)と3階の変数\(\mathcal{X}\)となり、3階の変数\(\mathcal{X}\)は述語変数\(P\)を変数にとり\(\mathcal{X}\left(P\right)\)は述語式になります。
これより、3階述語論理の述語式は\(\mathcal{X}\left(P\right)\)と\(P\left(x\right)\)の2種類存在して、\(\forall\mathcal{X}\forall P\mathcal{X}\left(P\right)\)と\(\forall P\forall xP\)\(\left(x\right)\)は論理式になります。

論理式を構成するもの

(8)命題定数

真\(\top\)または偽\(\bot\)で固定された値を命題定数という。
また、値を真または偽に固定した命題変数\(P\)も命題定数という。

(9)命題変数

値が真\(\top\)か偽\(\bot\)になる変数を命題変数といい、\(P\)や\(Q\)などで表される。

(10)項

項は次の個体定数、個体変数、関数値を有限回の操作で繰り返し、再帰的に定義されるものを項という。
\(a,b\)を個体定数として\(x,y\)を個体変数として、\(f,g\)を関数とすると、\(a+b,x+y,a+x,f\left(a+x\right),f\left(a,g\left(b+x\right)+y\right)\)などは項となります。

(a)個体定数

\(0,1,\pi,a,b,c\)などの定数を個体定数といい項となる。

(b)個体変数

\(x,y,z\)などの変数を個体変数といい項となる。

(c)関数値

非負整数\(n\in\mathbb{N}_{0}\)個の項\(x_{1},x_{2},\cdots,x_{n}\)を引数にとり、項を返すものを関数記号\(f\)で表すと関数値\(f\left(x_{1},x_{2},\cdots,x_{n}\right)\)は項となる。
項となるのものは「もの」で、真偽値や量化子や演算子などは項にはなりません。
引数が0個の関数の関数値は個体定数となります。
述語は真偽値を返しますが、関数は真偽値を返してはいけません。

(11)述語(命題関数)

非負整数\(n\in\mathbb{N}_{0}\)個の項\(x_{1},x_{2},\cdots,x_{n}\)を引数として、真または偽を返す関数\(P\)を述語や命題関数といい、\(P\left(x\right)\)や\(P\left(x_{1},x_{2},\cdots,x_{n}\right)\)などで表し、述語記号は\(P\)で\(P\left(x\right)\)を述語式などといいます。
\(x,y\)を固定変数として、\(x<y\)なども述語式となります。
項は1つでなくても0個でも複数でも構いません。
項が1つの述語を1項述語や単項述語といい、項が2つの述語を2項述語といいます。
引数となる項が0個である述語\(P\)は引数をとらずに述語式\(P\)で表され、このとき、述語式\(P\)は命題変数となります。
項で使う関数と区別するために命題関数ではなく述語を使うことのほうが多いです。

(12)原子式

\(n\in\mathbb{N}_{0}\)項述語\(P\)と\(n\)個の項\(x_{1},x_{2},\cdots,x_{n}\)で表される述語式\(P\left(x_{1},x_{2},\cdots,x_{n}\right)\)を原子式という。
原子式は真偽が決まる最小の論理式です。
0項述語式である命題変数\(P\)や1項述語式\(P\left(x\right)\)や2項述語式\(x<y\)などが原子式となります。
原子式と述語式とは同一のものとなります。
原子式に論理演算子や量化子は使っては行けません。