叔叔,我也要学数理逻辑!

之离散数学

题外话:(今年的复试听说是要线上举行,(淦!大概率要白给了555)。。。所以赶紧开个面试坑,将死之鱼最后关头好歹也要挣扎一下)

公理化集合论:

朴素集合论有悖论(理发师悖论),公理化集合论试图用“不证自明”的公理作为基础来解决悖论问题。

公理系统具有自洽性完备性(2020年面试)(独立性不是公理系统的性质,其是公理的性质)

自洽性指系统中不存在也不可推导出正反都对的命题(必要)。

完备性指对于任何命题都可以证明或证伪。

(ZFC集合论)

  1. 外延公理:含有元素完全相同的集合是相等的集合。(引出“集合相等”的概念)
  2. 正则公理:不存在属于自身的集合。(不可无限套娃)
  3. 空集公理:存在一个唯一的、不包含任何元素的集合Φ。
  4. 分离公式公理:集合必定以其他已存在集合为定义基础,集合不可阐释自身,一个通过一个谓词定义的集合的任何子类自身是一个集合。(解决了“罗素悖论”)
  5. 配对公理:假如x, y为集合,那就有另一个集合{x,y}包含x与y作为它的仅有元素。(两个箱子配成一对)({x,x}={x})(定义“元有序对”<x,y>={{x},{x,y}})
  6. 并集公理:每一个集合都有一个并集。也就是说,对于每一个集合x,也总存在着另一个集合y,而y的元素也就是而且只会是x的元素的元素。(把箱子拆开,把内容物放出来)
  7. 替换公式公理:一个集合在一个映射下的像也是一个集合。
  8. 无穷公理:(数学归纳法:皮亚诺公理)有一个集合包含所有的自然数。(定义x的后继:x∪{x}:冯诺依曼的自然数定义,构造一个同时包含x和x的后继(对“后继”函数封闭)的集合,其基数即自然数)
  9. 幂集公理:每一个集合都有其幂集。
  10. 选择公理:给定由相互不交的非空集合组成的任何集合,存在着至少一个集合,它与每个非空集合恰好有一个公共元素。(任何集合族都有选择函数)

可数和不可数(不可数集合的基数,等势)

若集合A和B二者之间存在一种一一对应的关系,则称A和B是等势的。

凡是与自然数集N等势的集合,称为可数集合,势记为\(\aleph_{0}\)

可数集合举例:所有的有限集合、正奇数集合、整数集合(希尔伯特旅馆)、整点集合、素数集合、有理数集合(凹型集合证明、跳过未约分分数)

凡是势比自然数集N高的集合,称不可数集合

其中与开区间(0,1)等势的集合,势记为\(\aleph_{1}\)。

势为\(\aleph_{1}\)的集合举例:闭区间[0,1],正整数集的幂集,无理数集,实数集(连续统,稠密无洞),平面单位正方形中的点集、平面点集、单位立方体点集、三维空间点集、单位超立方体乃至高维空间点集

(康托定理,对角化证明)

析取和合取

析取(\(\vee\))就是命题的交(和),合取(\(\wedge\))就是命题的并(或,可兼或)

蕴含(\( \rightarrow \))表示可从一个命推导至另一个命题,\(A \rightarrow B\) 即 \(\overline{A\overline{B}}\),当且仅当A真B假时此命题为假。其中A称为前件,B称为后件。

等价(\(\leftrightarrow\))A等价B当且仅当AB同真同假时为真。

注:上述都是逻辑运算符,而例如 \(\Leftrightarrow\) 为逻辑关系符,代表两个公式的等价关系,并非运算符,这点需要注意。

并且, \(A\Leftrightarrow B\) 的充要条件是\(A\leftrightarrow B\) 永真。

可判定性:若某公式能通过某些方式得知其是永真公式、永假公式还是可满足式(一般的),则称此公式具有可判定性。由于命题公式的变元数量是有限的,所以命题公式一定具有可判定性。

范式

文字:命题变元或者命题变元的否定称作文字

短语:有限个文字的合取称作短语(有限合取式)

子句:有限个文字的析取称作子句(有限析取式)

关系是一种特殊的集合,其中的所有元素都是n元有序对

关系可以以前、中、后缀表示法表达

关系有自反性、反自反性、对称性、反对称性、传递性五种特殊性质,(注意传递性比较麻烦且容易损失)

一个关系不可同时具有自反性和反自反性,但是可以同时具有对称性和反对称性(举例:恒等关系)。

等价关系(自反、对称、传递)==》等价类==》划分(非空、互不相交、并起来等于全集)==》第二类stirling数

(将m个元素的集合划分成n个等价类的方法数S(m,n))

S(m,n)=S(m-1,n-1)+nS(m-1,n)

(两类stirling数的基本模型及其递推、catalan数的应用(出入栈)以及其证明(抽象为走地图+镜像翻转证明))

一个元素数量为n的集合中可以存在\(\sum_{i=1}^{n} S(n,i)\)个等价关系(集合A对其中每一个等价关系的商集都唯一确定该集合的一个划分(集族))

恒等关系(幺关系)和全域关系是两种特殊的等价关系(都具有自反、对称、传递性),恒等关系中,每个元素都自己独立成为一个等价类;全域关系则是集合整体成为一个等价类

偏序关系(自反、反对称、传递)==》\(\preceq\) 小于等于==》集合A和其上的一个偏序关系组成的有序对叫作偏序集\(<A, \preceq>\)

整除关系是偏序关系!某集合的幂集中元素集合的包含关系是偏序关系,划分的加细也是偏序关系

可比关系:若一个偏序集的集合中两个元素a、b之间满足偏序关系(\(a\preceq b\)或\(b\preceq a\)都可),则称a和b是可比的

拟序关系:若a和b可比且不相等,则称a 严格小于 b,记做\(a\prec b\)(反自反,反对称,传递)(真整除、小于、真包含)

覆盖关系:若x严格小于y,且不存在中介元素z使得\(x\prec z\wedge z\prec y\),则称y覆盖x;(显然,覆盖关系具有反自反性、反对称性,不具有传递性)

哈斯图:上大下小,用节点表示集合中的元素,只在具有覆盖关系的元素之间用边来连接

全序关系(线序关系),若某个偏序集的集合中任意两个元素都可比,则称这个偏序集的偏序关系为全序关系,一个偏序关系为全序关系的充要条件是这个偏序关系的哈斯图为一条直线

拟全序关系(拟线序关系、三岐性):若某个拟序集的集合中任意两个元素要么满足逆序关系要么相等,则称该拟序关系为拟全序关系。

最大元(在集合中,且大于等于集合中所有元素,唯一)、极大元(在集合中,且集合中不存在大于其的元素,可以不唯一)、上界(可以不在集合中,且大于等于集合中所有元素,可以不唯一)、上确界(最小的上界,唯一)

链(元素互相可比的子集)、反链(元素互相不可比的子集)

良序关系:如果偏序集A的任意子集都有最小元,则称该偏序集为良序集,偏序关系为良序关系(自然数有良序关系,因此可以归纳)

Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments