一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．
上！） 1、设集合X={0，1，2}，R 是X 上的二元关系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，则R 的关系矩阵M R = 。 2、66,Z <⊕>为模6整数加群， 则由2生成的子群<2>= ，右陪集<2>⊕65= 。
3、设A 和B 为有限集，|A|=m ，|B|=n ，则有 个从A 到B 的关系，有 个从A 到B 的函数。
4、无向图G 如下图所示，G 的点连通度κ为 ，边连通度λ为 。
5、在上面无向图中，已给出了一棵生成树T （粗边所示），则树枝d 对应的基本割集是 ，弦b 对应的基本回路是 。
6、令F(x)： x 是整数，G(x)：x 是奇数，则“不存在不是奇数的整数”符号化为 。
7、含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 （用m i 形式表示最小项）。
二、单选题（20分，每题1分，请将本题答案写在下方表格．．．．中！）
A 、{}1111
,110,10,0 B 、{}01,001,000,10 C 、{}1101,1001,101,110, D 、{}abc aba ac aa c b ,,,,, 2、下列( )组赋值不是命题公式C ()A B →∨?的成真赋值。 A 、010 B 、011 C 、110 D 、101
3、设A={a ，b ，c ，d}，A 上的等价关系R={，，
A 、{{a ，b}，{c ，d}}
B 、{{a ，b ，d}，{c}}
C 、{{a}，{b}，{c}，{d}}
D 、{{a}，{b ，c}，{d}} 4、二部图3,3K 是( ) 。
A 、欧拉图
B 、 哈密顿图
C 、 非连通图
D 、完全图
5、令p: 我将去上网，q: 我有时间，则“我将去上网，仅当我有时间”可符号化为( )。
(A) q p → (B) q p ? (C)p q → (D)q p ?∨?
6、下面（ ）图不一定是树。
A 、每对结点间都有路的图
B 、无回路的连通图
C 、连通但删去一条边则不连通的图
D 、有n 个顶点n —1条边的连通图 7、集合A = {1, 2, …, 10}上的关系R ={
(A) 自反的 (B) 传递的、对称的 (C) 对称的 (D) 反自反的、传递的 8、设G 如右图，那么G 不是( )。 (A)哈密顿图 (B)完全图 (C)欧拉图 (D)树
9、设图D 的邻接矩阵为???
?
??
?
?
?????
???01101
101011101100101
11110
，则D 的顶点数与边数分别为
( ) 。
A 、4， 5
B 、5， 16
C 、4， 10
D 、5， 8 10、下列式子中正确的是（ ）。 A 、Φ＝1 B 、Φ∈Φ C 、Φ?｛Φ｝ D 、Φ＝{Φ}
11、由2个命题变元p 和q 组成的不等值的命题公式的个数有( )。 (A)2 (B)4 (C) 16 (D) 8 12、给定下列非负整数序列，可构成简单无向图的节点度数序列的为( )。 (A) (1， 3， 4， 4， 5) (B) (1， 1， 2， 2， 2) (C) (0， 1， 3， 3， 5) (D) (1， 1， 2， 2， 3)
13、 4阶完全无向图4K 中含3条边的不同构的生成子图有( )。 (A)5 (B)4 (C)3 (D)2
14、任意12阶群的子群的阶一定不为 ( )。 (A)3 (B)6 (C)8 (D)4 15、在公式x ?F(x ， y)→ ? yG(x ，y)中变元x 是( )。
(A) 既是自由变元，又是约束变元 (B) 既不是自由变元，又不是约束变元 (C) 自由变元 (D) 约束变元
16、设图G=
17、给定公式)()(x xP x xP ?→?，当D={a,b}时，解释( )使该公式真值为0。 A.P(a)=0、P(b)=0 B.P(a)=0、P(b)=1 C.P(a)=1、P(b)=1 18、设A={1 ,2 ,3 }，则A 上有（ ）个二元关系。
A 、23
B 、32
C 、 322
D 、2
32
19、设Z 是整数集合，“+”是数的加法运算，则
20、设R 和S 是集合A={1，2，3，4}上的二元关系，则S 是R 的（ ）闭包。
R = {<1 ，1>，<1 ，2>，<2 ，2>，<2 ，3>，<4 ，4>}
S = {<1 ，1>，<1 ，2>，<2 ，2>，<2 ，3>，<3 ，3>，<4 ，4>} A 、对称 B 、自反 C 、传递 D 、以上都不对 三、求解题（40分，每题8分，请将本题答案写在后面答题纸上！） 1、在自然推理系统中构造证明： 已知张三或李四的彩票中奖了。如果张三的彩票中奖了，那么你会知道张三的彩票中奖了。如果李四的彩票中奖了，那么王五的彩票也中奖了。你不知道张三的彩票中奖了。所以，李四和王五的彩票都中奖了。
2、设A={a,b,c,d,e}，A 上的偏序关系R ＝{
(2) 求子集B={c,d,e}的极大元，极小元，最大元，最小元。
3、求一阶逻辑公式的前束范式：(?xF(x,y) →?yG(y)) → ?xH(x,y,z)。
4、设7个字母在通信中出现的频率如下：a: 35%，b: 20%，c: 15%，d: 10%，e: 10%，f: 5%，
g: 5%，用Huffman 算法求传输它们的最佳前缀码。要求画出最优二叉树，并指出传输100个按上述频率出现的字母，需要多少个二进制数字。
5、
四、证明题（30分，每题7、7、8、8分，请将本题答案写在后面答题纸上！） 1、例如，f 和g 都是群
2、要在七天安排七场考试，同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试，请证明：安排这样的考试日程表是可以的。
3、设R 是集合A 上一个等价关系，
{,|,(,,)}S x y x y A z x z R z y R =<>∈∧?<>∈∧<>∈，试证明S 也是A
上的一个等价关系。
4、
参考答案
一、
1、101001110??????????
2、{0，2，4}，{5，1，3}
3、2mn ，n m
4、2，3
5、d,b,c ，bade
6、(F()(x))
或(F()(x))x x G x x G ??∧??→ 7、m6?m7
二、
第二次在线作业 1.（ 2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）设< L*1*2> 是代数系统，其中是*1*2二元运算符，如果*1*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L*1*2> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）零元是不可逆的 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案：正确此题得分：2.5分
6.（2.5分）设abc是阿贝尔群< G+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分） < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案：正确此题得分：2.5分
11.（2.5分）不含回路的连通图是树 ?正确 ?错误 我的答案：正确此题得分：2.5分 12.（2.5分）简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案：正确此题得分：2.5分 13.（2.5分）树一定是连通图 ?正确 ?错误 我的答案：正确此题得分：2.5分 14.（2.5分）无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案：正确此题得分：2.5分 15.（2.5分）不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案：正确此题得分：2.5分
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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 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，所以这一段的论述为真。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 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1，g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中，则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中， _______________________________是其Euler 路 . 5. 设有向图G = (V , E )，V = {v 1，v 2，v 3，v 4}，若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2．集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3．若R 和S 是集合A 上的两个关系，则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4．集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是．．t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式
离散数学复习注意事项： 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为实数。命题“任何有理数都是实数”的符号化为（）
2013年4月考试离散数学第二次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列语句中为命题的是（） A. 暮春三月，江南草长. B. 这是多么可爱的风景啊！ C. 大家想做什么，就做什么，行吗？ D. 请勿践踏草地！ 2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ，则以下正确的是（）。 A. A＝B B. A?B C. B?A D. 以上都不对 5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（） A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中，为真的命题是（） A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。 A. B. C.
第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3，2} (4) {5，6，7，8，9，10，11，12，13，14，15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6．写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明：如果B?C，则ρ(B) ?ρ(C)。 证明任取x∈ρ(B)，则x?B，又因为B?C，所以x?C，x∈ρ(C)。 10．设U = {1, 2, 3, 4, 5}，A = {1, 4}，B = {1, 2, 5}和C = {2, 4}，试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11．证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x， x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12．设A, B, C是集合，下列等式成立的条件是什么？ (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C)
------------------------------------------------------------------------------------------------------------------------------ 1.（2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 正确 错误 正确答案： 2.（2.5分）设< L,*1,*2> 是代数系统，其中是*1,*2二元运算符，如果*1,*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L,*1,*2> 是格 正确 错误 正确答案： 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 正确 错误 正确答案： 4.（2.5分）零元是不可逆的 正确 错误 正确答案： 5.（2.5分）群中每个元素的逆元都是惟一的 正确 错误 正确答案： 6.（2.5分）设a,b,c是阿贝尔群< G,+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) 正确 错误 正确答案： 7.（2.5分） < {0,1,2,3,4},MAX,MIN> 是格 正确 错误 正确答案： 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 正确 错误 正确答案： 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 正确 错误 正确答案： 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 正确 错误 正确答案： 11.（2.5分）不含回路的连通图是树
离散数学作业答案 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={
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B 的。 17、集合上的三种特殊元是、 及。 18、设A={a, b}，则ρ(A) 的四个元素分别 是：，，，。 19、代数系统是指由及其上的或 组成的系统。 20、设
离散数学作业布置 第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规则 第五章
离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G=
2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）：
《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
第四章部分课后习题参考答案 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)在两个个体域中都解释为) ?，在（a）中为假命题，在(b)中为真命题。 (x xF (2)在两个个体域中都解释为) (x ?，在（a）(b)中均为真命题。 xG 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) x x∧ ? ?? F ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) x F H x→ ?? (x ) ( ( 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? y ∧ )) ( , ( ) x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y x F G y→ ?? ∧ ? x ( ) ( , H ( x ) (y ( 9.给定解释I如下: (a) 个体域D为实数集合R.
离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A )
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f