电子科技大学离散数学课程组国家精品课程汇总

7/1故5/2：020G1∧G2∧…∧Gn→H是永真公式。
8
电子科技大学离散数学课程组——国家精品课程
判定定理（续）
“”若G1∧G2∧…∧Gn→H是永真式，但G1, G2, …,Gn Ｈ不是有效的推理形式，
故存在G1, G2, …,Gn, H的一个解释I，使 得G1, G2, …,Gn都为真，而H为假，故 G1∧G2∧…∧Gn为真，而H为假，即是说 G1∧G2∧…∧Gn →H为假，这 就与 G1∧G2∧…∧Gn→H是永真式相矛盾，
公式。
7/15/2020
10
电子科技大学离散数学课程组——国家精品课程
5.2.2 判断有效结论的常用方法
要求
Г=｛G1, G2, …,Gn｝ Г H
也就是 G1∧G2∧…∧Gn→Ｈ 为永真公式
因而 真值表技术、演绎法和 间接证明方法
7/15/2020
11
电子科技大学离散数学课程组——国家精品课程
引入事实
事实库
规则匹配
新事实
事实=结论？
触发规则
N
公理库
将事实加入到事实库中
Y 结束
7/15/2020
19
电子科技大学离散数学课程组——国家精品课程
引入推理规则
在数理逻辑中，主要的推理规则有： ① P规则（称为前提引用规则）：在推导的过程中， 可随时引入前提集合中的任意一个前提； ② 规则Ｔ（逻辑结果引用规则）：在推导的过程 中，可以随时引入公式S，该公式S是由其前的一个 或多个公式推导出来的逻辑结果。 ③ 规则ＣＰ（附加前提规则）：如果能从给定的 前提集合Г与公式P推导出S，则能从此前提集合Г 推导出P→S。
结论：陈某是凶手。
则可描述为：P→R,┐R ┐P

例2.2.4
由 Alice 、 Ben 、 Connie 、 Dolph 、 Egbert 和 Francisco六个人组成的委员会，要选出一个主席、 一个秘书和一个出纳员。 （1）共有多少种选法？ （2）若主席必须从Alice和Ben种选出，共有多少 种选法？ （3）若Egbert必须有职位，共有多少种选法？ （4）若Dolph和Francisco都有职位，共有多少种 选法？
2.2.1 乘法原理
如果一些工作需要t步完成，第一步有n1种 不同的选择，第二步有n2种不同的选择，… ， 第t步有nt种不同的选择，那么完成这项工作所 有可能的选择种数为：
n1×n2××nt
例2.2.2 Melissa病毒
1990年，一种名叫Melissa的病毒利用侵吞系统资源的 方法来破坏计算机系统，通过以含恶意宏的字处理文 档为附件的电子邮件传播。当字处理文档被打开时， 宏从用户的地址本中找出前50个地址，并将病毒转发 给他们。用户接收到这些被转发的附件并将字处理文 档打开后，病毒会自动继续转发，不断往复扩散。病
3
1 离散概率 2 离散概念的计 算公式及性质
表2.2.1
开胃食品
种类
价格 (元)
玉米片 2.15 (Co)
色拉(Sa) 1.90
主食
饮料
种类 价格 种类 价格
汉堡(H) 3.25 茶水(T) 0.70
三明治 3.65 牛奶 0.85
(S)
(M)
鱼排(F) 3.15 可乐(C) 0.75
啤酒(B) 0.75
例2.3.1
从含3个不同元素的集合S中有序选取2个元素的排 列总数。 解 从含3个元素的不同集合S中有序选取2个元素 的排列总数为6种。 如果将这3个元素记为A、B和C，则6个排列为

3/4[13]…
所以，有理数集合必是可数集合。
2019/9/16
67-9
电子科技大学离散数学课程组——国家精品课程
定理1.3.1
两个有限集合等势当且仅当它们有相同 的元素个数；
有限集合不和其任何真子集等势； 可数集合可以和其可数的真子集等势。
2019/9/16
67-10
电子科技大学离散数学课程组——国家精品课程
67-7
电子科技大学离散数学课程组——国家精品课程
2）
在P与N之间建立1-1对应的关系f：N→P如下： N ０ １ ２ ３ ４ ... ｆ ↓ ↓ ↓ ↓ ↓ ... P ２ ３ ５ ７ 11 ...
所以，P是可数集合。
2019/9/16
67-8
电子科技大学离散数学课程组——国家精品课程
3）
→ …-3/1[18] -2/1[5] -1/1[4] 0/1[0] 1/1[1] 2/1[10] -3/1[11]…
定义1.3.1 设A，B是两个集合，若在A，B之 间存在1-1对应的关系：
ψ：A→B 则称A与B是等势的(equipotential)，记为：AB。 也称集合A与B等势(equipotent)。
注意：若A＝B，则 AB。 （∨）
若AB，则 A＝B
（×）
2019/9/16
67-5
电子科技大学离散数学课程组——国家精品课程
例2.4.3 解（续）
设只会英、日、德、法语的人数分别为x1,x2,x3,x4， 则
x1＝|A|－|(B∪C∪D)∩A| ＝|A|－|(B∩A)∪(C∩A)∪(D∩A)|
对B∩A、C∩A、D∩A应用容斥原理，得
|(B∩A)∪(C∩A)∪(D∩A)|

置可用二进制信号表示。试问如何选取鼓轮 16 个部分的材
料才能使鼓轮每转过一个部分得到一个不同的二进制信号， 即每转一周，能得到0000到1111的16个数。
2015/12/25 110-23
电子科技大学离散数学课程组——国家精品课程 双语示范课程
电子科技大学离散数学课程组——国家精品课程 双语示范课程
3、计算机鼓轮设计
假设一个旋转鼓的表面被等 分为 24 个部分，如图所示，其中 每一部分分别由导体或绝缘体构 成，图中阴影部分表示导体，空 白部分表示绝缘体，导体部分给 出信号 1 ，绝缘体部分给出信号 0 。 根据鼓轮转动时所处的位置， 四个触头 A 、B 、C 、 D 将获得一定的信息。因此，鼓轮的位
以上定义既适合无向图，又适合有向图。
2015/12/25
110-6
电子科技大学离散数学课程组——国家精品课程 双语示范课程
欧拉通路和欧拉回路的特征
欧拉通路是经过图中所有边的通路中长度最短 的通路，即为通过图中所有边的简单通路；
欧拉回路是经过图中所有边的回路中长度最短 的回路，即为通过图中所有边的简单回路。 如果仅用边来描述，欧拉通路和欧拉回路就是 图中所有边的一种全排列。
P12 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8e9v2e10v4e11v6e12v8e8v1
110-18
2015/12/25
电子科技大学离散数学课程组——国家精品课程 双语示范课程
11.2.3 欧拉图的难点
1. 仅有欧拉通路而无欧拉回路的图不是欧拉图；
2. 图中是否存在欧拉通路、欧拉回路图的判定非 常简单，只需要数一下图中结点的度数即可； 3. 使用 Fleury 算法求欧拉通路 ( 回路 ) 时，每次走 一条边，在可能的情况下，不走桥。