全称命題と存在命題 - ノリの悪い日記

全称命題と存在命題の扱いに慣れるために, 以前解いた問題を見直してみる.

※ 2 つ前の記事「便利な(?) 論理演算」からの続きである.

【問】
$a$ は定数とする. $2$ つの不等式

$3x+ 5 > 5x-1$ ,
$5x+2a>4-x$

を同時に満たす整数 $x$ が存在し, かつそれが自然数のみになるとき, $a$ の値の範囲を求めよ.

【解】
与えられた二つの不等式を整理して,

$\dfrac{2-a}{3} < x < 3$

問題の条件から (前件の真集合が後件の真集合の部分集合である条件を求めることに対応して),

$\displaystyle{\forall x \in \mathbb{Z} \left[\dfrac{2-a}{3} < x < 3 \Rightarrow 1 \leq x \leq 2\right] \\ \iff \forall x \in \mathbb{Z} \left\{ \begin{array}{l} \dfrac{2-a}{3} < x < 3 \Rightarrow 1 \leq x\\ \dfrac{2-a}{3} < x < 3 \Rightarrow x \leq 2\\ \end{array}\right. \\ \iff \left\{ \begin{array}{l} \forall x \in \mathbb{Z} \\ \quad \left[\dfrac{2-a}{3} < x < 3 \Rightarrow 1 \leq x\right] \\ \forall x \in \mathbb{Z} \\ \quad \left[\dfrac{2-a}{3} < x < 3 \Rightarrow x \leq 2\right]\\ \end{array}\right.}$

(最後の上の式)
$\iff \forall x \in \mathbb{Z} \\ \quad \left[\left(\dfrac{2-a}{3} < x < 3\right) \wedge (x < 1) \Rightarrow O\right] \\ \iff \forall x \in \mathbb{Z} \left[\dfrac{2-a}{3} < x < 1 \Rightarrow O\right] \\ \iff \dfrac{2-a}{3} \geq 0 \\ \iff a \leq 2$

(下の式)
そもそも, $x \in \mathbb{Z}(x < 3 \Rightarrow x \leq 2)$ なので, 恒真である.

したがって,

$\displaystyle{\forall x \in \mathbb{Z} \left[\dfrac{2-a}{3} < x < 3 \Rightarrow 1 \leq x \leq 2\right] \\ \iff a \leq 2}$

$x$ の存在条件 (前件の真集合が空集合でないという条件に対応する) は,

$\displaystyle{\exists x \in \mathbb{Z} \left[\dfrac{2-a}{3} < x < 3 \ \right] \\ \iff \dfrac{2-a}{3} < 2 \\ \iff a > -4}$

※ $p =\dfrac{2-a}{3}$ とおくと,

$\exists x \in \mathbb{Z} (p < x < 3 ) \Rightarrow p < 2 \\ \iff \forall x \in \mathbb{Z} [p < x < 3 \Rightarrow p < 2] \\ \iff \forall x \in \mathbb{Z} [(p < x < 3 ) \wedge (p \geq 2) \Rightarrow O]$

実際, $p < x < 3$ かつ $p \geq 2$ を仮定すると, $2 \leq p < 3$ となって, $p < x < 3$ に矛盾する. 逆は明らか.//

したがって, 求める条件は,

$\displaystyle{ -4 < a \leq 2}$
//

【問】
$\forall x (b < x \Rightarrow a \leq x)$

と $a \leq b$ は同値であることを証明せよ.

【解】
( $\Rightarrow$ )

$\displaystyle{\forall x (b < x \Rightarrow a \leq x) \Rightarrow a \leq b \\ \iff \exists x [ (b < x \Rightarrow a \leq x) \Rightarrow a \leq b] \\ \iff \exists x [ (b \geq x) \vee (a \leq x) \Rightarrow a \leq b] \\ \iff \exists x \left\{ \begin {array}{l} b \geq x \Rightarrow a \leq b \\ a \leq x \Rightarrow a \leq b\\ \end{array} \right. \\ \iff \exists x \left\{ \begin {array}{l} (b \geq x) \wedge (a > b) \Rightarrow O \\ (a \leq x) \wedge (a > b) \Rightarrow O\\ \end{array} \right. }$

$b < x < a$ となるように $x$ を取れば成立する (稠密性より, このような $x$ はとれる).

( $\Leftarrow$ )

$a \leq b \Rightarrow \forall x (b < x \Rightarrow a \leq x) \\ \iff \forall x [ a \leq b \Rightarrow (b < x \Rightarrow a \leq x) ] \\ \iff \forall x [ a \leq b \Rightarrow (b \geq x) \vee ( a \leq x) ] \\ \iff \forall x [ (a \leq b) \wedge (b < x) \Rightarrow a \leq x ]$
//

※
$\forall x p(x) \Rightarrow q \\ \iff \overline{\forall x p(x)} \vee q \\ \iff \exists x \overline{p(x)} \vee q \\ \iff \exists x[ \overline{p(x)} \vee q] \\ \iff \exists x [p(x) \Rightarrow q]$

同様にして,

$\exists x p(x) \Rightarrow q \\ \iff \forall x [p(x) \Rightarrow q]$

$p \Rightarrow \forall x q(x) \\ \iff \overline{p} \vee \forall x q(x) \\ \iff \forall x [\overline{p} \vee q(x)] \\ \iff \forall x [p \Rightarrow q(x)]$

同様にして,

$p \Rightarrow \exists x q(x) \\ \iff \exists x [p \Rightarrow q(x)]$

なお,

$\forall x p(x) \Rightarrow \exists x q(x) \\ \iff \overline{\forall x p(x)} \vee \exists x q(x) \\ \iff \exists x \overline{p(x)} \vee \exists x q(x) \\ \iff \exists x [\overline{p(x)} \vee q(x)] \\ \iff \exists x [p(x) \Rightarrow q(x)]$

である. ところが, 以下の場合には,

$\exists x p(x) \Rightarrow \forall x q(x) \\ \iff \overline{\exists x p(x)} \vee \forall x q(x) \\ \iff \forall x \overline{p(x)} \vee \forall x q(x) \\ \implies \forall x [\overline{p(x)} \vee q(x)] \\ \iff \forall x [p(x) \Rightarrow q(x)]$

となって同値変形ではなくなる. 同値変形にする場合は,

$\exists x p(x) \Rightarrow \forall x q(x) \\ \iff \overline{\exists x p(x)} \vee \forall x q(x) \\ \iff \forall x \overline{p(x)} \vee \forall x q(x) \\ \iff \forall x \overline{p(x)} \vee \forall y q(y) \\ \iff \forall x \forall y [\overline{p(x)} \vee q(y)] \\ \iff \forall x \forall y [p(x) \Rightarrow q(y)]$

と改名する.

※ 練習

$\exists x P(x)\vee (\exists x Q(x)\wedge \forall x R(x)) \\ \iff \exists x P(x)\vee (\exists x Q(x)\wedge \forall y R(y)) \\ \iff \exists x P(x)\vee \exists x(Q(x)\wedge \forall y R(y)) \\ \iff \exists x[P(x) \vee (Q(x) \wedge \forall y R(y)) ] \\ \iff \exists x \forall y [P(x) \vee (Q(x) \wedge R(y)) ]$