駆け足で読む『計算理論の基礎』３巻構成とか、全体に関すること

0 序論
- 0.1 オートマトン、計算可能性、複雑さ
  - 『計算機の本質的な能力とその限界は何か？』が全体を束ねる問
  - それに答えるために３巻構成
    - (1) オートマトン
      - 計算・言語の数学的モデル
    - (2) 計算可能性
      - 解を求められる問題か、求められない問題か
    - (3) 複雑さ
      - 問題が簡単か、難しいか
- 0.2 数学的概念や用語
  - 集合
    - 元、部分集合・真部分集合、重複集合、無限集合、空集合、ベン図
  - 列と組
    - 列(sequence)と組(tuple)、直積 $A \times B$
  - 関数と関係
    - 関数、写像、定義域・値域
    - 引数、k-項関数、項数、二項関数
    - 前置記法、中置記法
    - 同値関係(反射律、対称律、推移律)
  - グラフ
    - ノード、エッジ、ラベル付けグラフ、部分グラフ、パス、連結、巡回、木、根、葉、有向グラフ、入次数・出次数、強連結
  - 文字列と言語
    - 文字、文字列、長さ、空列、逆順、部分文字列、連結、辞書式順序、言語
  - BOOLE論理
    - Boole 値、Boole演算、否定、論理積、論理和、オペランド、排他的論理和、等価、含意、分配則
- 0.3 定義、定理、証明
  - 定義definitionとは構成要素が何であり、構成要素でないものは何であるかを明確にして、ものや概念を規定する
  - 命題statementとは定義されたものや概念がある性質を持つことを述べたものであって、真偽を決することができるだけ十分に詳細に、また曖昧でないように記述されたもの
  - 証明proofとは命題が真であることを納得させる論理的な議論のこと
  - 定理theoremとは真であると証明された命題のこと
  - 補題lemmaとは重要な命題を証明するときにその補助となる命題のこと
  - 系corollaryとはある定理や証明を用いて、真であることを容易に示せる、他の命題のこと
- 0.4 証明のタイプ
  - 構成的証明、背理法、帰納法