离散数学网上作业题
- 格式:doc
- 大小:816.50 KB
- 文档页数:15
离散数学(第2版)_在线作业_1交卷时间2019-09-26 14:15:30一、单选题(每题5分,共20道小题,总分值100分)1.命题变元P和Q的极大项M1表示()。
(5分)┐P∨Q┐P∧QP∧┐QP∨┐Q正确答案您的答案是D回答正确展开2.设,下面集合等于A的是()。
(5分)ABCD正确答案您的答案是B回答正确展开3.下面既是哈密顿图又是欧拉图的是()。
(5分)ABCD正确答案您的答案是C回答正确展开4.下列语句中为命题的是()。
(5分)AB水开了吗?C再过5000年,地球上就没有水了D请不要抽烟!正确答案您的答案是C回答正确展开5.n个结点、m条边的无向连通图是树当且仅当m=()。
(5分)A2n-1B nC n-1D n+1正确答案您的答案是C回答正确展开6.命题变元P和Q的极小项m1表示()。
(5分)P∧┐Q┐P∧Q┐P∨QP∨┐Q正确答案您的答案是B回答正确展开7.公式的前束范式为()。
(5分)ABCD正确答案您的答案是D回答正确展开8.无向完全图有()条边。
(5分)A nB n2C n(n-1)D n(n-1)/2正确答案您的答案是D回答正确展开9.设无向图G的所有结点的度数之和为12,则G一定有()。
(5分)6条边5条边3条边4条边正确答案您的答案是A回答正确展开10.下列语句中不是命题的是()。
(5分)AB我是大学生C3是奇数D请勿吸烟!正确答案您的答案是D回答正确展开11.下列不一定是树的是()。
(5分)A每对结点之间都有通路的图B连通但删去一条边则不连通的图C有n个结点,n-1条边的连通图D无回路的连通图正确答案您的答案是A回答正确展开12.在有3个结点的图中,奇度数结点的个数为()。
(5分)A0或2B0C1D1或3正确答案您的答案是A回答正确展开13.集合的对称差运算不满足()。
(5分)A消去律B结合律C交换律D幂等律正确答案您的答案是D回答正确展开14.下列图中()是平面图。
数理逻辑习题判断题1.任何命题公式存在惟一的特异析取范式 ( √ ) 2. 公式)(q p p →⌝→是永真式 ( √ ) 3.命题公式p q p →∧)(是永真式 ( √ ) 4.命题公式r q p ∧⌝∧的成真赋值为010 ( × ) 5.))(()(B x A x B x xA →∃=→∀ ( √ )6.命题“如果1+2=3,则雪是黑的”是真命题 ( × ) 7.p q p p =∧∨)( ( √ )8.))()((x G x F x →∀是永真式 ( × ) 9.“我正在撒谎”是命题 ( × ) 10. )()(x xG x xF ∃→∀是永真式( √ )11.命题“如果1+2=0,则雪是黑的”是假命题 ( × ) 12.p q p p =∨∧)( ( √ )13.))()((x G x F x →∀是永假式 ( × )14.每个命题公式都有唯一的特异(主)合取范式 ( √ ) 15.若雪是黑色的:p ,则q →p 公式是永真式 ( √ ) 16.每个逻辑公式都有唯一的前束范式 ( × ) 17.q →p 公式的特异(主)析取式为q p ∨⌝ ( × ) 18.命题公式 )(r q p →∨⌝的成假赋值是110 ( √ ) 19.一阶逻辑公式)),()((y x G x F x →∀是闭式( × )单项选择题1. 下述不是命题的是( A )A.花儿真美啊! B.明天是阴天。
C.2是偶数。
D.铅球是方的。
2.谓词公式(∀y)(∀x)(P(x)→R(x,y))∧∃yQ(x,y)中变元y (B)A.是自由变元但不是约束变元B.是约束变元但不是自由变元C.既是自由变元又是约束变元D.既不是自由变元又不是约束变元3.下列命题公式为重言式的是( A )A.p→ (p∨q)B.(p∨┐p)→qC.q∧┐q D.p→┐q4.下列语句中不是..命题的只有(A )A.花儿为什么这样红?B.2+2=0C.飞碟来自地球外的星球。
离散数学⽹上作业题东北农业⼤学⽹络教育学院离散数学复习题复习题⼀⼀、证明1、对任意两个集合B A 和,证明 ()()A B A B A =??-2、构造下⾯命题推理的证明如果今天是星期三,那么我有⼀次英语或数学测验;如果数学⽼师有事,那么没有数学测验;今天是星期三且数学⽼师有事,所以我有⼀次英语测验。
⼆、计算1、(1)画⼀个有⼀条欧拉回路和⼀条汉密顿回路的图。
(2)画⼀个有⼀条欧拉回路但没有汉密顿回路的图(3)画⼀个没有欧拉回路但有⼀条汉密顿回路的图2、设()(){}212,,,个体域为为,整除为3、⼀棵树有2n 个结点度数为2 ,3n 个结点度数为3,… ,k n 个结点度数为k ,问它有⼏个度数为1的结点。
4、设集合{}A A ,4,3,2,1=上的关系 {4,33,21,22,1,1,1=R ,求出它的⾃反闭包,对称闭包和传递闭包。
三、设{}45,36,27,15,9,6,5,3,2,1=A 上的整除关系{}212121,,,a a A a a a a R 整除∈=, R 是否为A 上的偏序关系?若是,则:1、画出R 的哈斯图;2、求{}{}{}9,2glb 9,2lub 9,2和最⼤下界的最⼩上界。
四、⽤推导法求公式()()R Q P →→的主析取范式和主合取范式。
五、设实数集2R 上的关系{}c b d a R d c b a dc b a +=+∈,,,,,,2=ρ,证明:ρ是2R 上的等价关系。
六、设+R R 和分别是实数集和正实数集,+和×分别是普通加法和乘法,定义函数+→R R f :为r r f 2)(=,证明 ),(),(?++R R f 到是从的同构映射。
七、设R 是实数集合,}0{*-=R R ,在R R ?*上定义⼆元运算ο为:()()()d bc ac d c b a +=,,,ο,试证明>?<ο,*R R 是⼀个群。
>?<ο,*R R 是否阿贝尔群?复习题⼆⼀、设上的整除关系完成下列各⼩题。
1、设p:我们划船,q:我们跑步, 则有命题“我们不能既划船又跑步”符号化为( )1. D.2、设集合A中有4个元素,则A上的等价关系共有( )个1. C. 153、设集合A中有4个元素,则A上的划分共有( )个1. C. 154、1. B. 结合律5、设集合A中有99个元素,则A的子集有( )个1. A.6、域与整环的关系为( )1. D. 整环是域7、下列联结词中,不满足交换律的是( )1. D.8、集合A = {1, 2, 3, 4}上的关系R= {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是t(R)中元素的是( )1. B. (1, 2)9、具有4个结点的非同构的无向树的数目是( )1. A. 210、设集合A中有4个元素,则A上的划分共有( )个.1. C. 1511、1. C. 412、设集合A中有99个元素,则A的子集有( )个.1. A.13、*()1. C.14、下列联结词中,不满足交换律的是( ).1. D.15、设集合A中有4个元素,则A上的等价关系共有( )个.1. C. 1516、集合A= {1, 2, …, 10}上的关系R ={(x, y)|x + y = 10, x, y ∈A}, 则R的性质是( )1. B. 对称的17、在任意n阶连通图中,其边数( ).1. B. 至少n – 1条18、设集合A = {1, 2, 3, 4, 5}上的关系R = {(x, y)|x, y A且x + y = 6},则R的性质是( )1. B. 对称的19、1. B.×20、1. B.×21、1. B.×22、1. B.×23、1. B.×24、任意最小联结词集至少有2个联结词.1. B.×25、有生成树的无向图是连通的.1. A.√26、1. B.×27、1. B.×28、1. B.×29、1. B.×30、1. A.√31、1. A.√32、任意整数都是0的因数.1. A.√33、1. A.√34、1. B.×35、1. B.×36、设x和y是实数集中的变量, 则x + y > 0是命题函数.1. A.√37、1. A.√38、1. B.×39、实数集R上的乘法和加法运算相互可分配.1. B.×40、实数集R关于数的乘法运算“×”阿贝尔群.1. B.×41、群可分为Abel群和非Abel群.1. A.√42、强连通图一定是单向连通的.1. A.√43、本题参考答案:44、在同构意义下,3阶群有( )个,4阶群有( )个,5阶群有( )个本题参考答案:1;2;145、设集合A = {1, 2, 3},则A上的置换共有( )个本题参考答案:646、本题参考答案:2;3;247、集合A上的等价关系R必满足( 、、)本题参考答案:自反性;对称性;传递性48、所有6的因数组成的集合为( ).本题参考答案:{-1,-2,-3,-6,1,2,3,6}.49、对于任意集合A, 若|A| = n, 则A的幂集合P(A)有( )个元素.本题参考答案:2n<\/sup><\/em><\/span>50、设A = {1, 2, 3, 4},A上的二元关系R = {(1,2),(2,3),(3,2)},S = {(l,3),(2,3),(4,3)},则(R - S)-1 = {___________}.51、有限域的元素个数为( ), 其中( )且( )本题参考答案:p n;p为素数;n为正整数52、本题参考答案:是<\/span>53、三个元素集合的划分共有( )种.本题参考答案:554、设A = {a, b}, B = {2, 4},则A ×B = {____ _______}.本题参考答案:{(a, 2), (a, 4), (b, 2), (b, 4)}.55、设Q是有理数集合,Q关于数的乘法运算“×”能构成( ).本题参考答案:独异点56、本题参考答案:57、本题参考答案:58、集合A上的等价关系R必满足( 、、).本题参考答案:自反性;对称性;传递性59、若n个人,每个人恰有3个朋友,则n必为偶数,试证明之本题参考答案:60、画出所有不同构的6阶无向树.本题参考答案:61、画出所有不同构的5阶无向树.本题参考答案:62、画出所有不同构的4阶根树.本题参考答案:。
离散数学试题及答案解析一、选择题1. 在集合{1,2,3,4}中,含有3个元素的子集有多少个?A. 4B. 8C. 16D. 32答案:B解析:含有3个元素的子集可以通过组合数公式C(n, k) = n! / [k!(n-k)!]来计算,其中n为集合的元素个数,k为子集中的元素个数。
在本题中,n=4,k=3,所以C(4, 3) = 4! / [3!(4-3)!] = 4。
2. 下列哪个命题是真命题?A. 所有偶数都是整数。
B. 所有整数都是偶数。
C. 所有整数都是奇数。
D. 所有奇数都是整数。
答案:A解析:偶数是指能被2整除的整数,因此所有偶数都是整数,选项A是真命题。
选项B、C和D都是错误的,因为并非所有整数都是偶数或奇数。
二、填空题1. 逻辑运算符“非”(NOT)的真值表是:当输入为真时,输出为______;当输入为假时,输出为真。
答案:假解析:逻辑运算符“非”(NOT)是一元运算符,它将输入的真值取反。
如果输入为真,则输出为假;如果输入为假,则输出为真。
2. 命题逻辑中,合取词“与”(AND)的真值表是:当两个命题都为真时,输出为真;否则输出为______。
答案:假解析:合取词“与”(AND)是二元运算符,只有当两个命题都为真时,输出才为真;如果其中一个或两个命题为假,则输出为假。
三、简答题1. 解释什么是等价关系,并给出一个例子。
答案:等价关系是定义在集合上的一个二元关系,它满足自反性、对称性和传递性。
例如,考虑整数集合上的“同余”关系。
对于任意整数a,b,如果a和b除以同一个正整数n后余数相同,则称a和b模n同余。
这个关系是自反的(a同余a),对称的(如果a同余b,则b同余a),并且是传递的(如果a同余b且b同余c,则a同余c)。
2. 什么是图的连通性?一个图是连通的需要满足什么条件?答案:图的连通性是指在无向图中,任意两个顶点之间都存在一条路径。
一个图是连通的需要满足以下条件:图中的任意两个顶点v和w,都可以通过图中的边相互到达。
[0004]《离散数学》网上作业题答案第1次作业[论述题]第1次作业一、填空题1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个,其中有( )单射,( )个满射.2. 令G (x ): x 是金子,F (x ): x 是闪光的,则命题“金子都是闪光的,但闪光的未必是金子”符号化为( ).3. 设X 是非空集合,则X 的幂集P (X )关于集合的⋃运算的单位元是( ),零元是( ),P (X )关于集合的⋂运算的单位元是( ).4. 6阶非Abel 群的2阶子群共有( )个,3阶子群共有( )个,4阶子群共有( )个.5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图,当n ≥ ( )时是Hamilton 图,当n ( )时是平面图.二、单选题1. 幂集P (P (P (∅))) 为( )(A){{∅}, {∅, {∅}}}. (B){∅, {∅, {∅}}, {∅}}. (C){ ∅, {∅, {∅}}, {{∅}}, {∅}} (D){ ∅, {∅, {∅}}}. 2. 设R 是集合A 上的偏序关系,则1-⋃R R 是( ).(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对 3. 下列( )组命题公式是不等值的.(A))(B A →⌝与B A ⌝∧. (B) )(B A ↔⌝与)()(B A B A ∧⌝∨⌝∧. (C))(C B A ∨→与C B A →⌝∧)(. (D))(C B A ∨→与)(C B A ∨∧⌝. 4.下列代数结构(G , *)中,( )是群.(A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法.(C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 5.4阶完全无向图4K 中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2三、设A 和B 是集合,使B B A =-成立的充要条件是什么,并给出理由. 四、设R 和S 是集合A 上的对称关系,证明S R 对称的充要条件是R S S R =. 五、分别利用(1)等值演算法和(2)真值表求命题公式))(())((r q p p q r A ∨→→→∨⌝=的主析取范式和主合取范式.六、设G 是(n , m )无向图,若n m ≥,证明G 中必存在圈.参考答案:第1次作业答案一、1. 32,0,30.2.))()(())()((x G x F x x F x G x ⌝∧∃∧→∀.3.∅,X ,X .4. 3,1,0.5.n 为奇数,3,4≤n .二、1(C); 2(B); 3(D); 4(D); 5(A). 三、证 ==⇔=-B A B B A ∅. (⇐)显然.(⇒)因为B A B A ⋂=-,根据B B A =-得B B B B A ⋂=⋂⋂)(,于是B = ∅,进而A = ∅.四、解 由于R 和S 是对称的,所以S S R R==--11,.(⇐)因为R S S R =,两边取逆得11)()(--=R S S R ,而S R S R R S ==---111)(.所以S R S R =-1)(,因此S R 是对称关系.(⇒)由于S R 对称,所以S R S R =-1)(. 而R S R S S R ==---111)(,因而R S S R =.五、解 (1)等值演算法 A 的主合取范式:))(())((r q p p q r A ∨→→→∨⌝== ))(())((r q p p q r ∨∨⌝→∨⌝∨⌝ = )())((r q p p q r ∨∨⌝∨∨⌝∨⌝⌝= )()(r q p p q r ∨∨⌝∨⌝∧∧ = r q p ∨∨⌝(由吸收律得到). 于是,A 的主析取范式为))(())((r q p p q r A ∨→→→∨⌝== ∨⌝∧⌝∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝)()()()(r q p r q p r q p r q p)()()(r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧.(2)真值表法命题公式))(())((r q p p q r A ∨→→→∨⌝=的真值表如下:由表可知,))(())((r q p p q r A ∨→→→∨⌝=的主合取范式为r q p A ∨∨⌝=.A 的主析取范式为A = ∨⌝∧⌝∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝)()()()(r q p r q p r q p r q p)()()(r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧.七、证(反证)假设G 中不含圈. 设G 有k (k ≥ 1)个连通分支k G G G ,...,,21,其节点个数分别为k n n n ,...,,21,其边数分别为k m m m ,...,,21. 这时,i G 为树,根据树的基本性质有1-=i i n m )1(k i i ≤≤. 进而n k n n m m ki i k i i <-=-==∑∑==)1(11,与已知n m ≥矛盾. 证毕.第2次作业[论述题]第2次作业一、填空题1.设A = {2, {3}, 4, a }, B = {1, 3, 4, {a }}, 则{3}( )A ,{a }( )B ,{{a }}( )B .2. 设A = {1, 2, 3, 4, 5}上的关系R = {(1, 2), (3, 4), (2, 2)}, S = {(4, 2), (2, 5), (3, 1), (1, 3)}, 则=S R { }, =R S { },=R R { }.3. 在同构意义下,3阶群有( )个,4阶群有( )个,5阶群有( )个.4.任意有限布尔代数)1,0,,,,(⋅+B 均与集合代数( )同构,其元素个数为( ), 其中( )是B 的所有原子组成的集合.5. 不同构的5阶无向树有( )棵,不同构的5阶根树有( )棵.二、单选题1. 在有理数集合Q 上定义运算“*”如下:对于任意x , y ∈ Q ,y x * = x + y – xy ,则Q 关于*的单位元是( ).(A)x . (B)y . (C)1. (D)0.2. 设A = {1, 2, 3}, 下图分别给出了A 上的两个关系R 和S ,则S R 是( )关系.(A)自反. (B)对称. (C)传递. (D)等价.3.令T (x ): x 是火车,B (x ): x 是汽车,F (x , y ): x 比y 快,则“某些汽车比所有的火车慢”符号化为( ).(A)()()),()()(y x H x T x y B y →∀∧∃. (B)()()),()()(y x H x T x y B y ∧∀→∃. (C)()()),()()(y x H x T y B y x ∧→∃∀.G SG R(D)()()),()()(y x H x T x y B y →∀→∃.4. 整数集合Z 关于数的加法“+”和数的乘法“⋅”构成的代数结构(Z, +, ⋅)是( ). (A)域 (B)域和整环 (C)整环 (D) 有零因子环5.设G 是简单图,G 是G 的补图,若G G ≅,则称G 为自补图. 5阶不同构的自补图个数为( ).(A)0. (B)1. (C)2. (D)3.三、设C B g B A f →→:,:, 若g f 是单射,证明f 是单射,并举例说明g 不一定是单射.四、设A = {a , b , c , d }上的关系R = {(a , b ), (b , d ), (c , c ), (a , c )}, 画出R 的关系图,并求出R的自反闭包r (R )、对称闭包s (R )和传递闭包t (R ).五、设G 是(6,12) 的简单连通平面图,则G 的面由多少条边围成,为什么? 六、任意6个人中,一定有3个人彼此认识或有3个人彼此不认识.参考答案:第2次作业答案一、1. ∈,∈,⊆.2.{(1,5), (3, 2), (2, 5)}, {(4, 2), (3, 2), (1, 4)}, {(1, 2), (2, 2)}.3. 1, 2, 1.4. ,,,),((⋂⋃X P ∅, X ), 2n , n .5. 3, 9.二、1(D); 2(B); 3(A); 4(C); 5(C).三、证 对于任意A x x ∈21,,若)()(21x f x f =,则))(())((21x f g x f g =,于是))(())((21x f g x g f =. 由于g f 是单射,所以21x x =,因此f 是单射.例如,A = {a , b }, B = {1, 2, 3}, C = {α, β, γ}, f = {(a , 1), (b , 2)}, g = {(a , α), (b , β), (c , β)}, 这时)},2(),,1{(βα=g f ,它是A 到C 的单射,但g 不是单射. 四、解 R 的关系图如下:}),(),,(),,(),,(),,(),,(),,{()(d d b b a a c a c c d b b a R r =, }),(),,(),,(),,(),,(),,(),,{()(a c b d a b c a c c d b b a R s =. }),(),,(),,(),,(),,{()(d a c a c c d b b a R t =.五、证 根据Euler 公式,G 的面数为r = 12 – 6 +2 = 8. 由握手定理知,∑=⋅=vv 24122)deg(,而简单连通平面图的每个面至少由3条边围成,所以G 的每个面恰由3条边围成.六、证 用6个节点分别表示这6个人,可得6阶完全无向图6K . 若两个人认识,则在相应的两个节点所在的边上涂上红色,若两个人不认识,则在相应的两个节点所在的边上涂上蓝色.对于任意的6K 的节点v ,因为5)deg(=v ,与v 邻接的边有5条,当用红、蓝颜色去涂时,至少3条边涂的是同一种颜色,不妨设321,,vv vv vv 是红色. 若3条边21v v ,32v v ,31v v 是红色,则存在红色3K ,这意味着有3个人相互认识; 若21v v ,32v v ,31v v 都是蓝色,则存在蓝色3K ,这意味着有3个人相互不认识. 结论成立.第3次作业[论述题]第3次作业 参考答案:第3次作业一、1.{1, 3, {1, 2}, {3}};{{2, 3}, {1}};{1, 3, {1, 2}, {3}, {2, 3}, {1}}.2.0,1,0.3. ))()((x O x Z x →⌝∀.4. p n , p 为素数,n 为正整数.abd5. 是,3,10.二、1(B); 2(C); 3(D); 4(C); 5(A).三、证 对于任意C z ∈,由于g f 是满射,必存在A x ∈,使得z x f g x g f ==))(())(( . 令B x f y ∈=)(,有z y g =)(,因此,g 是满射.设},,{c b a A =,}3,2,1{=B ,},{βα=C ,令B A f →:,,:C B g →3)(,3)(,2)(===c f b f a f ,βαβ===)3(,)2(,)1(g g g .这时,α==))(())((a f g a g f ,β==))(())((b f g b g f ,显然有},{)(ran βα=g f ,g f 是满射. 而ran f = {2, 3},f 不是满射.四、证 (1)对于任意x ∈ Z , 由于x x x x +=+22, 所以(x , x ) ∈ R , 即R 是自反的. (2)因为(0, 0) ∈ R , 因此R 不是反自反的.(3)对于任意x , y ∈ Z , 若(x , y ) ∈ R , 则y y x x +=+22, 于是x x y y +=+22, 进而(y , x ) ∈ R , 即R 是对称的.(4)因为(2, -3) ∈ R 且(-3, 2) ∈ R ,因此R 不是反对称的.(5)对于任意x , y , z ∈ Z , 若(x , y ) ∈ R 且(y , z ) ∈ R , 则y y x x +=+22且z z y y +=+22,于是z z x x +=+22,所以(x , z ) ∈ R , 即R 是传递的. 综上所述,知R 是自反的、对称的和传递的.五、解 命题公式)())(q p q p A ⌝→↔→⌝=的真值表如下:A 的主析取范式为:)()(q p q p A ⌝∧∨∧=.A 的主合取范式为:)()(q p q p A ∨∧⌝∨=.六、证 对于任意的6K 的节点v ,因为5)deg(=v ,与v 邻接的边有5条,当用红、蓝颜色去涂时,至少3条边涂的是同一种颜色,不妨设321,,vv vv vv 是红色. 若3条边21v v ,32v v ,31v v 是红色,则存在红色3K ; 若21v v ,32v v ,31v v 都是蓝色,则存在蓝色.第4次作业[论述题]第4次作业 参考答案:第4次作业答案一、1.自反性、对称性和传递性.2. Abel.3. 6.4. 封闭性和结合性.5. 不含圈的连通.二、1(A); 2(C); 3(B); 4(D); 5(C).三、证 对于任意A b a ∈,,假定)()(b f a f =. 由于≤是偏序,于是a a ≤,所以)(a f a ∈,进而)(b f a ∈,根据定义知b a ≤. 同理可证,a b ≤. 根据偏序的反对称性有b a =,因此f 是单射.当b a ≤时,对于任意)(a f x ∈,于是a x ≤. 根据偏序的传递性有b x ≤,即)(b f x ∈,故)()(b f a f ⊆.四、证 (1) 与非联结词“↑”的运算表如下:(2)p p p p p ↑=∧⌝=⌝)(.)()()())((q p q p q p q p q p ↑↑↑=↑⌝=∧⌝⌝=∧. )()()()()(q q p p q p q p q p ↑↑↑=⌝↑⌝=⌝∧⌝⌝=∨.五、解 ))),(),((),,((v y vQ u x uQ z y x zP y x ∃→∃∧∃∀∀=))),(),((),,((v y vQ u x uQ z y x zP y x ∃∨⌝∃∧∃∀∀ =))),(),((),,((v y vQ u x Q u z y x zP y x ∃∨⌝∀∧∃∀∀=))),(),((),,((v y Q u x Q v u z y x zP y x ∨⌝∃∀∧∃∀∀ =))),(),((),,((v y Q u x Q z y x P v u z y x ∨⌝∧∃∀∃∀∀ 六、证 (1)根据Euler 公式,有2+-=n m r . (2)31052)2(5-≤⇒≤+-n m m n m . (3) 若Petersen 图是平面图,由于其每个面至少5条边围成,于是由(2)知3105-≤n m . 因为在Petersen 图中,m = 15, n = 10, 于是31010515-⋅≤,矛盾.第5次作业[论述题]第5次作业 参考答案:第5次作业答案一、1. 2n .2. 反自反、反对称、传递.3. 是.4. 独异点.5. 上确界和下确界. 二、1(C); 2(A); 3(B); 4 (D); 5(B).三、(1)证 对于任意∈),(),,(2211y x y x R ⨯ R ,若)),(()),((2211y x f y x f =,于是),(),(22221111y x y x y x y x -+=-+,进而2211y x y x +=+且2211y x y x -=-. 由此可得,2121,y y x x ==,因而),(),(2211y x y x =,故f 是单射.对于任意∈),(q p R ⨯ R ,取2,2qp y q p x -=+=,容易得知),(),()),((q p y x y x y x f =-+=.由上可知,f 是双射. (2)解 由上的证明过程知,⎪⎭⎫⎝⎛-+=-2,2)),((1y x y x y x f.(3)解 很显然If f =- 1R ⨯R ,即),()),)(((1y x y x f f=- .)2,2())()(),()(()),(()),)(((y x y x y x y x y x y x y x f y x f f =--+-++=-+= .四、解 }),(),,(),,(),,(),,{()(c c b b c b b a a a I R R r A =⋃=. }),(),,(),,(),,(),,{()(1b c a b c b b a a a RR R s =⋃=-.}),(),,(),,(),,{()(c a c b b a a a R t =. 五、证(1))(x xP ∀ P (2)P (c ) US(1) (3))))()(()((x R y Q x P x ∧→∀ P (4)))()(()(c R y Q c P ∧→ US(3) (5))()(c R y Q ∧ T(2)(4)I (6)Q (y ) T(5)I (7)R (c ) T(5)I (8))()(c R c P ∧ T(2)(7)I (9)))()((x R x P x ∧∀ UG(8) (10)))()(()(x R x P x y Q ∧∀∧ T(6)(9)I六、证 设G 是一棵阶数2≥的无向树,k k v v v v L 121...:-是G 中的最长路径. `若1v 和k v 至少有一个不是树叶,不妨设k v 不是树叶,即2)deg(≥k v ,则k v 除与1-k v 邻接外,还存在1+k v 与k v 邻接.若1+k v 在L 上,则G 中存在圈,不可能. 若1+k v 不在L 上,则G 中存在一条比L 长1的路径1121...+-k k k v v v v v ,与L 是G 中最长路径矛盾.第6次作业[论述题]第6次作业 参考答案:第6次作业答案一、1. 1,3,5,7,11,13,17,19.2. 平行.3. 010, 100, 101, 110, 111.4. 2.5. 3.二、1(B); 2(A); 3(D); 4(C); 5(A).三、(1)证 任意∈),(),,(2211y x y x R ×R , 若),(),(2211y x f y x f =,则),(),(22221111y x y x y x y x -+=-+,进而2211y x y x +=+且2211y x y x -=-,于是21x x =且21y y =,从而f 是单射.任意∈),(q p R ×R , 取⎪⎩⎪⎨⎧-=+=22q p y q p x , 通过计算易知),(),(q p y x f =,因此f 是满射. 故f 是双射.(2) 解 由上面的证明知,f 存在逆函数且⎪⎭⎫⎝⎛-+=-2,2),(1y x y x y x f.又()()),(2,2,1y x y x y x f y x f f=⎪⎭⎫⎝⎛-+=- ,即I f f=- 1R ×R ,而()()())2,2())()(),()((,,y x y x y x y x y x y x y x f y x f f =--+-++=++= .四、解 R 的传递闭包t (R )的关系图如下:于是,有t (R ) = {(1, 3), (3, 1), (2, 3), (4, 3), (4, 5), (6, 5), (1, 1), (3, 3),(2,1),(4,1)}. 五、解 首先写出命题公式()())()(p q r r q p A →→↔→→=的真值表如下:从真值表可得命题公式A 的主析取范式为:∨⌝∧⌝∧∨∧⌝∧∨∧∧=)()()(r q p r q p r q p A)()()(r q p r q p r q p ⌝∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝.命题公式A 的主合取范式为:)()(r q p r q p A ∨⌝∨⌝∧⌝∨⌝∨=.七、解 对于2, 3, 5, 7, 8,先组合两个最小的权2+3 = 5, 得5, 5, 7, 8;在所得到的序列中再组合5+5 = 10, 重新排列后为7, 8, 10;再组合7+8 =15, 得10, 15;最后组合10+15 = 25.2515108710875587532 所求的最优2叉树树如下:。
离散数学试题及答案一、选择题1. 下列哪个是由离散数学的基本概念组成的?A. 集合论和函数论B. 图论和逻辑C. 运算符和关系D. 全数论和数论答案:B2. 下列哪个是离散数学的一个应用领域?A. 数据结构和算法分析B. 微积分和线性代数C. 概率论和统计学D. 数值分析和微分方程答案:A3. 集合A={1, 2, 3},集合B={2, 3, 4},则A交B的结果是:A. {1, 2, 3, 4}B. {2, 3}C. {2}D. {1}答案:B4. 下列哪个是对于集合的补集运算的正确描述?A. A∪A' = ∅B. A∩A' = ∅C. A - A' = AD. A'∩B' = (A∪B)'答案:B5. 若命题p为真,命题q为假,则命题p→q的真值为:A. 真B. 假C. 不确定D. 无法确定答案:B二、填空题1. 对于命题“如果x是偶数,则x能被2整除”,其逆命题为________________。
答案:如果x不能被2整除,则x不是偶数。
2. 在一个完全图中,如果有12条边,则这个图有__________个顶点。
答案:6个顶点。
3. 设集合A={1, 2, 3, 4},则A的幂集的元素个数是__________。
答案:2^4=16个元素。
4. 设关系R={(-1, 0), (0, 1), (1, 0)},则R的逆关系是__________。
答案:R^(-1)={(0, -1), (1, 0), (0, 1)}。
5. 若集合A={1, 2, 3},集合B={2, 3, 4},则A的笛卡尔积B是__________。
答案:A×B={(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。
三、计算题1. 求集合A={1, 2, 3}和集合B={2, 3, 4}的并集。
离散数学考试试题及答案一、单项选择题(每题5分,共20分)1. 在离散数学中,以下哪个概念不是布尔代数的基本元素?A. 逻辑与B. 逻辑或C. 逻辑非D. 逻辑异或答案:D2. 下列哪个命题不是命题逻辑中的命题?A. 所有学生都是勤奋的B. 有些学生是勤奋的C. 学生是勤奋的D. 勤奋的学生答案:D3. 在集合论中,以下哪个符号表示集合的并集?A. ∩B. ∪C. ⊆D. ⊂答案:B4. 以下哪个图不是无向图?A. 简单图B. 完全图C. 有向图D. 多重图答案:C二、填空题(每题5分,共20分)1. 如果一个命题的逆否命题为真,则原命题的________为真。
答案:逆命题2. 在图论中,如果一个图的任意两个顶点都由一条边连接,则称这个图为________图。
答案:完全3. 一个集合的幂集是指包含该集合的所有________的集合。
答案:子集4. 如果一个函数的定义域和值域都是有限集合,那么这个函数被称为________函数。
答案:有限三、简答题(每题10分,共30分)1. 请简述什么是图的欧拉路径。
答案:欧拉路径是一条通过图中每条边恰好一次的路径。
2. 解释什么是二元关系,并给出一个例子。
答案:二元关系是指定义在两个集合之间的关系,它将第一个集合中的元素与第二个集合中的元素联系起来。
例如,小于关系就是一个二元关系。
3. 请说明什么是递归函数,并给出一个简单的例子。
答案:递归函数是一种通过自身定义来计算函数值的函数。
例如,阶乘函数就是一个递归函数,定义为:n! = n * (n-1)!,其中n! = 1当n=0时。
四、计算题(每题10分,共30分)1. 计算以下逻辑表达式:(P ∧ Q) ∨ ¬R答案:首先计算P ∧ Q,然后计算¬R,最后计算两者的逻辑或。
2. 给定集合A = {1, 2, 3},B = {2, 3, 4},求A ∪ B。
答案:A ∪ B = {1, 2, 3, 4}3. 已知函数f(x) = 2x + 3,求f(5)。
《离散数学》在线作业(二)设G为v个结点e条边的连通平面图,则面r等于()A:e-v+2B:v-e+2C:v+e+2D:v+e-2参考选项:A利用二元关系R的关系图求其对称闭包时,()A:每两个结点之间都加上两条方向相反的边B:若两个结点间有一条单向边,则添加一条与其方向相反的边C:每个结点上加上一个自环D:若两个结点间没有边相连,则加上两条方向相反的边参考选项:B图G和G1的结点和相应的边分别存在一一对应关系是图G和G1同构的()A:必要条件B:充分必要条件C:充分条件D:即不充分也不必要条件参考选项:BA:AB:BC:CD:D参考选项:C汉密尔顿回路是()A:闭迹B:路径C:既是闭迹又是圈D:既不是闭迹也不是圈参考选项:CA:AB:BC:CD:D参考选项:C只含有有限个元素的格称为有限格,有限格必是()A:有界格B:有补格C:分配格D:布尔格参考选项:A无向图中的边e是割边的充分必要条件是()A:边e不是重边B:边e是重边C:边e不包含在图的某个回路中D:边e不包含在图的任一闭迹中参考选项:DA:AB:BC:CD:D参考选项:A下列语句中是命题的是()A:今天是晴天。
B:你身体好吗?C:我真高兴。
D:请勿吵闹。
参考选项:A在代数系统中整环和域的关系是()A:整环一定是域B:域一定是整环C:域不一定是整环D:域一定不是整环参考选项:B设集合A={1,2,3,6,12},其中£为A上的整除关系。
则子集B={2,3}的极大元有()A:1B:3C:2D:6参考选项:B,C。
离散数学试题及答案解析一、单项选择题(每题2分,共10分)1. 集合A={1,2,3},集合B={2,3,4},则A∩B等于:A. {1,2,3}B. {2,3}C. {1,4}D. {3,4}答案:B2. 以下哪个命题是真命题?A. 所有天鹅都是白色的。
B. 有些天鹅不是白色的。
C. 所有天鹅都不是白色的。
D. 没有天鹅是白色的。
答案:B3. 函数f: A→B的定义域是A,值域是B,那么f是:A. 单射B. 满射C. 双射D. 既不是单射也不是满射答案:D4. 逻辑表达式(p∧q)→r的逆否命题是:A. ¬r→¬(p∧q)B. ¬r→¬p∨¬qC. r→(p∧q)D. ¬r∧¬p∨¬q答案:B5. 有限集合A={a, b, c}的子集个数为:A. 3B. 4C. 7D. 8答案:D二、填空题(每题3分,共15分)1. 如果一个关系R在集合A上是自反的,那么对于A中的每一个元素a,都有___________。
答案:(a, a)∈R2. 命题逻辑中,合取(AND)的逻辑运算符用___________表示。
答案:∧3. 在图论中,一个连通图是指图中任意两个顶点之间都存在___________。
答案:路径4. 集合{1, 2, 3}的幂集包含___________个元素。
答案:85. 如果一个函数f是单射,那么对于任意的x1, x2∈A,如果f(x1)=f(x2),则x1___________x2。
答案:=三、解答题(每题10分,共20分)1. 证明:若p是q的充分条件,q是r的充分条件,则p是r的充分条件。
证明:假设p成立,由于p是q的充分条件,所以q成立。
又因为q是r的充分条件,所以r成立。
因此,p成立可以推出r成立,即p是r的充分条件。
2. 给定一个有向图,其中包含顶点A、B、C、D,边为(A, B),(B, C),(C, D),(D, A),(A, C)。
《离散数学》在线作业(一)
A:错误
B:正确
参考选项:B
任意平面图至少是四色的。
A:错误
B:正确
参考选项:A
A:错误
B:正确
参考选项:A
任意函数一定有逆函数。
A:错误
B:正确
参考选项:A
模格一定是分配格。
A:错误
B:正确
参考选项:A
图G的邻接矩阵A,Al中的i行j列表示结点vi到vj长度为l路的数目。
A:错误
B:正确
参考选项:B
质数阶群必是循环群。
A:错误
B:正确
参考选项:A
A:错误
B:正确
参考选项:A
任意一棵无向树至少有两片树叶(退化树除外)。
A:错误
B:正确
参考选项:B
A:错误
B:正确
参考选项:A
任何循环群必是阿贝尔群。
A:错误
B:正确
参考选项:B
若连通图所有结点度数均为奇数,则该图为欧拉图。
A:错误
B:正确
参考选项:A
任意一个谓词公式均和一个前束范式等价。
A:错误
B:正确
参考选项:B
R是A上的二元关系,R是自反的,当且仅当r(R)=R。
A:错误
B:正确
参考选项:B
若函数f,g为入射则其复合函数也为入射。
A:错误
B:正确
参考选项:B
A:错误
B:正确
参考选项:A
集合A上的等价关系确定了A的一个划分。
A:错误
B:正确
参考选项:B
在任何图中,度数为偶数的结点必定是偶数个。
A:错误。
东北农业大学网络教育学院离散数学复习题复习题一一、证明1、对任意两个集合B A 和,证明 ()()A B A B A =⋂⋃-2、构造下面命题推理的证明如果今天是星期三,那么我有一次英语或数学测验;如果数学老师有事,那么没有数学测验;今天是星期三且数学老师有事,所以我有一次英语测验。
二 、计算1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。
(2)画一个有一条欧拉回路但没有汉密顿回路的图 (3)画一个没有欧拉回路但有一条汉密顿回路的图2、设()(){}212,,,个体域为为,整除为<x x Q y x y x P ,求公式: ()()()()()x Q y x P y x →∃∀,的真值。
3、一棵树有2n 个结点度数为2 ,3n 个结点度数为3,… ,k n 个结点度数为k ,问它有几个度数为1的结点。
4、设集合{}A A ,4,3,2,1=上的关系 {4,33,21,22,1,1,1=R ,求出它的自反闭包,对称闭包和传递闭包。
三、设{}45,36,27,15,9,6,5,3,2,1=A 上的整除关系{}212121,,,a a A a a a a R 整除∈=, R 是否为A 上的偏序关系?若是,则:1、画出R 的哈斯图;2、求{}{}{}9,2glb 9,2lub 9,2和最大下界的最小上界。
四、用推导法求公式()()R Q P →→的主析取范式和主合取范式。
五、设实数集2R 上的关系{}c bd a R d c b a dc b a +=+∈,,,,,,2=ρ,证明:ρ是2R 上的等价关系。
六、设+R R 和分别是实数集和正实数集,+和×分别是普通加法和乘法,定义函数+→R R f :为r r f 2)(=,证明 ),(),(⨯++R R f 到是从的同构映射。
七、设R 是实数集合,}0{*-=R R ,在R R ⨯*上定义二元运算ο为:()()()d bc ac d c b a +=,,,ο,试证明>⨯<ο,*R R 是一个群。
>⨯<ο,*R R 是否阿贝尔群?复习题二一、设 上的整除关系完成下列各小题。
1、 证明ρ是L 上的偏序关系。
2、 画出偏序集,L ρ<>的哈斯图。
3、 在L 上定义两个二元运算∧和∨:对任意,a b L ∈,(,)a b glb a b ∧=,(,)a b lub a b ∨=。
请填空(在横线上填是或不是):①代数系统,,L <∧∨> 格。
②代数系统,,L <∧∨> 有界格。
③代数系统,,L <∧∨> 有补格。
④代数系统,,L <∧∨> 分配格。
二、求布尔函数的析取范式和合取范式设°123122323(,,)()()()E x x x x x x x x x =∧∨∧∨∧是布尔代数{0,1},,,<∨∧>%上的一个布尔表达式。
试写出123(,,)E x x x 的析取范式和合取范式(用推导法或列函数表的方法均可)。
三、画出满足下列要求的图①有一条欧拉回路和一条汉密尔顿回路。
②有一条欧拉回路但没有汉密尔顿回路。
③没有欧拉回路但有汉密尔顿回路。
④既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中,边的总数等于2(n-1),这里n 是叶子数。
五、计算求带权2、3、5、7、11、13的最优二叉树。
六、证明在一个连通平面图中,若它有n 个结点,m 条边,且每个面由k 条边围成。
试证(2)2k n m k -=-七、证明设V 是有限字母表,给定代数系统*,V <>o ,其中o 是串的连接运算。
对于任一串*V α∈,建立*V 到N 的映射f ,()||f αα=。
证明f 是*,V <>o 到,N <+>的一个满同态,且当||1V =时,f 是同构映射。
{}1,2,3,4,12L ={}121212,,,a aa a L a a ρ=∈整除八、应用给定有限状态机(,,,,,)s M Q S R f h A =,它的状态图如附图所示。
1、 求状态A 的011010的后继以及可接受状态序列。
2、 求s M 对于激励010110的响应。
3、构造一台与s M 相似的转换赋值机t M ,画出t M 的状态图。
九、证明考察一个(8,4)码C ,它的校验位a 5,a 6,a 7,a 8满足下列方程 a 5=a 1+ a 2+ a 4 a 6=a 1+ a 3+ a 4 a 7=a 1+ a 2+ a 3 a 8=a 2+ a 3+ a 4其中a 1,a 2,a 3,a 4为信息位。
求出这个码的一致校验矩阵。
证明0min x C x ∈≠()4W X =。
复习题三一、设集合完成下列各小题。
1求S 的幂集()P S 。
2证明(),P S <⊆>是偏序集。
3画出偏序集(),P S <⊆>的哈斯图。
4在()P S 上定义两个二元运算∧和∨:对任意,()A B P S ∈,A B A B ∧=⋂,A B A B ∨=⋃。
请填空(在横线上填是或不是并回答为什么):①代数系统(),P S <⊆>格,因为 。
{},,S a b c =②代数系统(),P S <⊆> 有界格,因为 。
③代数系统(),P S <⊆> 有补格,因为 。
④代数系统(),P S <⊆> 分配格,因为 。
⑤代数系统(),,,~P S <⋂⋃> 布尔代数,因为 。
二、计算设°123122323(,,)()()()E x x x x x x x x x =∧∨∧∨∧是布尔代数{0,1},,,<∨∧>%上的一个布尔表达式。
试写出123(,,)E x x x 的析取范式和合取范式(用列函数表的方法)。
三、回答问题完全图n K 是否是欧拉图?是否是哈密尔顿图?为什么? 四、画图对于下图,利用克鲁斯克尔算法求一棵最小生成树。
五、计算一棵树有两个结点度数为2 ,1个结点度数为3,3个结点度数为4 ,其余结点度数为1。
问该树有几个度数为1的结点。
六、证明(,)G V E =图是无向简单图,其中||||V n E m ==,,证明:2)1(-≤n n m 。
证明 因为G 是简单图,所以图G 中没有环和平行边,任意两结点间最多有一条边,故2(1)2n n n m C -≤=。
七、证明已知(,,,),{,,},{,,},:(1)(2)(3)(4)(5)(6)(7)N T N T G V V P V B C V a b c P a BC aBC CB BC aB ab bB bb bC bc cC ccσσσσσ===→→→→→→→求证 *n n na b c σ⇒ 八、设计设计一台有限状态机M ,它的输出是已经输入符号数的模3数(即设计模3计数器)。
九、计算给定码C={00000,10001,01100,10101},求码C 中任两个码字的海明距和min ()d C 。
复习题四一、填空1、设A 和B 为有限集,|A|=m ,|B|=n ,则有 个从A 到B 的关系,有 个从A 到B 的函数,其中当m ≤n 时有 个入射,当m=n 时,有 个双射。
2、集合2{|}A n n N =∈ (是/不是)可数的。
二、计算1、用推导法求下列公式的主合取范式和主析取范式:(())P Q R ⌝∨→2设A A },4,3,2,1{=上二元关系{1,2,2,2,2,4,3,4}R =<><><><>,求其自反闭包、对称闭包、传递闭包。
三、证明1、设C B A ,,是三个集合,证明:()()A B C A C B ⋂-=-⋂ 2证明等价式:()(()())()()()()x A x B x x A x x B x ∃→⇔∀→∃ 四、将下列命题推理符号化并给出形式证明:已知张三或李四的彩票中奖了;如果张三的彩票中奖了,那么你是知道的;如果李四的彩票中奖了,那么王五的彩票也中奖了;现在你不知道张三的彩票中奖。
所以李四和王五的彩票都中奖了。
五、设复数集合{|,,0}C a bi a b R a =+∈≠,定义C R 上二元关系:,a bi c di R <++>∈当且仅当0ac >,证明:R 为等价关系。
六、证明:若A B C D A B C D ⨯⨯:::和,则。
七、设集合{23|,}m nG m n I =∈,⨯是普通乘法,证明:,G <⨯>是一个群。
八、设实数集合R ,+和x 是普通加法和乘法,定义映射:f R R →,,()xx R f x e ∀∈=,证明,,f R R <+><⨯>是从到的单一同态。
复习题五一、填空1、实数集合R (是/不是)可数的。
2、设A 和B 为有限集,|A|=m ,|B|=n ,则有 个从A 到B 的关系,有 个从A 到B 的函数,其中当m ≤n 时有 个入射,当m=n 时,有 个双射。
二、计算1、用推导法求下列公式的主合取范式和主析取范式:(())P Q R ⌝∨→2设A A },4,3,2,1{=上二元关系{1,1,2,3,2,4,3,2,3,4}R =<><><><><>,求其自反闭包、对称闭包、传递闭包。
三、证明1、设C B A ,,是三个集合,证明:()()A B C A C B --=-- 2证明等价式:()(()())()()()()x A x B x x A x x B x ∀→⇔∃→∀ 四、将下列命题推理符号化并给出形式证明:已知今天下雨或刮风;如果今天下雨,那么我在家看书;如果今天刮风,那么我去放风筝;今天我没有在家看书。
所以今天刮风并且我去放风筝了。
五、设正整数集合I +上的二元关系{,|,,}2x yR x y x y I I +-=<>∈∈,证明:R 为等价关系。
六、证明:若A B C D A B C D ⨯⨯:::和,则。
七、设集合{5|}nG n I =∈,⨯是普通乘法,证明:,G <⨯>是一个群。
八、设正实数集合R +和实数集合R ,+和x 是普通加法和乘法,定义映射:f R R +→,,()ln x R f x x +∀∈=,证明,,f R R +<⨯><+>是从到的同构。
复习题六一、 求公式q ∧(p ∨┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明:前提 (∃x)(F(x)∧S(x))→(∀y)(M(y) →W(y)),(∃y)(M(y)∧┐W(y)) 结论 (∀x)(F(x)→┐S(x)) 三、计算题1.证明逻辑等价式A →(A →B)⇔A →B 成立。