Science Metro

述語論理

$命題関数$

命題関数

P (x)

:

x

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

$全称命題$

\forall x (P (x))

すべての値で命題関数

P (x)

が真となる時真となる命題

$存在命題$

\exists x (P (x))

命題関数

P (x)

が真となる値が存在する時真となる命題

$スコープ$

\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))

$演算順序$

演算の優先度は

関数記号,

(\forall, \exists) \neg, (\land, \lor), \to

$含意を含む恒真式$

P (x) \Rightarrow Q (x) :

\forall x (P (x) \to Q (x)) = T

Q (x)

の十分条件:

P (x)

P (x)

の必要条件:

Q (x)

$同値を含む恒真式$

P (x) \Leftrightarrow Q (x) :

\forall x (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)

\neg\neg 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) \lor (\neg P (x)) \Leftrightarrow T

P (x) \land (\neg P (x)) \Leftrightarrow F

P (x) \land P (x) \Leftrightarrow P (x)

P (x) \lor P (x) \Leftrightarrow P (x)

P (x) \to Q (x) \Leftrightarrow (\neg Q (x)) \to (\neg P (x))

\neg (P (x) \land Q (x)) \Leftrightarrow \neg P (x) \lor \neg Q (x)

\neg (P (x) \lor Q (x)) \Leftrightarrow \neg P (x) \land \neg Q (x)

$性質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)

$ドモルガンの法則$

\neg\forall x P (x) \Leftrightarrow \exists x \neg P (x)

\neg\exists x P (x) \Leftrightarrow \forall x \neg P (x)

$性質1$

\forall x P (x) \land \forall x Q (x) \Leftrightarrow \forall x (P (x) \land Q (x))

\exists x P (x) \land \exists x Q (x) \Leftrightarrow \exists x (P (x) \lor Q (x))

$性質2$

\forall x P (x) \lor \forall x Q (x) \Rightarrow \forall x (P (x) \lor Q (x))

\exists x P (x) \land \exists x Q (x) \Rightarrow \exists x (P (x) \land Q (x))

$性質3$

\exists x (P (x) \to Q (x)) \Leftrightarrow \forall x P (x) \to \exists x Q (x)

$性質4$

\forall x (P (x) \to Q (x)) \Rightarrow \forall x P (x) \to \forall x Q (x)

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