述語論理

9.命題関数

命題関数

変数に値を代入すると真偽が確定して命題となる文や式を命題関数という

コメント

高校論理の範囲で扱った「条件」である
論じる対象が集合\(S\)の時\(x\in S\)であり、\(P(x)\)は\(S\)を定義域とする命題関数と呼ぶ

命題関数\(P(x)\)「\(x\)は奇数である」の場合
\(P(3)\)は真の命題\(P(4)\)は偽の命題となる

10.全称命題

全称命題\(\forall\)

\(\forall x \in S (P(x))\)
集合Sのすべての要素で命題関数P(x)が真となる時真となる命題

コメント

\(\forall\)は全称量化記号と呼ばれ「すべての(For All)」の意味である
全称命題は集合Sの要素\({x_1,x_2,...x_n,...}\)に対して\(P(x_1) \land P(x_2) \land ...\land P(x_n) \land...\)という命題関数だと考えられる

命題関数\(P(x)\)「\(x\)は整数である」の時\(\forall x \in \mathbb{N}(P(x))\)は自然数はすべて整数なので真である

11.存在命題

存在命題\(\exists\)

\(\exists x \in S (P(x))\)
集合Sに命題関数P(x)が真となる要素が存在する時真となる命題

コメント

\(\exists\)は存在量化記号と呼ばれ「ある...存在する(Exists)」の意味である
全称命題は集合Sの要素\({x_1,x_2,...x_n,...}\)に対して\(P(x_1) \lor P(x_2) \lor ...\lor P(x_n) \lor...\)という命題関数だと考えられる

命題関数\(P(x)\)「\(x\)は自然数である」の時\(\forall x \in \{1,0.5,-1,-3\}(P(x))\)は1が自然数なので真である

12.束縛変数、自由変数

束縛変数、自由変数

対象の論理式内で量化記号\((\forall, \exists)\)の修飾を受けている変数を束縛変数といい、受けていない変数を自由変数とする。

\(\forall x \exists y P(x,y)\)を考える

\(\forall x \exists y P(x,y)\)において\(x,y\)は束縛変数
\(\exists y P(x,y)\)において\(x\)は自由変数、\(y\)は束縛変数
\(P(x,y)\)において\(x,y\)は自由変数

論理式

命題(変数)、命題関数、論理記号、量化記号などからなる式を論理式とし、自由変数を含まない論理式を閉じた論理式と呼ぶ
\(\forall x \exists y P(x,y)\)は閉じた論理式である

スコープ

\(\forall x \exists y P(x,y) \Leftrightarrow \forall x (\exists y P(x,y))\)
\(\exists x \forall y P(x,y)\Leftrightarrow \exists x (\forall y P(x,y))\)
である

13.述語論理

述語論理

命題論理に命題関数と量子化記号を加えて真偽を研究する分野である

演算順序

演算の優先度は
関数記号,\((\forall, \exists) \lnot,(∧,∨), \rightarrow\)である

例えば
「\(P \rightarrow \lnot P ∧\forall x\in S(Q(x)) \)」は
「\(P \rightarrow ((\lnot P) ∧(\forall x\in S(Q(x)))) \)」
の順番で演算する