人がいっぱい。この授業では計算可能性と、計算の複雑さについて理論を学ぶ授業である。前期の「オートマトン」のつづきのような授業だ。
で、先生がはっきり言っていたが、この授業は離散数学に関する授業である。１の２期はやや余裕があるので、数学をがんばってみる。
この日は、ガイダンスと集合についての復習。部分集合や空集合、和集合の補集合、積集合などの説明。まぁ、今までやってきた内容なので、難しくはないが、集合の証明のコツのようなものがわかった。
例えば空集合φはすべての集合の部分集合であるという証明をあげてみよう。
まず、部分集合の定義とは、Ａ⊆Ｂ⇔∀x(x∈Ａ⇒x∈Ｂ）である。このＡをφにしたものを証明すればよい。
φ⊆Ａ⇔∀x（ｘ∈φ⇒ｘ∈Ａ）を示せばよいのだが、この⇒（ならば）という演算子の左辺ｘ∈φは常に偽になる。⇒の左辺が偽の場合は式全体の評価は常に真になる（定義より）。よって空集合はすべての集合の部分集合である。
授業の最後にあったＡ∨Ｂ＝Ｂ⇔Ａ⊆Ｂの証明も基本的には定義に還元して証明すればよい。ただ⇔は両方向の証明が必要になる。
