内容发布更新时间 : 2024/5/17 19:33:42星期一 下面是文章的全部内容请认真阅读。
《离散数学》期末考试试题
一、 填空题（每空2分，合计20分）
1. 设个体域为D?{?2,3,6, }F(x):x?3，G(x):x?0。则在此解释下公式
(?x)(F(x)?G(x))的真值为______。
2. 设p:我是大学生，q:我喜欢数学。命题“我是喜欢数学的大学生”为可符合化
为 。
3. 设A?{1,2,3,4}，B?{2,4,6}，则A?B=________，A?B=________。 4. 合式公式?(Q?P)?P是永______式。
5. 给定集合A?{1,2,3,4,5}，在集合A上定义两种关系：
R?{?1,3?,?3,4?,?2,2?}, S?{?4,2?,?3,1?,?2,3?}， 则R?S?_______________，S?R?_______________。
6. 设e是群G上的幺元，若a?G且a2?e,则a?1=____ , a?2=__________。
7． 公式?(P?Q)?(P??(Q??S))的对偶公式为 。 8. 设A?{2,3,6,12},
是A上的整除关系，则偏序集?A,?的最大元是________，极
小元是_ _。
9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。
?0?1?{v1,v2,v3,v4}，若G的邻接矩阵A???1??1101?011??，100??000?10. 设图G??V,E?, V则deg?(v1)=________, deg?(v4)=____________。
二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。
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(x))??xP(x)??xQ(x)； D、?x(P(x)?Q)??xP(x)?Q。
第 1 页 （共 4 页）
2．谓词公式?x(P(x)??yR(y))?Q(x)中的 x是（ ）。
A、自由变元； B、约束变元；
C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。
．．．
3．集合的以下运算律不成立的是( )。 A．AB?BA B．AB?BA C．A?B?B?A
D．A?B?B?A
4. 公式?x?y(P(x,y)?Q(y,z))??xP(x,y)换名（ ）。 A. ?x?u(P(x,u)?Q(u,z))??xP(x,y) B. ?x?y(P(x,u)?Q(u,z))??xP(x,u) C. ?x?y(P(x,y)?Q(y,z))??xP(x,u) D. ?u?y(P(u,y)?Q(y,z))??uP(u,y)。
5. 设集合A，B是有穷集合，且A?m,B?n，则从A到B有（ ）个不同的双射函数。
A、n ； B、m ； C、n! ； D、m! 。 6．设A?{a,b,c,d}，A上的等价关系
R?{?a,b?,?b,a?,?c,d?,?d,c?}，
则对应于R的A的划分是（ ）
A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}} 7. 设A?{1,2,3,4}，则A上的二元关系有（ ）个。
A． 24
B. 42
C．24?4 D．42?2
8．下面集合（ ）关于减法运算是封闭的。
A、N ； B、{2xx?I} ； C、{2x?1x?I} ； D、{xx是质数}。 9.
设
集
合
X?{0,1，R是X上的二元关系，
R?{?0,0?,?0,2?,?1,2?,?1,3?,?2,0?,?2,1?,?3,3?}，则R的关系矩阵MR是
( )
第 2 页 （共 4 页）
?1?1 A．??0??0?0?1 C. ??0??1010??1?0100?? B.??1001???011??0001?010?? D. 101??110??1?0??0??1010?011?? 100??001?110?011?? 001??010?10． 一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 三、计算题（每题8分 合计40分）
1． 写出命题公式?(p?q)?(?p?q)的真值表。
2． 集合A?{2,3,6,12,24,36}上的偏序关系|为整除关系。设B?{6,12}，
C?{2,3,6}，试画出
下界和下确界。
3. 求命题公式?(P?Q)??(?P?R)的主析取范式。 4.求下图所示的边赋权图的一棵最小生成树。
v1?0v2?0?5. 已知某有向图的邻接矩阵如下：A?v3?1?v4?0001111010??1? 试求：v3到v1的长度为4的有1??1?向路径的条数。
四 证明题（每题10分， 合计20分）
1. 设论域D为全总个体域，谓词G(x)：x是研究生，T(x)：x是推荐免试者，K(x)：x是统
考选拔者。在谓词逻辑中符号化下列各命题，推证结论的有效性。
“所有的研究生或者是推荐免试者或者是统考选拔者；并非所有的研究生都是推荐免试者。结论：有些研究生是统考选拔者。”
2. ?G,*?是一个群, u?G，定义G中的运算“?”为a?b?a*u?1*b，对任意a,b?G，求证：?G,??也是个群。
第 3 页 （共 4 页）