OS-做一个简单的shell

也系边上老师的课边做的一些笔记以及自己的一些想法，但有时候可能会拖更，分享给大家，有不妥之处，敬请评论区指正。

集合的基本概念及其运算

集合与元素

• 集合要有明确特征，不能是模糊概念，如：高个子学生
• 集合的表示方法：
  • 枚举法
  • 抽象法：用谓词来概括，$S=\{x|P(x)\}$
    • 抽象描述不唯一。
    • 不能取 $p(x)为x\notin x$ ，否则罗素悖论

      $T=\{x|x\notin x\},有\mathrm{\forall }x,x\in T\iff x\notin x$
      $假设这里的x就是T，那么就有T\in T\iff T\notin T$
      
      猫了个打盹（）

    • $所以其实抽象原则有点危险，Cantor悖论，理发师悖论，说谎者悖论。$
    • $悖论产生的原因：自引用，自作用。$
  • 归纳定义：包含基本项、归纳项、以及最小化。（可以类比一下上学期公理系统的定义）
    • 基本项和归纳项不难理解，归纳项就是推演规则。

      这里我们来定义一个集合A
      $非空集合S_0\subseteq A(基本项)$
      
      $一组规则，\mathrm{\forall }x\in A,x\stackrel{这一组规则}{⟶}y,y\in A(归纳项)$

    • 这里重点辨析一下极小化：

      保证A中每个元素都可通过有限次使用1或2来获得。
      $如果集合S\subseteq A也满足1和2，则A\subseteq S$
      $（如果集合S\subseteq A也满足1和2，则S=A）$
      
      最小化很必要，就是说如果只有1和2两句话，A中有其他不符合1、2规则的元素也可以满足，归纳定义法定义的集合就不唯一！！！
      为什么叫极小化，就是说A中没有其他多余的元素，是通过1、2能得到的最小集合，清清爽爽。

集合的相等与包含

相等和包含的定义在高中的时候就说过了，这里说点不一样的。

• 集合与元素的排列次序与元素重复出现的次数无关

  体现为{1,2,3}={3,1,2}
  {a,b,c}={a,a,c,b,b,c}(这个也叫多重集)

• 相等与包含的等价表示

  $A=B\iff \mathrm{\forall }x(x\in A\leftrightarrow x\in B)$
  $A\subseteq B\iff \mathrm{\forall }x(x\in A\to x\in B)$
  $A\subset B\iff A\subseteq B\wedge A\ne B\iff \mathrm{\forall }x(x\in A\to x\in B)\wedge \mathrm{\exists }x(x\in B\wedge x\notin A)$

• 集合的元素可以是集合

  所以这里就有必要辨析一下 $“\in ”和“\subseteq ”$ 的区别
  例：A={1,2,{1,2,3}}
  $\therefore 1\in A$
  
  $\{1,2\}\subseteq A$
  
  $\{1,2,3\}\in A$
  
  $\{1,\{1,2,3\}\}\subseteq A$
  
  在这里，“1”，“2”，“{1，2，3}”是平级的。这里我们可以类比电脑的文件夹存储方式。

• 还有一个关系，咱们可以看看。

  $设A，B，C都是集合，若A\subseteq B且B\subseteq C,则A\subseteq C$
  $但是，若A\in B,B\in C,则A不一定\in C$
  $例：A=\{1\},B=\{\{1\}\},C=\{\{\{1\}\}\}(晕.jpg)$

幂集

• 集合A的全部子集构成的集合 称为A的 幂集，记作 $\rho (A)$。

  $\rho (A)=\{X|X\subseteq A\}$
  $\therefore B\subseteq A⟺B\in \rho (A)$

• 基数，有穷集合A中所含有元素的个数称为 A 的基数。记作#A。

  对于A中的每个元素在A的幂集元素中只有两种选择，(to be | not to be) ,所以只要A是有穷集合，则 $\mathrm{♯}\rho (A)=2^{\mathrm{♯}A}$

集合的运算

• $有\cup ,\cap ,-(差，也叫对称补),\sim (补，也称绝对补)，\oplus (叫对称差)$
  • $为啥\sim 叫绝对补捏,因为\sim A=U-A$

    $所以x\notin A⟺x\in \sim A$

  • $那为啥\oplus 叫对称差捏,因为A\oplus B=(A-B)\cup (B-A)$

    就是去除掉相同的部分，跟异或有点像有米有。

• $还有俩特殊的\bigcup 、\bigcap ,推广到n个集合的情况$
  • $记作:\bigcup _{i=1}^n{A}_i,也可以写成无穷的形式:\bigcap _{i=1}^{\mathrm{\infty }}{A}_i$
• 集合族，集合的聚合：如果一个集合的所有元素都是集合，则称该集合为 集合族 或 集合的聚合。
  • $标码集合的概念：A=\{A_{s1},A_{s2},\dots \},J=\{s1,s2,\dots \}$

    $则A可以简化写成：A=\{A_i|i\in J\},咱们把A叫加标集合，J叫标码集合$

  • $聚合上的\bigcup ,\bigcap 运算也有点讲究，我们将其称为广义并、广义交，主要体现在\bigcap 上$

    $集合族A，A元素的并集可以表示为\bigcup A或者\bigcup _{i\in J}{A}_i$
    
    即有就留下。
    $即：\bigcup A=\{x|\mathrm{\exists }S(S\in A\vee x\in S)\}$
    $特殊的来了，对于\bigcap 咱们要求A\ne \varphi ,命名同上$
    $我们定义：\bigcap A=\{x|\mathrm{\forall }S(S\in A\to x\in S)\},$
    $\therefore 若A=\varphi ，则S\in A\to x\in S永真，\bigcap A为U。$
    $这里的\bigcup A有取所有A的元素都有的元素就留下$

    • 我觉得在这个定义上，和运算上的 $\times ÷$ 有点像，但我基础不够说不出来有什么内部的联系，等我研究一下，有成果在评论区告诉大家

• 另外，由集合族定义牵扯的广义分配律，广义德摩根律大家也可以去看看形式，这里不赘述了
• 还有一有意思的原理：（集合恒等式的基本形式可以与逻辑等值式类比）
  • 对偶原理：在不含有 $-和\oplus$ 的集合恒等式中，将 $\cup 与\cap$ 互换，$\varphi 与U$ 互换，得到的仍是集合恒等式（或者可以用逻辑上的对偶定理来理解，真值不变）。

    是不是很有趣，为啥会这样呢。这两个玩意都是布尔代数的特例，可以去了解一下布尔代数

• 咱们学过范式，我们可以用 $\{\mathrm{\neg },\vee ,\wedge \}$ 这个完备集来表示所有的逻辑情况，在集合里我们也可以用把所有的其他运算符化成 $\{\sim ,\cup ,\cap \}$ 来简化运算。当然很多时候可以用元素分析，需要灵活应对。

  $A-B=A\cap \sim B$
  $A\oplus B=(A-B)\cup (B-A)=(A\cap \sim B)\cup (B\cap \sim A)$

有穷集的计数原理

• 如题，有定理 $\mathrm{♯}(A\cup B)=\mathrm{♯}A+\mathrm{♯}B-\mathrm{♯}(A\cap B)$
• 可以画Venn图辅助理解。

集合的归纳定义法

• 在第一节集合与元素讲过基础的定义，其中我们说抽象定义有时会有点不清楚，所以我们学习更好的归纳定义。
• 其中需注意的极小化定义，一般表述为“只有有限次应用基础语句和归纳语句得到的元素才是该集合中的元素”

有序偶和笛卡尔乘积

• 有序偶：两个对象x、y，他们按规定的顺序构成的序列，称之为有序偶，记为 < x , y >。
• 其中x称为第一元，y称为第二元。
• 有序偶的集合表示：

  < x , y > = { { x } , {x , y}}

  • 这样表示的话，有序偶的有序性得以体现。

• $n元序偶定义为：<x_1,x_2,x_3,\dots ,x_n>=<<x_1,x_2,\dots x_{n-1}>,x_n>$
  • 尝试着写一下n元序偶的集合表示呗！
• 笛卡尔乘积：

  $A\times B=\{<x,y>|x\in A\wedge y\in B\}$

  • 由于有序偶的有序性，所以笛卡尔积不符合交换律和结合律
  • $\mathrm{♯}(A\times B)=\mathrm{♯}A\cdot \mathrm{♯}B(A,B为任意有限集)$

• 运算性质：

  $A\times (B\cup C)=(A\times B)\cup (A\times C)$
  
  $(A\cup B)\times C=(A\times C)\cup (B\times C)$

  • 类似的分配律性质对 $\cap ,-$ 也适用

• n个集合的笛卡尔积推广，自己类推一下叭。

未完待续。。。