2015年离散数学测试题
离散数学测试题
一、 某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派
法？如何派？
(1)若A去，则C和D中要去1个人；(2) B和C不能都去；(3)若C去，则D留下。
二、 试构造下面推理的证明。
如果小张和小王去看电影，则小李也去看电影；小赵不去看电影或小张去看电影；小王去看电影。所以，当小赵去看电影时，小李也去看电影。
三、 对某单位的100名员工进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜
欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，则只喜欢看电影的有( )。 A.22人 B.28人 C.30人 D.36人
四、 设A、B和C是三个集合，则A?B??(B?A)。
五、 设
（1）画出
（2）求A的所有极大元和极小元
（3）求B={2,3,6}的最小上界和最大下界
六、 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。
七、 设命题公式的主析取范式和主合取范式：?(P→Q)∨(Q∧(?P→R))
八、 推理证明题
(1)(P→(Q→S))∧(?R∨P)∧Q?R→S
(2)C∨D, (C∨D)→?E, ?E→(A∧?B), (A∧?B)→(R∨S)?R∨S
九、 把下列公式化成前束范式。
(1) ?x F(x) →?x G(x) (2) ?x F(x) →?x G(x) (3) (?xP(x)∨?yQ(y))→?xR(x)
十、 设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)。
十一、证明：(1)R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。(2)若f：A→B是双射，则f－1：B→A是双射。
十二、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
十三、设A,B为任意集合，证明：(1) (A－B)－C = A－(B∪C). (2) A－(A∩B) = (A∪B)－B
十四、设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}, S＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出R和S的关系矩阵；(2) 计算R?S, R∪S, R－1, S－1?R－1 .
十五、选择题：
1．若风大，就放飞风筝。若气温高，就不放飞风筝。若天空不晴朗，就不放飞风筝。
假设以上说法正确，若放飞风筝，则以下哪些说法是正确的：（）
A、风大
B、天空晴朗
C、气温高
D、风大和天空晴朗
2．彭平是一个计算机编程专家，姚欣是一位数学家。其实，所有的计算机编程专家都是数学家。我们知道，今天国内大多数综合性大学都在培养着计算机编程专家。据
此，我们可以认为： ( )
A：彭平是由综合性大学所培养的。
B：大多数计算机编程专家是由综合性大学所培养的。
C：姚欣并不是毕业于综合性大学。
D：有些数学家是计算机编程专家
3．派出所民警讯问公共汽车上的一桩盗窃案的嫌疑人甲、乙、丙、丁的笔录如下：甲说：“反正不是我干的” 乙说：“是丁干的。” 丙说：“是乙干的。” 丁说：“乙是诬
陷。” 他们当中只有三人说真话，扒手只有一个，是( )。
A. 甲
B. 乙
C. 丙
D. 丁
4．要从代号为A、B、C、D、E、F六个侦查员中挑选若干人去破案，人选的配备要求必须注意下列各点： ① A、B两人中至少去一人；② A、D不能一起 ；③ A、E、F
三人中要派两人去；④ B、C两人都去或都不去 ；⑤ C、D两人中去一人；⑥ 若D
不去、则E也不去。则( )
A. 挑了A、B、F三人去
B. 挑了A、B、C、F四人去
C. 挑了B、C、E三人去
D. 挑了B、C、D、E四人去
5．莎士比亚在《威尼斯商人》中，写富家少女鲍细娅品貌双全，贵族子弟、公子王孙纷纷向她求婚。鲍细娅按照其父遗嘱，由求婚者猜盒定婚。鲍细娅有金、银、铅
三个盒子，分别刻有三句话，其中只有一个盒子，放有鲍细娅肖像。求婚者通过这
三句话，猜中鲍细娅的肖像放在哪只盒子里，就嫁给谁。三个盒子上刻的三句话分
别是： (1)金盒子：“肖像不在此盒中。” (2)银盒子：“肖像在铅盒中。” (3)铅盒
子：“肖像不在此盒中。鲍西娅告诉求婚者，上述三句话中，最多只有一句话是真
的。鲍西娅的肖像究竟放在哪一个盒子里？（）
A. 金盒子
B. 银盒子
C. 铅盒子
D. 不确定
6．英、红、燕三个人讨论一数学题，当她们都把自己的解法说出来以后，英说：“我做错了。”红说：“英作对了。”燕说：“我做错了。”老师看过他们的答案并听了她
们的上述意见后说：“你们三个人有一个做对了，有一个说对了”。那么，谁做对
了呢？( )
A. 红
B. 英
C. 燕
D. 不能确定。
离散数学试卷及答案(2)
一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为
自考离散数学试题及答案
一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．． 命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．． 谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ） A ．一定是等价关系 B ．一定是相容关系
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
离散数学试卷及答案
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选 项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z， Z是整数集， 定义为x xy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x ??????????????????????精品自学考料推荐?????????????????? 浙江省 2019 年 7 月高等教育自学考试 离散数学试题 课程代码： 02324 一、单项选择题 (在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在 题干的括号内。每小题 1 分，共 14 分 ) 1.给定如下 4 个语句 : (1) 我不会游泳。(2)如果天不下雨,我就去踢足球。 (3) 我每天都看新闻联播。(4)火星上有人吗? 其中不是复合命题的是()。 A.(1)(4) B.(1)(3)(4) C.(1)(3) D.(3)(4) 2.设 P,Q,R 是命题公式 ,则 P→ R， Q→ R， P∨Q ()。 A. P B. Q C. R D. ┐ R 3.下列公式中正确的等价式是()。 A. ┐ ( x)A(x)(x) ┐ A(x) B. ┐ ( x)A(x)(x)┐ A(x) C. ( x)( y)A(x,y)( y)( x)A(x,y) D. ( x)( (x)∧ B(x))( x)A(x) ∨ ( x)B(x) 4.谓词公式 ( x)(P(x) ∨ ( y)R(y)) → Q(x) 中的 x()。 A.只是约束变元 B.只是自由变元 C.既非约束变元又非自由变元 D.既是约束变元又是自由变元 5.设个体域为整数集 ,则下列公式中值为真的是 ()。 A. (y)(x)(x · y=2) B. (x)(y)(x · y=2) C. (x)(x · y=x) D. (x)(y)(x+y=2y) 6.设 A={a,b,c}, 则 A 中的双射共有 ()。 A.3 个 B.6 个 C.8 个 D.9 个 7.设 S={a,b,c}, 则 S 的幂集的元素的个数有()。 A.3 个 B.6 个 C.8 个 D.9 个 8.设 A={a,b,c}, 则 A ×A 中的元素有 ()。 A.3 个 B.6 个 1 《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 离散数学考试试题（A卷及答案） 一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((P→Q)∧Q)?((Q∨R)∧Q) 2)?((Q→P)∨?P)∧(P∨R) 3)((?P∨Q)→R)→((P∧Q)∨R) 解：1)永真式；2）永假式；3)可满足式。 二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。 解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4）） ?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4）） ?（0∨0）∧（0∨1） ?1∧1?0 三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？ 解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。 四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。 解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>} 五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。 解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。 由容斥原理，得 |A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以 |A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。 六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R ∩S=[a]R∩[a]S。 解：?x∈A，因为R和S是自反关系，所以 全国2018年7月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填 在题干的括号内。每小题1分，共14分) 1.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 2.关于命题变元P和Q的大项M01表示( )。 A.┐P∧Q B.┐P∨Q C.P∨┐Q D.P∧┐Q 3.公式(?x)(?y)(P(x,z)→Q(y))S(x,y)中的(?x)的辖域是( )。 A.(?y)(P(x,z)→Q(y)) B.P(x,z)→Q(y) C.P(x,z) D.S(x,z) 4.下列等价式不成立 ．．．的是( )。 A.┐(?x)A(x)?(?x)┐A(x) B.┐(?x)A(x)?(?x)┐A(x) 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.公式(?x)(?y)(P(x,y)∧Q(z))→R(x)中的x( )。 A.只是约束变元 B.只是自由变元 C.既是约束变元又是自由变元 D.既非约束变元又非自由变元 6.设A={a,{a}}，则下列各式正确的是( )。 A.{a}∈p(A)(A的幂集) B.{a}?p(A) C.{{a}}?p(A) D.{a,{a}}?p(A) 7.集合的以下运算律不成立 ．．．的是( )。 A.A∩B=B∩A B.A∪B=B∪A C.A⊕B=B⊕A D.A-B=B-A 8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。 A.入射 B.满射 C.双射 D.非以上三种的一般函数 9.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。 A.交换律 B.结合律 1 全国2009年4月自学考试离散数学试题（附答案） 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q）D．?（? P∨? Q） 4．命题公式（P∧（P→Q））→Q是（） A．矛盾式B．蕴含式 C．重言式D．等价式 5．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 6．在公式（x ?）F（x，y）→（?y）G（x，y）中变元x是（） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={ 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 离散数学考试试题(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 一、单项选择题(本大题共１５小题，每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是．． 命题的是( D ) A.中华人民共和国的首都是北京?B ．张三是学生 C.雪是黑色的? D.太好了! 2．下列式子不是．． 谓词合式公式的是（ Ｂ ) A.(?x ）P (x ）→R (y ） B.（?x ) ┐Ｐ（x ）?(?x )(P (x )→Q （x ）) Ｃ.(?x )(?y )(P (x )∧Q (y ))→（?ｘ)R (x ) D ．(?x )(P (x ，y )→Ｑ(x ，z ))∨(?ｚ）R (ｘ,z ） 3．下列式子为重言式的是( ） A ．（┐P ∧R )→Q ?B.Ｐ∨Q ∧R →┐Ｒ C ．P ∨(P ∧Q ）?D.(┐P ∨Q )?(P →Q ） 4．在指定的解释下，下列公式为真的是（ ) Ａ．(?x )(P （x )∨Q (ｘ)），P (x ）:x =1,Q (x ):x =2,论域:{1,2｝ B ．(?x )(P (x ）∧Q (x ))，P （ｘ):x =1,Ｑ(ｘ)：x =2,论域： {1，2} C ．(?x )(P (x ) →Q (ｘ))，Ｐ(x ):ｘ>2,Q (x )：x =０，论域:{3,4} Ｄ．(?x ）(P （ｘ)→Ｑ(x )）,P (ｘ):ｘ>２,Q （x ):x ＝0，论域：｛3，4} 5.对于公式(?x ) （?y )（Ｐ(x )∧Q (y ))→(?x ）Ｒ(x ,y )，下列说法正确的是（ ) A ．y 是自由变元? B ．y 是约束变元 Ｃ．（?x ）的辖域是R(x , ｙ) D.(?x )的辖域是(?ｙ）(Ｐ(x ）∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2},与公式(?x ）A (x )等价的是( ) Ａ．A (1)∨A (2)?B.A (1)→Ａ(2) C.Ａ(1）∧Ａ(2)?D ．A (2)→A （1) 7．设Z ＋是正整数集,R 是实数集，ｆ:Z ＋ →R , ｆ(n )=lo ｇ2n ,则f ( ） A ．仅是入射? B ．仅是满射 C ．是双射 Ｄ．不是函数 ８.下列关系矩阵所对应的关系具有反对称性的是（ ) Ａ.???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D.???? ??????001010101 9.设R 1和R 2是集合A 上的相容关系,下列关于复合关系R １?R ２的说法正确的是( ) A.一定是等价关系? B.一定是相容关系 全国2018年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是 ．．命题的是（） A．中华人民共和国的首都是北京B．张三是学生 C．雪是黑色的D．太好了！ 2．下列式子不是 ．．谓词合式公式的是（） A．（?x）P(x)→R(y) B．(?x) ┐P（x）?(?x)(P(x)→Q(x)) C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x) D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z) 3．下列式子为重言式的是（） A．(┐P∧R)→Q B．P∨Q∧R→┐R C．P∨(P∧Q) D．(┐P∨Q)?(P→Q) 4．在指定的解释下，下列公式为真的是（） A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(?x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(?x) (?y)(P(x)∧Q(y))→(?x)R(x,y)，下列说法正确的是（） A．y是自由变元B．y是约束变元 C．(?x)的辖域是R(x, y) D．(?x)的辖域是(?y)(P(x)∧Q(y))→(?x)R(x,y) 6．设论域为{1,2}，与公式(?x)A(x)等价的是（） A．A(1)∨A(2) B．A(1)→A(2) C．A(1)∧A(2) D．A(2)→A(1) 7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（） 1 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。 全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 离散数学练习题 1、图中度为零的结点称为孤立结点。 A. 正确 B. 错误 正确：【A】 2、域是整环。 A. 正确 B. 错误 正确：【A】 3、有限格都是有界格。 A. 正确 B. 错误 正确：【A】 4、连通且不含圈的图称为树。 A. 正确 B. 错误 正确：【A】 5、“如果1+1≠3，则2+2≠4”是真命题。 A. 正确 B. 错误 正确：【B】 6、无向图G为欧拉图，则G是连通的。 A. 正确 B. 错误 正确：【A】 7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。 A. 正确 B. 错误 8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。 A. 正确 B. 错误 正确：【A】 9、设〈L，≤〉是格，则格的交∧和并∨运算满足等幂律。 A. 正确 B. 错误 正确：【A】 10、“x+3>1。”是命题。 A. 正确 B. 错误 正确：【B】 11、半群满足交换律。 A. 正确 B. 错误 正确：【B】 12、在任何图中，奇数度的结点数必是偶数。 A. 正确 B. 错误 正确：【A】 13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。 A. 正确 B. 错误 正确：【A】 14、完全图Kn没有割集，它的连通性能是最好的。 A. 正确 B. 错误 15、对任意集合A，都有??A。 A. 正确 B. 错误 正确：【A】 17、强连通图一定是单向连通图。 A. 正确 B. 错误 正确：【A】 18、代数系统〈G，°〉为群的条件是存在零元素。 A. 正确 B. 错误 正确：【B】 19、对应日常生活中的“任意的”，“所有的”，“一切的”等词，用符号“任意”表示。 A. 正确 B. 错误 正确：【A】 20、如果a是集合A中的元素，则称a属于A，记作a?A。 A. 正确 B. 错误 正确：【B】 21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（） A. B. C. D. 正确：【B】 22、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)?f2(x)=0的解 习题参考答案 1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。 阮允准同学提供答案: 解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4 所以度数小于3的结点至少有4个 所以G至少有11个结点 2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。 阮允准同学答案： 证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。 若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。 若度数为5的结点数为6,8个，结论显然成立。 由上可知，G中至少有5个6度点或至少有6个5度点。 3、证明：简单图的最大度小于结点数。 阮同学认为题中应指定是无向简单图. 晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n. 4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。阮同学给出证明如下： 证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。 5、试证明下图中两个图不同构。 晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。 6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示：(晓津与阮同学答案一致)2020年7月全国自考离散数学试题及答案解析试卷及答案解析真题.docx
【浙江工商大学】《离散数学》期末考试题(B)
离散数学考试试题(A卷及答案)
7月全国自考离散数学试题及答案解析试卷及答案解析
自考离散数学02324真题含答案(2009.4-2016.4年整理版)
离散数学期末考试试题及答案
离散数学考试试题(A、B卷及答案)
2010年7月自考离散数学试题及标准答案
7月全国自考离散数学试题及答案解析
离散数学期末考试试题及答案
《离散数学》练习题和参考答案
离散数学及答案
《离散数学》期末考试试题
离散数学练习题
自考离散数学教材课后题第五章答案