《离散数学》期末复习题
一、填空题（每空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是阿贝尔群
10、一个图的哈密尔顿路是。
11、不能再分解的命题称为，至少包含一个联结词的命题称
为。
12、命题是。
13、如果p表示王强是一名大学生，则┐p表示。
14、与一个个体相关联的谓词叫做。
15、量词分两种：和。
16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B
的。
17、集合上的三种特殊元是、
及。
18、设A={a, b}，则ρ(A) 的四个元素分别
是：，，，。
19、代数系统是指由及其上的或
组成的系统。
20、设
足、，并且*1和*2满足，则称
21、集合A={a,b,c,d}，B={b }，则A \ B= 。
22、设A={1, 2}, 则∣A∣= 。
23、在有向图中，结点v的出度deg+(v)表示，入度deg-(v)表示
以。
24、一个图的欧拉回路是。
25、不含回路的连通图是。
26、不与任何结点相邻接的结点称为。
27、推理理论中的四个推理规则
是、、、。
二、判断题（每题2分，共20分）
1、空集是唯一的。
2、对任意的集合A，A包含A。
3、恒等关系不是对称的，也不是反对称的。
4、集合{1,2,3,3}和{1,2,2,3}是同一集合。
5、图G中，与顶点v关联的边数称为点v的度数，记作deg(v)。
6、在实数集上，普通加法和普通乘法不是可结合运算。
7、对于任何一命题公式，都存在与其等价的析取范式和合取范式。
8、设（A,*）是代数系统，a∈A，如果a*a＝a，则称a为（A，*）的等幂元。
9、设f：A→B，g：B→C。若f，g都是双射，则gf不是双射。
10、无向图的邻接矩阵是对称阵。
11、一个集合不可以是另一个集合的元素。
12、映射也可以称为函数，是一种特殊的二元关系。
13、群中每个元素的逆元都不是惟一的。
14、<{0,1,2,3,4},MAX,MIN>是格。
15、树一定是连通图。
16、单位元不是可逆的。
17、一个命题可赋予一个值，称为真值。
18、复合命题是由连结词、标点符号和原子命题复合构成的命题。
19、任何两个重言式的合取或析取不是一个重言式。
20、设f：A→B，g：B→C。若f，g都是满射，则g?f不是满射。
21、集合{1,2,3,3}和{1,2,3}是同一集合。
22、零元是不可逆的。
23、一般的，把与n个个体相关联的谓词叫做一元谓词。
24、“我正在说谎。”不是命题。
25、用A表示“是个大学生”，c表示“张三”，则A(c)：张三是个大学生。
26、设F＝{<3,3>,<6,2>}，则F-1＝{<6,3>,<2,6>}。
27、欧拉图是有欧拉回路的图。
28、设f：A→B，g：B→C。若f，g都是单射，则g?f也是单射。
三、计算题（每题10分，共40分）
1、设A={c,d}, B={0,1,2}，则计算A×B，B×A。
2、A = {a,b,c}，B = {1,2}，计算A×B。
3、A = {a,b,c}，计算A×A。
4、符号化命题“如果2大于3，则2大于4。”。
5、符号化命题“并不是所有的兔子都比所有的乌龟跑得快”。
6、符号化命题“2是素数且是偶数”。
7、设A={a,b,c,d}，R是A的二元关系，定义为：R={
8、设A={1,2,3,4}，R是A的二元关系，定义为：R={<1,1>,<1,2>,<2,1>,<3,2>, <3,1>,<4,3>,<4,2>, <4,1>}，写出A上二元关系R的关系矩阵。
9、设有向图G如下所示，求各个结点的出度、入度和度数。
10、设有向图G如下所示，求各个结点的出度、入度和度数。
11、设无向图G如下所示，求它的邻接矩阵。
12、求命题公式┐ (p∧┐q)的真值表。
13、设<2x+y, 5>=<10, x－3y>，求x，y。
14、R1、R2是从{1, 2, 3, 4, 5}到{2, 4, 6}的关系，若R1＝{<1, 2>, <3, 4>, <5, 6>}，R2={<1, 4>, <2, 6>}，计算domR1，ranR1，fldR1，domR2，ranR2，fldR2。
15、例：设A={1, 2, 3, 4, 5}，B={3, 4, 5}, C={1, 2, 3}，A到B的关系R={
16、集合A={a, b, c}，B={1, 2, 3, 4, 5}，R是A上的关系，S是A到B的关系。R={ c>, 17、A＝{1, 2, 3, 4, 5, 6}，D是整除关系，画出哈斯图并求出最小元、最大元、极小元和极大元。 18、设集合A={a,b,c}，A上的关系R={ 20、分别用三种不同的遍历方式写出对下图中二叉树点的访问次序。 四、证明题（每题10分，共20分） 1、若R 和S 都是非空集A 上的等价关系，证明R ?S 是A 上的等价关系。 2、证明苏格拉底论证：凡人要死。苏格拉底是人，苏格拉底要死。 3、P →Q ，┐Q ∨R ，┐R ，┐S ∨P ?┐S 4、在群 5、设R 和S 是二元关系，证明：(R ?S)-1=R -1?S -1 6、证明：((Q ∧S)→R)∧(S →(P ∨R)) = (S ∧(P →Q))→R. 7、设I 是整数集合，k 是正整数，I 上的关系R ＝{ 8、证明((p →q)→r)? ((┐q ∧p)∨r) 9、证明(P ∨Q) ∧(P →R) ∧(Q →S)?S ∨R 10、证明P → ┐Q ，Q ∨┐R ，R ∧┐S ? ┐P 11、证 (?x)(P(x)∨Q(x)) ?┐(?x)P(x) →(?x)Q(x) 12、证明定理：设 离散数学复习注意事项： 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：他用功，命题“他虽聪明但不用功”的符号化正确的是（） 离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧()) 下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。 离散数学期末复习 一、选择题 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.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 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f 2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) ( 7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f 《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 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) 给我一杯水吧！ 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 离散数学（上）模拟题 1、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数x，总存在y使得xy=1。 c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得 f(a)=b. 2、简答题（共6道题，共32分） 1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范 式，并写出所有成真赋值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) xy(x+y=4) b) yx (x+y=4) 3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （AB）－C=(A-B) (A-C) b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. 设A是有穷集，|A|=5，问（每小题2分，共4分） a) A上有多少种不同的等价关系？ b) 从A到A的不同双射函数有多少个？ 6. 设有偏序集 下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即 可）(6分) 3、证明题（共3小题，共计40分） 1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10 分） a) A→(B∧C),(E→F)→C, B→(A∧S)B→E b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x) 2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R 满足：< 离散数学习题参考答案 第一章集合 １.分别用穷举法,描述法写出下列集合 （１）偶数集合 (２)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 离散数学复习题及答案文件排版存档编号：[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? → ∧ ? ? ? 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 《离散数学》综合复习资料参考答案 一、判断题 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． 设 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 离散数学期末试题及答 案 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的补元( ).(完整word版)离散数学期末练习题带答案
离散数学复习要点
离散数学模拟题一套及答案
离散数学期末复习
离散数学知识点整理
离散数学模拟试题讲解
离散数学模拟题(开卷)
离散数学题库及复习资料
离散数学模拟试卷和答案
离散数学(上)模拟题
离散数学期末复习试题及答案
离散数学复习题及答案
离散数学模拟试题及答案
离散数学模拟试卷和答案
《离散数学》综合复习资料
离散数学考试试题(A、B卷及答案)
离散数学期末试题及答案完整版
相关主题
文本预览