kagami studio
0%

离散数学名词词典

发表于 更新于 分类于 ， Valine：
本文字数： 2.6k 阅读时长 ≈ 2 分钟

离散数学概念、定理多而杂，经常出现学完一章后，前面的内容就忘得差不多的情况。对此建立一个离散数学名词词典，方便查询与复习使用。 主要参考书籍：离散数学/李盘林等编著. –3版. –北京：高等教育出版社，2016.2

1 数理逻辑

1.1 命题逻辑

1.1.1 命题与联结词

命题、命题常元、命题变元、联结词（\(\lnot\) \(\land\) \(\lor\) \(\to\) \(\leftrightarrow\)）

1.1.2 命题公式、翻译和真值表

1.1.3 公式分类和等价式

有14条基本等价式–命题定律:

  1. 双否律
  2. 交换律
  3. 结合律
  4. 分配律
  5. 德摩根律
  6. 等幂律
  7. 同一律
  8. 零律
  9. 吸收律
  10. 互补律
  11. 条件式转化律
  12. 双条件式转化律
  13. 输出律
  14. 归谬律

简单地说，联结词符合上面的几条定律。

1.1.3.1 代入规则和替换规则

1.1.4 对偶式与蕴含式

1.1.4.1 对偶式

定义: 给定仅使用 \(\lnot\) \(\land\) \(\lor\) 中的命题公式\(A\)中

将\(\land\)与\(\lor\)互换,\(F\)与\(T\)互换

得到新的命题公式\(A^*\),称\(A^*\)为\(A\)的对偶式

有以下性质(对偶定理):

  • \(A\)的否定等价于其命题变元否定的对偶式
  • 命题变元否定的公式等价于对偶式之否定

定理:

\(A \Leftrightarrow B\) 则 \(A^* \Leftrightarrow B^*\)

1.1.4.2 蕴含式

定义: 设\(A\)与\(B\)是两个命题公式,若\(A\rightarrow B\)是永真式,则称\(A\)蕴含于\(B\),记作\(A \Rightarrow B\)

称\(A \Rightarrow B\)为蕴含式或永真式.

给出常见永真式:

  1. 化简式 \(A \land B \Rightarrow A\)
  2. 化简式 \(A \lor B \Rightarrow B\)
  3. 附加式 \(A \Rightarrow A \land B\)
  4. 附加式变形 \(\lnot A \Rightarrow A \rightarrow B\) (略,详见书 p19)

1.1.5 联结词扩充与功能完全组

为了简介而直接地表达命题间的联系,新定义联结词:

合取非(\(\uparrow\)) 析取非(\(\downarrow\)) 条件非(\(\nRightarrow\)) 双条件非(\(\nLeftrightarrow\))

外观上,就是以前用的符号加了个横杠,表示”非”

用法上,在原来的用法的基础上,前面加个”\(\lnot\)“即可

e.g. \(P\) 和 \(Q\) 均为 \(T\) 时 , \(P \downarrow Q\) 为 \(F\)

1.1.5.1 功能完全组

用部分联结词等价表示某个命题公式

1.1.6 范式

1.1.6.1 简单合取式 简单析取式

文字: 命题变元及其否定

相应地:相反文字

简单析取式: 由文字析取得到的命题公式 每个文字为析取项

类似地:简单合取式、合取项

1.1.6.2 析取范式 合取范式

析取范式:大于等于一个简单合取式的析取

类似地:合取范式

求范式步骤:

  1. 消掉 \(\land \lor \lnot\)以外的联结词
  2. 将\(\lnot\)都移到命题变元之前
  3. 利用结合律分配律等整理即可

1.1.6.3 应用

可用于判断永假式、永真式

此外,范式不唯一

1.1.7 公式的主范式

1.1.7.1 主析取范式

小项: 含有n个命题变元的简单合取式中,若每个命题变元与其否定不同时存在,且二者其中出现且仅出现一次,则称该简单合取式为小项,或布尔积

\(n\) 个命题变元生成 \(2^n\) 个小项

小项的书写: 命题变元按字典排列,命题变元对应1,命题变元的否定对应0,可对\(2^n\)个小项依二进制数编码,记为\(m_i\)

其中,i是由二进制转化的十进制数,据此编码可求得小项的真值表.观察表的结构:

  1. 各小项的真值表均不同
  2. 两个不同的小项合取式永假
  3. 所有小项析取式永真
  4. 每个小项只有一个成真指派

主析取范式: 给定公式的析取范式中,若其简单合取式都是小项,则称该范式为主析取范式.

定理: 任意含n个命题变元的非永假命题公式都存在与其等价的主析取范式

定理: 任意含n个命题变元的非永假命题公式,主析取范式唯一

1.1.7.2 主合取范式

大项: n个命题变元的简单析取式中, 若每个命题变元与其否定不同时存在,且二者其中出现且仅出现一次,则称该简单析取式为大项,或布尔和

\(n\) 个命题变元生成 \(2^n\) 个大项

大项的书写:编码与小项相同.得到真值表,观察结构:

  1. 各大项的真值表均不同
  2. 两个不同的大项析取式永真
  3. 所有大项合取式永假
  4. 每个大项只有一个解释为假

定理: 任意含n个命题变元的非永真命题公式都存在与其等价的主合取范式

定理: 任意含n个命题变元的非永真命题公式,主合取范式唯一

1.2 谓词逻辑

1.2.1 基本概念与表示

个体: 原子命题中描述的对象

表示特定的个体: 个体常元;表示不确定的个体:个体变元

谓词: 原子命题中,用以描述个体的性质或者个体间关系的部分

表示: 对于给定的命题,用小写字母(个体常元/变元)表示个体,大写字母表示谓词

e.g. \(P(a_1,a_2,\dots,a_n)\)

n=1:一元谓词;特别地,n=0:零元谓词,这是一个命题

达成了命题与谓词的统一

1.2.1.1 量词

\(\forall x\)、 \(\exists x\)、 \(\exists! x\)(存在唯一),称\(x\)为指导变元.

1.2.2 谓词公式与翻译

项:由以下规则形成: - 个体常元和个体变元是项 - 若\(f\)是\(n\)元函数,且\(t_1,t_2 \dot t_n\)是项,则\(f(t_1,t_2 \dot t_n)\)是项. - 所有项都是有限次地使用以上两条规则生成

谓词逻辑的翻译: 将文字叙述的命题,用谓词公式表示出来.反之亦然.

1.2.3 约束变元与自由变元

定义 给定一个谓词公式\(A\),其中一部分公式形如\((\forall x)B(x)\)或\((\exists x)B(x)\),则称它为\(A\)的\(x\) 约束部分,称\(B(x)\)为相应量词 作用域 或 辖域 ,在辖域中,\(x\)的所有出现称为约束出现,\(x\)称为约束变元;\(B\)中不是约束出现的其他个体变元的出现称为自由出现,这些个体变元称为自由变元.

看自由出现还是约束出现,要针对某个变元的辖域来讲.

约束变元->改名

自由变元->代入

共同点:不能改变约束关系.

1.2.4 谓词逻辑的解释及其赋值

(持续更新)