Hatena::Groupxn--272ax3f

論理と計算のしくみ第1回

論理と計算のしくみ第1回

プレゼンテーション

一章

集合と関係 の定義など導入です.

集合

  • 要素/元/有限集合/外延的/無限集合/内包的/加算/非加算/外延的な等しさ

部分集合(subset)

  • 補集合(complement)
    •  B \subseteq A のとき  A \setminus B をBの補集合B^c = \hat{B} = A-B

直積と直和(direct product / direct sum)

  • 組 (touple) <x,y>
  • 直積  A \times B = \{ <x,y> \mid x \in A, y \in B \}
  • Aのn個の直積 A^n
  • 直和  A+B = \{<0,x>|  \in A} \cup \{<1,y> | y \in B \}
    • <0,x> と x は同一視

関数空間

  • function  f:A \rightarrow B ,  f(a)
  • 合成(composition)  g\circ f= gf:= g(f(a))
  • 全射(surjection), 単射(injection), 全単射(bijection) 逆関数(inverse function)  f^{-1}
  • 部分関数(partial function), 定義域(domain), 全関数(total function)
  • 関数空間  A \rightarrow B または  B^A
  • 外延的な等しさ ↔ f(a) = g(a) \forall a

ベキ集合

  • ベキ集合 2^A = \mathfrak{P}(A) Aすべての部分集合から成る集合
  • 特性関数 \iota_S= \{ 0 (a \in S)  1(a \notin S) ( S は A の部分集合)

関係

関係

二項関係

  • A上の二項関係  R \subset A \times A
    •  aRb \leftrightarrow <a,b> \in R
    • 逆関係 R^{-1}:=\{<b,a>\mid aRb\}

合成と閉包

  • A上の関係RとA上の関係Sの合成  g\circ f= gf:= \{<a,c> \mid \exists b \in A, aRb \wedge bSc\}
  • R^n:=R \circ R \circ \dots \circ R
  • R^0:=\{<a,a> \mid  \in A \}
  • 閉包(クリーネ閉包, Kleene closure)  R^*:= \{<a,c> \mid \exists b_0,\dots,b_n \in A, a = b_0 \wedge b_n = c \wedge b_iAb{i+1} (0 \leq i < n)\}
    •  R^*: = \bigcup_{n\in \mathbf{N}} R^n
    • 有効枝を関係とみるとパスが存在する関係
  • 反射的(refrective) ↔  \forall a \in A, aRa
  • 推移的(transitive) ↔ \forall a,b,c \in A aRb \wedge bRc \rightarrow aRc
  • 関係Sが反射的かつ推移的かつ R \subseteq S なら  R^* \subseteq S
    • R^* を反射推移閉包(reflective transitive closure)

順序

  • A上の関係R に関して  \forall a,b \in A, aRb, bRa \rightarrow a=b のとき反対称的 (anti-symmetric)
  • R が反射的かつ推移的かつ反対称的 のとき Rは 半順序 (partial order)
    • Aのベキ集合 \mathfrak{P}(A), 包含関係[\subseteq]
  • R が反射的かつ推移的のとき Rは 擬順序(quasi-order) または 前順序(pre-order)
    • mod k の  \leq とか?
  • 半順序Rに関して  \forall a,b \in A に対して aRb または bRa が成り立つとき R は全順序 (total order), 線形順序 (linear order)
  • 半順序集合 / 全順序集合(線形順序集合)
  • B \subseteq A a \in A に関して,  \forall b \in B に対して bRa が成り立つなら a は B の上界 (upper bound)
  • 最小の上界を上限(supermum)
    • 任意の上界a' に対して aRa' なら a は上界
    • 上限は存在するなら一意に定まるとあるし 書いてないけどここでは Rは全順序

  • A上の半順序 R が以下の条件を満たす時 AはRによって束(lattice) をなす.
    •  \forall a,b \in A に対して  \exists c \in A, cRa \wedge cRb,  \forall d \in A, dRa \wedge dRb なら  dRc
      • c を aとbの下限(infmum) といい  a \wedge b
    •  \forall a,b \in A に対して  \exists c \in A, aRc \wedge bRc,  \forall d \in A, aRd \wedge bRd なら  cRd
      • c を aとbの上限(supermum) といい  a \vee b
  • 任意の集合A のベキ集合 \mathfrak{P}(A) は包含関係 \subset によって束をなす.
    •  a \wedge b = a \cap b

同値関係

  • R は対称的(symmetric) ↔  \forall a \in A に対して  aRb \rightarrow bRa
  • Rは同値関係(equivalence relation) ↔ Rは反射的, 推移的, 対称的
    • 3 を法とする合同関係
  •  a\in A同値類(equivalence class)  \[a\]_R もしくは  \[a\]
  • Rに関する同値類の全体を商集合(quotient set)  A/R
    • \{ \[0\], \[1\], \[2\] \}
  • (R\cup R^{-1})^*反射的推移対称閉包(reflective transitive closure)

命題

  • 命題
    • 正しいか間違っているかのどちらかであるはずの主張
  • 真偽値  \top \bot

論理記号

  • 連言(conjunction)
  • 選言
    • PまたはQ,  P \vee Q