离散数学试题及答案
离散数学考试试题（A卷及答案）
一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？
(1)若A去，则C和D中要去1个人；
(2)B和C不能都去；
(3)若C去，则D留下。
解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：A→C⊕D，?(B ∧C)，C→?D必须同时成立。因此
(A→C⊕D)∧?(B∧C)∧(C→?D)
?(?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∧?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分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。
解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：
?x(S(x)∧W(x))，?x Y(x)?x(S(x)∧Y(x))
下面给出证明：
(1)?x Y(x) P
(2)Y(c) T(1)，ES
(3)?x(S(x)∧W(x)) P
(4)S( c)∧W( c) T(3)，US
(5)S( c) T(4)，I
(6)S( c)∧Y(c) T(2)(5)，I
(7)?x S((x)∧Y(x)) T(6) ，EG
三、（10分）设A、B和C是三个集合，则A?B??(B?A)。
证明：A?B??x(x∈A→x∈B)∧?x(x∈B∧x?A)??x(x?A∨x∈B)∧?x(x∈B∧x?A)
???x (x ∈A ∧x ?B )∧??x (x ?B ∨x ∈A )???x (x ∈A ∧x ?B )∨??x (x ∈A ∨x ?B )
??(?x (x ∈A ∧x ?B )∧?x (x ∈A ∨x ?B ))??(?x (x ∈A ∧x ?B )∧?x (x ∈B →x ∈A ))
??(B ?A )。
四、（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>} R 2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}
R 3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}
R 4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R 2
t (R )＝∞=1i R i ＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，
5>}。
五、（10分）R 是非空集合A 上的二元关系，若R 是对称的，则r (R )和t (R )是对称的。
证明 对任意的x 、y ∈A ，若xr (R )y ，则由r (R )＝R ∪I A 得，xRy 或xI A y 。因R 与I A 对称，所以有yRx 或yI A x ，于是yr (R )x 。所以r (R )是对称的。
下证对任意正整数n ，R n
对称。
因R 对称，则有xR 2y ??z (xRz ∧zRy )??z (zRx ∧yRz )?yR 2x ，所以R 2对称。若n R 对称，则x 1+n R y ??z (x n R z ∧zRy )??z (z n R x ∧yRz )?y 1+n R x ，所以1+n R 对称。因此，对任意正整数n ，n R 对称。 对任意的x 、y ∈A ，若xt (R )y ，则存在m 使得xR m y ，于是有yR m x ，即有yt (R )x 。因此，t (R )是对称的。
六、（10分）若f ：A →B 是双射，则f －1：B →A 是双射。
证明 因为f ：A →B 是双射，则f －1是B 到A 的函数。下证f －1是双射。
对任意x ∈A ，必存在y ∈B 使f (x)＝y ，从而f －1(y )＝x ，所以f －1是满射。
对任意的y 1、y 2∈B ，若f －1(y 1)＝f －1(y 2)＝x ，则f (x)＝y 1，f (x)＝y 2。因为f ：A→B 是函数，则y 1＝y 2。所以f －1是单射。
综上可得，f －1：B →A 是双射。
七、（10分）设是一个半群，如果S 是有限集，则必存在a ∈S ，使得a *a ＝a 。
证明 因为是一个半群，对任意的b ∈S ，由*的封闭性可知，b 2＝b *b ∈S ，b 3＝b 2*b ∈S ，…，b n ∈S ，…。
因为S 是有限集，所以必存在j ＞i ，使得i b ＝j b 。令p ＝j －i ，则j b ＝p b *j b 。所以对q ≥i ，有q b ＝p b *q b 。
因为p ≥1，所以总可找到k ≥1，使得kp ≥i 。对于kp b ∈S ，有kp b ＝p b *kp b ＝p b *(p b *kp b )＝…＝
kp b *kp b 。
令a ＝kp b ，则a ∈S 且a *a ＝a 。
八、（20分）（1）若G 是连通的平面图，且G 的每个面的次数至少为l (l ≥3)，则G 的边数m 与结点数n 有如下关系：
m ≤
2-l l (n －2)。 证明 设G 有r 个面，则2m ＝
∑=r i i f d 1
)(≥lr 。由欧拉公式得，n －m ＋r ＝2。于是， m ≤2-l l (n －2)。 （2）设平面图G ＝
证明 设G *＝
? G ，于是|F |＝|V *|＝|V |，将其代入欧拉公式|V |－|E |＋|F |＝2得，|E |＝2(|V |－1)。
离散数学考试试题（B卷及答案）
一、（10分）证明(P∨Q)∧(P→R)∧(Q→S)S∨R
证明因为S∨R??R→S，所以，即要证(P∨Q)∧(P→R)∧(Q→S)?R→S。
(1)?R附加前提
(2)P→R P
(3)?P T(1)(2)，I
(4)P∨Q P
(5)Q T(3)(4)，I
(6)Q→S P
(7)S T(5)(6)，I
(8)?R→S CP
(9)S∨R T(8)，E
二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。
设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：?x(P(x)→(A(x)∨B(x)))，?x(A(x)→Q(x))，??x(P(x)→Q(x))?x(P(x)∧B(x))。
(1)??x(P(x)→Q(x)) P
(2)??x(?P(x)∨Q(x)) T(1)，E
(3)?x(P(x)∧?Q(x)) T(2)，E
(4)P(a)∧?Q(a) T(3)，ES
(5)P(a) T(4)，I
(6)?Q(a) T(4)，I
(7)?x(P(x)→(A(x)∨B(x)) P
(8)P(a)→(A(a)∨B(a)) T(7)，US
(9)A(a)∨B(a) T(8)(5)，I
(10)?x(A(x)→Q(x)) P
(11)A(a)→Q(a) T(10)，US
(12)?A(a) T(11)(6)，I
(13)B(a) T(12)(9)，I
(14)P(a)∧B(a) T(5)(13)，I
(15)?x(P(x)∧B(x)) T(14)，EG
三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会
打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
解 设A 、B 、C 分别表示会打排球、网球和篮球的学生集合。则：
|A |＝12，|B |＝6，|C |＝14，|A ∩C |＝6，|B ∩C |＝5，|A ∩B ∩C |＝2，|(A ∪C )∩B |＝6。
因为|(A ∪C )∩B |＝(A ∩B )∪(B ∩C )|＝|(A ∩B )|＋|(B ∩C )|－|A ∩B ∩C |＝|(A ∩B )|＋5－2＝6，所以|(A ∩
B )|＝3。于是|A ∪B ∪
C |＝12＋6＋14－6－5－3＋2＝20，||C B A ＝25－20＝5。故，不会打这三种球的共5人。
四、（10分）设A 1、A 2和A 3是全集U 的子集，则形如3
1=i A i '(A i '为A i 或i A )的集合称为由A 1、A 2和
A 3产生的小项。试证由A 1、A 2和A 3所产生的所有非空小项的集合构成全集U 的一个划分。
证明 小项共8个，设有r 个非空小项s 1、s 2、…、s r (r ≤8)。
对任意的a ∈U ，则a ∈A i 或a ∈i A ，两者必有一个成立，取A i '为包含元素a 的A i 或i A ，则a ∈31=i A i '，即有a ∈r i 1= s i ，于是U ?r i 1= s i 。又显然有r i 1= s i ?U ，所以U ＝r
i 1= s i 。
任取两个非空小项s p 和s q ，若s p ≠s q ，则必存在某个A i 和i A 分别出现在s p 和s q 中，于是s p ∩s q ＝?。 综上可知，{s 1，s 2，…，s r }是U 的一个划分。
五、（15分）设R 是A 上的二元关系，则：R 是传递的?R *R ?R 。
证明 (5)若R 是传递的，则
反之，若R *R ?R ，则对任意的x 、y 、z ∈A ，如果xRz 且zRy ，则
六、（15分）若G 为连通平面图，则n －m ＋r ＝2，其中，n 、m 、r 分别为G 的结点数、边数和面数。 证明 对G 的边数m 作归纳法。
当m ＝0时，由于G 是连通图，所以G 为平凡图，此时n ＝1，r ＝1，结论自然成立。
假设对边数小于m 的连通平面图结论成立。下面考虑连通平面图G 的边数为m 的情况。
设e 是G 的一条边，从G 中删去e 后得到的图记为G '，并设其结点数、边数和面数分别为n '、m '和r '。对e 分为下列情况来讨论：
若e 为割边，则G '有两个连通分支G 1和G 2。G i 的结点数、边数和面数分别为n i 、m i 和r i 。显然n 1＋n 2＝n '＝n ，m 1＋m 2＝m '＝m －1，r 1＋r 2＝r '＋1＝r ＋1。由归纳假设有n 1－m 1＋r 1＝2，n 2－m 2＋r 2＝2，从而(n 1＋n 2)－(m 1＋m 2)＋(r 1＋r 2)＝4，n －(m －1)＋(r ＋1)＝4，即n －m ＋r ＝2。
若e 不为割边，则n '＝n ，m '＝m －1，r '＝r －1，由归纳假设有n '－m '＋r '＝2，从而n －(m －1)＋r －1＝2，即n －m ＋r ＝2。
由数学归纳法知，结论成立。
七、（10分）设函数g ：A →B ，f ：B →C ，则：
(1)f g 是A 到C 的函数；
(2)对任意的x∈A，有f g(x)＝f(g(x))。
证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使
对任意的x∈A，若存在y1、y2∈C，使得
综上可知，f g是A到C的函数。
(2)对任意的x∈A，由g：A→B是函数，有
八、（15分）设
证明对于任意a∈G，必有a－1∈G使得a－1*a＝e∈H，所以
若
若
综上可得，R是G中的一个等价关系。
对于任意的b∈[a]R，有
发到哪？给个邮箱啊~~~~~~~一、填空20% （每小题2分）
1．设（N：自然数集，E???+ 正偶数）则。
2．A，B，C表示三个集合，文图中阴影部分的集合表达式为
。
3．设P，Q 的真值为0，R，S的真值为1，则
的真值= 。
4．公式的主合取范式为
。
5．若解释I的论域D仅包含一个元素，则在I下真值为
。
6．设A={1，2，3，4}，A上关系图为
则R2 = 。
7．设A={a，b，c，d}，其上偏序关系R的哈斯图为
则R= 。
8．图的补图为。
9．设A={a，b，c，d} ，A上二元运算如下：
* a b c d
a
b
c
d a b c d
b c d a
c d a b
d a b c
那么代数系统
10．下图所示的偏序集中，是格的为。
二、选择20% （每小题2分）
1、下列是真命题的有（）
A．；B．；
C．；D．。
2、下列集合中相等的有（）
A．{4，3} ；B．{ ，3，4}；C．{4，，3，3}；D．{3，4}。
3、设A={1，2，3}，则A上的二元关系有（）个。
A．23 ；B．32 ；C．；D．。
4、设R，S是集合A上的关系，则下列说法正确的是（）
A．若R，S 是自反的，则是自反的；
B．若R，S 是反自反的，则是反自反的；
C．若R，S 是对称的，则是对称的；
D．若R，S 是传递的，则是传递的。
5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下
则P（A）/ R=（）
A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；
D．{{ }，{2}，{2，3}，{{2，3，4}}，{A}}
6、设A={ ，{1}，{1，3}，{1，2，3}}则A上包含关系“ ”的哈斯图为（）
7、下列函数是双射的为（）
A．f : I E , f (x) = 2x ；B．f : N N N, f (n) =
C．f : R I , f (x) = [x] ；D．f :I N, f (x) = | x | 。
（注：I—整数集，E—偶数集，N—自然数集，R—实数集）
8、图中从v1到v3长度为3 的通路有（）条。
A．0；B．1；C．2；D．3。
9、下图中既不是Eular图，也不是Hamilton图的图是（）
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。
A．1；B．2；C．3；D．4 。
三、证明26%
1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当
< a, b> 和在R中有<.b , c>在R中。（8分）
2、f和g都是群
3、G=
四、逻辑推演16%
用CP规则证明下题（每小题8分）
1、
2、
五、计算18%
1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。（9分）
2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（9分）
试卷一答案：
一、填空20% （每小题2分）
1、{0，1，2，3，4，6}；
2、；
3、1；
4、；
5、1；
6、{<1,1>, <1,3>, <2,2>, <2,4> }；
7、{
9、a ；a , b , c ,d ；a , d , c , d ；10、c;
二、选择20% （每小题2分）
题目 1 2 3 4 5 6 7 8 9 10
答案 C D B、C C A D C A D B A
三、证明26%
1、证：
“ ” 若由R对称性知，由R传递性得
“ ” 若，有任意，因若所以R是对称的。
若，则即R是传递的。
2、证，有，又
★★
★< C , ★> 是< G1 , ★>的子群。
3、证：
①设G有r个面，则，即。而故即得。（8分）
②彼得森图为，这样不成立，
所以彼得森图非平面图。（3分）
二、逻辑推演16%
1、证明：
①P（附加前提）
②T①I
③P
④T②③I
⑤T④I
⑥T⑤I
⑦P
⑧T⑥⑦I
⑨CP
2、证明
①P（附加前提）
②US①
③P
④US③
⑤T②④I
⑥UG⑤
⑦CP
三、计算18%
1、解：
，
，
t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }
2、解：用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图：树权C(T)=23+1+4+9+3+17=57即为总造价。
面给出证明:
(1) Some x is Y(x) P
(2) Y(c) (1) T(1)，ES
(3)Some(S(x)∧W(x)) P
(4)S(c)∧W(c) T(3),US
(5)S(c) T(4),I
(6)S(c)∧Y(c) T(2)(5),I
(7)(Every)S((x)∧Y(x)) T(6),EG
(完整版)离散数学试卷及答案
离散数学试题（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) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（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 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学复习要点
离散数学复习要点第一章命题逻辑 一、典型考查点 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：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
离散数学期末试题
离散数学考试试题（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 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 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 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
【浙江工商大学】《离散数学》期末考试题(B)
《离散数学》期末考试题(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.整环不一定是域. ( )
离散数学知识点整理
离散数学 一、逻辑和证明 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也是可数的。
离散数学期末试卷及答案
一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法
列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(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={
离散数学复习题
《离散数学》复习题 一、单项选择题 1.下列句子是原子命题的是（ A） A. 大熊猫产在我国； B. 2+x=5; C. 小王和小李是学生； D. 别讲话了！ 2. 设p：天下雨，q：我去新华书店，命题“除非天不下雨，我去新华书店”的符号化形式为（ D ） A．p→qＢ．q→pＣ．┐q→pＤ．┐p→q 3. 以下命题不是重言式的有（A ） ?P B. P∨?P A. P∧ C. (P→Q)?(?Q→?P) D. P→P∨Q 4. 以下语句中不是命题的为（B） A．明天我要上门去谢你。Ｂ．谢谢你给了我机会。 Ｃ．如果不说，我就不谢你。Ｄ．除非你做了，我才谢你 5．与(x) M(x) 等价的是 （D） A．(x) M(x) Ｂ．(x) M(x) Ｃ．(x) M(x) Ｄ．(x) M(x) 6. 设P(x)为“x是大学生”，Q(x)为“x满30岁”。命题“所有大学生都不满30岁”写成谓词公式为（ C ） A. ?x(P(x)∧Q(x)) B.? x(P(x)∧Q(x)) ?(P(x)→Q(x)) D.? x(P(x)→Q(x)) 7.公式 (x) (P(x)→(y)R(x, y))中，x的辖域为 （ B ） A．P(x) Ｂ．(P(x)→(y)R(x, y))
Ｃ．P(x)和R(x, y) Ｄ．P(x)→(y) 8．设S={a, b, c},则S的幂集的元素的个数有 （ C ） A．3 Ｂ．6 Ｃ. 8 Ｄ．9 9．以下等式中不正确的是： ( A ) A．A∪(B×C)=(A∪B)×(A∪C) Ｂ．A×(B∪C)=(A×B)∪(A×C) Ｃ．（A∪B)×C=(A×C)∪(A×C) Ｄ(A×B)×C=A×(B×C) 10．设A={1, 2, 3, 4}, A上的等价关系R={<1, 2>, <2, 1>, <3, 4>, <4, 3>}∪I A, 则对应于R的A的划分是 ( D ) A．{{1},{2, 3}, {4}} Ｂ．{{1, 2},{3}, {4}} Ｃ．{{1},{2}, {3}, {4}} Ｄ．{{1,2}, {3, 4}} 11．设函数f：{1，2}→{1}，则f是 ( B ) A．入射B．满射C．双射D．非入射非满射 12．设Z－是负正整数集合，+，－，*，△是普通数的加法、减法和平方运算，则能构成代数系统是 ( B ) A．< Z－, +> Ｂ．< Z－, －> Ｃ．< Z－, *> Ｄ< Z－, △> 13．若他聪明，他用功，则“他虽聪明但不用功”，可符号化为（ B ） A. B. C. D. 14. 若一个代数系统(A，*)满足运算封闭性及结合律，且有幺元，则它是 ( A ) A．独异点B．群C．格D．布尔代数15．设G为无限群，则( C )
离散数学期末试卷A卷及答案
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学试卷及答案
填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论
C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x)
离散数学期末考试试题及答案
离散数学试题(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．对任意集合A 、B 、C ，下述论断正确的是 【 A 】 （A ）若A ∈B ，B ?C ，则 A ∈C （B ）若A ∈B ，B ?C ，则 A ?C （C ）若A ?B ，B ∈C ，则 A ∈C （D ）若A ?B ，B ∈C ，则 A ?C 2．设{} {}a a A ,=，则下列选项错误的是 【 B 】 （A ）{})(A P a ∈ （B ）{})(A P a ? （C ）{}{ })(A P A ∈ （D ）{}{})(A P A ? 3．设{}c b a A ,,=上的关系如下，有传递关系的有 【 D 】 （A ）{}><><><><=a b b a a c c a R ,,,,,,,1 （B ）{}><><=a c c a R ,,,2 （C ）{}><><><><=c b a b c c b a R ,,,,,,,3 （D ）{},,4><=a a R 4．R 是A 上的自反关系，则 【 B 】 （A ）R R R ? （B ）R R R ? （C ）A I R R = （D ）A I R R = 5．4K 中含3条边的不同构生成子图有 【 C 】 （A ）1个 （B ）2个 （C ）3个 （D ）4个 6．设E V G ,=为无向图，V v u ∈,,若v u ,连通，则 【 D 】 （A ）0),(>v u d （B ）0),(=v u d （C ）0),( 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 《离散数学》期末考试试题 一、 填空题（每空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)
《离散数学》期末考试试题