总复习题
1. 设︱A ︱=5, ︱P(B)︱=512, ︱P(A ∩B)︱=8, 则︱A ⊕B ︱＝？, ︱A ∪B ︱＝？。
2. 设p :选小王当班长，q ：选小李当班长，则选小王或小李中的一人当班长可符号化为。
3. 命题公式根据赋值可分为那三类。
4. 含N 个个命题变项的命题公式有？组赋值，有？个真值。
5. ()A A B ∨∧=？，()A A B ∧∨=？。
6. 设{|3,,14}A x x k k N k ==∈≤≤，则用列举法表示A =？。
7. 集合A ={1，2}的幂集P (A )与A 的笛卡尔积()P A A ?=？。
8. 某无向图G 中，共有边15条，该图中共有5度顶点2个，4度顶点3个，剩下的均为2度顶
点，则该图中共有顶点？个。
9. 一个结点为n 的无向完全图，其边的数目为？。
10．已知
11. 已知关系R 1＝{
=？。
12、设Φ是一个空集，则下列之一哪一个不成立（
①、Φ∈Φ
②、Φ?Φ
③、Φ∈{Φ}
④、Φ?{Φ}
13、如果命题公式G=P ∧Q ，则下列之一哪一个成立（
①、G=?(P →Q) ②、G=?(P →?Q)
③、G=?(?P →Q)
④、G=?(?P →?Q)
14、设X 、Y 是两个集合，|X|＝n ，|Y|＝m ，则从X 到Y 可产生（
①、m
n
②、n
m
③、n m ?
④、2
m n
?
15、若复合映射τσ?是满射，则 ( )。 ①、τ是满射 ②、σ 是满射
③、τ是单射 ④、 σ是单射
16、若
①、交换律
②、消去律
③、幂等律
④、分配律
17、量词的约束范围称为量词的（。 ①、定义域 ②、个体域
③、辖域 ④、值域
18、下列公式中，（
①、?(P ∧Q)
②、?(P ∨Q)
③、(P ∨Q) ④、(P ∧Q) 19、设G 是一个12阶循环群，则该群一定有（
①、2 ②、4
③、6 ④、8
20、图的构成要素是（
①、结点
②、边 ③、结点与边 ④、结点、变和面
21、下列图中，（
①
② ③ ④
22、每个非平凡的无向树至少有（
①、1
②、2
③、3 ④、4
23、每个无限循环群有（
①、1
②、2
③、3 ④、4
24、设R 是集合A ＝{1,2,3,4}上的二元关系，R ＝{<2,1>,<2,3>,<1,3>},则下列（
①、R 是自反关系 ②、R 是反自反关系 ③、R 是反对称关系 ④、R 是传递关系 25、对一阶逻辑公式((,)(,))(,)x y P x y Q y z xP x y ??∧∧?的说法正确的是( )。 ①、x 是约束的，y 是约束的，z 是自由的；
②、x 是约束的，y 既是约束的又是自由的，z 是自由的； ③、x 是约束的，y 既是约束的又是自由的，z 是约束的； ④、x 是约束的，y 是约束的，z 是约束的。 26、下列命题中，（
①、海水是咸的当且仅当蝙蝠是瞎子 ②、如果南京是直辖市，那么北京是中国的首都 ③、若太阳从西边落下，则2是奇数 ④、夏天冷当切仅当冬天热
27、解释包括哪些内容。 28、试述函数单射的定义。 29、试述等价关系的定义。 30、试述握手定理的内容。 31、试述欧拉公式 32、试述环的定义。
33、试述零元、逆元`和幺元的定义。 34、P126页代数系统的积。 35、命题符号化
⑴ 只有天下大雨，他才坐公共汽车上班 (2) 如果天气凉快，小王就不去游泳。
(3) 2是偶数又是素数。
(4) 除非天下大雨，否则他不坐公共汽车上班） (5)小王在图书馆或者在教学楼 36、用等值演算的方法证明下列等式。
?(p ?q ) ? ((p ∨q ) ∧?（p ∧q ）)
37．试证明1V =
e
证明该映射是从1V 到2V 的同态映射。
38．已知100个学生中有32人学数学，20人学物理，45人学生物，15 人学数学和生物，7人学 数学和物理，10人学物理和生物，30人这三门课一门也没学。问三门课全部都学的学生人数有多少？
38、设{0,1,2}A =，{,}B a b =，求A
B 。
39． 集合A={1，2， 3，4，5}，(),P A <⊕>构成群，其中⊕为集合的对称差。求解方程
{1,3}{3,4,5}X ⊕=。
40. 已知图G 中有10条边，4个3度顶点，其余顶点的度数均小于等于2，求图G 中至少有多少
个顶点？为什么？
41．写出下图的关联矩阵。
2e 25
4
42．已知有向图D 的顶点集合V(D)={v 1,v 2,v 3,v 4}，如下图所示。求从v1到v3长度小于等于3的通路个数。
23
43．某通信体系统中有八种信源，分别为x 1，x 2，x 3，x 4，x 5，x 6，x 7，x 8，它们出现的概率为0.3，0.2，0.15，0.1，0.1，0.05，0.05，0.05。请画出对应的哈夫曼树，写出相应的编码方案，并求出
该编码方案的平均码字长度。
44．对下图给出的赋权图G ，求出结点v 1到其余各个结点的最短路径。
45．对下图给出的赋权图G ，求出结点v 0到其余各个结点的最短路径。
v 0
v 2
v 4v 5
46． 在如图所示的PERT 图中求关键路径，以及每一点的最早，最晚时间，和缓冲时间。
v
v 4
5
8
47．设{|,}S x x a a b Q ==+∈，+和?为普通加法和乘法。证明,,S <+?>是域。 48. 设,,S <+?>是环，,a b R ?∈计算2
()a b -和3
()a b -。
49．设{,,,}A a b c d =，{,,,,,,,}R a b b a b c c d =<><><><>，求R 、()r R 、()s R 和()t R 的关系图。
50．设{1,2,3}A =，求A 上的所有等价关系。
51． 关系分为？和？两类。
52. 求在1和1000之间不能被5或6。也不能被8整除的数的个数。
53．求(())p q r p ∨→→的主析取范式。
54．判断()p q q ?→∧、(())p q p q →∧→、()p q q →∧命题公式的类型。 55. 设{|0,1}A x x R x =∈∧≠。在A 上定义6个函数如下:
1()f x x =,21()f x x =
,3()1f x x =-, 41()1f x x =-, 51()x f x x -=，6()1
x f x x =-。,V S =<>，其中126{,,
,}S f f f =，为函数的合成。 （1）给出V 的计算表；（2）说明V
的幺元和所有可逆元素的逆元。
56. 求在1到1，000，000之间（包括1和1，000，000在内）有多少个整数既不是完全平方数，也不是完全立方数。
57. 以下两个置换是6S 中的置换，其中
123456246135σ??= ???，123456654123τ??= ???
（1） 试把σ和τ表示成不交的轮换之积；（2）求στ、1στσ-。
58. 设{,,,}S a b c d =，1R 、2R 为S 上的关系，1{,,,,,}S a a a b b d =<><><>，
2{,,,,,,,}S a d b c b d c b =<><><><>，计算12R R 、21R 、32R 。
59. 最短路径 60、完备匹配 61、哈密尔顿图 62、基本回路 63、最优2元树 64、有序完全正则树
65、下面（ ）不能成为图的度数序列
① (3,2,5,8) ②(1,9,7,3) ③(5,5,5,5) ④(3,2,1,5)
66、简单连通图G 中，若节点数为5，边数为（ ），则G 不可能是平面图 ①7 ②8 ③9 ④10
67、设S={1, 2, 3, 4}，R 为S 上的关系，其关系矩阵如下：
1001100000011000????????
??
??
则R 上的关系表达式为( )
① {<1,1>, <1,2>, <1,4>, <4,1>, <4,3>} ②{<1,1>, <1,4>, <2,1>, <4,1>, <3,4>} ③ {<1,1>, <1,2>, <1,4>, <1,4>, <4,3>} ④{<1,1>, <4,1>, <2,1>, <1,4>, <4,3>}
R R 中有（ ）个有序对。
①1 ② 3 ③ 6 ④7
68、设,V R +=，其中?为普通乘法，对任意x R +
∈，令1()||x
x φ=，2()2x x φ=，23()x x φ=，41
()x x
φ=
，5()x x φ=-，其中V 的自同态的映射有（ ）个。 ①0 ②1 ③ 2 ④3 ⑤4 ⑥5
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8.
C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D=
D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为
离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==，，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =， }},{},{{3c b a S =，}},,{{4c b a S =，}}{},{},{{5c b a S =，}},{},{{6c a a S = 则A 的覆盖有 ，A 的划分有 。 11. 设}2,121{Z x x x x M ∈≤≤=整除，被，}3,121{Z x x x x N ∈≤≤=整除，被，则 =?N M ，=-N M 。 12. 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则B A ?= ，B A ο= 。 13. A={1，2，3，4，5，6}，A 上二元关系}|,{是素数y x y x T ÷><=，则用列举法 T= ； T 的关系图为 ，T 具有 性质。
离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (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) 给我一杯水吧！
离散数学习题参考答案 第一章集合 １.分别用穷举法,描述法写出下列集合 （１）偶数集合 (２)36的正因子集合 (３)自然数中3的倍数 (４)大于１的正奇数 (1)E={?,-6,-4,-2,0,2,4,6,?} ={2 i | i∈I } (2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3) N3= { 3, 6, 9, ```} = { 3n | n∈N } (4) A d= {3, 5, 7, 9, ```} = { 2n+1 | n∈N } ２.确定下列结论正确与否 (１)φ∈φ× (２)φ∈｛φ｝√ (３)φ?φ√ (４)φ?｛φ｝√ (５)φ∈｛ａ｝× (６)φ?｛ａ｝√ (７)｛ａ,ｂ｝∈｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝× (８)｛ａ,ｂ｝?｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝√(９)｛ａ,ｂ｝∈｛ａ,ｂ,｛｛ａ,ｂ｝｝｝× (１０)｛ａ,ｂ｝?｛ａ,ｂ,｛｛ａ,ｂ｝｝｝√ ３.写出下列集合的幂集 (１)｛｛ａ｝｝ {φ, {{ a }}} ( 2 ) φ {φ} (３)｛φ,｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} } (４)｛φ,ａ,｛ａ,ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}, {a, {a b }}, {φ,a,{ a, b }} } (５)Ｐ(Ｐ(φ)) {φ, {φ}, {{φ}}, {φ,{φ}} } ４.对任意集合Ａ,Ｂ,Ｃ,确定下列结论的正确与否(１)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ∈Ｃ√
(２)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ?Ｃ× (３)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ∈Ｃ× (４)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ?Ｃ × ５.对任意集合Ａ,Ｂ,Ｃ,证明 右 分配差差左=--=--)C A ()B A ()C B (A M .D )C B (A )C B (A ) C A ()B A ()C B (A )1(I Y I Y I I I I I Y 右 差分配差左右差的结论差左=--=-------=-)C A ()B A ()C A ()B A () C B (A M . D )C B (A )2)C A ()B A ()C A ()B A ()1()C B (A )1) C A ()B A ()C B (A )2(Y I Y I Y I I I Y I Y Y I 右 交换结合幂等差左=--=-)C A ()B A (,)C B ()A A () C B (A M . D )C B (A ) C A ()B A ()C B (A )3(I I I I I I I I Y I I Y ))B )B (A ())B B ()B A ((,)B )B A (()B )B A ((B )B A (B A B )B A )(4(I I Y I Y I I Y I I Y --⊕=⊕+结合分配对称差差左 右 零一互补==φ-φ-)B A ()B A () A ()U ) B A ((Y Y I I Y
离散数学复习指导Ⅰ 命题逻辑部分 一学习要求 1．理解命题、联结词的含义，掌握命题的符号化； 2．理解命题公式的赋值，能求出公式的真值表，判断公式的类型； 3. 理解公式等值的定义,记住一些基本等值式,能进行等值演算; 4. 体会公式的主范式与公式赋值之间的关系,能利用等值演算求出范式; 5. 理解公式的蕴涵及推理的含义及联系,记住一些基本的推理规则,能用演绎 推理方法进给出推理证明; 二范例 例1 将下列命题符号化 ⑴小王聪明但不用功； ⑵说数理逻辑枯燥无味或毫无价值，那是不对的； ⑶你不及格就要补考。 ⑷不经一事，不长一智； 解：⑴设p：小王聪明，q：小王用功，则该命题可符号化为：q ∧。 p? ⑵ p：数理逻辑枯燥无味，q：数理逻辑毫无价值，则：) ?。 (q p∨ ⑶ p：你及格了；q：你要参加补考，则：q p? ?。 ⑷ p：经一事；Q：长一智，则：q ?。 p? → ⑸这是简单命题，则p：李卫与李星是兄弟。 例2 求命题公式r (的主析取范式和主合取范式，指出公式的成 ∧) q p∨
真赋值和成假赋值，并判断公式的类型。 解：r q p ∨?)(r p q q p ∨→∧→?))()(( ))(())((r p q r q p ∨→∧∨→? )()(r p q r q p ∨∨?∧∨∨?? 42M M ∧? （主合取范式） 765310m m m m m m ∨∨∨∨∨? ∑?)7,6,5,3,1,0( (主析取范式) 公式的成真赋值为：000，001，011，101，110，111 成假赋值为：010，100 公式为非重言式的可满足式 。 例3 构造下面推理的证明： 前提：s q r p q p ∨→?∧,, 结论：r s ∧ 证：(1) q p ?∧ P; (2) p T(1)化简规则; (3) q ? T(1)化简规则 (4) r p → P; (5) r T(3)(4)假言推理; (6) s q ∨ P; (7) s T(3)(6)析取三段论; (8) r s ∧ T(5)(7)合取式. 例4. 先将下列相关命题符号化,给出推理证明 如果4是偶数,则2不能整除5. 或者7不是素数或者2整除5. 7是素数.因此4不是偶数. 解: 设p: 4是偶数; q: 2能整除5; r: 7是素数; s: 2整除5,则 前提： ,,,r q r q p ∨??→ 结论：.p ? 证明: (1) )(p ?? 结论之否定; (2) p T(1)等值式; (3) q p ?→ P;
离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧?
答案： 令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y，都有x+y≥x。 答案： 令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化： 某些人对某些药物过敏。 答案：
令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式： 答案： 15. 证明： 答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明： 前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ?
《离散数学》综合复习资料参考答案 一、判断题 1．命题逻辑中任何命题公式的主析取范式如果存在一定是唯一的。（） 2．A、B、C是任意集合，如果A?B及B∈C，则A?C。（） 3．整数集是不可数集。（） 4．代数系统
7． 设树T 有17条边，有12片树叶，2个3度结点，求4度结点数。 8． 设A={1,2}，试构成集合P(A)?A 。 9. 设*运算是有理数集Q 上的二元运算，对于任意的a,b ∈Q ，a*b=a+b-a ?b ，问运算*是否可交换、可结合的？ 10.试求下面有向图的强分图、单侧分图和弱分图。 11、将下列命题符号化 （1）他即聪明又用功。（P ∧Q ） （2）仅当你走我才留下。（Q → P ） （3）所有老的国家选手都是运动员。（(?x)(R(x)→Q(x))） （4）某些教练是年老的，但是健壮的。（(?x)(P(x)∧Q(x) ∧R(x))） 12、设A 是一个非空集合，*是A 上的二元运算，对于任意a,b ∈A ，有a*b=b ，判定*运 算是否可结合的、可交换？ 13、试求下面有向图的强分图、单侧分图和弱分图 三、证明题 1． 设
1. 计算：2400 mod 319、2340 mod 11。 2. 设整数a 和b 不全为0，且a 和b 互素。请证明：ab 和a+b 互素。 3. 设n!的标准素因数分解式是 k k p p p εεεΛ2121 请证明： ∑∞=???? ? ?????=1s s i p n i ε，i=1,2,…,k 4. 300！末尾0的个数是？。 5. 解同余方程组：x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。 6. 求p →(p ∧(q →p))的主析取范式和主合取范式。（真值表法和等值演算法） 7. 求谓词公式?x ?y(P(x,y)?Q(x,y))→?x ?yR(x,y)的前束范式。 8. 证明下面的推理： “每个科研工作者都是努力工作的。每个努力工作而又聪明的人都取得事业的成功。某个人是科研工作者并且聪明。所以，某人事业取得成功。” 9. 设R={(1,2),(1,4),(3,3),(4,1)}是集合A={1,2,3,4}上的关系。 （1） R 是自反的吗？是对称的吗？是传递的吗？ （2） R 的自反对称闭包存在吗？ （3） R 的自反传递闭包存在吗？ （4） R 的对称传递闭包存在吗？ （5） R 的自反对称传递闭包存在吗？ （6） R 的反自反闭包存在吗？ （7） R 的反对称闭包存在吗？ 10. 设A={x|x ∈N ，且x|54}，R={(x,y)|x,y ∈A ，且x|y }。 （1） 列出集合A 和R 中的元素； （2） 给出R 的矩阵表示； （3） 证明(A,R)是偏序集，画出哈斯图； （4） 指出(A,R)中的最大元、最小元、极大元、极小元。 11. 设X={(x,y) | x 和y 是不为零的实数}，E 是X 上的关系：
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
v1.0 可编辑可修改 离散数学知识要点总结 第1章命题逻辑 1、会判断一个语句是否为命题（如P31-习题题） 练习：判断下列语句是否为命题。 (1).3+8=13； (2).离散数学是计算机系的一门必修课； (3).太阳系以外的星球上有生物； (4).你打算考硕士研究生吗 (5).9+5≤12 ； (6). 天上有三个月亮。 (7).x+5 > 6； (8).一定要努力学习！(9).2是素数； (10).x+5 > 6； (11).我正在说谎； (12).x=13. (13).这朵花多好看呀！ (14).7能被2整除. (15).我用的计算机CPU主频是 1G吗 (16).蓝色和黄色可以调成绿 色； (17). 雪是黑色的. (18). 明天会下雨吗； (19).我能进来吗 (20).这个男孩真勇敢呀！ (21).蓝色和黄色可以调成绿 色； (22).x≤3； (23)地球饶着太阳转. (24)青年人多么朝气蓬发呀！ (25).5能被2整除. (26).嫦娥一号太棒了！ (27).台湾是中国的一部分； (29) 你下午有会吗若无会，请 到我这儿来！ (30).请不要讲话！ (31) 5是奇数； (32). 3 2> + x 2、注意五个命题联结词的使用，会将命题进行符号化（如，，题的题型）或在判断体现逻辑联结词的逻辑有关系等。练习：将以下命题符号化 (1)如果你不去逛街，那么我也不去逛街。 (2)小李边吃饭边看电视。 (3)林芳学过英语或日语。 (4)张辉与王丽都是三好生. (5)小王住在101室或102室。 (6).2+2≠4当且仅当王红没努力学习离散数学。 (7)4或6是素数. (8).王晓聪明，但是他不用功. (9)如果今天是1号，则明天是5号。(10).小潘不能既跳舞又唱歌。 (11)如果你来了，他就唱歌而且陪你跳舞。 (12).或者雪是黑色的，或者太阳从东方升起。 (13).王晓既用功又聪明。 (14)2 + 2 ≠ 4 当且仅当美国位于非洲。 (15)小李学过英语或法语。 (16）如果石头会说话，那么月亮上就会出现海洋。(17）.如果天气寒冷，小梅就不去游泳。 （18）小红喜欢看书和画画。
《离散数学》习题与解答 第一篇数理逻辑 第一章命题逻辑 1-1（1）指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值 a)离散数学是计算机科学系的一门必修棵 b)∏> 2 吗？ c)明天我去看电影 d)请勿随地吐痰 e)不存在最大质数 f)如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了 g)9+5<12 h)x<3 i)月球上有水 j)我正在说假话 [解] a)不是命题 b)是命题,真值视具体情况而定 c)不是命题 d)是命题,真值为t e)是命题,真值为t f)是命题,真值为f g)不是命题 h)是命题, 真值视具体情况而定 i)不是命题 1-2(1)用P表示命题“天下雪”,(又表示命题“我将去镇上”,R表示命题“我有时间”.以符号形式写出下列命题: (a)如果天不下雪和我有时间,那么我将去镇上. (b)我将去镇上，仅当我有时间. (c)天不下雪 (d)天下雪,那么我不去镇上 [解] a)(┐P∧R)→Q b)Q→R c)┐P d)P→┐Q 1-2(2)将下面这段述中所出现的原子命题符号化,并指出他们的真值,然后将这段述中的每一命题符号化 2 是有理数是不对的.2是偶素数.2或4是素数.如果2是素数则3也是素数.2是素数当且仅当3也是素数. [解]:述中出现5个原子命题，将他们符号化为: P: 2 是有理数其真值为F Q:2是素数其真值为T
R:2是偶数其真值为T S:3是素数其真值为T U:4是素数其真值为F 述中各命题符号化为: ┐P;Q∧R;Q∨U;Q→S;Q＜＝＞S 1-2(3)将下列命题符号化 a)如果3+3=6,则雪是白色的. b)如果3+3≠6,则雪是白色的 c)如果3+3=6,则雪不是白色的. d)如果3+3≠6,则雪不是白色的 e)王强身体很好，成绩也很好. f)四边形ABCD是平行四边形,仅当其对边平行 [解]:设P:3+3=6 Q:雪是白色的 R:王强成绩很好S:王强身体很好 U: 四边形ABCD是平行四边形V: 四边形ABCD的对边是平行的于是: a)可表示为:P→Q b)可表示为: ┐P→Q c)可表示为: P→┐Q d)可表示为：┐P→┐Q e)可表示为：S∧R f)可表示为:U＜＝＞V 1-3(1)判别下列公式中哪些是合式公式,那些不是合式公式 a) (Q→R∧S) b) (P＜＝＞(R→S)) c) ((┐P→Q)→(Q→P))) d) (RS→T) e)((P→(Q→R))→((P→Q)→(P→R))) [解]: a)不是合式公式(若规定运算符优先级后也可以作为合式公式) b)是合式公式 c)不是合式公式(括号不配对) d)不是合式公式 e)是合式公式 1-3(2)对下列各式用指定的公式进行代换: a) (((A→B)→B)→A),用（A→C）代换A，用（（B∧C）→A代换B。 b)((A→B)∨(B→A),用B代换A,A代换B. [解]:a)((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b)((B→A)∨(A→B)) 1-3(3)用符号形式写出下列命题 a)假如上午不下雨,我去看电影;否则就在家里读书或看报. b)我今天进城,除非下雨. c)仅当你走,我将留下. [解]a)设P:上午天下雨. Q:我去看电影
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={