离散数学

第一章 集合论

1.1 集合的基本概念

指定范围内的每一个对象被称为这个集合的元素

集合 中的元素个数被称为集合 基数

基数有限的集合称为有限集,反之称为无限集

集合中的元素满足无序且互异

为任意两集合,如果 中每个元素都是 中的元素则称 子集,也称 包含,或 包含 ,记作

为任意两集合,如果 则称 真子集,记作

不含任何元素的集合叫做空集,记作

在一个相对固定的范围内,包含此范围内所有元素的集合称为全集或论集,用 表示

为任意集合,称 的所有不同子集构成的集合为 幂集,记作 ,即

  1. 称含有 个元素的集合为 元集
  2. 元集,则称 的含有 个元素的子集为它的 元子集

1.2 集合的运算

称为 并集,称 “”为并运算

称为 交集,称 “”为交运算

称为 差集,称 “”为差运算 又可叫做相对补集

特别指出,当 时, 称为集合 的补集,记为 称为补运算

称为 对称差集,称 “”为对称差运算

1.3 无限集

为两个集合,若在 之间存在一一对应关系 则称 等势的

凡与自然数集 等势的集合,称为可数集(可列集),该集合的基数记为 ,读作“阿列夫零”

  1. 两个有限集等势当且仅当它们有相同的元素个数
  2. 有限集不和其任何真子集等势
  3. 可数集可以和其可数的真子集等势

称开区间 不可数集,其基数称为 ,凡与开区间 等势的集合都是不可数集

第二章 命题逻辑

2.1 命题与命题联结词

能够判断真假陈述句称为命题。称“真”和“假”为命题的真值

不能再分解为更简单命题的命题,称为原子命题(简单命题);像“或者”这种连接命题的关联词称为命题联结词;由命题联结词联结原子命题而成的命题称为复合命题

  1. 否定联结词

    是任意一个命题,称复合命题“非 ”为 的否定,记作 ,称符号 否定联结词

  2. 合取联结词

    是任意两个命题,称复合命题“ 并且 ”为 合取,记作 ,称符号 合取联结词

  3. 析取联结词

    是任意两个命题,称复合命题“”为 析取,记作 ,称符号 析取联结词

  4. 蕴含联结词

    是任意两个命题,称复合命题“如果 ,则 ”为 蕴含,记作 ,称符号 蕴含联结词 为蕴含式的前件 为蕴含式的后件

  5. 等价联结词

    是任意两个命题,称复合命题“ 当且仅当 ”为 等价,记作 ,称符号 等价联结词

自然语言描述 符号化结果
仅当
除非 ,否则非

2.2 命题公式、解释与真值表

原子命题又常被称作命题常量,或常值命题

字母 通常被称为命题变量,或命题变元

命题公式 又被称为 真值函数

命题演算的合式公式,又称命题公式,可按递归规则定义

是出现在公式 中的所有命题变元,给它们各指定一个真值,则称这些指定的真值组成 的一个解释(或赋值),常记为

若赋值 使 取值为真则称这个赋值为成真赋值,也称 满足于 ;反之称成假赋值,也称 弄假与

个不同的解释及 对应的真值构成一张表称为 真值表

任意解释 ,公式 的真值全为真则称 永真公式(重言式);如果全为假则称 永假公式(矛盾式);如果存在至少一个为真称为可满足公式

两个命题公式, 是出现在 中的所有命题变元。如果对于 组不同的解释, 的结果都相同,则称公式 等价,记作

的充要条件是 是永真公式

2.3 公式的标准型——范式

如果任意一个命题公式都可用 中的联结词进行等价表示,则称 联结词的完备集

是一个联结词的完备集且 。如果至少存在一个命题公式不能用 中的联结词进行等价表示,则称 极小联结词的完备集

称命题变元或命题变元的否定为文字

如果一个命题公式具有形式 其中 是文字,则称该命题公式为合取式或短语

如果一个命题公式具有形式 其中 是文字,则称该命题公式为析取式或子句

如果一个命题公式具有形式 其中 是析取式,则称该命题公式为合取范式

如果一个命题公式具有形式 其中 是合取式,则称该命题公式为析取范式

  1. 单个的文字是合取式、析取式、析取范式、合取范式
  2. 析取范式、合取范式仅含联结词
  3. 有括号的公式必须作为一个整体来看,如 是合取范式但不是析取范式

在含有 个命题变元 的合/析取式中,若每个命题变元与其否定不同时存在但二者之一恰好出现一次且仅一次,则称此合/析取式为关于 的一个极小/大项

如果一个命题公式具有形式 其中 是极大项,则称该命题公式为主合取范式

如果一个命题公式具有形式 其中 是极小式,则称该命题公式为主析取范式

编码规则

利用真值表计算主范式的方法被称为真值表技术

是命题公式。对任意解释 ,如果 为真, 也为真,则称 逻辑结果,或者 共同蕴含 ,记作

是命题公式,如果 的逻辑结果,则称 有效的或者正确的,否则称为无效的,称 为一组前提结论

等价公式转换法

  1. 合取所有前提作为蕴含式的前件,结论作为蕴含式的后件
  2. 化简蕴含式
  3. 如果结果为 则推理有效否则无效

演绎法

推理规则

  1. P 规则:引入前提
  2. T 规则:引入推理过程的中间结果
  3. CP 规则:如果逻辑结果为蕴含式,并将逻辑式的前件作为前提引入

引入的定理

  1. I:推理定理
  2. E:等价定理

反证法:在 的证明过程中,将 作为附加前提然后推出矛盾的方法

是两个析取式,如果 中有文字 中有文字 ,则从 中分别消去 ,并将余下的部分析取构成一个新的析取式 ,这个过程称为消解 被称为 消解式

消解原理:如果 的消解式,则

第三章 谓词逻辑

3.1 自然语言的谓词符号化

在原子命题中,可以独立存在的客体称为个体词,用以刻画客体性质或客体之间关系的部分称为谓词

具体明确的个体称为个体常量,个体常量一般用带或不带下标的小写英文字母 等表示

泛指的或抽象的个体称为个体变量,一般用带或不带下标的小写英文字母 表示

个体变量的取值范围称为个体域(或论域),常用字母 表示

宇宙间的所有个体聚集在一起所构成的个体域称为全总个体域

是定义在 元函数,其中 为非空的个体域,如果 的值域是 ,则称 元命题函数或者 谓词

表示全部数量关系的词语称为全称量词,记为

表示部分数量关系的词语称为存在量词,记为

其中 被称为作用变量

一般将量词加在对应的谓词之前,记为 。此时 被称为全称量词和存在量词的辖域

为了描述的统一性和方便性,将表示个体域的名词称为特性谓词,并用一元谓词表示。一般来说量词后的名词即为特性谓词

3.2 谓词公式与解释

函数的定义域和值域都是个体域

谓词的定义域是 ,值域是

元谓词符号化涉及到的符号总结如下

  1. 常量符号:用带或不带下标的小写英文字母 表示,当个体域 给出时它可以是 中某个确定的元素

  2. 变量符号:用带或不带下标的小写英文字母 表示,当个体域 给出时它可以是 中的任意元素

  3. 函数符号:用带或不带下标的小写英文字母 表示,当个体域 给出时, 元函数 可以是 的任意一个函数

  4. 谓词符号:用带或不带下标的大写英文字母 表示,当个体域 给出时, 元谓词 可以是 的任意一个谓词

谓词逻辑中的递归定义

  1. 任意的常量符号或变量符号是项
  2. 元函数符号, 是项,则 也是项
  3. 有限次使用 1 和 2 后得到的符号串都是项

注意:项是个体域 中的某个个体次

元谓词, 是项,则称 原子谓词公式,简称原子公式

合式谓词公式可按递归规则生成

给定公式 的辖域,则 的出现都约束出现,称变元 约束变元 中的不同于 的其他变元的出现则是自由出现,称这些变元为自由变元

  1. 约束变元改名规则,简称改名规则
    1. 将量词辖域内与作用变元相同的约束变元都用新的个体变元替换
    2. 新的变元一定要有别于改名辖域中的所有其他变元
  2. 自由变元带入规则,简称带入规则
    1. 将公示中出现某个自由变元的每一处都用新的个体变元或个体常量替换
    2. 新变元不允许在原公式中以任何约束形式出现

是任意一个公式,若 中无自由变元则称 封闭的公式,简称闭式,闭式一定是命题

谓词逻辑中谓词公式 的每一个解释 由如下四个部分组成

  1. 非空的个体域
  2. 中的每个常量符号,指定 中某个特定元素
  3. 中每个 元函数符号,指定 的某个函数
  4. 中的每个 元谓词符号,指定 的某个特定谓词

任意解释 ,谓词公式 的真值全为真则称 永真公式;如果全为假则称 永假公式;如果存在至少一个为真称为可满足公式

是谓词公式,如果谓词公式 是永真公式,那么 等价的,记为

3.3 谓词公式的标准型——前束范式

具有形式 形式的谓词公式称为前束范式,其中 为量词 为不含量词的公式

设公式 是一个前束合取范式,按照从左到右去掉 中的存在量词,若 是存在量词且 ,则直接用个体变量取代 中所有的 ,并在 中删去 ,若 都是全称量词,则在 中使用一个未使用过的函数符号如 ,并用 替换 中所有的 ,然后删去 。重复此过程直到没有存在量词。这样得到的公式称为 Skolem 范式

3.4 谓词逻辑的推理理论

在谓词公式 中,若 不自由出现在量词 的辖域中,则称 对于 是自由的

  1. 推理规则

    1. UI:全称量词消去

      取代 的新变元在新公式中是自由出现的

    2. EI:存在量词消去

      如果 中还有出 以外的自由变元,需要用这些变元的函数符号来取代

    3. UG:全称量词引入

      自由才可以引入

    4. EG:存在量词引入

      取代 在原公式中不曾出现过

  2. 推理定律

如果需要使用 UI 和 EI 规则并且选用的个体常量是同一个符号,则必须先使用 EI 规则再使用 UI 规则

第四章 二元关系

4.1 二元关系及其表示

由两个元素 按照一定次序组成的二元组称为有序偶对,简称序偶,记作

是两个集合,称集合 为集合 笛卡尔积

个集合,称集合 为集合 的笛卡尔积

时,可记

为两个非空集合,称 的任意子集 为从 的一个二元关系,简称关系,记作 。如果 ,则称 上的一个二元关系,记作

序偶 ,可记作 ,读作“ 有关系

时,称 空关系

时,称 全关系

时,称 上的恒等关系

个集合,称 的子集 为以 为基的 元关系

,此时 称为 前域 称为 后域 称为 定义域,记作 称为 值域,记作 称为

是从 的二元关系,称矩阵 为关系 关系矩阵

  1. 如果 是两个 布尔矩阵,则布尔并也是 矩阵,记作
  2. 如果 是两个 布尔矩阵,则布尔交也是 布尔矩阵,记作
  3. 如果 是两个 布尔矩阵,则布尔积也是 布尔矩阵,记作

4.2 关系的运算

是三个集合