意味論：導入

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

1. 問 1前の単元から論理式の上の関数は、各変数での値と、$\sigI\varphi\psi$ での値を $\varphi$、$\psi$、および両者での値から計算する規則とを与えることで定義される。こうして関数がちょうど一つ定義されることを保証するのは何か。

   一意読み取り可能性。すなわち、どの複合論理式も、先頭の黒丸と二つの成分へただ一通りに分解される。

   規則がつねに $0$ か $1$ を返すこと。

   何も保証しない。論理式ごとに値を確かめなければならず、論理式は無限にあるので、それはできない。

   略記 $\neg$、$\vee$、$\wedge$ も一意読み取り可能であること。

2. 問 2前の単元からコースの公式の略記のもとで、$(\varphi \vee \varphi)$ はどの論理式か。

   $\neg\neg\varphi$ と同じ記号列。

   冪等律により、$\varphi$ そのもの。

   $(\varphi \downarrow \varphi)$。

   どれでもない。選言には二つの異なる論理式が必要である。

3. 問 3前の単元からすべての論理式がある性質をもつことを複雑さに関する帰納法で証明するには、どの場合を扱わなければならないか。

   変数と、唯一の形成規則 $\sigI\varphi\psi$、すなわち $(\varphi \downarrow \psi)$。

   変数、否定、連言、選言。

   規則 $(\varphi \downarrow \psi)$ だけ。変数はその特別な場合である。

   変数と六つの結合子 $\neg$、$\vee$、$\wedge$、$\rightarrow$、$\leftrightarrow$、$\veebar$。

4. 問 4前の単元から帰納法の課の定義にしたがって、論理式 $\alpha$ の代わりに論理式 $\beta$ を $\varphi$ に代入するとき、$\alpha$ のどの出現が変わるか。

   部分論理式としてのすべての出現が、同時に変わる。

   記号列を左から右へ読んだときの、最初の出現だけ。

   略記した表記で見える出現だけ。

   $\alpha$ の出現と、そのあと $\beta$ の写しに現れる出現。

5. 問 5ある付値が $p$ に値 $0$ を、$q$ に値 $1$ を与える。$(\varphi \downarrow \psi)$ が値 $1$ をとるのはちょうど $\varphi$ と $\psi$ が値 $0$ をとるときであるとすると、論理式 $(p \downarrow (q \downarrow p))$ はどの値をとるか。

   $1$。

   $0$。$q$ の値が $1$ だから。

   ほかの変数の値を知らなければ計算できない。

   成分のまとめ方による。

6. 問 6$\not\models \varphi$ は何を意味するか。

   ある付値が $\varphi$ に値 $0$ を与えること。つまり $\varphi$ は恒真でない。

   $\varphi$ が矛盾式であること。

   どの付値も $\varphi$ を充足しないこと。

   $\varphi$ がコースの体系で導出されないこと。

7. 問 7$\Gamma \cup \{\varphi\} \models \psi$ であることがわかっている。すなわち、$\Gamma$ と $\varphi$ を充足するどの付値も $\psi$ を充足する。何が帰結するか。

   $\Gamma \models (\varphi \rightarrow \psi)$。

   $\Gamma \models \psi$。

   $\Gamma \models (\psi \rightarrow \varphi)$。

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

8. 問 8論理式 $(v_{1} \vee \neg v_{1})$ は恒真である。一様代入の定理により恒真であるのは、次のどの論理式か。

   $(\neg v_{2} \vee \neg\neg v_{2})$。

   $(v_{1} \vee \neg v_{2})$。

   $(\neg v_{2} \vee \neg v_{3})$。

   どれでもない。一様代入で許されるのは、変数をほかの変数に変えることだけである。

9. 問 9コースの規約によれば、括弧なしで書かれた表現 $v_{1} \wedge v_{2} \wedge v_{3}$ はどの論理式を表すか。

   $((v_{1} \wedge v_{2}) \wedge v_{3})$。

   $(v_{1} \wedge (v_{2} \wedge v_{3}))$。

   両方のまとめ方。同じ記号列だから。

   どれでもない。括弧がなければ表現は何も表さない。

10. 問 10二変数の真理関数は、値 $0$ または $1$ を、四つの行 $(1, 1)$、$(1, 0)$、$(0, 1)$、$(0, 0)$ のそれぞれに割り当てる。二変数の真理関数はいくつあるか。

11. 問 11変数から $\wedge$ と $\vee$ だけで書かれた論理式が、値 $0$ をとることはありうるか。ただし付値は、すべての変数に $1$ を与えるものとする。

    ありえない。$\wedge$ と $\vee$ だけで書かれた論理式は、どれもこの付値で値 $1$ をとる。

    ありうる。連言と選言を十分に入れ子にすればよい。

    ありうる。否定論理和だけで十分なのだから、連言と選言でも十分である。

    各論理式の表を書かなければわからない。

12. 問 12リテラルとは、変数または変数の否定である。次の論理式のうち、リテラルはどれか。

    $\neg v_{2}$。

    $\neg\neg v_{1}$。

    $(v_{1} \wedge v_{2})$。

    $\top$。

13. 問 13連言標準形 $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ は恒真か。

    恒真でない。第二の節は相補対を一つも含まず、$0$ を $v_{3}$ に、$1$ を $v_{2}$ に与える付値がこれを反駁する。

    恒真である。第一の節が相補対を含み、一つあれば十分である。

    恒真である。充足可能だから。

    八行の表がなければ決定できない。

14. 問 14論理式を選言標準形にするには、連言を選言の上に分配する。正しい規則はどれか。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$。

    $(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$。

15. 問 15ある回路では、レバー $p$ と $q$ の二つの正スイッチが直列につながれ、その一組がレバー $r$ の正スイッチと並列につながれている。回路がいつ導通するかを述べる論理式はどれか。

    $((p \wedge q) \vee r)$。

    $((p \vee q) \wedge r)$。

    $((p \wedge q) \wedge r)$。

    $((p \vee q) \vee r)$。