コンテンツへスキップ
Topos Uranos
日本語

命題論理の言語

要約

この課では、コースのすべての論理式を書くための言語をゼロから構成する。まず集合について欠かせないこと（所属、外延的および内包的に与えられた集合、包含と和集合）を導入し、それを記号列に適用する。すなわち記号列の長さ、連結、接頭辞、そして二つの記号で書ける記号列の数え上げである。白丸と黒丸という二つの記号からなるアルファベットの上に、基本言語を定義する。無限個の変数、ただ一つの形成規則、そして閉包条項であり、この条項から、すべての論理式の性質を証明するための原理が導かれる。次に、記号列が論理式であるかどうかを判定する方法を示し、一意読み取り可能性を述べ、最後に、基本言語の上に、以後用いるメタ言語を構成する。メタ変数、括弧を用いて書いた否定論理和、そして残りの結合子の公式の略記とその日本語での読み方である。

学習目標

  1. 記号列の集合を外延的および内包的に記述し、それらの間の所属、包含、和集合の関係を判定する。
  2. 二つの記号からなるアルファベット上で、与えられた長さの記号列と、長さが上から抑えられた記号列を数える。
  3. 白丸と黒丸からなる記号列が論理式であるかどうかを判定し、論理式である場合には、それがどのように形成されたかを再構成する。
  4. 閉包原理によってすべての論理式がある性質をもつことを証明し、その性質を使って記号列を除外する。
  5. 対象言語とメタ言語を区別し、略記を基本言語の記号列まで展開し、論理式を日本語で読む。

集合について必要なこと

形式言語とは、何よりもまず記号列の集まりである。そうであるならば、それについて正確に語るには、集まりについての語彙が必要になる。その語彙が集合の語彙であり、この課ではそのうちコースで使う部分だけを取り上げる。集合とは対象の集まりであり、その対象を集合の要素と呼ぶ。集合はその要素によって決まる。すなわち、同じ要素をもつ二つの集合は同じ集合である。対象 aa が集合 AA の要素であることを a∈Aa \in A と書き、「aa は AA に属する」と読む。要素でないことは a∉Aa \notin A と書く。

集合の与え方は二通りある。外延的定義では、要素を一つずつ波括弧の中に挙げ、順序や重複は問わない。内包的定義では、要素が満たし、しかも要素だけが満たす条件を述べ、そのときのコロンは「であるような」と読む。たとえば、55 より小さい自然数は次の集合をなす。

{1,2,3,4}={n∈N:n<5}\{1, 2, 3, 4\} = \{ n \in \mathbb{N} : n < 5 \}

内包的定義の一種で、以下で頻繁に使うものは、要素をその形によって記述する。{2n:n∈N}\{ 2n : n \in \mathbb{N} \} は 2n2n（nn は自然数）の形の数全体の集合、すなわち偶数全体の集合である。外延的に与えた集合は必ず有限である。内包的には無限集合も与えられ、偶数全体の集合がその例である。

AA が BB に含まれるといい、A⊆BA \subseteq B と書くのは、AA のどの要素も BB の要素であるときである。このことから、二つの集合が等しいのは、それぞれが他方に含まれるとき、かつそのときに限る。そのとき両者は同じ要素をもつからである。そして実際、これが集合の等式を証明する通常の方法である。すなわち二つの包含を示す。最後に、和集合 A∪BA \cup B とは、AA に属するか、BB に属するか、その両方に属する対象全体の集合である。したがって、二つの集合のいずれもその和集合に含まれる。

例所属、包含、和集合

A={1,2,3}A = \{1, 2, 3\}、B={2,4,6,8}B = \{2, 4, 6, 8\}、P={2n:n∈N}P = \{ 2n : n \in \mathbb{N} \} とする。2∈A2 \in A かつ 4∉A4 \notin A である。さらに B⊆PB \subseteq P である。BB の各要素は自然数の二倍だからである。一方、AA は PP に含まれない。1∈A1 \in A かつ 1∉P1 \notin P だからである。AA と BB の和集合は {1,2,3,4,6,8}\{1, 2, 3, 4, 6, 8\} であり、両方に属する 22 は一度だけ現れる。