离散数学
第一章命题逻辑
1.1 命题及其表示方法
1.2 联结词
1.3 命题公式与翻译
1.4 真值表与等价公式
1.5 重言式与蕴含式
1.6 其它联结词
1.7 对偶与范式
1.8 推理理论
1.1 命题及其表示方法
命题：具有确定真值的陈述句
命题的类型（原子命题和复合命题）
命题的表示（一个命题标识符（比如P）表示确定的命题）
重点：如何判断语句是否为命题。
1.2 联结词
否定?
合取∧
析取∨
条件→
双条件?
重点：五种联结词的含义、真值表
1.3 命题公式与翻译
命题公式
符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由
命题标识符、联结词和括号表示的合式公式。
命题符号化的重要性
命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。
重点：命题的符号化
符号化应该注意下列事项:
①确定给定句子是否为命题。
②句子中连词是否为命题联结词。
③要正确地表示原子命题和适当选择命题联结词。
1.4 真值表与等价公式
真值表的构造方法
(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺
序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.
(2) 按从低到高的顺序写出公式的各个层次.
(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.
等价关系的含义
等价式的判别方法
?真值表法
?等价演算法
基本等价式（必须掌握）
(1)对合律（双重否定）：??P?P
(2)幂等律：P∧P?P，P∨P?P
(3)结合律：(P∧Q)∧R?P∧(Q∧R)，
(P∨Q)∨R?P∨(Q∨R)
(4)交换律：P∧Q?Q∧P，P∨Q?Q∨P
(5)分配律：P∧(Q∨R)?(P∧Q)∨(P∧R)，
P∨(Q∧R)?(P∨Q)∧(P∨R)
(6)德·摩根律：? (P∧Q) ??P∨?Q，
? (P∨Q) ??P∧?Q
(7)吸收律：P∧(P∨Q)?P，P∨(P∧Q)?P
(8)同一律：P∧T?P，P∨F?P
(9)零律：P∧F?F，P∨T?T
(10)否定律：P∧?P?F，P∨?P?T
(11) 条件式转化律：
P→Q??P∨Q，
P→Q??Q→?P
(12) 双条件式转化律：
P?Q ?(P→Q)∧(Q→P) ?(P∧Q)∨(?P∧?Q)
? (P?Q) ?P??Q ??P?Q
(13) 输出律(CP规则)：
P→(Q→R) ?(P∧Q)→R
重点：等价式的证明、基本等价式
1.5 重言式与蕴含式
重言式或永真公式
定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。
矛盾式（永假式）
定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为假，则称该命题公式为矛盾式或永假公式。
可满足式
如果命题公式既不是重言式，也不是矛盾式，则称该命题公式是可满足式。
重言式的性质定理
任何两个重言式的合取或析取，仍然是一个重言式。
一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。（代入规则）
等价
设A 、B 为两个命题公式, A ? B 当且仅当A ? B 为一重言式。
蕴含
定义1-5.3 当且仅当P→Q 是一个重言式，我们称“P 蕴含Q” ，或“Q 是P 的有效结论” ，并记作P ? Q.
等价与蕴含的关系
设P、Q为任意两个命题公式，P ? Q 的充要条件是P ? Q 且Q ? P.
常用的蕴含式（必须掌握）
[1].附加规则：P?(P∨Q)，Q?(P∨Q)
[2].化简规则：(P∧Q)?P, (P∧Q)?Q
[3].合取引入规则：P ,Q?P∧Q
[4].假言推理：P∧ (P→Q) ?Q
[5].拒取式（反证法）：?Q ∧ (P→Q) ??P
[6].析取三段论（排除法）：?Q ∧ (P∨Q) ?P
[7].假言三段论（传递性）：(P→Q)∧(Q→R)?(P→R)
[8].二难推论：
?(P→R)∧(Q→R)∧(P∨Q)?R //简单型
?(P→R)∧(Q→S)∧(P∨Q)?(R∨S) //复杂型
[9].等价三段论：( P?Q)∧(Q?R)?(P?R)
[10]. (P→Q)∧(R→S)?(P ∧ R)→ (Q ∧S)
重点：（1）判定重言式、矛盾式、可满足式。（2）蕴含式的证明方法。
（3）逆换式、反换式、逆反式的求法。
1.6 其它联结词
（1）不可兼析取
（2）条件否定
（3）与非↑
（4）或非↓
全功能联结词组：任一个公式都可以用仅含联结词组中的联结词表示。
最小全功能联结词组：{?, ∧}、{?,∧}、{?, →}、{?, c→}。
重点：（1）四种联结词的性质和真值表。（2）最小全功能联结词组的判定方法。
1.7 对偶与范式
对偶式
定义1-7.1 在给定的命题公式 A 中，将联结词∧换成∨，将∨换成∧，若有特殊变元 F 和T 亦相互取代，所得公式A* 称为 A 的对偶式。
对偶式的性质
如果 A ? B, 则A* ? B*。
合取范式
定义1-7.2 一个命题公式称为合取范式，当且仅当它具有型式：
A1∧A2∧… ∧A n( n≥1)
其中，A1 , A2, … , A n 都是由命题变元或其否定所组成的析取式。
析取范式
定义1-7.3 一个命题公式称为析取范式，当且仅当它具有型式：
A1∨A2∨… ∨A n( n≥1)
其中，A1 , A2, … , A n 都是由命题变元或其否定所组成的合取式。
范式的求法
?将公式中的联结词化归成∧∨?。
?利用德?摩根律将?消去或内移。
?利用分配律、结合律将公式归约为合取(析取)范式。
主范式
·一个命题公式的合取范式或析取范式并不是唯一的。
·那么，如何使任意一个命题公式化成唯一等价命题的标准形式呢？
·解决方案：主范式（主析取范式和主合取范式）
主析取范式
·定义1-7.4（小项）n 个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
·定义1-7.5 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。
主析取范式的求法—等价演算法
?化为析取范式。
?除去其中所有永假的合取式。
?在合取式中合并相同的命题变元。
?对合取式补入没有出现的命题变元，即添加（P ∨?P）式，然后应用分配律展开公式。
?除去相同的小项，并将小项按编号由小到大的顺序排列。
主析取范式的用途
●判别命题公式的类型
?永真式：包含所有的小项
?矛盾式：没有小项
?可满足式：包含部分小项
●给出命题公式的成真赋值或成假赋值
?成真赋值：出现的小项对应的真值指派
?成假赋值：没有出现的小项对应的真值指派
●判别两个命题公式是否等价
主合取范式
●定义1-7.6（大项）大项n 个命题变元的析取式，称作布尔析取或大项，
其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
●定义1-7.7 对于给定的命题公式，如果有一个等价公式，它仅由大项的
合取所组成，则该等价式称作原式的主合取范式。
主合取范式的求法—等价演算法
?化为合取范式。
?除去其中所有永真的析取式。
?在析取式中合并相同的命题变元。
?对析取式补入没有出现的命题变元，即添加（P ∧?P）式，然后应用分配律展开公式。
?除去相同的大项，并将大项按编号由小到大的顺序排列。
主合取范式的用途
●判别命题公式的类型
?永真式：没有大项
?永假式：包含所有的大项
?可满足式：包含部分大项
●给出命题公式的成真赋值或成假赋值
?成真赋值：没有出现的大项对应的真值指派
?成假赋值：出现的大项对应的真值指派
●判别两个命题公式是否等价
重点：（1）对偶式的求法。（2）析取范式、合取范式、主合取范式、主析取范式的求法、用途、应用。
1.8 推理理论
●定义1-8.1 设A和C是两个命题公式，当且仅当A →C 是一重言式，即A ?C，称C是A的有效结论。
●论证方法：
?真值表法
?直接证法
?间接证法
1. 真值表法
●从真值表上找出H1 , H2 ,… , H n 真值均为T (1)的行，对每一个这样的行，若C 的真值也为T(1), 则H1 ∧ H2 ∧… ∧ H n ?C 成立。
●或看C为F (0) 的行, 在每个这样的行中，H1 , H2 ,… , H n 真值中至少有一个为F(0), 则H1 ∧ H2 ∧… ∧ H n ?C 也成立。
2. 直接证法
●由一组前提, 利用一些公认的推理规则,根据已知的等价或蕴含式, 推演得到有效的结论。
●P规则:前提在推导过程中任何时候都可引用、使用。
●T规则:在推导中,若有一个或多个公式重言蕴含着公式S, 则S 可引入推导中。
3. 间接证法
●欲证H1∧ H2∧…∧H m?C, 即只要证明公式H1∧ H2∧…∧H m∧? C永假
●CP 规则
欲证H1∧ H2∧…∧H m?（R→C）, 即只要证明公式（H1∧ H2∧…∧H m∧R）→C 永真
重点：有效结论的判定方法。
第二章谓词逻辑
2.1 谓词的概念与表示
2.2 命题函数与量词
2.3 谓词公式与翻译
2.4 变元的约束
2.5 谓词演算的等价式与蕴含式
2.6 前束范式
2.7 谓词演算的推理理论
2.1 谓词的概念和表示
2.2 命题函数与量词
全称量词
●?：称为全称量词，用以表达“对所有的”，“每一个”，“对任一个”等。
●对于?，表示客体变化范围的特性谓词通常作为条件联接词的前件。
例：
每个学生都要参加考试。
P(x): x 是学生，Q(x): x 要参加考试，
(?x) (P(x) →Q(x))
存在量词
●?：称为存在量词，用以表达“存在一些”，“至少有一个”，“对于一些”等。
●对于?，表示客体变化范围的特性谓词通常作为合取项。
例：
有一些人是聪明的
M(x): x 是人，R(x): x 是聪明的。
(?x)(M(x) ∧ R(x))
2.3 谓词公式与翻译
重点：命题的符号化
2.4 变元的约束
指导变元、作用域、约束变元、自由变元
●给定一个谓词公式，其中有一部分公式的形式为：(?x) P(x) 或(?x) P(x) 。?这里?、?后面的x叫做量词的指导变元（作用变元），P(x)叫做相应量词的作用域（辖域）。
●在作用域中x的一切出现称为x在公式中的约束出现，x称为约束变元。
●在公式中除去约束变元之外所出现的变元称作自由变元。
约束变元的换名规则：
1) 换名范围:量词中的指导变元和作用域中出现的该变元.公式中其余部分不变.
2) 要换成作用域中没有出现的变元名称.
自由变元代入的规则：
1) 对该自由变元每一处进行代入.
2) 代入的变元与原公式中所有变元名称不能相同.
有限的个体域
●量词作用域中的约束变元，当论域的元素是有限时, 客体变元的所有可能的取代是可枚举的。
●设论域的元素是a1,a2,…,a n，则
●?x A(x) ? A(a1) ∧… ∧ A(a n)
●?x A(x) ? A(a1) ∨… ∨ A(a n)
重点：约束变元换名、自由变元代入方法。
2.5 谓词演算的等价式与蕴含式
等价
●定义2-5.1 给定任何两个谓词公式wff A和wff B，设它们有共同的个体域E, 若对A和B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的，并记作：A?B
永真的、不可满足的、可满足的
●定义2-5.2 给定任意谓词公式wff A，其个体域为E，对于A的所有赋值，wff A都真,则称wff A在E上是永真的(有效的)。
●定义2-5.3 一谓词公式wff A，若在所有赋值下都为假，则称wff A 是不可满足的。
●定义2-5.4 一谓词公式wff A，若至少在一种赋值下为真，则称wff A 是可满足的。
谓词演算的等价式
(1) 量词分配律
(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x)
(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x)
(2) 量词否定律
?(?x)A?(?x)?A
?(?x)A ?(?x)?A
3）量词作用域的扩张与收缩律
(?x )(A (x )∧B )?(?x )A (x )∧B
(?x )(A (x )∨B )?(?x )A (x )∨B
(?x )(A (x )→B )?(?x )A (x )→B
(?x )(B →A (x ))?B →(?x )A (x
)
(?x )(A (x )∧B )?(?x )A (x )∧B
(?x )(A (x )∨B )?(?x )A (x )∨B
(?x )(A (x )→B )?(?x )A (x )→B
(?x )(B →A (x ))?B →(?x )A (x )
（4）其他等价式
谓词演算的蕴含式
((?x )A (x )∨(?x )B (x )?(?x )(A (x )∨B (x
))
(?x )(A (x )∧B (x ))?(?x )A (x )∧(?x )B (x )
(?x )(A (x ) ? B (x ))?(?x )A (x ) ?(?x )B (x
)
(?x )(A (x )→B (x ))?(?x )A (x )→(?x )B (x
)
(?x )(A (x )→B (x ))?(?x )A (x )→(?x )B (x
)
(?x )A (x )→(?x )B (x ) ?(?x )(A (x )→B (x ))
(?x )A (x ) ?(?x )A (x
)
第70-71页的8个公式
重点：基本的等价式和蕴含式。等价式和蕴含式的证明。
2.6前束范式
前束范式
●定义2-6.1 一个公式若量词均在全式的开头,作用域延伸到整个公式,则该公式叫做前束范式.
前束合(析)取范式
范式存在定理
●定理2-6.1 任何一个谓词公式均有与其等价的前束范式。
●定理2-6.2 任何一个谓词公式均可转为与其等价的前束合取范式。
●定理2-6.3 任何一个谓词公式均可转为与其等价的前束析取范式。
(()())()()
x A x B x xA x xB x ?→??→?
前束范式的求法
●通常先消去条件和双条件联结词；
●把否定深入到原子公式的前面；
●在需要的时候进行约束变元换名或自由变元代入；
●把量词移到全式的最前面。
重点：前束范式、前束析取范式、前束合取范式的求法。
2.7 谓词演算的推理理论
消去(添加)量词的规则
1) 全称指定规则 US
?xA(x)? A(c)
c 是论域中某个任意客体.
●如果个体域的所有元素都具有性质A ，则个体域中的任一个元素具有性质A 。
2) 全称推广规则 UG
A(c) ? ?xA(x)
必须能够证明对于每个c, A(c)都为真.
●如果个体域中任意一个个体都具有性质A ，则个体域中的全体个体都具有性质
A.
3) 存在指定规则 ES
?xA(x) ? A(c)
c 是论域中使A(c)为真的客体.
●如果个体域中存在有性质A 的元素，则个体域中必有某一元素c 具有性质A.
4) 存在推广规则 EG
A(c) ? ?xA(x)
c 是论域中使A(c)为真的客体.
●如果个体域中某一元素c 具有性质A ，则个体域中存在着具有性质A 的元素。
例子
●设个体域为人，试证明：任何人如果他喜欢音乐，他就不喜欢体育。每个人或者喜欢体育，或者喜欢美术。有的人不喜欢美术。因此有的人不喜欢音乐。
设)(x P ：x 喜欢美术，)(x Q ：x 喜欢体育，)(x R ：x 喜欢音乐。论域：人。
命题形式化为：前提：))()((x Q x P x ?→?，))()((x R x Q x ∨?，)(x R x ??
结论：)(x P x ??。
证明：（1）)(x R x ?? P
(2) )(a R ? ES(1)
(3) ))()((x R x Q x ∨? P
(4) )()(a R a Q ∨ US(4)
(5) )(a Q T(2)(4)I
(6) ))()((x Q x P x ?→? P
(7) )()(a Q a P ?→ US(6)
(8) )(a P ? T(5)(7)I
(9) )(x P x ?? EG(8)
·
重点：符号化命题、有效结论推证。
第三章集合与关系
3.1 集合的概念和表示法
3.2 集合的运算
3.4 序偶与笛卡儿积
3.5 关系及其表示
3.6 关系的性质
3.7 复合关系和逆关系
3.8 关系的闭包运算
3.9 集合的划分和覆盖
3.10 等价关系与等价类
3.12 序关系
3.1 集合的概念和表示法
●集合与元素
●集合的势
●集合的表示法
●集合相等
●子集、全集、空集
●幂集
重点：判定两个集合相等方法、幂集求法。
3.2 集合的运算
●集合的交
●集合的并
●集合的相对补（差）
●集合的绝对补（补）
●集合的对称差
重点：集合各种运算的定义和性质。
3.4 序偶与笛卡儿积
序偶：具有确定次序的两个元素的集合，记为
重点：笛卡尔乘积的性质定理。
3.5 关系及其表示
关系(二元关系) : 任一序偶的集合,确定了一个二元关系R.
X到Y的关系: X ? Y 的任何子集,都定义一种关系R，称作X 到Y 的关系.
若X=Y,则R 为集合X 上的关系
域(前域) Dom(R)?X
值域Ran(R)?Y
关系的表示方法——关系矩阵和关系图
重点：定义在集合上的不同关系的数目。
3.6 关系的性质
●1.自反性(reflexive)
●2.反自反性(irreflexive)
●3.对称性(symmetric)
●4.反对称性(antisymmetric)
●5.传递性(transitive)
在关系矩阵中
●自反性对角线上的所有元素都是1.
●反自反性对角线上的所有元素都是0.
●对称性关系矩阵是对称的.
●反对称性以主对角线对称的元素不能同时为1.
●传递性较难判断.
在关系图中
●自反性每点必有一闭路.
●反自反性任一结点,均无闭路.
●对称性结点间若有边,必是往返两条.
●反对称性若两点间有边,只会是一条,没有返回边.
●传递性若从结点a 到结点b有长度大于 1 的路,则从a到b必有长度为
1 的路存在.
重点：利用关系集合、关系矩阵、关系图来判定关系的性质。
3.7复合关系和逆关系
复合关系：设 R 是从 X 到 Y 的关系, S 是从 Y 到 Z 的关系,则 R ?S 称为 R 和 S 的复合关系(合成关系), 表示为
逆关系：设 R 为 X 到 Y 的二元关系,如将 R 中每一序偶的元素顺序互换,所得到的集合称为 R 的逆关系.记作 R C
定理
R 为 X 上的二元关系,则
a) R 为对称的充分必要条件是 R = R C ;
b) R 为反对称的充分必要条件是 R ? R C ? I X ;
c) R 是自反当且仅当 I X ? R ；
d) R 是反自反当且仅当 R ? I X = ? ；
e) R 是传递当且仅当 R o R ? R .
重点：复合关系和逆关系的求法、性质。
3.8 关系的闭包运算
自反（对称、传递）闭包：
X 上的关系 R 的自反（对称、传递）闭包
就是包含 R 的 X 上最小的 自反（对称、传递）关系
用Warshall 算法求传递闭包
重点：自反、对称、传递闭包的求法和性质。
3.9 集合的划分和覆盖
∧∈∧∈><=Z z X x z x S R ,{ )},,(S z y R y x Y y y >∈<∧>∈<∧∈?},,{R y x x y R C >∈<><=C R R R s ?=)(X I R R r ?=)(+∞==?=R R R t i i )(1)()()2(k R R R ???= n
k ≤
??=)2(R R
覆盖与划分
重点：覆盖、划分的判定。
3.10 等价关系与等价类
●等价关系：自反、对称、传递的关系。
●等价类：设 R 为集合 A 上的等价关系,对任何 a ∈ A , [a ]R = {x | x ∈A ∧ aRx } ●商集：等价类的集合。
●等价关系与划分：集合 A 上的等价关系与其划分是一一对应的。
重点：等价类、商集的求法。如何根据等价关系给出划分，如何根据划分给出等价关系。
3.12 序关系
偏序关系：自反的、 反对称的、传递的关系
y 盖住 x
哈斯图是简化的关系图：
(1)自反性：每个顶点都有自回路，省去自回路。
(2)反对称性：从小到大安置顶点，可省略箭头。
(3)传递性：
由于有<ａ,ｂ>，<ｂ,ｃ>∈R 则<ａ,ｃ>∈R ，故只画<ａ,ｂ>，<ｂ,ｃ>对应的边，省略边<ａ,ｃ>
。
链（反链）
极大元（极小元）
划分是覆盖的特殊情形.划分的元素S i 称为划分的类.
最大元（最小元）
上界（下界）
上确界（下确界）
重点：偏序关系判定、哈斯图画法、极大元（极小元）、最大元（最小元）、 上界（下界）、上确界（下确界）的求法
第四章 函数
●4.1 函数的概念
●4.2 逆函数和复合函数
4.1 函数的概念
函数的概念
●任何两个集合 X 和 Y , f 是 X 到 Y 的 一个关系，若对每个 x ∈ X , 有唯一y ∈ Y 使得
函数与关系
●函数的定义域是X , 而不是X 的 某个真子集；
● 一个 x 只能对应于唯一的 y ；
● X ? Y 的子集并不都能成为 X 到 Y 的函数。
函数相等
● 设函数 f : A → B 、 g : C → D,如果A=C , B =D , 且对于所有 x ∈ A 和 x ∈ C 有 f(x) = g(x) , 则称函数 f 和 g 相等，记作 f = g 。
特殊的函数：入射、满射、双射
4.2 逆函数和复合函数
逆函数（反函数）
设f :X →Y 是一个双射函数, 称Y → X 的双射函数f c 是f 的逆函数(反函数),记为f -1.
复合函数
))}
()((y g z x f y Y y =∧=∧∈y Z z X x z x f g ?∧∈∧∈><=,{ Y X f →:定义, :g Z Y →称为复合函数.
f g
重点：函数、入射、满射、双射的判定；逆函数和复合函数的定义和相关性质。定义在有限集合上的不同入射函数和双射函数的数目。
第五章代数结构
●5.1 代数系统的引入
●5.2 运算及其性质
●5.3 半群
●5.4 群和子群
●5.5 阿贝尔群和循环群
5.1 代数系统的引入
5.2 运算及其性质
运算的性质
设*, ?是定义在集合A上的二元运算, 如果对于任意的x, y, z∈A,
1 若总有x*y∈ A，则称二元运算*在A上是封闭的；
2 若总有x*y = y*x，则称*是可交换的；
3 若总有(x*y )*z = x* (y* z)，则称*是可结合的；
4 若总有x* (y? z) = (x*y ) ? (x* z)
(y?z )*x = (y*x ) ? (z* x)
则称运算*对?是可分配的；
5 若总有x* (x? y) = x
x? (x*y) = x
则称运算*和运算?满足吸收律；
6 若总有x*x = x，则称运算*是幂等的。
幺元
设*是定义在集合A上的二元运算, 若有e ∈ A , 对于任意的x∈A ,
e *x = x *e = x
定理
设*是定义在集合A上的二元运算, 且在A中有关于运算*的左幺元e l 和右幺元e r，则e l = e r = e，且A中的幺元是唯一的。
零元
设*是定义在集合A上的二元运算, 若有θ∈A , 对于任意的x∈A , θ*x = x *θ = θ
定理
设*是定义在集合A上的二元运算, 且在A中有关于运算*的左零元
θ l 和右零元 θ r ，则 θ l = θ r = θ ，且 A 中的零元是唯一的。
定理
●设代数系统 , 且 | A | > 1。如果该代数系统中存在幺元 e 和零元 θ ，则 e ≠ θ。
逆元
定理
设代数系统 , 这里 * 是定义在 A 上的一个二元运算，A 中存在幺元 e , 且每一个元素都有左逆元。如果 * 是可结合的，则该代数系统中任何一个元素的左逆元必定是该元素的右逆元，且每个元素的逆元是唯一的。
运算表与运算的性质
设代数系统 ，运算的性质可以从运算表中看出
●封闭性：表中的每个元素都属于 A ;
●交换性：表关于主对角线对称；
●幂等性：主对角线上的每一个元素与它所在行（列）的表头元素相同； ●有零元：该元素所对应的行和列中的元素都与该元素相同；
●有幺元：该元素所对应的行和列依次与运算表的行和列相一致；
●设 A 中有幺元，a 和 b 互逆，当且仅当位于 a 所在行，b 所在列的元素以及 b 所在行，a 所在列的元素都是幺元。
重点：运算各种性质的含义、不同运算性质的判定。零元、幺元、逆元的定义、求法和性质。
5.3 半群
广群、半群
一代数系统< S , * >, 其中 S 是非空集合，* 是 S 上的一个二元运算， ●如果运算 * 是封闭的，则称代数系统 < S , * >为广群。
显然a 和b 互为逆元.使b *a = e ，则称b 为a 左逆元；右逆元；
●如果运算*是封闭的、可结合的，则称代数系统< S , * >为半群。
独异点（含幺半群）
●含有幺元的半群称为独异点.（封闭结合幺元）
重点：广群、半群、独异点的定义和判定
5.4 群和子群
群
●设< G , * > 是一代数系统, 其中G 是非空集合, *为G 上一个二元运算,若
1) *是封闭的
2) *是可结合的
3) 存在幺元e
4) 对任一x∈G, 存在它的逆元x-1
则称< G , * > 是一个群.
定理（1-5）
●群< G , * >中不可能有零元。
●设< G , * >是一个群，对于a,b∈G，必存在唯一的x∈G，使得a*x = b。
●设< G , * >是一个群，对于任意的a,b,c∈G，如果有a*b = a*c 或者b*a = c*a , 则必有b = c。
●群< G , * >的运算表中的每一行或每一列都是G 的元素的一个置换。
●在群< A , * >中, 除幺元e外, 不可能有别的幂等元。
子群：设< G , * >是一个群, S是G中的非空子集，如果< S , * >也构成群，则称< S , * >是< G , * >的一个子群。
定理6：设< G , * >是一个群, < S , * >是< G , * >的一个子群，那么< G , * >中的幺元e必定也是< S , * >中的幺元。
定理7：设< G , * >是一个群，B 是G的非空子集，如果B是一个有限集，那么只要运算*在B上封闭，< B , * >必定是< G , * >的子群。
定理8：设
重点：群的性质和证明；子群的定义和证明
5.5 阿贝尔群和循环群
阿贝尔群：如果群< G , * > 中的运算*是可交换的，则称该群为阿贝尔群，
离散数学论文
浅论离散数学的实际应用 摘要： 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字：离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。1.2离散数学的内容 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1 逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”
离散数学作业
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学第四章二元关系和函数知识点总结
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作
不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取
离散数学(大作业)与答案
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G)
《离散数学》及答案
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
离散数学作业(2)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
离散数学作业答案
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
离散数学作业
命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
离散数学课后答案
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学作业
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
离散数学(屈婉玲版)第四章部分答案
离散数学(屈婉玲版)第四章部分答案
4.1 （1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如 果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。 （2）设有序对
离散数学答案
02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={
5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集
华南理工离散数学作业题2017版
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
离散数学作业答案一
离散数学作业7 离散数学数理逻辑部分形成性考核书 面作业 本课程形成性考核书面作业共3次,内容主要分别就是集合论部分、图论部分、数理逻辑部分的综合练习,基本上就是按照考试的题型(除单项选择题外)安排练习题目,目的就是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业就是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”与“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值就是 T 或1 . 2.设P :她生病了,Q :她出差了.R :我同意她不参加学习、 则命题“如果她生病或出差了,我就同意她不参加学习”符号化的结果为 (P ∨Q)→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式就是 )()(R Q P R Q P ?∧∧∨∧∧ . 4.设P (x ):x 就是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ))()((x Q x P x ∧? . 5.设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ))()(())()((b B a B b A a A ∧∨∨ . 6.设个体域D ＝{1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 F 或0 . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天就是天晴”翻译成命题公式. P 。，P 则今天是天晴设答:: 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. Q 。P ；，Q P ∧则小李去旅游小王去旅游设答::: 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. Q 。P ；，Q P →则我去滑雪明天下雪设答;:: 4.请将语句“她去旅游,仅当她有时间.”翻译成命题公式.
离散数学第四章部分答案
4、1 (1)设S={1,2},R 就是S 上的二元关系,且xRy 。如果R=Is,则(A);如果R 就是数的小于等于关系,则(B),如果R=Es,则(C)。 (2)设有序对
离散数学教学大纲(本科)
《离散数学》课程教学大纲 一、《离散数学》课程说明 课程英文名称：Discrete mathematics 课程类型：考试课 课程性质：专业技术基础课 总学时： 72学时 适用对象：计算机科学与技术专业本科生 先修课程：高等数学线性代数 （一）课程简介 离散数学，是现代数学的一个重要分支，是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。 《离散数学》内容主要包括:集合、映射与运算，关系，命题逻辑，谓词逻辑，代数结构，图论，以及几类特殊的图和组合计数.通过该课程可以培养学生的抽象思维和慎密的概括能力，是计算机专业的必修课。 （二）课程性质、目的和任务 《离散数学》课程是为计算机科学与技术专业的学生开设的一门专业基础课程。随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述，从而为研究计算机科学及相关学科提供了有利的理论基础和工具。是学习后续专业课程不可缺少的数学工具，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。 教学的目的是进一步提高学生的抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。并为后续课程的学习打下良好的基础。 （三）与其他课程的联系 除要求学生具有矩阵和矩阵运算方面的一些知识外，离散数学基本上是一门体系独立自行封闭的基础数学课程，但由于它内容抽象，理论性较强，因此它需要学生先期有较好的数学思维的训练。最好将此课程安排在高等数学和线性代数课程之后。
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学作业答案完整版
离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
离散数学课后习题答案第四章
离散数学课后习题答案第四章
第十章部分课后习题参考答案 4．判断下列集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。 封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合普通的除法运算。不封闭 （3） 全体n n ?实矩阵集合 （R ）和矩阵加法及乘法运算，其中n 2。 封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元； 乘法单位元是单位矩阵，零元是零矩阵； （4）全体n n ?实可逆矩阵集合关于矩阵加法及乘法运算，其中n 2。不封闭 （5）正实数集合 和 运算，其中 运算定义为： 不封闭 因为 +?-=--?=R 1111111ο （6）n 关于普通的加法和乘法运算。 封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元； 乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a Λ n 运算定义如下： 封闭 不满足交换律，满足结合律， （8）S = 关于普通的加法和乘法运算。 封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。 加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S = ,S 关于普通的加法和乘法运算。 加法不封闭，乘法封闭，乘法满足交换律，结合律
10．令S={a ，b}，S 上有四个运算：*，分别有表10.8确定。 (a) (b) (c) (d) (1)这4个运算中哪些运算满足交换律，结合律，幂等律？ (a) 交换律，结合律，幂等律都满足， 零元为a,没有单位元； (b)满足交换律和结合律，不满足幂等律，单位元为a,没有零元 b b a a ==--11, (c)满足交换律,不满足幂等律,不满足结合律 a b a b b a b a a b b a ====οοοοοο)(,)( b b a b b a οοοο)()(≠ 没有单位元, 没有零元 (d) 不满足交换律，满足结合律和幂等律 没有单位元, 没有零元 (1) 求每个运算的单位元，零元以及每一个可逆元素的逆元。 见上 16．设V=〈 N ，+ ，〉，其中+ ， 分别代表普通加法与乘法，对下面给定的每个集合确定它是否 构成V 的子代数，为什么？ （1）S 1= 是 （2）S 2= 不是 加法不封闭 （3）S 3 = {-1，0，1} 不是，加法不封闭 第十一章部分课后习题参考答案 8.设S={0，1，2，3}， 为模4乘法，即 "?x,y ∈S, x y=(xy)mod 4
离散数学答案【2】
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) xF ?，在（a）中为假命题，在(b)中为真命题。 (x (2)在两个个体域中都解释为) ?，在（a）(b)中均为真命题。 xG (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ? x ?? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F x→ ?? x ) H ( ( (x 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? ∧ y H )) ( , x ( ((y ( ) (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快
命题符号化为: ))) y F x G y→ ?? ∧ ? H x ) x , ( ( (y ( ( ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x
- 2018国家开放大学离散数学(本)形考任务答案
- 苏州大学离散数学期末试卷
- 大学离散数学期末重点知识点总结(考试专用)
- 大学本科高等数学《离散数学》试题及答案
- 大学离散数学试题集(完整试题)
- 大学离散数学题库答案
- 大学离散数学答案
- 大学离散数学试卷及答案1
- 上海大学离散数学
- 大学离散数学期末重点知识点总结(考试专用)
- 大学离散数学试题集(非常完整试题)
- 四处大学离散数学答案
- 东北大学离散数学试卷及答案
- 吉林大学离散数学精品试卷
- 大学离散数学复习试题 (1)
- 上海大学-离散数学2-图部分试题
- 大学离散数学怎么学
- 东北大学离散数学复习总结满分版)
- 大学离散数学试题集
- 2018国家开放大学离散数学本形考任务答案