离散数学作业
第一章命题逻辑的基本概念
一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化
（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 -
三、用等值演算求下列公式的主析取范式与主合取范式，并求成真赋值
(1)(?p→q)→(?q∨p)
(2)?(p→q)∧q∧r
(3)(p∨(q∧r))→(p∨q∨r)
四、用真值表法求下列公式的主析取范式,再用主析取范式求主合取范式
(1) (p∨q)∧r (2)p→(p∨q∨r)
- 4 -
第三章命题逻辑的推理理论
一、填空
1.数理逻辑的的主要任务是。
推理是指，前提是，结论是。
2.推理正确是指：
3.命题公式A
1，A
,2
， ，A
,k
推B的推理正确当且仅当
二、先把下列命题符号化，再写出前提、结论、推理的形式结构，然后用3种方法证明（真值表法、等值演算法、主析取范式法）证明下列推理是正确的。
若a是奇数，则a不能被2整除。若a是偶数，则a能被2整除。因此，若a 是偶数，则a不是奇数。
设p: a是奇数,q: a能被2整除,r: a是偶数
- 5 -
三、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推
理的证明
(1)前提：p→q,?(q∧r),r
结论：?p (2)前提：q→p,q?s,s?t,t∧r
结论：p∧q
（3）前提：p→(q→r),s→p,q （4）前提：p→?q,?r∨q,r∧?s 结论：s→r 结论：?p
四、在自然推理系统下构造下列推理的证明
如果我学习，那么我数学不会不及格。如果不热衷于玩游戏，那么我将学习。
但我数学不及格。因此我热衷于玩游戏。
- 6 -
- 7 -
第四章 一阶逻辑的基本概念
一、将下列命题用0元谓词符号化. (1) 小王学过英语和法语。
(2)除非李建是东北人，否则他一定怕冷。 (3)2大于3仅当2大于4。 (4)3不是偶数。 (5)2或3是素数。
二、在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:
(1) 对于任意x,均有)2)(2(22-+=-x x x (2) 存在x,使得x+5=9.
其中(a)个体域为自然数集合. (b)个体域为实数集合.
三、在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数。 (2) 在北京卖菜的人不全是外地人。 (3)乌鸦都是黑的。 (4)有的人天天锻炼身体。
四、给定解释I如下:
(a) 个体域D为实数集合R.
(b) D中特定元素a=0.
(c) 特定函数f(x,y)=x-y,x,y D
∈
(d) 特定谓词F(x,y):x=y, G(x,y):x ∈. 说明下列公式在I下的含义,并指出各公式的真值: (1))) y G x? ? x ? → y , ) ( ( (y F x , (2))) f x y F y ? ? x→ a ( ), ) , , ( x (y ( G (3) )) G x y F y x? ? ? → f ), ( ( , ) , y (a ( x (4) )) x a y f G ? x→ y ? (y ) F , ), ( x , ( ( 五、给定下列各公式一个成真的解释，一个成假的解释。 (1) ?x(F(x)∨G(x)) (2) ?x(F(x) ∨G(x) ∧H(x)) 六、判断下列公式的类型 (1) F(x,y)→(G(x,y)→F(x,y)) (2) ?x?y F(x,y)→?x?y F(x,y) - 8 - - 9 - 第五章 一阶逻辑的等值演算与推理 一、设个体域D={a,b,c},消去下列各式的量词 (1) ?x ?y(F(x) ∧G(y)) (2) ?x ?y(F(x) ∨G(y)) (3) ?x F(x) →?y G(y) 二、求下列公式的前束范式 （1）?x F(x) →?y G(x,y) （2）?x(F(x,y) →?y G(x,y,z)) 三、设个体域D={1,2,3,4}，F(x):x 是2的倍数，G(x):x 是奇数。 将命题?x (F(x) →? G(y))中的量词消去，并讨论命题的真值。 四、在自然推理系统下用直接法或用附加前提法或用归谬法构造下列推理的证明 ? 1.全称量词消去规则(UI) ? 2.全称量词引入规则(UG) ? 3. 存在量词引入规则(EG) ? 4. 存在量词消去规则(EI) )() ()()(c A x xA y A x xA ∴?∴?或)() (x xA y A ?∴) ()(x xA c A ?∴) () (c A x xA ∴? （1）前提：?x (F(x) →G(x)), ?x F(x) 结论：?x G(x) (2)前提：?x(F(x)→G(x)) 结论：?xF(x)→?x G(x) (3)前提：?x(F(x)∨G(x))，┐?x G(x) 结论：?x F(x) 五、在自然推理系统下构造下列推理的证明 没有白色的乌鸦，北京鸭都是白色的。因此，北京鸭都不是乌鸦。- 10 - 第六章集合论 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 二、1．设集合A有n个元素，那么A的幂集合P(A)的元素个数为． 2．设集合A＝{a，b}，那么集合A的幂集是． 三、（1）B、C为任意的三个集合，如果A∪B=A∪C，判断结论B=C是否成立？并说明理由． （2）B、C为任意的三个集合，如果A⊕B=A⊕C，判断结论B=C是否成立？并说明理由． - 11 - - 12 - 四、 1．设集合A ＝{a , b , c }，B ={b , d , e }，求 （1）B ?A ； （2）A ?B ； （3）A －B ； （4）B ⊕A ． 2．设A ={{a , b }, 1, 2}，B ={ a , b , {1}, 1}，试计算 （1）（A -B ） （2）（A ∪B ） （3）（A ∪B ）-（A ∩B ） 五．证明集合等式：A ? (B ?C )=(A ?B ) ? (A ?C ) 六、某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。 第七章二元关系（1） 一、单项选择题 1．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={ A．自反的B．对称的 C．传递且对称的D．反自反且传递的 2．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b∈A , 且a +b = 8}，则R具有的性质为（）． A．自反的B．对称的 C．对称和传递的D．反自反和传递的 3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A．0 B．2 C．1 D．3 4．设集合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．以上都不对二、填空题 1．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， ∈ R? x x y < 且 =且 > ∈ ∈ {B , , } A y y B x A 则R的有序对集合为．2．设集合A={0, 1, 2}，B={0, 2, 4},R是A到B的二元关系， ∈ R? y x ∈ ∈ 且 =且 < > y {B , x } A , A y B x 则R的关系矩阵M R＝ ． 3．设集合A={a,b,c}，A上的二元关系 R={ 则(R?S)－1=． 4．设集合A=｛a,b,c｝，A上的二元关系R={ - 13 - - 14 - 三、设A={a ，b}，构成集合ρ（A ）×A 。 四、(1)列出集合A={2,3,4}上的恒等关系I A ,全域关系E A ,小于或等于关系L A ,整除关系D A . (2)设A={a,b,c,d}，1 R ， 2R 为A 上的关系，其中 1 R = { },,,,,a a a b b d { } 2,,,,,,R a d b c b d c b = 求23 122112,,,R R R R R R 。 五、设集合A ＝{a , b , c , d } 如图1所示． （1）写出R 的表达式； （2）写出R 的关系矩阵； （3）求出R 2 ． 六、设集合A ={1，2，3，4}，R ={ （1）写出R 的集合表示； （2）画出R 的关系图； （3）说明R 满足自反性，不满足传递性． 图1 - 15 - 第七章 二元关系（2） 一、选择题 1. 下列说法正确的是( ) A ．C B =?=?则 C A B A B ．C B =?=?则C A B A C ．C B =⊕=⊕则C A B A D ．B A =Φ=-则B A 2. 若A={（x ，y ）| （y －4）/（x+2）=1}和B={（x ，y ）| y=3x －2}，则A∩B 为（ ） A ．{(x ，y)| (y －3)/(x －1)=1} B ．{(x ，y)| x=4，y=10} C ．{(x ，y)| y=x+2} D ．Ф 3. 设A 为有限集，元素个数为n 个，P(A)为A 的幂集，则P(A)的元素个数 及A A ?的元素个数为( ) A ．n n ， B ．n 2 及 2n C ．n 2 及 n D ．以上全不对 4. 设A 是非空集合，则A 上的空关系不具有( ) A ．反自反性 B ．自反性 C ．对称性 D ．传递性 5．设} 10......3 2 1 {，，，，=A ， R 是A 上相等关系“=”，由R 产生等价类有( ) A ．10个 B ．50个 C ．100个 D ．1个 6.集合A 的一个划分，确定A 的元素间的关系为( ). A ．全序关系 B ．等价关系 C ．偏序关系 D ．拟序关系 7．集合A={1，2，3}上的下列关系矩阵中符合等价关系条件的是（ ） A ．?? ??? ?????100010101 B ．?? ??? ?????101010101 C ．?? ?? ? ?????101110011 D ．?? ?? ? ?????111011001 8.给定A={1、2、3}上的关系R={<1, 1>, <2, 2>, <1, 3>, <3, 1>, <2, 3>}则( ) A R 是自反的且传递 B R 不反自反且不对称 C R 是反对称且不对称 D R 不自反且传递 9．A={1、2、3}，则A 上不同等价关系有( ) A. 5 B.10 C. 15 D.8 二、设A={1，2，3，4},R={<1,1>,<2,2>,<3,3>,<4,4>,<2,3>,<3,2>}是A上的等价关系吗？如果是,给出给出每个元素的等价类；如果不是,请说明理由。 三、设集合A={1，2，3，6，8，12，24，36}，R为A上整除关系，画出R的哈斯图，并指出B={2，6，8}的极大元，极小元、最大元，最小元、及上确界和下确界。 四、设A={1，2，3，4}，在A?A上定义二元关系R， ? (1)证明R 是A?A上的等价关系. (2)确定由R 引起的对A?A的划分. - 16 - - 17 - 第八章 函数 一、选择题 1．设A={a, b}，B={1, 2}，R1，R2，R3是A 到B 的二元关系，且R1={, }，R2={, , }，R3={, }，则（ ）不是从A 到B 的函数． A ．R1和R2 B ．R2 C ．R3 D ．R1和R3 2.设A={a ，b ，c}，B={1，2}，作f ：A →B ，则不同的函数个数为( ) A ． 6 B.5 C. 9 D.8 3.下列函数中为双射的是( ). A ．3 (mod) )( , :j j f I I f =→ B ． 是偶数，是奇数，j j j f N N f 01)( ,:= → C ．1|2| )( ,:+=→i i f N I f D ．152)( ,:-=→r r f R R f 4.设Z 是整数集，E={…,-4,-2,0,2,4，…}，f ：Z →E ，f （x ）=2x ，则f 是( ) A ．仅是满射 B ．仅是单射 C ．是双射 D ．无逆函数 二、判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的? (1) f:N →N, f(x)=x 2+2 (2) f:N →N,f(x)=(x)mod 3, x 除以3的余数 (3) f:N →N,f(x)=10x x ???，若为奇数 ，若为偶数 (4) f:N →{0,1},f(x)=01x x ???，若为奇数 ，若为偶数 (5) f:N-{0}→R,f(x)=lgx (6) f:R →R,f(x)=x 2-2x-15 三、设X={a,b,c,d},Y={1,2,3},f={ (1)f是从X到Y的二元关系,但不是从X到Y的函数; (2)f是从X到Y的函数,但不是满射,也不是单射的; (3)f是从X到Y的满射,但不是单射; (4)f是从X到Y的双射. 四、设A={1,2}，B={a,b,c},写出所有A到B的函数，并说明所具有的性质。 五、已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B 的函数数是多少？ 六、设N是自然数集合，定义 N 上的二元关系R： R={(x,y): x ∈N, y ∈N, x+y 是偶数} (1)证明R是等价关系。 (2)求关系R的等价类。 - 18 - - 19 - 第十四、十五章 一、单项选择题 1．一个无向图有4个结点，其中3个的度数为2，3，3，则第4个结点的度数不可能是（ ） A.0 B. 1 C. 2 D. 4 2．无向完全图n K 有 ( )条边 A. n B. n 2 C. n(n-1) D. n(n-1)/2 3．整数列（1，3，3，5，4）（ ） A ．可以简单图化 B. 不可图化 C. 可图化，不可简单图化 4．若答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ). A. (1,2,2,3,4,5) B. (1,2,3,4,5,5) C. (1,1,1,2,3) D. (2,3,3,4,5,6). 5．设简单图G 所有结点的度之和为12，则G 一定有( ). A ．3条边 B ．4条边 C ．5条边 D ．6条边 6．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ ） A ．3 B ．4 C ．5 D ．6 7．下列各图中既是欧拉图，又是汉密尔顿图的是（ ） A ． B ． C ． D ． 8.设G 为完全二部图K 2,3，下面命题中为真的是( ) A.G 为欧拉图 B.G 为哈密尔顿图 C.G 为平面图 D.G 为正则图 二、填空 1．简单无向图有21条边,3个4度结点,其余均为3度结点,则G 有___个结点. 2．无向图G= 3.设K 6是有6个点的完全图，则K 6共有____________条边。 4. .已知n 阶无向简单图G 有m 条边，则G 的补图G 有__________条边。 5. 若一条路中，所有边均不相同，则此路称作____________；若一条路中所 有的结点均不相同，则称此路为____________。 6．图G 如图1所示，那么图G 的割点是 。 7．如图2所示 G 的邻接矩阵A=_______ a b f c e d 图1 4 v 3 v 2 v 1v 图2 - 20 - 8.下图的点连通度等于 ，边连通度等于_________。 9.已知n 阶无向图G 中有m 条边，各顶点的度数均为3。又已知2n-3=m ， 则m= . 三、（1）已知无向图G 有12条边，1度顶点有2个，2度、3度、5度顶点各1个，其余顶点度数均为4，求4度顶点的个数。 （2）假设在图G(有向图或无向图)中，有10条边，4个3度的结点，其余结点的度数不大于2。问G 中至少有几个结点？ 四、判断下图是否欧拉图，若是，找出一个欧拉回路。 五．设简单无向图G 有n 个结点,n+1条边，证明G 中至少有一上结点的度≥3。 六、画出彼德森图，K 5，K 3,3，并判断他们是否是欧拉图，是否是哈密顿图。 3 v 5 v 第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （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 - 离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设Ｐ：他去旅游 Ｑ：他有时间 则命题公式为Ｐ→Ｑ 3．请将语句“有人不去工作”翻译成谓词公式． 设Ａ（x）:x是人 Ｂ（x）：去工作 则谓词公式为?x（A(x)∧－B（x）) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习 则谓词公式为?x（A（x）∧B（x）） 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A-B)；（2）(A∩B)；（3）A×B． 解： （1）（A-B）＝{{1}，{2}} （2）（A∩B）＝{1，2} （3）A×B＝ {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2．设A={1，2，3，4，5}，R={ 离散数学作业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 去工作， 一、请给出一个集合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次作业（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 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。 华南理工大学网络教育学院 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 离散数学作业 软件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 ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素. 离散数学作业答案 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）-------数理逻辑部分 一、 填空题 1. 将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。 2、命题公式G=（P ∧Q ）→R ，则G 共有 个不同的解释；把G 在其所有解释下所 取真值列成一个表，称为G 的 ；解释（?P ，Q ，?R ）或（0，1，0）使G 的真值为 。 3、 已知命题公式R Q P G →∧?=)(，则G 的析取范式是 。 4、 求公式)()(R P Q P ∧?∨∧的主析取范式 。 5、 设命题公式)(R Q P G →?→=，则使公式G 为假的解释是 、 和 。 6、在谓次词逻辑中将下面命题符号化：在北京工作的人未必都是北京人（提示：设F （x ）：x 在北京工作。G （x ）：x 是北京人。） 。 7、将公式化成等价的前束范式，=→?→???)))()((),((x R z zQ y x yP x 。 8、设谓词的定义域为},,{c b a ，将表达式)()(x xS x xR ?∧?中的量词消除，写成与之等价的 命题公式是 。 二、 单项选择题 1、下列语句中，（ ）是命题。 A ．下午有会吗？ B ．这朵花多好看呀！ C ．2是常数。 D ．请把门关上。 2、一个公式在等价意义下，下面哪个写法是唯一的（ ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 3、设命题公式P Q P G →∧=)(，则G 是（ ）。 A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式 4、设命题公式)(), (P Q P H Q P G ?→→=→?=，则G 与H 的关系是（ ）。 以上都不是。.;.;.;.D H G C G H B H G A =?? 5、已知命题))((R Q P G ∧→?=，则所有使G 取真值1的解释是（ ）。 A （0，0，0），（0，0，1），（1，0，0） B （1，0，0），（1，0，1），（1，1，0） C （0，1，0），（1，0，1），（0，0，1） D （0，0，1），（1，0，1），（1，1，1） 6、设I 是如下一个解释，0 101),(),(),() ,(},,{b b P a b P b a P a a P b a D =， 则在解释I 下取真值为1的公式是（ ）。 ),(.);,(.);,(.);,(.y x yP x D x x xP C y x yP x B y x yP x A ??????? 7、下面给出的一阶逻辑等价式中，（ ）是错的。 )). (()(.)); (()(.); ()())()((.); ()())()((.x B A x x xB A D x A x x xA C x xB x xA x B x A x B x xB x xA x B x A x A →?=?→??=???∨?=∨??∨?=∨? 三、 计算题 1. 求命题公式?（P ∨Q ）?（P ∧Q ）的析取范式与合取范式。 第一章 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、下列语句中哪个是真命题（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 a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a * A B C D 8、下列图中是欧拉图的是（ A ）。 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 ）： 国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {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>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 『离散数学』课程 作业3： P64：3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。 解：直接使用容斥原理。我们做如下设定： A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|B∩C|=4，|A∩B∩C|=2 由容斥原理: |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|=14+12+6-6-5-4+2=19 —————————————————————————————————————— 但相当一部分同学没有直接使用容斥原理， 而是画了文氏图。 使用文氏图的方法，会发现此题存在问题： 表示只会打网球的同学是-1人， 此种情况与实际不符。 这可能是作者的疏忽，该教材第一版中， “已知6个会打网球的人中有4人会打排球。” 一句是写作 “已知6个会打网球的人都会打篮球或排球。” 则用容斥原理或文氏图，都可以得到5的结果。 A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|A∩B∩C|=2 因为“会打网球的人都会打篮球或排球。” 所以C =（A∩C）∪（B∩C） 由容斥原理: |C|=|（A∩C）∪（B∩C）| = |（A∩C）|+|（B∩C）|-|（A∩C）∩（B∩C）| 可知|（B∩C）|= |C|-|（A∩C）|+|（A∩C）∩（B∩C）| = 6-5+2=3 |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C| =14+12+6-6-5-3+2=20 离散数学(第2版)_在线作业 _4 交卷时间：2017-01-12 14:00:56 一、单选题 1. (5分) ? A. q ∧┐q ? B. p →┐q ? C. p → (p ∨q) ? D. (p ∨┐p)→q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 2. (5分) ? A. ? B. ? C. ? D. 下列命题公式为重言式的是( )。 设，下列式子正确的是( )。 纠错 得分： 5 知识点： 离散数学(第2版 ) 收起解析 答案 C 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 4. (5分) ? A. ? B. ? C. 下列是两个命题变元的极小项的是( )。 设G 是有个顶点， 条边和个面的连通平面图，则 等于( )。 ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. 满射函数 ? B. 非单射非满射函数 ? C. 双射函数 ? D. 单射函数 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 6. (5分) 设R 是实数集合，函数，则是( )。 ? A. 11，3，4 ? B. 10，4，3 ? C. 11，3，5 ? D. 12，3，6 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. x*y=gcd(x,y)，即x,y 的最大公约数 ? B. x*y=lcm(x,y)，即x,y 的最小公倍数 ? C. x*y=max{x,y} ? D. x*y=min{x,y} 纠错 得分： 5 知识点： 离散数学(第2版) 下列平面图的三个面的次数分别是( )。 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？( )。 《离散数学》作业一、选择或填空 1．下列公式中哪些是永真式？( ) A.(┐P ∧Q)→(Q→?R) B.P→(Q→Q) C.(P ∧Q)→P D.P→(P ∨Q) 2．设全体域D 是正整数集合，确定下列命题的真值： A. ?x ?y (xy=y) ( ) B. ?x ?y(x+y=y) ( ) C. ?x ?y(x+y=x) ( ) D. ?x ?y(y=2x) ( ) 3．有n 个结点的树，其结点度数之和是( )。 4．举出集合A 上的既是等价关系又是偏序关系的一个例子。( ) 5．群 《离散数学》作业参考答案一、选择或填空： 1． B C D 2． A， F B，F C，F D，T 3． 2n-2 4． I A 5．单位元，1 6． A 7． A D 8． (1) P→?Q (2) P??Q 9．偶数 10．自反性、对称性和传递性 11． 1，单位元，0 12．所有边一次且恰好一次 13． B C D E F 14． B D 15． 5,10 16． D 17． B 18． D 19． A 20．（1）R R={ 〈1，1〉，〈1，3〉，〈2，2〉，〈2，4〉} （2）Ｒ-1＝｛〈1，2〉，〈2，1〉，〈3，2〉，〈4，3〉｝ 21． m=n-1 22． 9,3 23． A 24． D 25 (1) 26 (2) 27 (3) 28 (1) 29 (1) 30 (3) 31 (2) 32 (3) 33 (2) 34 (4) 35 (2) 36 (1) 二、求下列各公式的主析取范式和主合取范式 解：1． P∨?Q （主合取范式） ?（P∧(?Q∨Q)）∨（(?P∨P)∧?Q） ?(P∧?Q)∨（P∧Q）∨（?P∧?Q）∨（P∧?Q） ?(P∧?Q)∨（P∧Q）∨（?P∧?Q）（主析取范式） 2．Q→( P∨?R) ??Q∨P∨?R（主合取范式） ?（Q→( P∨?R)） ?（?P∨?Q∨?R）∧（?P∨?Q∨R）∧（?P∨Q∨?R）∧（?P∨Q∨R）∧（P∨?Q∨R）∧ （P∨Q∨?R）∧（P∨Q∨R）（原公式否定的主合取范式） Q→( P∨?R) ?（P∧Q∧R）∨（P∧Q∧?R）∨（P∧?Q∧R）∨（P∧?Q∧?R）∨（?P∧Q∧?R）∨（?P∧?Q∧R）∨（?P∧?Q∧?R）（主析取范式） 3． P→Q??P∨Q（主合取范式） ?(?P∧(Q∨?Q))∨((?P∨P)∧Q) ?(?P∧Q)∨(?P∧?Q)∨(?P∧Q)∨(P∧Q) ?(?P∧Q)∨(?P∧?Q)∨(P∧Q)（主析取范式） 4．?(P→Q)∨(R∧P)??(?P∨Q)∨(R∧P) ?(P∧?Q)∨(R∧P)（析取范式） ?(P∧?Q∧(R∨?R))∨(P∧(?Q∨Q) ∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)（主析取范式） ?(?(P→Q)∨(R∧P)) ?(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R) （原公式否定的主析取范式） ?(P→Q)∨(R∧P) ?(?P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)∧(P∨Q∨R)∧(P∨?Q∨R)（主合取范式）5．P∧Q（主析取范式） ?(P∨(Q∧?Q))∧((P∧?P)∨Q) ?(P∨?Q)∧(P∨Q)∧(P∨Q)∧(?P∨Q) ?(P∨?Q)∧(P∨Q)∧(?P∨Q)（主合取范式） 6 Q→(P∨?R) ??Q∨P∨?R（主合取范式） ?(Q→(P∨?R))离散数学作业
离散数学形成性考核作业4题目与答案
离散数学作业答案
离散数学(大作业)与答案
离散数学作业(2)
离散数学作业
华南理工离散数学作业题2017版
离散数学作业
离散数学作业答案完整版
离散数学课程作业(2)
离散数学作业答案
离散数学作业标准答案
离散数学 作业及答案
国开放大学离散数学本离散数学作业答案
离散数学 作业 3~4 答案
离散数学(第2版)_在线作业_4
《离散数学》作业
《离散数学》作业参考答案
- 离散数学作业答案
- 吉林大学2019-2020学年第一学期期末考试《离散数学》大作业参考答案
- 离散数学作业答案完整版
- 吉林大学2019 离散数学大作业 辅导答案
- 离散数学大作业——编程实现最小生成树
- 离散数学作业答案
- 离散数学大作业
- 离散数学大作业
- 离散数学期末大作业
- 离散数学(大作业)离散数学(大作业)以及参考答案
- 离散数学课程大作业
- 最新离散数学作业答案一
- 离散数学(大作业)-吉林大学
- 离散数学(大作业) (1)
- 2018年春季 [0004]《离散数学》大作业 答案
- 华南理工网络教育2018年离散数学大作业参考答案#试题
- 2016离散数学作业3标准答案
- 离散数学
- 离散数学作业答案
- 离散数学(大作业)与答案