离散数学期末复习题2014-6-14
1.命题“他在教室看书或在宿舍看书。”可以符号化为P∨S。( ) 2.(P ?Q)→┐(P ∨Q)是可满足式。()
3. 设P、Q是两个命题,当且仅当P、Q的真值均相同时,P ?Q的值为T. ( )
4. 命题公式(P∧(P→Q)) →Q是永真式. ( )
5. 命题联结词集{∨、∧}是极小功能完备的联结词集. ( )
6. (┐P → Q)→(Q →┐P )是可满足式。()7.一个命题的合取范式不是唯一的。()8.若命题公式A的主析取范式包含全部的极小项,则A为永真式( ) 9.等价式?(?x)A(x)?(?x)?A(x)成立。( ) 10.?xA(x)∨?x B(x)??x ( A(x) ∨B(x)) ()
11.当个体域S={a,b,c}消去公式(?x) P(x)∨(?x)Q(x)中量词为
(P(a)∨Q(a)) ∧(P(b)) ∨Q(b)) ∧(P(c)∨Q(c)) ( )
12. ?xA(x) ∨?x B(x) ??x ( A(x) ∨B(x)) ( )
13. ?x?y((P(x)→ Q(f(x,y))∧ R(x,y))在任何解释下均是命题()
14.?xA(x) ∧?x B(x) ??x ( A(x) ∧ B(x)) ()
15.{a }?{{a}}()16.{}={φ}()17.ρ(A?B)=ρ(A)?ρ(B)()18. 若关系R不具有对称性则R一定具有反对称性( ) 19.若R和S是X上的具有传递性的关系,则R ?S也具有传递性。()
20.集合X 上的一个划分A 一定能确定X 上的一个等价关系R ( )
21.已知函数 ?: X →Y 是单射函数,f -1是f 的逆关系,
则f -1必是Y 到X 的函数。 ( )
22.集合X 上的一个等价关系R 一定能确定X 上的一个划分A ( )
23.有限集合A 上的单射函数一定是双射函数。 ( )
24.已知函数 ?: X →Y 是双射函数,f -1是f 的逆关系必是Y 到X 的函数。 ( )
25. 有向图D 中结点之间的距离满足对称性。 ( )
26. 简单有向图G =
27. 无向图中结点之间的连通关系是等价关系。 ( )
28. 无向图G 中结点之间的连通关系是等价关系。 ( )
29. 有向图图D 中两点i v ,j v 的距离d(i v ,j v ) = d(j v ,i v ) ( )
F F T T F T T T T F
F T T F F F F F F T
F T T T F F T T F
二、填空题
1. 已知A = { {x ,y},Φ },
则B 的幂集ρ(A )= { }
2.
已知A={1,2,3,4,5,6,7},B={2,4,6,8,10},则
A -B= { } ,A + B= { } 。
3.设A={1,2,3,{1,2},{3}},B={{1},2,3,{2,3},}
A –(B∩A) = {}
B 十A = {}
4.设A、B是有穷集合,|A|=n,|B|=m,那么#ρ(A)= ,|A×B|= ,|ρ(A×B)|= ,
所有可能的函数?:A→B的集合的基数为。
定义在A上的所有的双射函数有_____________________
5.已知A={x,y,z,s,t},B={a,b,c},则
集合笛卡尔积A ⅹB的基数有______________
定义在A到B的不同关系R有___________种.
定义在A到B的不同函数F有___________种.
6.R是集合X上的关系。如果R满足,,,
则R是X上的等价关系。
7. 两个重言式的析取是,一个重言式与一个矛盾式的析取是 .
8. 公式(P∨Q) ?R的只含联结词{┐、∧}的等值式,
9.给定命题公式(P ∧ Q) ∨ R,该公式在全功能集合{?,→}中的形式
为: ___________________________.
10. 命题公式((p ∧q) →r ) ∧( p →?( q ∧r ) )
该公式的主析取范式为____________________
该公式的主合取范式为____
11.设谓词Q(x):x < 5,以及个体域是{-1,0,1,3,5,7}
则(?x)Q(x)真值为_____, (?x)Q(x)真值为______ .
12.设个体为实数集,R(x):x是闪光的,Q(x):x是金子
则命题“闪光的未必是金子”形式化为:
13、设个体为自然数集,N(x):x是自然数,L(x,y):x>y
则命题“存在最大的自然数”形式化为: .
14. 谓词公式?xF(x,y) →??y G(x,y)的前束范式为
______ .
15.公式?x F(x,y) →?y G(x,y) 的前束范式
为__
16. 设个体域为A={a,b},消去公式?x?y (P(x)→Q(y) )中的量词,
?x?y ( P(x)→Q(y))? .
17. 设A={1,2,3,4}上的关系R={<1,2>,<2,3>,<1,1>,<4,4>,<1,3> }
具有关系的五个性质中的哪些性质?__ ___
关系R具有哪些性质? ________________________.
19. 设A={a,b,c }上的关系R={ ,,
则R3 = { }
20.无向图G有15条边,有三个度数为4的结点,三个度为1的结点,其余
结点的度数均为3,那末图中共有_______个结点?
21.简单无向完全图(n,m),图中边和结点的数目有什么关系?
即m = ________________
简单有向完全图(n,m),图中边和结点的数目有什么关系?
即m = __________________
22. 设函数f:A→B为可逆函数,则f-1of= ,
fof-1 = .
三、选择题(多选题)
1.选出下列语句中的命题()
A.天气多麽晴朗啊!
B.我正在说谎。
C.雪是黑色的。
D.我做完作业了。
2.下列关系中哪一些能构成函数( )
A. R={ 1,x 2 >|( x 1 ,x 2 ∈N)∧(x 1 + x 2 <10)} B. R={ 1,y 2 >|( y 1 ,y 2 ∈R)∧(y 2 = y 1 +2)} C. R={ 1,y 2 >|( y 1 ,y 2 ∈R)∧(y2 2 = y2 1 )} D. R={ 3 .下列式中错误的是( ) A. (?x)(A(x)∨p(x)) ? (?x)A(x)∨ (?x)p(x) B. (?x)A(x) ∧ p ? (?x)(A(x) ∧ p ) C. (?x)(A(x)∨B(x)) ? (?x)A(x)∨(?x)B(x) D. (?x)(A(x)∧B(x)) ? (?x)A(x)∧(?x)B(x) 4. 下列等价式中错误的是( ) A. (?x)( A(x) →B(x) ) ??xA(x) →?x B(x) B. (?x)A(x) →p ? (?x)(A(x) →p ) C. (?x)(A(x)∧ B(x))?(?x)A(x)∧(?x)B(x) D. (?x)(A(x)∨ B(x))?(?x)A(x)∨(?x)B(x) 5.下列各式中哪个是不成立的:( ) A: p →q ?┐p →┐q B: (?x)(P(x)∨Q(x)) ?(?x)P(x)∨(?x)Q(x); C: (p →q) ∧┐q ?┐p ; D: (?x)(P(x)∨Q(x)) ?( ?x)P(x)∨(?x)Q(x); 6.下面哪组命题公式是等值的;( ) A: A→(B∨C), ┐A∧(B∨C); B:┐(A →B),A∧┐B; C: ┐(A ?B),(A∧┐B)∨(┐A∧B); D: A →(B∨C), (A∧┐B) →C. 7. 下列推理式是正确的有() A)P ∧ ( Q→ P) ?Q B)(P ∧Q) ? P → Q C)P→ Q ?Q→ P D)(Q → (P ∧P)) → (R →(P ∧P)) ? R → Q 8.若A ?B ,则与之等价的结论有( ) A) A ∩~B ≠φB) A ∪B =B C) A∩B = A D) A - B = φ; 9. 设F(x):为有理数,G(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)) 10. 设P:2是素数,Q:5是素数,R: π是有理数。下面复合命题中为假的是() A) (P ∧ Q ) ∨R B) R ∧ (P ∨Q ) C)(P ∧ R)? Q D) (P ∧ R) → Q 11.设个体域A={a,b},公式(?x)P(x)∨(?x)S(x)在A上消去量词后为( ) A) P(x)∧S(x); B) P(a) ∨P(b) ∨S(a) ∧S(b); C) P(a)∧S(b); D) P(a) ∨P(b) ∨(S(a) ∧S(b)). 12.谓词公式(?x)(P(x)∨(?y)(R(y))→Q(x)中变元x是( ) A)自由变元; B) 既是自由变元又是约束变元. C) 既不是自由变元也不是约束变元D)约束变元; 13. 设A={1,2,3,4,5,6}上的关系为R ={(i,z)|i,z ∈A ∧i > z }, 则R的逆关系的性质是( ) A) 对称的;自反的B) 自反的;可传递的 C) 反对称的.自反的;D) 反自反的,可传递的 14.设A={a,b,c}上的关系如下,无传递性的为( ) A)ρ1 ={ } B)ρ2 ={, C)ρ3 ={, 15. 设f和g都是从A到A的双射函数,则(fog)-1为( ) A) f-1og-1B)fog-1 C )(gof)-1D)g-1of-1 16. 给定下列联结词集合,哪个可构成联结词完备集( ) A) {∨,∧,┐}B) {↑} C) {┐,→,}D) {┐,∧} 17.设D是简单有向图,下列结论正确的有() A)D是弱连通的,则D是单向连通的。 B)D是单向连通的,则D是强连通的。 C)D中的任意两点的距离满足对称性。 D)D是强连通的,则D是单向连通的。 18.给定下列序列,哪一个可构成无向简单图的结点度数序列( ) A) (1,1,2,2,3); B)(1,1,2,2,2); C) (2,1,3,2,2); D)(1,3,4,4,5). 四、运算题 (1)求命题公式((P→Q)?(┐Q→┐P)) ∧S 的最简等值式. (2)命题公式P ?( Q→R) 该公式的主析取范式为__________________________________. 该公式的主合取范式为__________________________________. 该公式的全部成真赋值为_____________________________________ (3)给定解释I为:个体域为D={1,2}; a=1, b=2, f(1)=2, f(2)=1 P(1,1)=P(1,2)=1, P(2,1)= P(2,2)=0 求一阶公式?x?y ( P(f(x), f(y)) →P(x, y) ) 在解释I下的真值 (要求写出代人的过程) 1 0 0 1 (4) 设集合X={ x , y , z , t } ,集合X上的关系R和S的关系矩阵为M R= 0 0 1 0 0 0 0 1 1 1 0 1 1 0 1 0 M S= 0 1 0 0 1)给出关系R和S的集合表示 0 0 1 0 2)给出复合关系R?S的关系矩阵和集合表示 1 0 0 0 3)求出R?S的逆关系的关系矩阵 1) R={ S={ 2)R?S={ 1 0 1 1 1 1 0 1 3) M(R?S)-1= 1 0 0 1 0 0 1 0 0 1 0 1 M(R?S)=1 0 0 0 1 0 0 1 1 1 1 1 (5) a x >= 0 设f(x) = 是实数集上的函数。 b x < 0 定义等价关系S={< x ,y>| x,y ∈R ∧f(x)= f(y)} a)写出实数集关于等价关系S的等价类及商集R/S [f(x)=a]S={ x?x >= 0 } [f(x)=b]S={ x?x < 0 } R/S = { [f(x)=a]S , [f(x)=b]S } b)建立实数集R到商集R/S的自然映射g(x),并说明该映射是单函数、 满函数或双射函数? g(x)= [x]S说明g(x)的性质:是满函数 (6) 已知集合X={ a,b,c } a) 写出该集合上的所有双射函数 b) 写出以上各函数的反函数: f1-1=f1 f2-1=f2 f3-1=f3 f4-1=f4 f5-1=f6 f6-1=f5 (7)设A={0,1,2}到B ={0,2,4}的关系为 R={|a,b∈A∩B}, 则R = { <0,0>,<2,2>,<0,2>,<2,0>} 。 (8)已知一个图有16条边,每个结点的度数均为2,此图共有多少个结点? 设节点个数为x 总节点的度数为 2 m = 2*16=32 每个节点的度为2 总节点的度数为2* x 所以2x=32 x=16 (9)有向图G的V={v1,v2,v3,v4}, E={ a.写出该图的邻接矩阵A 1 1 0 0 A=0 1 1 0 0 0 1 1 1 0 0 1 b.求出相应的A2,A3 1 2 1 0 1 3 3 1 A2=0 1 2 1 A3= 1 1 3 3 1 0 1 2 3 1 1 3 2 1 0 1 3 3 1 1 c.通过以上矩阵中的元素特征指出: v1到v2有 2 条长度为2的路径, v4到v1有 5 条长度为小于等于3的路径, V2到v3有 5 条长度为小于等于3的路径, 共有8 条长度小于或等于3的回路。 五、证明题 (1)用推理规则证明?t→m是前提条件:p→ (q→m), ?t→p, q的有效结论 (2)证明结论(?x )( C(x) →? A(x))是 前提条件:?x (A(x) →B (x)), ?x (C(x) →?B(x))的有效结论 (3)用形式推理规则证明: 证明(?x)P(x)是前提(?x)(P(x)∨Q(x)), (?x)(┓Q(x)∨┓R(x)),(?x )R(x)的有效结论。 (4)给定集合X,且R是X中的二元关系。试证明,R2?R,当且仅当关系R是可传递的。 (5)给定集合X,且R和S是X中具有传递性的二元关系。试证明R∩S也是可传递的二元关系。 (6)设R是集合X上具有自反性的关系, 证明:若R满足: ?a, b, c ∈X,若有 ,< a, c> ∈R, 则必有 ∈R,那么R是一个等价关系 离散数学期末考试试卷(A卷) 一、判断题:(每题2分,共10分) (1) (1) (2)对任意的命题公式, 若, 则 (0) (3)设是集合上的等价关系, 是由诱导的上的等价关系,则。(1) (4)任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 (0) (5)设是上的关系,分别表示的对称和传递闭包,则 (0) 二、填空题:(每题2分,共10分) (1) 空集的幂集的幂集为()。 (2) 写出的对偶式()。 (3)设是我校本科生全体构成的集合,两位同学等价当且仅当他们在 同一个班,则等价类的个数为(),同学小王所在 的等价类为()。 (4)设是上的关系,则满足下列性质的哪几条:自反的,对称的,传递的,反自反的,反对称的。 () (5)写出命题公式的两种等价公式( )。 三、用命题公式符号化下列命题(1)(2)(3),用谓词公式符号化下列命题(4)(5)(6)。(12分) (1)(1)仅当今晚有时间,我去看电影。 (2)(2)假如上午不下雨,我去看电影,否则就在家里读书。 (3)你能通你能通过考试,除非你不复习。 (4)(4)并非发光的都是金子。 (5)(5)有些男同志,既是教练员,又是国家选手。 (6)(6)有一个数比任何数都大。 四、设,给定上的两个关系和分别是 (1)(1)写出 和 的关系矩阵。(2)求 及 (12分) 五、求 的主析取范式和主合取范式。(10分) 六、设 是 到 的关系, 是 到 的关系,证明: (8分) 七、设 是一个等价关系,设 对某一个 ,有 ,证明: 也是一个等价关系。(10分) 八、(10分)用命题推理理论来论证 下述推证是否有效? 甲、乙、丙、丁四人参加比赛,如果甲获胜,则乙失败;如果丙获胜,则乙也获 胜,如果甲不获胜,则丁不失败。所以,如果丙获胜,则丁不失败。 九、(10分) 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行,他就不喜欢乘汽车,每一个人或喜欢乘汽车,或喜欢骑 自行车(可能这两种都喜欢)。有的人不爱骑自行车,因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后,有人问他们,谁的成绩最好, 甲说:“不是我,”乙说:“是丁,”丙说:“是乙,” 丁说:“不是我。” 四人的回答只有一人符合实际,问若只有一人成绩最 好,是谁? 离散数学期末考试试卷答案(A 卷) 一、判断题:(每题2分,共10分) (1)}}{{}{x x x -∈ ( ∨) (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) (3)设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系,则L R =。 ( ∨ ) (4) 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 ( ? ) (5)设R 是A 上的关系,)(),(R t R s 分别表示R 的对称和传递闭包,则 )()(R st R ts ? ( ? ) 二、填空题:(每题2分,共10分) 2006-2007学年第2学期 2005级《离散数学2》期末考试试题(A卷) 考试时间:2007年6月班级_______________________ 学号_____________________ 姓名_____________________ 请将答案写在答题纸上,写明题号,不必抄题,字迹工整、清晰; 请在答题纸和试题纸上都写上你的班级,学号和姓名,交卷时请将试题纸、答题纸和草纸一并交上来。 一.综合体(30分,每题3分) 1. 求( 1 3 5 ) (2 5 4 ) (3 4 ) 2. 只有两个生成元的循环群一定是有限循环群吗?并说明理由。 3. 有限循环群中是否一定存在周期与群的元数相等的元素? 4. 下面哪个是域GF( 16)的真子域 (A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16) 5. 有限布尔代数的元素个数必定是如下哪个形式? (A)2n;(B)n 2 ;(C)2 n;(D)4n. 6. 下列代数系统(S, *)中,哪个是群? (A) S={0,1,3,5},* 是模7的乘法;(B) S是有理数集合,*运算是普通乘法; (C) S是整数集合,*是普通乘法;(D) S={1,3,4,9},* 是模11的乘法。 7. 设A={0,1,2,3,4},运算为模5加法,请给出A的所有子群。 8. n元恒等置换是奇置换还是偶置换?对换呢? 9?请给出一个有余,但不是分配格的例子。 10.设R是模12的整数环,R={0,1,2,…,11},下面哪一个是极大理想: (A) 6R; (B)2R; (C)4R; (D)8R 二.计算题(25分,每题5分) 1. 计算分圆多项式①24(X). 2. 设(Z,+)为整数加法群,(C*,??)为非零复数的乘法群,令 f: n -i n ,是Z到C*中的同态映射,请求出f的同态核。 3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。 4. 设G是3次对称群,H是由I和(13)作成的子群,求H得所有右陪集。 5. 设A={0,1,2,3,4,5}, 运算为模6加法,请给出A中所有元素的周期。 三.(10分)证明或者反驳:f(x)=3x 5+5X2+1 四.(10分)设(G, *)是群,(A, *)和(B,*)是它的两个子群,C={a*b|a € A, b€ B}.证明:若*满足交换律,则(C, *)也是(G,*)的子群。 五.(10分)设Z是整数集合,X={(a,b)|a,b € Z},定义X上的二元运算①和。 如下:对任意(ab) ,(a 2,b2)€ X,有: (a1b"e (a2,b2)= (a+a?,b1+b2), (a1bJ O (a2,b2)= (ax a2,b 1X b),其中,+,x分别是整数加法与乘法。 证明:(X,?,O)是环,如果此环有零因子请给出它们 离散数学》双语课程教学大纲 一、课程编号:040510 二、课程类型:必修 课程学时:理论教学 72学时 / 4.5学分。 适用专业:信息与计算科学专业。 先修课程:线性代数、概率论、高等数学等。 后续课程:编译原理、操作系统、数据结构、数据库等。 三、课程性质与任务 《离散数学》是信息与计算科学中基础理论的核心课程。该课程采用双语教学形式,教材是国外原版英语教材。通过本课程的学习,主要培养学生的抽象思维能力、严密的逻辑推理能力、阅读外文科技文献能力和专业英语写作能力。并为学生今后处理离散信息、离散建模、软件开发、计算机硬件系统设计、程序设计的时间和空间复杂度分析等提供理论指导基础,是学生从事信息科学的实际工作必备数学工具。 四、教学主要内容及学时分配 五、教学基本要求 了解离散数学所涵盖的内容及背景思想;理解离散数学组的数学思想和基本概念。掌握离散数学常用的基本方法、手段、技巧,并具备一定的分析论证能力和较强的利用离散数学解决实际问题能力。具体要求有: (1 )理解子集、空集、全集、集合相等、幂集等基本概念;掌握集合的两种表示法。 (2)熟练掌握集合的交、并、差补运算;能通过文氏图理解与掌握集合的有关运算;了解包含排斥定理及其简单应用。 (3)熟练掌握集合运算的基本定律,并能熟练地应用这些定律证明集合恒等式。(4)掌握逻辑代数的基本理论和方法,理解命题﹑复合命题及真值表的概念,熟练掌握逻辑运算符‘非’﹑‘合取’ ﹑‘析取’﹑‘蕴涵’﹑及 ‘存在’﹑‘任意’等量词的定义及使用;理解条件语句的概念;理解等价。掌握一些常见的逻辑推理方法。 (5)熟练掌握乘法原理﹑加法原理﹑排列﹑组合﹑鸽笼原理及递归式,会用组合计数思想的方法计算简单的古典概率问题。 (6)理解序偶与笛卡尔积的概念;理解 n 元组与 n 个集合笛卡尔集的概念。 深刻理解关系的基本概念;掌握二元关系的关系矩阵与关系图。熟练掌握关系的自反性、对称性、反对称性和传递性四种性质并熟练掌握其求法。 深刻理解二元关系的自反闭包、对称闭包和传递闭包的概念并熟练掌握其求法。熟练掌握等价关系的判定与相关等价类的求法。了解关系的计算机表示﹑关系的运算﹑传递闭包及Warshall算法。 (7)理解映射、满射、单射、双射的概念并熟练掌握其判定方法;了解复合映射与逆映射的概念及求法。 (8)理解有向树,无向树,根数,标定树的定义及性质;掌握极小生成树算法; 了解生成树搜索法。 (9)理解无向图,哈密顿圈及哈密顿路,传输网络,匹配问题,图的着色的定义及性质;掌握欧拉环游及欧拉通路,最大流问题的定义﹑性质及算法。 掌握有关哈密顿图的一些必要和充分条件。 六、对学生课外作业的要求 本课程概念多、比较抽象、定理证明和应用有一定难度,为了学生进一步理解课堂教学内容,拟布置一定数量的课外习题为宜,教师批改作业本的 2/3, 并安排时间上习题课。各章节习题量分布如下: 七、教材及主要参考书 本科高等数学离散数学试题及答案 一、填空题 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变成完全图。 离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】 一、填空题 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=(PQ)∧R,则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB= _________________________;AB=_________________________;A-B=_____________________. 7.设R是集合A上的等价关系,则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G=(P(QR)),则使公式G为真的解释有 __________________________, _____________________________,__________________________. 9.设集合A={1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则 《离散数学》+答案 一、选择或填空: 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 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=__{3}__________________; ρ(A) - ρ(B)=___________________{3},{1,3},{2,3},{123}______ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _____2^(n^2)_____________________. 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)}, R2= {(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变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除,写成与之对应的命题公 离散数学辅助教材 概念分析结构思想与推理证明 第一部分 集合论 刘国荣 交大电信学院计算机系 离散数学习题解答 习题一(第一章集合) 1. 列出下述集合的全部元素: 1)A={x | x ∈N∧x是偶数∧x<15} 2)B={x|x∈N∧4+x=3} 3)C={x|x是十进制的数字} [解] 1)A={2,4,6,8,10,12,14} 2)B=? 3)C={0,1,2,3,4,5,6,7,8,9} 2. 用谓词法表示下列集合: 1){奇整数集合} 2){小于7的非负整数集合} 3){3,5,7,11,13,17,19,23,29} [解] 1){n n∈I∧(?m∈I)(n=2m+1)}; 2){n n∈I∧n≥0∧n<7}; 3){p p∈N∧p>2∧p<30∧?(?d∈N)(d≠1∧d≠p∧(?k∈N)(p=k?d))}。 3. 确定下列各命题的真假性: 1)??? 2)?∈? 3)??{?} 4)?∈{?} 5){a,b}?{a,b,c,{a,b,c}} 6){a,b}∈(a,b,c,{a,b,c}) 7){a,b}?{a,b,{{a,b,}}} 8){a,b}∈{a,b,{{a,b,}}} [解]1)真。因为空集是任意集合的子集; 2)假。因为空集不含任何元素; 3)真。因为空集是任意集合的子集; 4)真。因为?是集合{?}的元素; 5)真。因为{a,b}是集合{a,b,c,{a,b,c}}的子集; 6)假。因为{a,b}不是集合{a,b,c,{a,b,c}}的元素; 7)真。因为{a,b}是集合{a,b,{{a,b}}}的子集; 8)假。因为{a,b}不是集合{a,b,{{a,b}}}的元素。 4. 对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B∈C,则A∈C。 2)如果A∈B∧B∈C,则A∈C。 3)如果A?B∧B∈C,则A∈C。 [解] 1)假。例如A={a},B={a,b},C={{a},{b}},从而A∈B∧B∈C但A∈C。 2)假。例如A={a},B={a,{a}},C={{a},{{a}}},从而A∈B∧B∈C,但、A ∈C。 3)假。例如A={a},B={a,b},C={{a},a,b},从而ACB∧B∈.C,但A∈C。5.对任意集合A,B,C,确定下列命题的真假性: 1)如果A∈B∧B?C,则A∈C。 2)如果A∈B∧B?C,则A?C。 3)如果A?B∧B∈C,则A∈C。 3)如果A?B∧B∈C,则A?C。 [解] 1)真。因为B?C??x(x∈B?x∈C),因此A∈B?A∈C。 2)假。例如A={a},B={{a},{b}},C={{a},{b},{c}}从而A∈B∧B?C,但A?C。 3)假。例如A={a},B={{a,b}},C={{a,{a,b}},从而A?B∧B∈C,但A?C。 4)假。例如A={a},B={{a,b}},C={{a,b},b},从而A?B∧B∈C,但A?C。6.求下列集合的幂集: 1){a,b,c} 2){a,{b,c}} 3){?} 4){?,{?}} 5){{a,b},{a,a,b},{a,b,a,b}} [解] 1){?,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} 2){,{a},{{b,c}},{a,{a,b}}} 3){?,{?}} 4){?,{?},{{?}},{?,{?}}} 5){?,{{a,b}}} 7.给定自然数集合N的下列子集: 常熟理工学院20 ~20 学年第学期 《离散数学》考试试卷(试卷库01卷) 试题总分: 100 分考试时限:120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题(每题2分,共20分) 1.下列表达式正确的有( ) (A)(B)(C)(D) 2.设P:2×2=5,Q:雪是黑的,R:2×4=8,S:太阳从东方升起,下列( )命题的真值为 真。 (A)(B)(C)(D) 3.集合A={1,2,…,10}上的关系R={ 1.n个命题变元组成的命题公式共有种不同的等价公式。 2.设〈L,≤〉为有界格,a为L中任意元素,如果存在元素b∈L,使,则称b是a 的补元。 3.设*,Δ是定义在集合A上的两个可交换二元运算,如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4.设T是一棵树,则T是一个连通且的图。 5.一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6.量词否定等价式? ("x)P(x) ?,? ($x)P(x) ?。 7.二叉树有5个度为2的结点,则它的叶子结点数为。 8.设 第一章 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规则 第五章 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸,将答题过程手工书写,并拍照上传. 一、填空题 1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是15 . 2.设给定图G(如右由图所示),则图G的点割集是 { f },{ e,c} . 3.设G是一个图,结点集合为V,边集合为E,则 G的结点度数之和等于边数的两倍. 4.无向图G存在欧拉回路,当且仅当G连通且不含奇数度结 点. 5.设G= 8.结点数v与边数e满足e=v - 1 关系的无向连通图就是树. 9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树. 10.设正则5叉树的树叶数为17,则分支数为i = 4 . 二、判断说明题(判断下列各题,并说明理由.) 1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路. 答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。” 2.如下图所示的图G存在一条欧拉回路. 答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。 3.如下图所示的图G不是欧拉图而是汉密尔顿图. 请判断下列各题的正确性。 ⑴2A∩2B=2A∩B。 ⑵A\B=A当且仅当B=。 ⑶(A′C)\(B′D)=(A\B)′(C\D)。 ⑷设|A|=5,则A上恰有31个不同的等价关系。 ⑸设R非空集合A上的关系,R是A上可传递的,当且仅当R○RíR。 ⑹若R1,R2均为非空集合A上的等价关系,那么R1○ R2也为A上的等价关系。 ⑺设 为半序集,1SíP,若S有上界,则S必有上确界。 ⑻设N为自然数集合,I为整数集合,′是算术乘法,则 图2 题1(15)图 2 (8分) 设(G,*)为循环群,生成元为a,设(A,*)和(B,*)均为(G,*)的子群,而ai和aj分别为(A,*)和(B, *)的生成元。 ①证明(A∩B,*)是(G,*)的子群。 ②请问:(A∩B)是否为循环群。如果是,请给出其生成元。 3 (10分) 设(A,,)是环,AA={f |f是A到A的函数}。定义AA上的运算à和*如下,设f,gAA, 对于任意的xA。 (fàg)(x)=f(x)g(x); (f*g)(x)=f(x)g(x); 证明:(AA,à,*)是环。 4 (6分) 设A= 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不? (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不? B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 离散数学课后答案 习题一 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 《离散数学》双语专业词汇表 set:集合subset:子集 element, member:成员,元素well-defined:良定,完全确定brace:花括号representation:表示 sensible:有意义的rational number:有理数 empty set:空集Venn diagram:文氏图 contain(in):包含(于)universal set:全集 finite (infinite) set:有限(无限)集cardinality:基数,势 power set:幂集operation on sets:集合运算 disjoint sets:不相交集intersection:交 union:并complement of B with respect to A:A与B的差集symmetric difference:对称差commutative:可交换的associative:可结合的distributive:可分配的idempotent:等幂的de Morgan’s laws:德摩根律 inclusion-exclusion principle:容斥原理sequence:序列 subscript:下标recursive:递归 explicit:显式的string:串,字符串 set corresponding to a sequence:对应于序列的集合 linear array(list):线性表characteristic function:特征函数countable(uncountable):可数(不可数)alphabet:字母表 word:词empty sequence(string):空串 catenation:合并,拼接regular expression:正则表达式division:除法multiple:倍数prime:素(数) algorithm:算法common divisor:公因子 GCD(greatest common divisor):最大公因子 LCM(least common multiple):最小公倍数 Euclidian algorithm:欧几里得算法,辗转相除法 pseudocode:伪码(拟码)matrix:矩阵square matrix:方阵 row:行column:列 entry(element):元素diagonal matrix:对角阵 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={离散数学期末考试试卷(A卷)
吉林大学离散数学精品试卷
离散数学》双语课程教学大纲
大学本科高等数学《离散数学》试题及答案
离散数学试题及答案精选版
《离散数学》及答案
太原理工大学离散数学试题
离散数学(西安交大版)习题解第一部分(集合论部分)
离散数学题库
中的幺元是,α的逆元是。 10.设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>} = 。 = 。 三、判断题(每题1分,共10分) 1.命题公式是一个矛盾式。() 2.,若,则必有。() 3.设S为集合X上的二元关系,则S是传递的当且仅当(S S)S。() 4.任何一棵二叉树的结点可对应一个前缀码。() 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。() 6.一个有限平面图,面的次数之和等于该图的边数。() 7.A′B = B′A () 8.设*定义在集合A上的一个二元运算,如果A中有关于运算*的左零元θl和右零θr,则A中 有零元。() 9.一个循环群的生成元不是唯一的。() 10.任何一个前缀码都对应一棵二叉树。() 四、解答题(5小题,共30分) 1.(5分)什么是欧拉路?如何用欧拉路判定一个图G是否可一笔画出? 2.(8分)求公式 (P∨Q)R 的主析取范式和主合取范式。离散数学作业答案
2018国家开放大学离散数学本形考任务答案
西安交大离散数学复试题
离散数学题库及答案
离散数学课后答案
离散数学双语专业词汇表
大学离散数学期末重点知识点总结(考试专用)