演繹：導入

単元を始める前に、自分の出発点を測りましょう。短い自己評価です。採点はされず、結果はあなたのブラウザーにだけ保存されます。

1. 問 1前の単元から記号列 $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ は、$\sigI\varphi\psi$ という形の複合論理式である。その成分 $\varphi$ と $\psi$ は何か。

   $\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$、$\psi = \sigO\sigI$。

   $\varphi = \sigI\sigO\sigI$、$\psi = \sigO\sigO\sigI\sigO\sigI$。

   先頭の黒丸のあとのどこで記号列を切るかに応じて、二通りの分解を許す。

   $\varphi$ は先頭の黒丸に続く記号列全体であり、$\psi$ は空列である。

2. 問 2前の単元からすべての自然数 $n$ が性質 $P(n)$ をもつことを累積帰納法で証明するとき、$P(n)$ を証明する段階で何を仮定してよいか。

   $P(m)$ が、すべての自然数 $m$（ただし $n$ より小さいもの）について成り立つこと。

   $P(n - 1)$ が成り立つことだけ。

   $P(m)$ が、すべての自然数 $m$（ただし $n$ 以下のもの）について成り立つこと。

   $P(1)$ と $P(2)$ を別々に証明するまでは、何も仮定できない。

3. 問 3前の単元から本コースの公式の略記で、$(\varphi \rightarrow \psi)$ を否定論理和と否定で書くと、どの論理式を表すか。

   $\neg(\neg\varphi \downarrow \psi)$。

   $(\neg\varphi \downarrow \psi)$。

   $\neg(\varphi \downarrow \neg\psi)$。

   特定の論理式はない。どう読むと決めるかによる。

4. 問 4図式 A1 は $(\varphi \rightarrow (\psi \rightarrow \varphi))$ である。論理式 $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ は A1 の代入例か。

   いいえ。$\varphi$ の最初の出現と最後の出現には同じ論理式が代入されなければならないが、ここではそれらは $v_{1}$ と $v_{3}$ である。

   はい。$\varphi := v_{1}$、$\psi := v_{2}$ とすればよい。

   はい。後件がまた含意であるような含意は、すべて A1 の代入例だからである。

   いいえ。図式の代入例は変数を含むことができないからである。

5. 問 5ある演繹に、すでに行 $\psi$ と $(\varphi \rightarrow \psi)$ がある。ここで $\varphi$ と $\psi$ は異なる論理式である。この二つの行にモーダス・ポネンスを適用すると、どの論理式を書くことができるか。

   どれも書けない。モーダス・ポネンスは前件 $\varphi$ を必要とするが、手もとにあるのは後件である。

   $\varphi$。

   $(\psi \rightarrow \varphi)$。

   $\neg\varphi$。

6. 問 6$\{\varphi\} \vdash \psi$、すなわち $\psi$ の演繹で、唯一の前提が $\varphi$ であるものが存在することがわかっている。このとき演繹定理は何を主張するか。

   $\vdash (\varphi \rightarrow \psi)$ であること。含意は定理である。

   $\vdash \psi$ であること。前提はそのまま取り除いてよい。

   $\vdash (\psi \rightarrow \varphi)$ であること。

   $\{\psi\} \vdash \varphi$ であること。

7. 問 7ほかの前提なしに、集合 $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ から何が演繹されるか。

   $(\varphi \rightarrow \chi)$。

   モーダス・ポネンスを二回適用して、$\chi$。

   $(\chi \rightarrow \varphi)$。

   $(\varphi \wedge \chi)$。

8. 問 8二重否定の置換の規則（二重否定置換）は、一つの行において部分論理式のただ一つの出現を変え、基本言語の記号列に作用する。部分論理式 $\neg v_{1}$ は、$(v_{1} \rightarrow v_{2})$ が表す記号列のなかに何回現れるか。

   二回。

   一回。前件に対応するもの。

   一回も現れない。この論理式は否定を含まない。

   四回。

9. 問 9$(\neg\varphi \rightarrow \psi)$ から対偶によって、二重否定を付け加えずに、どの論理式が得られるか。

   $(\neg\psi \rightarrow \varphi)$。

   $(\psi \rightarrow \neg\varphi)$。

   $(\varphi \rightarrow \neg\psi)$。

   $(\neg\psi \rightarrow \neg\varphi)$。

10. 問 10$(\varphi \vee \psi)$ と $(\neg\varphi \rightarrow \psi)$ は同じ論理式を表すか。

    いいえ。前者は $\neg(\varphi \downarrow \psi)$、後者は $\neg(\neg\neg\varphi \downarrow \psi)$ であり、異なる論理式で、証明可能な同値である。

    はい。含意の定義による。

    はい。どちらも「$\varphi$ または $\psi$」と読まれるからである。

    いいえ。しかも一方から他方は演繹されない。

11. 問 11$\varphi \dashv\vdash \varphi'$、すなわちそれぞれが他方から演繹されることがわかっている。$\neg\varphi \dashv\vdash \neg\varphi'$ でもあることを正当化するものは何か。

    一つの定理、すなわち同値なものの置換であり、これは演繹定理と対偶によって証明される。

    特別な正当化はいらない。同値の「両辺を否定する」だけでよい。

    否定の定義。$\neg\varphi$ は $(\varphi \downarrow \varphi)$ だからである。

    何も正当化しない。そもそも正しくないからである。否定は同値な論理式を分けてしまうことがある。

12. 問 12前提集合 $\Gamma \cup \{\neg\varphi\}$ から、論理式 $\chi$ とその否定 $\neg\chi$ が演繹される。何が結論できるか。

    $\Gamma \vdash \varphi$。

    $\Gamma \vdash \neg\varphi$。

    $\Gamma$ から任意の論理式が演繹される。

    何も結論できない。矛盾に行き着く演繹は何も証明しない。

13. 問 13含意の否定 $\neg(\varphi \rightarrow \psi)$ は、どの論理式と同値か。

    $(\varphi \wedge \neg\psi)$ と同値である。

    $(\neg\varphi \rightarrow \neg\psi)$ と同値である。

    $(\varphi \rightarrow \neg\psi)$ と同値である。

    $(\neg\varphi \wedge \psi)$ と同値である。