华侨大学计算机学院09级离散数学(1)试卷B-1

《离散数学》试题及答案一、选择题（每题5分，共25分）1. 下列关系中，哪个是等价关系？（）A. 小于等于（≤）B. 大于等于（≥）C. 整除（|）D. 模2同余（≡）答案：D2. 下列哪个图是完全图？（）A. 无向图B. 有向图C. 简单图D. n阶完全图答案：D3. 设A和B为集合，若A∪B=A，则下列哪个结论成立？（）A. A⊆BB. B⊆AC. A=BD. A∩B=∅答案：B4. 下列哪个命题是永真命题？（）A. (p→q)∧(q→p)B. (p∧q)→(p∨q)C. (p→q)∧(p→¬q)D. (p∧¬q)→(p→q)答案：B5. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的最小生成树的边数是（）。

A. 4B. 5C. 6D. 7答案：B二、填空题（每题5分，共25分）6. 设A={1,2,3,4,5}，B={3,4,5,6,7}，则A∩B=_________。

答案：{3,4,5}7. 设图G的顶点集V={a,b,c,d}，边集E={e1,e2,e3,e4,e5}，其中e1=(a,b)，e2=(a,c)，e3=(b,d)，e4=(c,d)，e5=(d,a)，则G的邻接矩阵为_________。

答案：[0 1 1 0 0; 1 0 0 1 0; 1 0 0 1 0; 0 1 1 0 1;0 0 0 1 0]8. 设p为真命题，q为假命题，则(p∧q)∨(¬p∧¬q)的值为_________。

答案：真9. 设G=(V,E)是一个连通图，其中V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，若G的度数序列为（3,3,3,3,3,3），则G的边数是_________。

答案：1510. 下列命题中，与“若p，则q”互为逆否命题的是_________。

2020-2021《离散数学》期末课程考试试卷B1专业：考试日期： 所需时间：120分钟 总分：100 分 闭卷一、选择题（每小题2分，共20分） 1．下列语句中是命题的只有（ ）A ．1+8==30B ．5x+6==30C ．5y+1<30D ．x mod 20==3。

2．设命题公式G ：)(R Q P ∧→⌝,则使公式G 取真值为1的P ，Q ，R 赋值分别是 ( )1,1,1.0,1,0.1,0,0.0,0,0.D C B A3．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。

A 、A ⊆Φ； B 、{6，7，8}∈A ；C 、{{4，5}}⊂A ；D 、{1，2，3}⊂A 。

4．给定下列序列，（ ）可以构成无向简单图的结点度数序列。

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。

5．给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（ ）。

A 、{<V1,V2>,<V7,V8>}；B 、{<V1,V4>,<V3,V4>}；C 、{<V4,V7>,<V4,V8>}；D 、{<V1,V4>,<V2,V3>}。

6．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。

A 、 P Q →； B 、P Q ∧； C 、P Q ⌝→⌝； D 、P Q ⌝∨．7．集合A 上的关系R 为一个等价关系，当且仅当R 具有（ ）。

A 、自反性、对称性和传递性； B 、自反性、反对称性和传递性； C 、反自反性、对称性和传递性； D 、反自反性、反对称性和传递性 8．设Q 为有理数集，〈Q ，•〉（其中•为普通乘法）不能构成（ ）。

考试时间：2009年7月16日北京化工大学2008——2009学年第二学期《 离散数学（I ） 》期末考试试卷班级： 姓名： 学号： 分数：一、填空题（共20分，每小题2分）1. 设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。

2.设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数），则A ∩B= 。

3. A={1, 2, 3, 4}，则A 上有____个不同的双射函数。

4. 谓词公式)()(x xQ x xP ∃→∀的前束范式为 。

5. 所有极小项的析取式为 。

6. 若集合S 有n 个元素，则其幂集P(S)有 个元素。

7. 设P ：它占据空间，Q ：它有质量，R ：它不断运动，S ：它叫做物质。

命题 “占据空间的，有质量的而且不断运动的叫做物质”的符号化为 。

8. 公式 P ∨⌝(Q ∧⌝S) 的对偶式为 。

9. 设},,{c b a X =，X 上的关系R 的关系矩阵是⎪⎪⎪⎭⎫ ⎝⎛=111011101R M ，则 =R R M。

10. 设有关系R={<1,2>, <2,4>, <3,3>}，则D(R) = 。

二、判断题（共20分，每小题2分，正确的在题号前打√，错误的在题号前打×）1.设R 是集合S 上的一个二元关系，若R 是自反的，则R -1也是自反的。

2.空集是任何集合的真子集S 。

3.设A ,B ,C 是集合，若A ⊆B 、B ⊆C 、C ⊆A ，则A=B=C 。

4.只有双射函数才有反函数。

5.同一个谓词公式，指定的论域不同，其真值也可能不同。

6.若R 不是A 上的对称关系，则R 一定是A 上的反对称关系7.若A ≠φ，则{A}是A 的一个划分。

8. 三个命题变元的极小项~P ∧Q ∧~R 的编码是m =010。

离散数学考试试题（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。

安徽大学计算机学院2010 —20 11 学年第 1 学期《离散数学---数理逻辑部分》测试试卷院/系 计算机 年级 09 专业 计算机科技 姓名 倪晨 学号 E10914029一、填空题（每小题1分，共16分）1、 判断下列公式的类型① (P Q)( P Q R)∨⌝→⌝∧∧是 偶然 式；② (Q P)(P Q)→∧⌝∧是 永假 式； ③ ()P (P Q P →∧→是 永真 式；2、 命题联结词有 否定 、合取 、 析取 、 蕴含 、 等值 。

3、 含有n 个命题变元的主析取范式的个数是 2的2n 个 。

4、 辖域：紧接在量词之后最小的子公式 。

5、 命题公式P 与()()P Q P Q ∧∨∧⌝是 等值 （等值、不等值）。

6、 ()()()(),,,x y P x y Q x y xP x y ∀∀∧∧∃的自由变元是 y 。

7、 已知公式A 含有两个命题变元，且A 的主析取范式为12m m ∨，则它的主合取范式为 ()()P Q P Q ⌝∨⌝∧∨。

8、 假言推理的规则为 如果P 且P →Q 是真 则Q 。

9、 “中国有四大发明” 是（是，不是）命题。

10、 谓词公式()()()(),,,,x Px y tQ t z R x y t ∀∧∃→中量词∃的辖域为 Q(t,z) 。

二、选择题（每小题2分，共20分） 1、 下列语句中哪个是真命题（ C ） （A ）我正在说谎（B ）如果1+2=3，那么雪是黑的 （C ）如果1+2=5，那么雪是黑 （D ）严禁吸烟2、 下面哪个命题公式是重言式（B ） （A ）()()P Q Q P →∧→ （B ）()P Q P ∧→（C ）()()P Q P Q ⌝∨∧⌝⌝∧⌝ （D ）()P Q ⌝∨3、 下列推理不正确的是（A ） （A ）()P Q P Q →∧→ （B ）()P Q P P →∧→ （C ）()P Q P Q ∨∧⌝→ （D ）()P Q Q P →∧→4、 设论述域为整数集，下列公式中哪个的值为真（ B ） （A ）()0x y x y ∀∃+= （B ）()0x y x y ∃∀+= （C ）()0x y x y ∀∀+=（D ）()0x y x y ⌝∃∃+=5、 设个体域为A={a,b},公式()()xP x xS x ∀∧∃在A 上消去量词后应为（ B ） （A ）()()P x S x ∧（B ）()()()()()P a P b S a S b ∧∧∨ （C ）()()P a P b ∧（D ）()()()()P a P b S a S b ∧∧∨6、 设P ：我去镇上，Q ：我有时间。

离散数学一、填空题(本大题共48分，共16小题，每小题3分)1.--公式为之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定2.无向图G具有是生成树，当且仅当的，若G为(n,m)连通图，要确定G的一棵生成树必删掉G的条边。

3.一个无向图的欧拉回路要求经过图中一次且仅一次，汉密顿图要求经过图中一次且仅一次。

4.设P：我生病，Q：我去学校(1)命题“我虽然生病但我仍去学校”符号化为o (2)命题“只有生病的时候，我才不去学校”符号化为o (3)命题"如果我生病，那么我不去学校”符号化为o5.设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数6.若HlAH2A-AHn是 ,则称Hl, H2, -Hn是相容的，若HlAH2A-AHn是 ,则称H1.H2, -Hn是不相容的7.设f,g,h 是N 到N上的函数(N 为自然数集合),f(n)=n+l;g(n)=2n;h(n)=0；贝lj(fdg)oh=8.K5的点连通度为 ,边连通度为o9.A={1, 2, 3, 4, 5, 6, 8, 10, 24, 36}, R 是A 上的整除关系。

子B={1, 2, 3, 4},那么B的上界是； B的下界是；：6的上确界是; B的下确界为10.命题公式P-*QAR的对偶式为11.设入={1, {2}, <t>},则A的幕集有元素个。

12.设A={0, 1,2, 3}, B={4,6, 7}, C={8, 9, 12, 14}, R1 是由A 到B 的关系,R2 是由B到C原关系，分别定义为Rl={<2, 6>, <3, 4>, <0, 7>} ;R2={<4, 8>, <4, 12>, <6, 12>,〈7, 14〉},则复合关系RloR2 为：13.设A= {<i)}, B={<t>, (<!>}},贝i]P(A) nP(B)= 。

离散数学考试题(后附详细答案)一、命题符号化(共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.二、简答题(共6道题，共32分)1. 求命题公式(P T(Q T R)).r(R T(Q T P))的主析取范式、主合取范式，并写出所有成真赋值。

(5分)2. 设个体域为{1,2,3}，求下列命题的真值(4分)a) -x y(x+y=4)b) y -x (x+y=4)3. 求-x(F(x) T G(x)) T ( xF(x) T-I X G(X))的前束范式。

(4 分)4. 判断下面命题的真假，并说明原因。

(每小题2分，共4分)a) (A _.B)—C=(A-B) (A-C)b) 若f是从集合A到集合B的入射函数，则|A| < |B|5. 设A是有穷集，|A|=5，问(每小题2分，共4分)a) A上有多少种不同的等价关系？b) 从A到A的不同双射函数有多少个？6. 设有偏序集<A, < >，其哈斯图如图1,求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)7. 已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数K IS;P(S);N,N ；P(N);R,R X R,{o,1}(写出即可)(6 分)三、证明题(共3小题，共计40分)1. 使用构造性证明，证明下面推理的有效性。

(每小题5分，共10分)a) A T (B A C),(E T—F) T—C, B T (A A ~S)二B T Eb) -x(P(x) T—Q(x)), -x(Q(x) V R(x)) , x—R(x)二x~P(x)2. 设R1是A上的等价关系，R2是B上的等价关系，A工._且B =_,关系R满足：<<X1,y1>,<X2,y2>>€ R，当且仅当< x 1, X2> € R1 且<y 1,y2> € R2。

离散数学参考答案及评分标准(B)09级计算机学院各专业 2011年1月 一、判断题（每小题2分，共10分）判断下面论述是否正确，并在括号内填“对”或“错”。

1、设R 和S 是集合A 上的关系，若R 和S 是自反的，则R ￮S 也是自反的。

（ 对）2、公式p →(q →r ) 与(p ∧q )→r 等值。

（ 对 ）3、集合{Z n n∈|2}关于普通加法运算能构成半群。

（ 对） 4、无向完全图是每对顶点之间都有一条边的无向图。

（ 错） 5、公式(∀x )(∃y )P (x , y )与公式(∃ y )(∀ x )P (x , y ) 等值 。

（ 错） 二、填空题（每小题2分，共10分）1、设R ={<1,2>,<2,3>,<1,4>}，则R -1 = {<2,1>,<3,2>, 4,1>}2、设A ，B 为有限集合，f 是从A 到B 的函数，则：f 是单射的必要条件为|A|≤|B|；3、无向图G 是欧拉图当且仅当G 是连通的且无奇度顶点。

4、设公式A ⇔（p ∧q ）∨r 的主析取范式为m 1 ∨m 3 ∨m 5 ∨ m 6∨m 7，则A 的主合取范式为M 0 ∧ M 2∧ M 45、设Z 4={ 0,1, 2,3}，⊗为模4乘法，即x ⊗y =(xy )mod 4，则<Z 4, ⊗>的运算表为三、 试解下列各题（每小题5分，共20分）1、设集合A ={a ,b ,c }，R 是A 上的二元关系，已知R 的关系矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=110110001R M(1) 写出R 的集合表达式；(2) 画出R 的关系图.；(3) 说明R 具有哪些性质。

解 (1)R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>} (2) R 的关系图(3) R 是自反的，对称的，传递的。

华侨大学计算机学院09级离散数学(1)试卷B班级 学号________ 姓名__________ 成绩一、填空（ 共30分，每小题3分）1、符号化命题，“老张不是中医”： 。

2、若P ，Q ，为二命题，Q P →真值为0 当且仅当 。

3、集合}5{≤x x x 是正整数且有 个元素，它们是 。

4、))(()(x xG x xF ∃⌝∧∀的前束范式为 。

5、集合A={1，2，3，4}上的偏序关系图为：, 则它的Hass 图为 。

6、若关系R 是偏序关系，则R 满足性质 。

7、若集合A 中有n 个元素，则A 中有 个不同的二元关系，其中 个是函数。

8、关系R 是反对称的，当且仅当关系矩阵中 ，在关系图上 。

9、若g 和f 都是满射，则f g 是 ，若g 和f 都是单射，则f g 是 。

10、 集合A={a,b,c}上有 个不同的划分，每一个划分唯一对应一个等价关系，写出其中一个划分 ，其对应的等价关系 ：二、运算题（共50分）1. 设集合A={1,2,4}，B={2,3,4,6,8}，全集U={1,2,3,4,5,6,7,8},求下列集合：（12分）(1) A ⋃ B (2) A ⋂ B (3)A - B(4) A 的补集 (5) A ⊕B (6) ρ(A)2. 通过主合取范式，求出使公式R Q P ∨→⌝⌝)(的值为F 的真值指派（8分）。

3. 设},,,,{54321x x x x x A =，偏序集><R A ,的Hass 图为求 ① A 中最小元与最大元（2分）； ② },,{543x x x 的最大元和最小元，极大元和极小元，上界和上确界，下界和下确界（8分）。

4. 200人中，有150人喜爱游泳或慢跑或同时喜爱二者。

若85人喜爱游泳，60人同时喜爱游泳或慢跑，问有多少人喜爱慢跑？（10分）。

5. 设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}，（1）写出R 的关系矩阵和关系图。