論理記号と証明の方法の練習問題

考え方

「すべての〜」「ある〜」を含む主張を正しく否定し、背理法や数学的帰納法で筋道立てて示せるようになります。仕様や契約の条件の読み取り、テストでの反例探しなど、言葉の論理を誤解なく扱う場面で役立ちます。

$\forall$（全称記号）

「すべての〜について」。$\forall x\ P(x)$ は「どの $x$ でも $P(x)$ が成り立つ」。

$\exists$（存在記号）

「ある〜について」「〜が少なくとも1つある」。

背理法

示したいことの否定を仮定して矛盾を導き、もとの主張が正しいと結論する方法。

数学的帰納法

$n = 1$ で成り立つことと、$n = k$ で成り立てば $n = k + 1$ でも成り立つことを示して、すべての自然数で成り立つと結論する方法。

「全店舗が目標を達成した」の否定は、「目標を達成しなかった店舗が少なくとも1つある」です。「全店舗が達成しなかった」ではありません。「すべて」の否定は「〜でないものがある」、「ある」の否定は「すべて〜でない」になります。

記号では、$\lnot$ を内側へ移すたびに、通過した $\forall$ と $\exists$ が入れかわります。$\forall x\ \exists y\ P(x, y)$ の否定は $\exists x\ \forall y\ \lnot P(x, y)$ です。最後に中の条件を否定し、「以上（$\ge$）」の否定は「未満（$<$）」のように等号の扱いに注意します。

背理法は、示したい命題 $P$ が成り立たない（$\lnot P$）と仮定して、矛盾を導く方法です。だから、まず $\lnot P$ を正しく書けることが大切です。

数学的帰納法はドミノ倒しです。(I) 1枚目（$n = 1$）が倒れること、(II) $k$ 枚目が倒れれば $k + 1$ 枚目も倒れること、の2つを示せば、すべてが倒れます。(II) では「$n = k$ のとき成り立つ」を仮定として使い、$n = k + 1$ の式に代入します。

ポイント

$\lnot(\forall x\ P(x)) \equiv \exists x\ \lnot P(x)$

$\lnot(\exists x\ P(x)) \equiv \forall x\ \lnot P(x)$

$a \ge c$ の否定は $a < c$、$a > c$ の否定は $a \le c$

帰納法: (I) $n = 1$ で成り立つ　(II) $n = k$ で成り立つと仮定すると、$n = k + 1$ でも成り立つ

解き方の手順

1. 否定: 量化記号を前から順にすべて入れかえる（$\forall \leftrightarrow \exists$）。
2. かっこの中の条件を否定する（不等号は等号がどちらに入るかに注意）。
3. 帰納法の (I): $n = 1$ を代入して、左辺と右辺が等しいことを確かめる。
4. 帰納法の (II): $S(k + 1) = S(k) + a_{k+1}$ に仮定 $S(k) = F(k)$ を代入して整理し、$F(k + 1)$ と一致することを確かめる。