下载文档原格式
离散数学考试试题（A、B卷及答案）离散数学考试试题(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再反用分配律( A∧(P?Q))∨C(A∧(P?Q))→C2) ?(P↑Q)??P↓?Q。
证明:?(P↑Q)??(?(P∧Q))??(?P∨?Q))??P↓?Q。
二、分别用真值表法与公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式,并写出其相应的成真赋值与成假赋值(15分)。
主析取范式与析取范式的区别:主析取范式里每个括号里都必须有全部的变元。
主析取范式可由析取范式经等值演算法算得。
证明:公式法:因为(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)4M使(非P析取Q析取R)为0所赋真值,即100,二进制为4M∧6M∧50m∨1m∨2m∨3m∨7m所以,公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式,其相应的成真赋值为000、001、010、011、111:成假赋值为:100、101、110。
真值表法:0 0 1 0 1 00 1 11 0 0 1 0 1 1 1 0 1 1 1 0111111111111111111为000、001、010、011、111:成假赋值为:100、101、110。
离散数学试题（A 卷答案）一、（10分）求(P ↓Q )→(P ∧⌝(Q ∨⌝R ))的主析取范式 解：(P ↓Q )→(P ∧⌝(Q ∨⌝R ))⇔⌝(⌝( P ∨Q ))∨(P ∧⌝Q ∧R ))⇔(P ∨Q )∨(P ∧⌝Q ∧R ))⇔(P ∨Q ∨P )∧(P ∨Q ∨⌝Q )∧(P ∨Q ∨R ) ⇔(P ∨Q )∧(P ∨Q ∨R )⇔(P ∨Q ∨(R ∧⌝R ))∧(P ∨Q ∨R ) ⇔(P ∨Q ∨R )∧(P ∨Q ∨⌝R )∧(P ∨Q ∨R ) ⇔0M ∧1M⇔2m ∨3m ∨4m ∨5m ∨6m ∨7m二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。
乙说：王教授不是上海人，是苏州人。
丙说：王教授既不是上海人，也不是杭州人。
王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。
试判断王教授是哪里人？解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。
则根据题意应有： 甲：⌝P ∧Q 乙：⌝Q ∧P 丙：⌝Q ∧⌝R王教授只可能是其中一个城市的人或者3个城市都不是。
所以，丙至少说对了一半。
因此，可得甲或乙必有一人全错了。
又因为，若甲全错了，则有⌝Q ∧P ，因此，乙全对。
同理，乙全错则甲全对。
所以丙必是一对一错。
故王教授的话符号化为：((⌝P ∧Q )∧((Q ∧⌝R )∨(⌝Q ∧R )))∨((⌝Q ∧P )∧(⌝Q ∧R ))⇔(⌝P ∧Q ∧Q ∧⌝R )∨(⌝P ∧Q ∧⌝Q ∧R )∨(⌝Q ∧P ∧⌝Q ∧R ) ⇔(⌝P ∧Q ∧⌝R )∨(P ∧⌝Q ∧R ) ⇔⌝P ∧Q ∧⌝R ⇔T因此，王教授是上海人。
三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。
证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。
2020-2021《离散数学》期末课程考试试卷A一、填空题（每空3分，共15分）1．命题公式)(r q p p ∨∨→的类型是 。
2．设p ：我将去镇上。
q ：我有时间。
则命题“我将去镇上，仅当我有时间。
”的符号化形式为 。
3．化简下面集合表达式：)())((C B A C A B -= 。
4．已知一有向图的D 的度序列为（2,3,2,3），出度序列为（1,2,1,1），则D 的入度序列为 。
5．5个顶点的非同构的无向树共有 棵。
二、选择题（单项选择题，每题3分，共30分）1．设命题公式)(p q p ⌝→∧，记作A ，则使A 的真值指派为1的p ，q 的取值是（ ）。
A 、00B 、 01C 、10D 、112．设p ：你努力。
q ：你将失败。
则命题“除非你努力，否则你将失败。
”符号化为（ ）。
A 、p →q B 、q →p C 、┐p →q D 、┐q →p 3．下列公式中不与)(q p ↔⌝等值的是（ ）。
A 、)()(q p q p ∨⌝∧⌝∨B 、)()(q p q p ∧⌝∨⌝∧C 、q p ↔⌝D 、q p ⌝↔4．下面公式正确的是（ ）。
A 、)()())()((x xB x xA x B x A x ∀∨∀⇔∨∀ B 、)()())()((x xB x xA x B x A x ∃∨∃⇔∨∃C 、)())((x xB A x B A x ∃→⇔→∀D 、)()(x A x x xA ⌝∃⇔⌝∃5．下列命题错误的是（ ）。
A 、}},,{,,,{},{c b a c b a b a ⊆ B 、}},{,,,{},{b a c b a b a ∈ C 、}}},{{,,{},{b a b a b a ⊆D 、}}},{{,,{},{b a b a b a ∈6．设R={<x,y>|x,y ∈R ，x-y+2>0且x-y-2<0}，则R 具有的性质是（ ）。
21年4月西工大机考《离散数学》试卷总分:100 得分:100一、单选题 (共 20 道试题,共 40 分)1.下列代数系统中，哪个不构成群？（）A.S={1，10}，*是模11乘法B.S = I，* 是普通减法C.S=Q，*是普通加法D.S=Q，*是普通乘法正确答案:B2. {A.{<imgsrc="https://:8088/fileroot/question/3396cd17-f5b6-4ed4-b2c5-1120f041b33f/7fb275e4-3d9d-48d3-8ac9-a04f45cdc593.jpg">B.{<imgsrc="https://:8088/fileroot/question/3396cd17-f5b6-4ed4-b2c5-1120f041b33f/370d6c12-9c63-43bf-90b6-e4bff553565d.jpg">C.A(x)→BD.{<imgsrc="https://:8088/fileroot/question/3396cd17-f5b6-4ed4-b2c5-1120f041b33f/077b840e-8898-4f33-9305-ba91bb3b7cd7.jpg">正确答案:A3. 设R，S是非空集合A上的等价关系，则R∩S的对称性（）。
A.一定成立B.一定不成立C.不一定成立D.取决于R是否包含S正确答案:A4.下列哪个不是命题（）。
A.明天你去看球赛吗?B.2是奇数而3是偶数C.1+1=2D.今天风力2-3级正确答案:A5. 下列哪个是真命题？（）A.我正在说谎B.严禁吸烟C.如果1+2=3，则雪是黑的D.如果1+2=5，则雪是黑的正确答案:D6.下列命题公式等值的是（）。
A.{<imgsrc="https://:8088/fileroot/question/3915552f-b7a2-4752-8acc-e9afa6cd4af8/75c23c36-265b-441d-85a7-cfb311c16fef.jpg">B.{<imgsrc="https://:8088/fileroot/question/3915552f-b7a2-4752-8acc-e9afa6cd4af8/92126b01-f9d1-41bf-b44d-93b5a0b7fc19.jpg">C.{<imgsrc="https://:8088/fileroot/question/3915552f-b7a2-4752-8acc-e9afa6cd4af8/ca4c13f0-05d7-4ea9-a78a-d1933f9caf07.jpg">D.{<imgsrc="https://:8088/fileroot/question/3915552f-b7a2-4752-8acc-e9afa6cd4af8/172389ca-5e1b-43ff-bc98-1d015e553878.jpg">正确答案:C7.设p：我将去市里，q：我有时间，命题“我将去市里，当我有时间时”符号代为（）。
离散数学考试题目及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，集合B={3,4,5}，则A∩B的元素个数为：A. 0B. 1C. 2D. 3答案：B2. 函数f: X→Y是一个双射，当且仅当：A. f是单射且满射B. f是单射C. f是满射D. f是双射答案：A3. 命题p: "x是偶数"，命题q: "x是3的倍数"，下列逻辑运算中，表示"x是6的倍数"的是：A. p∧qB. p∨qC. ¬p∧¬qD. ¬p∨¬q答案：A4. 有向图G中，若存在从顶点u到顶点v的有向路径，则称顶点u可达顶点v。
若G中任意两个顶点都相互可达，则称G为：A. 强连通图B. 弱连通图C. 无向图D. 有向无环图答案：A5. 在二进制数系统中，下列哪个数的值最大？A. 1010B. 1100C. 1110D. 1101答案：C6. 布尔代数中，逻辑或运算符表示为：A. ∧B. ∨C. ¬D. →答案：B7. 有限自动机中，状态q0是初始状态，状态q1是接受状态。
若存在从q0到q1的ε-转移，则该自动机：A. 仅在输入为空时接受B. 仅在输入非空时接受C. 无论输入为何都接受D. 无法确定是否接受答案：C8. 命题逻辑中，若命题p和q都为真，则p∧q的真值是：A. 真B. 假C. 可能为真，也可能为假D. 无法确定答案：A9. 集合{1,2,3}的子集个数为：A. 4B. 6C. 7D. 8答案：D10. 若关系R在集合A上是自反的，则对于A中的任意元素a，有：A. (a,a)∈RB. (a,a)∉RC. (a,a)是R的自反对D. (a,a)不是R的自反对答案：A二、填空题（每题3分，共15分）1. 集合A={1,2,3}的幂集包含__个元素。
答案：82. 若函数f: X→Y是满射，则对于Y中的任意元素y，至少存在X中的一个元素x，使得f(x)=__。
离散数学考试试题(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}，求x3y (x+y=4)的真值。
解：x3y (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 人至少乘坐过其中的两种。
离散数学试题及答案一、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝_____{3}______________; ρ(A) - ρ(B)＝____{{3}，{1，3}，{2,3},{1,2,3}}__________ .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________.4. 已知命题公式G＝⌝(P→Q)∧R，则G的主析取范式是____P∧⌝Q∧R (m5)____.5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12______，分枝点数为_______3_________.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝______{4}______; A⋃B＝____{1,2,3,4}_________;A－B＝______{1,2}_______ .7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______自反性____________, _________对称性_________, _________传递性_____________.8. 设命题公式G＝⌝(P→(Q∧R))，则使公式G为真的解释有_____（1,0,0）__________，______(1,0,1)________, ________(1,1,0)________.9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1•R2= ___{(1,3),(2,2),(3,1)}____,R2•R1 =_____{(2,4), (3,3), (4,2)}_____, R12=_______{(2,2), (3,3)}_________.10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = ______2^(m*n)___________.11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ ,A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________________{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_________.14. 设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G的前束范式是_____∃y∃x(P(y)→Q(x))________ _____.15.设G是具有8个顶点的树，则G中增加__21___条边才能把G变成完全图。
2020-2021《离散数学》期末课程考试试卷A2专业: 考试日期： 所需时间：120分钟 总分：100分 闭卷 一、选择题（每小题3分，总共30分）1、设P ：我们划船，Q ：我们跑步。
命题“我们不能既划船又跑步”符号化为（ ）A 、Q P ⌝∧⌝B 、Q P ⌝∨⌝C 、)(Q P ↔⌝D 、)(Q P ⌝↔ 2、下列语句中哪个是真命题？（ ）A 、我正在说谎。
B 、严禁吸烟C 、如果1+2=3，那么雪是黑的。
D 、如果1+2=5，那么雪是黑的。
3、命题公式Q Q P P →→∧))((是（ ）A 、矛盾式B 、蕴含式C 、重言式D 、等值式4、谓词公式)())()((x Q y yR x P x →∃∨∀中变元x 是（ ） A 、自由变量 B 、约束变量 C 、既不是自由变量也不是约束变量 D 、既是自由变量也是约束变量5、若个体域为整数域，下列公式中哪个值为真？（ ）A 、)0(=+∃∀y x y xB 、)0(=+∀∃y x x yC 、)0(=+∀∀y x y xD 、)0(=+∃⌝∃y x y x6、设个体域A={a,b},公式)()(x xS x xP ∃∧∀在A 中消去量词应为（ ） A 、)()(x S x P ∧ B 、))()(()()(b S a S b P a P ∨∧∧ C 、)()(b S a P ∧ D 、)()()()(b S a S b P a P ∨∧∧8、设A={{1，2，3}，{4，5}，{6，7，8}}，下列正确的是（ ） A 、1∈A B 、{1，2，3}⊆A C 、{{4，5}}⊂A D 、Φ∈A 9、幂集P （P （P （Φ）））为（ ）A 、{{Φ}，{Φ，{Φ}}}B 、{Φ，{Φ}，{Φ，{Φ}}}C 、{Φ，{Φ}，{Φ，{Φ}}，{{Φ}}}D 、{Φ，{Φ，{Φ}}}10、任意一个具有多个等幂元的半群，它（ ）A 、不能构成群B 、不一定能构成群C 、能构成群D 、不能构成交换群 二、填空题（每小题2分，总共16分）1、对于前提：S Q ⌝→，S ∨R ，R ⌝，Q P ↔⌝，其有效结论为2、谓词公式)()()(y yR x xQ x xP ∃∨∀→∀的前束范式为3、设集合A={x|x <3,x ∈Z},B={x|x=2k,k ∈Z} C={1,2,3,4,5},则 A ⊕（C-B ）=4、某校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，其中只有3人同时参加3种球队，则仅仅参加两种球队的队员为 人 。
《离散数学》考试试卷（试卷库14卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库14卷）试题总分： 100 分考试时限：120 分钟⼀、选择题（每题2分，共20分）1. 下述命题公式中，是重⾔式的为( )（A ）)()(q p q p ∨→∧（B ）q p ∨))()((p q q p →∨→?（C ）q q p ∧→?)(（D ）q q p →?∧)(2. 对任意集合A,B,C,下列结论正确的是（）（A ）若A ?B,B ∈C,则A ?C ；（B ）若A ∈B,BC,则A ?C ；（C ）若A ?B,B ∈C,则A ∈C ；（D ）若A ∈B,B ?C,则A ∈C ； 3. 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系, ,则由R 产⽣的S S ?上⼀个划分共有( )个分块。
（A ）4（B ）5（C ）6（D ）94. 下列偏序集( )能构成格5. 连通图G 是⼀棵树当且仅当G 中( )（A ）有些边是割边（B ）每条边都是割边（C ）所有边都不是割边（D ）图中存在⼀条欧拉路径6. 有n 个结点)3(≥n ，m 条边的连通简单图是平⾯图的必要条件( )（A ） 63-≤n m（B ）63-≤m n （C ）63-≥n m （D ） 63-≥m n7. 设P,Q 的真值为0,R,S 的真值为1,则下⾯命题公式中真值为1的是（）（A ）R →P （B ）Q ∧S （C ）P S （D ）Q ∨R 8. 在图G=中,结点总度数与边数的关系是（）（A ）deg()2||i v E =（B ）deg()||i v E =（C ）deg()2||iv Vv E ∈=∑（D ）deg()||iv Vv E ∈=∑9. 设有33盏灯,拟公⽤⼀个电源,则⾄少需有五插头的接线板数（）（A ）７（B ）８（C ）９（D ）１４ 10. 设集合A 上有四个元素,则A 上的不同的等价关系的个数为（）（A ）11 （B ）14 （C ）17（D ）15⼆、填空题（每题2分，共20分）1. 设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则R= 。
