【数学】命題と論理式，その証明のチートシート

ド・モルガンの法則

$\overline{P\wedge Q} 　is　\overline{P} \vee \overline{Q}$
$\overline{P\vee Q} 　is　\overline{P} \wedge \overline{Q}$

存在記号

$\exists x : P(x) \; s.t. \; Q(x)$
ex. $\exists x \in \mathbb{N} \; \; s.t. \; \; x \: is \: odd$

$\exists x : P(x) \; s.t. \; Q(x)$ の否定

$\overline{ \exists x : P(x) \; s.t. \; Q(x) } \equiv \forall x : P(x) , \overline{Q(x)}$

$\exists x : P(x) \; s.t. \; Q(x)$ の証明

How to prove $\exists x : P(x) \; s.t. \; Q(x)$

Find x so that P(x) is true.

Prove that Q(x) is true.

全称記号

$\forall x : P(x) , Q(x)$
ex. $\forall x \in \mathbb{Z} , x^2+x+1 > 0$

$\forall x : P(x) , Q(x)$ の否定

$\overline{ \forall x : P(x) , Q(x) } \equiv \exists x : P(x) \; s.t. \; \overline{Q(x)}$

$\forall x : P(x) , Q(x)$ の証明

How to prove $\forall x : P(x) , Q(x)$

Let x be any element satisfying P(x).

Prove Q(x)

命題が偽であることの証明

Statement X.

It is True if we prove X.

It is False if we prove the negation $\overline{X}$

全称記号の書き換え

以下の3式はすべて同じ意味

$\forall x \in X : P(x), Q(x)$
$\forall x \in X , (P(x) \Rightarrow Q(x))$
$( (x \in X) \wedge P(x) ) \Rightarrow Q(x)$

$\Rightarrow$ の証明

For " $P \Rightarrow Q$ ", P is hypothesis or assumption, Q is conclusioin.

In order to prove " $P \Rightarrow Q$ ", we have to prove Q by using the assumption that P is True.

推論のルール

Let P, Q, R be statements.

$( (P \Rightarrow Q ) \wedge (Q \Rightarrow R) ) \Rightarrow (P \Rightarrow R)$

$( (P \Rightarrow Q) \wedge P ) \Rightarrow Q$

$( (P \Rightarrow Q) \wedge \overline{Q} ) \Rightarrow \overline{P}$

対偶

$\overline{Q} \Rightarrow \overline{P} \equiv P \Rightarrow Q$

背理法

Prove $P \Rightarrow Q$ by proving $P \wedge \overline{Q}$ is false (or have a contradiction)
$\lnot (P \wedge \overline{Q}) \equiv (\overline{P} \wedge Q) \equiv (P \Rightarrow Q)$

$\forall x \; \exists y \; s.t. \; P(x,y)$ の証明

How to prove $\forall x \; \exists y \; s.t. \; P(x,y)$ .

Let x be an element (satisfying conditions).

Find y, which usually depends on x, so that $P(x,y)$ is true.

Prove P(x, y).

$\exists x \; s.t. \; \forall y, P(x, y)$ の証明

Find x so that $\forall y \; P(x, y)$ it true

Let y be an element

Prove P(x, y)

$\forall , \exists$ の両方があるときの否定

$\lnot (\forall x \exists y \; s.t. \; P(x, y) ) \equiv \exists x \; s.t. \; \forall y , \overline{P(x, y)}$
$\lnot (\exists x \; s.t. \; \forall y , P(x, y) ) \equiv \forall x , \exists y \; s.t. \; \overline{P(x, y)}$

$\forall , \exists$ の命題の性質

$\forall x, \forall y , P(x, y) \equiv \forall y , \forall x, P(x, y)$
$\exists x \; s.t. \; \exists y \; s.t. \; P(x,y) \equiv \exists y \; s.t. \; \exists x \; s.t. \; P(x, y)$
$\exists x \; s.t. \; \forall y \; P(x, y) \Rightarrow \forall y , \exists x \; P(x, y)$