Discrete Maths

Posted by Sakura on June 25, 2018

离散数学

前言

离散数学是武汉大学计算机学院软件工程专业大一下半学期所学习的一门专业课,教材为黑色砖头系列书籍离散数学及其应用,这个专题的博客为该课程学习的粗略提纲。


基础:逻辑和证明

命题逻辑

命题是一个陈述语句(即陈述事实的语句),它或真或假,但不能既真又假。

如果一个命题是真命题,那么它的真值为真

涉及命题的逻辑领域称为命题演算命题逻辑

按照优先级从高到低

  • 优先级最高
    • 命题的否定
  • 优先级中间
    • 命题的合取(只有两个命题都为真时才为真)
    • 命题的析取(只有两个命题都为假时才为假)
    • 命题的异或(当两个命题恰好一真一假时才为真,否则为假)
  • 优先级最低
    • 条件语句(也被称为蕴含)
    • 双向蕴含(互为充分必要条件)

复合命题的真值表

逻辑运算和位运算

命题等价式

一个真值永远是真的复合命题称为永真式(tautology),一个真值永远为假的复合命题称为矛盾式(contradiction),既不是永真式又不是矛盾式的复合命题称为可能式(contingency)

如果两个命题的双向蕴含是永真式,那么这两个命题是逻辑等价的,可以用真值表来证明两个命题的逻辑等价。

若干重要的等价式:

example

其中,德摩根律可以进行扩展

由上表可以证明出很多式子之间的逻辑等价性。

谓词和量词

谓词逻辑是含有变量的语句,当变量值未被指定的时候,这些语句既不为真也不为假。

  • 例如令P(x)表示语句“x>3”,那么P(4)和P(2)具有不同的真值。

当命题函数中的变量均被赋值时,所得到的语句就变成某个具有某个真值的命题。但还有另一种称为量化的重要方式可以从命题函数生成一个命题。量化表示在何种程度上谓词对于一定范围的个体成立,所有、某些、许多、没有等都可以用在量化上。

我们讨论两类量化:

  • 全称量词:表示断言某一性质对于变量在某一特定域内的所有值都为真
  • 存在量词:表示断言某一性质对于变量在某一特定域中存在至少一个值为真

全称量词和存在量词比命题演算中的所有逻辑运算符都具有更高的优先级。

量词的德摩根律:

  • P(x)的存在量词语句的否定,为非P(x)的的全称量词
  • P(x)的全称量词语句的否定,为非P(x)的的存在量词

嵌套量词

example

推理规则

命题逻辑的推理规则:

example example

量化命题的推理规则:

example

证明导论

  • 直接证明法
  • 反证法
  • 归谬证明法

基本结构:集合、函数与矩阵

集合

集合是对象的一个无序的聚集,对象也称为集合的元素或成员。集合包含它的元素。

  • 相关定义:空集、文氏图、开区间、闭区间、集合的相等、全集、子集
  • 集合的大小:用基数cardinality来表示
  • 幂集(power set)是某集合所有子集的集合
  • 集合的笛卡尔积

集合运算

  • 并集、交集、补集

集合恒等式:

example example

函数

定义1:A和B为非空集合,从A到B的函数f是对元素的一种指派,对A的每个元素恰好指派B的一个元素。如果B中元素b是唯一由函数f指派给A中元素a的,则我们写成f(a)=b,如果f是从A到B的函数,就写成f:A→B 定义2:f是从A到B的函数,那么A是f的定义域,B是f的陪域。如果f(a)=b,我们说b是a的像,而a是b的原像。f的值域是A中元素所有像的集合。

一对一函数:函数f是一对一函数或者单射函数,当且仅当对于f的定义域中所有a和b有f(a)=f(b)蕴涵a=b。

映上函数:一个从A到B的函数f称为映上或满射函数,当且仅当对每个属于B的元素b有A中的元素a使得f(a)=b。

双射函数:既是一对一的又是映上的函数称为双射函数

一些重要的函数

  • 向上取整函数
  • 向下取整函数
  • 阶乘函数

矩阵

  • 矩阵的加法、乘法
  • 矩阵的转置
    • 和转置矩阵相等的矩阵称为对称矩阵
  • 矩阵的幂
  • 0-1矩阵
    • 0-1矩阵的并和交
  • 矩阵的布尔积

关系

关系及其性质

设A和B是集合,一个从A到B的二元关系是A×B的子集。

举例:设A是学校学生的集合,B是课程的集合,令R是由(a,b)对构成的关系,其中a是选修课程b的学生。例如如果姚文卿选修了离散数学,那么(姚文卿,离散数学)属于R,如果姚文卿没有选修线性代数,那么(姚文卿,线性代数)不在R中。

定义在集合上的关系:集合A上的关系是从A到A的关系。

关系的性质:

  • 自反性:若对A中的每个元素a都有(a,a)属于R,那么定义在集合A上的关系R称为自反的。
  • 对称性:对于A中的任意元素a和b,若只要(a,b)属于R就有(b,a)属于R,则称定义在集合A上的关系R为对称的。
  • 反对称:对于A中的任意元素a和b,若只要(a,b)属于R且(b,a)属于R,就一定有a=b,则称定义在集合A上的关系R为反对称的。
  • 传递性:对于A中的任意元素a、b和c,若(a,b)属于R,(b,c)属于R,就有(a,c)属于R,则称定义在集合A上的关系R为传递的。

关系的合成:设R是从集合A到集合B的关系,S是从集合B到集合C的关系。R与S的合成是由有序对(a,c)的集合构成的关系,其中a属于A,c属于C,并且存在一个B中的元素b,使得(a,b)属于R且(b,c)属于S。

关系的n次幂被递归定义,为关系对自己本身的n-1次合成。

关系的表示

  • 用0-1矩阵表示关系
    • 通过矩阵的主对角线上的元素判断自反性
    • 通过矩阵是否对称判断对称性
    • 关系的交和关系的并
    • 表示关系合成的矩阵(矩阵相乘,大于等于1的地方记为1)
    • 表示关系幂的矩阵
  • 用图表示关系
    • 每个元素是一个点,每个有序对是一条带有箭头的弧
    • 对称关系可以用无向图表示

关系的闭包

设R是集合A上的关系。R可能具有或者不具有某些性质P,例如自反性、对称性或传递性,如果存在包含R的具有性质P的关系S,而且S是所有包含R且具有性质P的关系的子集,那么S叫做R的关于性质P的闭包。

  • 自反闭包的寻找,将矩阵主对角线上元素全变成1并加入对应的映射
  • 对称闭包的寻找,将矩阵变为对称阵,变的过程只将0变为1,并加入对应的映射
  • 传递闭包:即在集合A上的关系R存在一条连通性的通路,寻找采用沃舍尔算法

等价关系

等价关系:定义在集合A上的关系叫做等价关系,如果它是自反的、对称的和传递的

等价类:设A是武汉大学所有的学生的集合,考虑定义在集合A上的关系R,R由所有的对(x,y)构成,其中x和y从同一高中毕业。给定学生x,我们可以形成与x具有R等价关系的所有学生的集合。这个集合由与x在同一高中毕业的所有学生构成。A的这个子集叫做这个关系的一个等价类。

设R是集合A上的等价关系,与A中的一个元素a有关系的所有元素的集合叫做a的等价类

等价类与划分:设R是集合S上的等价关系,那么R的等价类构成S的划分

偏序

定义在集合S上的关系R,如果它是自反的、反对称的和传递的,就称为偏序。集合S与定义在其上的偏序R一起称为偏序集,记做(S,R)。集合S中的成员称为偏序集中的元素。