述語論理での恒真式

14.命題関数の恒真式

含意を含む恒真式

\(\forall x(P(x)\rightarrow Q(x))=T\)の時\(P(x) \Rightarrow Q(x)\)とし
この時
\(P(x)\)は\(Q(x)\)の十分条件
\(Q(x)\)は\(P(x)\)の必要条件

「\(x\)は自然数」\(\rightarrow\)「\(x\)は整数」は任意の\(x\)で真となるので、「\(x\)は自然数」\(\Rightarrow\)「\(x\)は整数」

同値を含む恒真式

\(\forall x(P(x)\leftrightarrow Q(x))=T\)の時\(P(x) \Leftrightarrow Q(x)\)とし
この時
\(P(x)\)と\(Q(x)\)は互いの必要十分条件という

命題関数の恒真式

命題論理での恒真式は命題の真理値によらず成り立った。つまり構成する命題が命題関数であっても任意の値で成立する。

命題関数の主な性質

\( P(x) \land T \Leftrightarrow P(x)\)    \(P(x) \land F \Leftrightarrow F\)
\( P(x) \lor T \Leftrightarrow T\)    \(P(x) \lor F \Leftrightarrow P(x)\)
\( \lnot \lnot P(x) \Leftrightarrow P(x)\)
\(P(x)\land Q(x) \Leftrightarrow Q(x) \land P(x)\)
\(P(x)\lor Q(x) \Leftrightarrow Q(x) \lor P(x)\)
\((P(x)\land Q(x)) \land R(x) \Leftrightarrow P(x)\land ( Q(x) \land R(x))\)
\((P(x)\lor Q(x) \lor R(x)\Leftrightarrow P(x)\lor ( Q(x) \lor R(x))\)
\(P(x)\land (Q(x) \lor R(x)) \Leftrightarrow (P(x)\land Q(x)) \lor(Q(x) \land R(x))\)
\(P(x)\lor (Q(x) \land R(x)) \Leftrightarrow (P(x)\lor Q(x))\land ( Q(x) \lor R(x))\)
\(P(x)\land (P(x) \lor Q(x)) \Leftrightarrow P(x)\)
\(P(x)\lor (P(x) \land Q(x)) \Leftrightarrow P(x)\)
\(P(x)∨(\lnot P(x)) \Leftrightarrow T\)
\(P(x) \land (\lnot P(x)) \Leftrightarrow F\)
\(P(x) \land P(x) \Leftrightarrow P(x) \\P(x) \lor P(x) \Leftrightarrow P(x)\)
\(P(x) \rightarrow Q(x)   \Leftrightarrow (\lnot Q(x)) \rightarrow (\lnot P(x))\)
\( \lnot (P(x)∧Q(x)) \Leftrightarrow   \lnot {P(x)}∨\lnot {Q(x)} \\ \lnot (P(x)∨Q(x))\Leftrightarrow \lnot{P(x)}∧ \lnot{Q(x)}\)

15.量化記号の性質

性質1

\(\forall x \forall y P(x,y) \Leftrightarrow \forall y \forall x P(x,y)\)
\(\exists x \exists y P(x,y)\Leftrightarrow \exists y \exists x P(x,y)\)

性質2

\(\forall x P(x) \Rightarrow \exists x P(x)\)

性質3

\(\exists x\forall y  P(x,y) \Rightarrow \forall y\exists x P(x,y)\)

コメント

もし\(\exists x\forall y  P(x,y)\)が真だとわかっている場合同時に\(\forall y\exists x P(x,y)\)も真であることがわかるということである

16.述語論理での性質

ドモルガンの法則

\(\lnot\forall xP(x)\Leftrightarrow \exists x\lnot P(x)\)
\(\lnot\exists xP(x)\Leftrightarrow \forall x \lnot P(x)\)

性質1

\(\forall xP(x) \land \forall xQ(x) \Leftrightarrow \forall x(P(x)\land Q(x))\)
\(\exists xP(x) \land \exists xQ(x)\Leftrightarrow \exists x(P(x)\lor Q(x))\)

性質2

\(\forall xP(x) \lor \forall xQ(x)\Rightarrow \forall x(P(x)\lor Q(x))\)
\(\exists xP(x) \land \exists xQ(x)\Rightarrow \exists x(P(x)\land Q(x))\)

性質3

\(\exists x(P(x) \rightarrow Q(x))\Leftrightarrow \forall xP(x) \rightarrow \exists xQ(x)\)

性質4

\(\forall x(P(x) \rightarrow Q(x)) \Rightarrow \forall xP(x) \rightarrow \forall xQ(x)\)
\(\forall x(P(x) \rightarrow Q(x)) \Rightarrow \exists xP(x) \rightarrow \exists xQ(x)\)

数学における論理

このように様々な組み合わせから多様な性質が導かれ、このような一般的な性質を導き出すのが述語論理の役割とも言える。また、数学はこの論理式に具体的な要素を入れて法則を見出すことで構築されていく。