メタ理論：導入

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

1. 問 1前の単元から$\Gamma \models \varphi$ は何を意味するか。

   $\Gamma$ のすべての論理式を充足するどの付値も $\varphi$ を充足する。

   $\varphi$ の $\Gamma$ からの演繹が存在する。

   ある付値が $\Gamma$ と $\varphi$ を同時に充足する。

   $\varphi$ は $\Gamma$ のある一つの論理式だけの帰結である。

2. 問 2前の単元から次の主張のうち、$\Gamma \models \varphi$ と同値なのはどれか。

   $\Gamma \cup \{\neg\varphi\}$ は充足不能である。

   $\Gamma \cup \{\varphi\}$ は充足可能である。

   $\Gamma \cup \{\neg\varphi\}$ は充足可能である。

   $\neg\varphi$ は充足不能である。

3. 問 3前の単元から付値 $v$ が $\alpha$ に値 $1$ を与えるなら、$(\alpha \downarrow \beta)$ にはどの値を与えるか。

   $0$。$\beta$ の値が何であっても。

   $\beta$ 次第である。値が $1$ になるのは、$\beta$ が $0$ をとるときである。

   $1 - v(\beta)$。

   $1$。成分の一方が真だから。

4. 問 4前の単元から$\varphi$ の変数は $v_{2}$ と $v_{7}$ である。二つの付値 $v$ と $w$ は、$v_{2}$ と $v_{7}$ に同じ値を与え、他のすべての変数には反対の値を与える。$v(\varphi) = 1$ なら、$w(\varphi)$ について何が言えるか。

   $w(\varphi) = 1$。

   何も言えない。$v$ と $w$ は無限個の変数で異なるから。

   $w(\varphi) = 0$。$w$ は $v$ のほとんどすべての値を反転させるから。

   $w(\varphi) = 1$。ただし、$v$ と $w$ が $v_{1}, \ldots, v_{6}$ でも一致する場合に限る。

5. 問 5前の単元から$\Gamma$ を、$\Gamma \vdash \varphi$ となるような論理式の無限集合とする。何が言えるか。

   $\Gamma$ のある有限部分集合が $\varphi$ を演繹する。

   $\varphi$ は定理である。

   その演繹は $\Gamma$ のすべての論理式を用いる。

   コンパクト性定理なしには何も言えない。$\Gamma$ は無限だから。

6. 問 6前の単元から$\Gamma \cup \{p\} \vdash \chi$ であり、かつ $\Gamma \cup \{\neg p\} \vdash \chi$ であることがわかっている。場合分けによる証明によって何が結論できるか。

   $\Gamma \vdash \chi$。

   $\Gamma$ が $p$ を演繹するのか $\neg p$ を演繹するのかがわからない限り、何も結論できない。

   $\Gamma \vdash (p \leftrightarrow \chi)$。

   $\Gamma \cup \{p, \neg p\} \vdash \chi$ だけ。

7. 問 7本コースの体系は健全である。この性質は何を主張するか。

   すべての集合 $\Gamma$ について、$\Gamma \vdash \varphi$ ならば $\Gamma \models \varphi$。

   $\Gamma \models \varphi$ ならば $\Gamma \vdash \varphi$。

   $\varphi$ という論理式で、$\vdash \varphi$ かつ $\vdash \neg\varphi$ となるものは存在しない。

   真な論理式はすべて定理である。

8. 問 8$v$ を、$1$ を $p$ に、$0$ を $q$ に与える付値とする。カルマーの補題は、変数 $p$ と $q$ によって、論理式 $(p \leftrightarrow q)$ について何を主張するか。

   $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$。

   $\{p, \neg q\} \vdash (p \leftrightarrow q)$。

   $\{p, q\} \vdash \neg(p \leftrightarrow q)$。

   $\vdash \neg(p \leftrightarrow q)$。

9. 問 9演繹体系は、完全でなくても健全でありうるか。

   ありうる。ウカシェヴィチの体系は、二重否定置換の規則がなければ健全であり、トートロジー $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ を演繹しない。

   ありえない。健全性と完全性は互いに導かれる。

   ありえない。公理がトートロジーである体系は、すべてのトートロジーを演繹する。

   ありうる。ただし体系が矛盾している場合に限る。

10. 問 10コンパクト性定理は何を主張するか。

    論理式の集合が充足可能であるのは、そのすべての有限部分集合が充足可能であるとき、かつそのときに限る。

    論理式の集合が充足可能であるのは、その各論理式が充足可能であるとき、かつそのときに限る。

    論理式の無限集合はすべて充足可能である。

    集合は、その有限部分集合のどれか一つが充足可能なら、充足可能である。

11. 問 11$\Gamma$ を、$\Gamma \models \varphi$ となるような論理式の無限集合とする。コンパクト性は何を保証するか。

    $\Gamma_{0} \models \varphi$。ここで $\Gamma_{0}$ は $\Gamma$ のある有限部分集合である。

    $\varphi$ は $\Gamma$ のある一つの論理式だけの帰結である。

    $\varphi$ は $\Gamma$ のすべての有限部分集合の帰結である。

    $\varphi$ は妥当である。

12. 問 12第一の課は、有限の前提集合について完全性を証明する。それを無限集合 $\Gamma$ へ拡張するのに、演繹の有限性で足りないのはなぜか。

    有限性が語るのは $\Gamma \vdash \varphi$ についてであり、手もとにあるのは $\Gamma \models \varphi$ だからである。有限部分に帰着されなければならないのは、演繹ではなく帰結であり、それがコンパクト性である。

    足りる。$\Gamma \models \varphi$ なら、有限性は有限の $\Gamma_{0}$ で $\Gamma_{0} \models \varphi$ となるものを与える。

    カルマーの補題は、無限個の変数をもつ論理式については成り立たないから。

    完全性は、無限の前提集合については偽だから。

13. 問 13節 $\{p, \neg q, r\}$ と $\{q, s\}$ の融合節は何か。

    $\{p, r, s\}$。

    $\{p, \neg q, r, q, s\}$。

    $\{p, r\}$。

    共通のリテラルがないので、融合節をもたない。

14. 問 14融合によって $\{(p \vee q), \neg p\} \models q$ かどうかを決定するために、どの節集合を反駁しようとするか。

    $\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$。

    $\{\{p, q\}, \{\neg p\}, \{q\}\}$。

    $\{\{p, q\}, \{\neg p\}\}$。

    $\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$。

15. 問 15空節 $\Box$ は、集合 $\{\{p, q\}, \{\neg p, \neg q\}\}$ から融合によって生成されうるか。

    されない。集合は充足可能であり、融合は健全である。

    される。一段階で、二つの相補対を同時に取り除けばよい。

    される。二段階で、まず $p$ について、次に $q$ について融合すればよい。

    されない。二つの節のどちらも単位節ではないから。