《离散数学》复习纲要A
一、单项选择题
A1.任意两个不同小项的合取式为( )。
A.永假式
B.永真式
C.可满足式
D.重言式
A2.设{}{}
,,4,A B B A =?=?=I 则( )。
A.?
B.E
C.B
D.{4}
D3.将命题“若m 是奇数,则2m 是偶数”符号化为( ),设O():x x 是奇数,E():x x 是 偶数。
A.O(m)(2)E m U
B.O(m)(2)E m ?→
C.O(m)(2)E m I
D.O(m)(2)E m → C4.命题“小张不是跳高运动员”,可以符号化为( )。设():M x x 是跳高运动员;C:小张。
A.()M c
B.()M x ?
C.()M c ?
D.()M x
D5.在公式()(()(,))()(,)x P z Q x z z R x z ?→∧?中,z ?的辖域是( )。
A.()P z
B.(,)Q x z
C.()(,)P z Q x z →
D.(,)R x z
C6.给定{}1,3,1,4,2,3
,1,2,3,4,2,4,3,4A A R R ????
==?????
?
上的关系为,则R 满足的性质是( )。 A.自反的 B.对称的
C.传递的
D.不可传递的
C7.下列各式中判断自由变元和约束变元不正确的是( )。
A.()()()()()()()()x
P x R x S x x P x Q x ?∨∧→?∧,其中x 是约束出现
B.()()()(
)
x Q x P x R y ?→∧,其中x 是约束出现,而y 是自由出现 C.()()(
)
()x y P x Q x S y ???→∧, 其中x 和y 都是约束出现 D.()()(
)
,x P x yR x y ?∧?, 其中x 和y 都是约束出现 C8.设{}A φ=,则()P A =( )。
A.φ
B.{}φ
C.
{}{},φφ
D.
{}{}φ
D9.集合{a,b,c }到集合{0,1}可定义的特征函数的个数为( )。
A.3
B.6
C.8
D.9
D10.整数集合Z 上的关系≠的传递闭包是关系( )。
A.<
B.>
C.全域关系
z
U
D.≠ A11.三阶群中不同构的有( )个。
A.1
B.2
C.3
D.4
B12.设{}
G=23,m n m n I ?∈,*为普通乘法,则代数系统,*G 的幺元为( )。 A.不存在 B.00
23e =? C.23e =?
D.1
1
23e --=?
A13.任意具有多个等幂元的半群,它( )。
A.不能构成群
B.不一定能构成群
C.不能构成交换群
D.能构成交换群 B14.5个结点7条边的简单图共有( )种。
A.2
B.3
C.5
D.7
D15.具有如下定义的代数系统,*G ,( )不构成群。
A.G={1,10},*是模11乘
B.G={1,3,4,5,9},*同是模11乘
C.G=Q(有理数),*是普通加法
D.G=Q(有理数),*是普通乘法
B16.设,V N =+,其中N 为自然数集合,+为普通加法,令():,2N N x x ??→=,下面四个命题为真的是( )。
A.?是满同态
B.?是单自同态
C.?是自同构
D.?是V 到自身的映射,但A,B,C 都不是
D17.n 个结点的无向完全图K n 的边数为( )。
A.()1n n +
B.()12
n n +
C.()1n n -
D.
()
12
n n - A18.在自然数集合N 上,下列哪种运算是可结合的?( ) A.()max ,x y x y *= B.2x y x y *=+ C.2
2
x y x y *=+
D.x y x y *=- D19.n 阶有向完全图的边数为( )。
A.n
B.()1n n -
C.1n -
D.
()
12
n n -
B20.一棵树有2个4度顶点,3个3度顶点,其余是树叶,则该树中树叶的个数是( )。A.8 B. 9 C.10
D. 11
C21.设无向图G 中有12条边,已知G 中3度结点有6个,其余结点的度数均小于3,则G 中结点数至少是( )。
A.6
B.8
C.9
D.12 B22.简单图的最大度( )结点数。
A.大于
B.小于
C.等于
D. 以上三个都不对
B23.含5个结点,4条边的无向连通图(不同构)有( )个。
A.1
B.3
C.6
D.7 C24.下面图中( )是根树。
A.}{}1,,,,,,,G a b c d a a a b c d =
B.}{}2,,,,,,,G a b c d a b
b d
c d = C.{}{}3,,,,,,,G a b c d a b
a d
c a = D.}{}4,,,,,,,G a b c
d a b a c
d d =
D25.前提(),,W Q Q R R ?∧??∨?的结论是( )。
A.Q ?
B.R ?
C.W
D.W ?
二、判断题(正确填“T ”,错误填“F ”) 1.任何群G 都至少有两个平凡子群。 ( ) 2.任何无向树都是二部图。
( )
3.设12,,,n p p p K 是不同的命题变元,关于12,,,n p p p K 的极大项是简单析取式,但简单析取式不一定是极大项。
( ) 4.设A,B 为任意集合,则A B A ?I 。
( ) 5.设A,B,C,D 都是集合,如果,A B C D A C B D ?????则有和。 ( ) 6.一阶逻辑公式()()()
,x F x G x y ?→是闭式。 ( ) 7.{}{}{}x x x x ∈→∈
。
( ) 8.若A,B 为任意集合,则A B B A ?=?。 ( ) 9.A,B 是集合,A B φ⊕=,当且仅当A=B 。
( ) 10.任何平面图G 的对偶图G *
都是连通平面图。
( )
三、填空题
1.若一个元素既是___因子,又是___因子,则称它为零因子。 2.若群G 中,只含有一个元素,即,1G e G ==,则称G 为___。 3.原子Q 既可说成是___范式,也可说成是___范式。 4.公式()()()x R x Q y ?→中,x 是___出现,y 是___出现。
5.如果把可达性看成是有向图结点集上的一个二元关系,那么它具有___和传递性性质。 6.设,*G 是群,若运算*在G 上满足交换律,则称G 为___群或___群。
《离散数学》复习纲要A答案一、单项选择题
三、填空题
1、左零右零
2、平凡群
3、合取析取
4、约束自由
5、自反性
6、交换 Abel
离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档. 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、公式翻译题 1.请将语句“小王去上课,小李也去上课.”翻译成命题公式. 设P:小王去上课 Q:小李去上课 则:命题公式P∧Q 2.请将语句“他去旅游,仅当他有时间.”翻译成命题公式. 设P:他去旅游 Q:他有时间 则命题公式为P→Q
3.请将语句“有人不去工作”翻译成谓词公式. 设A(x):x是人 B(x):去工作 则谓词公式为?x(A(x)∧-B(x)) 4.请将语句“所有人都努力学习.”翻译成谓词公式. 设A(x): x是人 B(x):努力学习 则谓词公式为?x(A(x)∧B(x)) 二、计算题 1.设A={{1},{2},1,2},B={1,2,{1,2}},试计算 (1)(A-B);(2)(A∩B);(3)A×B. 解: (1)(A-B)={{1},{2}} (2)(A∩B)={1,2} (3)A×B= {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2.设A={1,2,3,4,5},R={
离散数学试题(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 ={,,,,,,,,
2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元,其中第三单元的名称是(A ). 选择一项: A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合,其中第2章关系与函数中的第3个知识点的名称是(D ). 选择一项: A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中,VOD点播版块中共有(B)讲. 选择一项: A. 18 B. 20 C. 19
D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业,第3次形成性考核作业的名称是( C).选择一项: A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是:(C). 选择一项: A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是:(D). 选择一项:
A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第(A)个版块. 选择一项: A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下,放有本课程历年考试试卷的栏目名称是:(D ). 选择一项: A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划,学习计划应该包括:课程性质和目标(参考教学大纲)、学习内容、考核方式,以及自己的学习安排,字数要求在100—500字.完成后在下列文本框中提交. 解答:学习计划 学习离散数学任务目标:
试卷二试题与参考答案 一、填空 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、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等 性 ;就是否有对称性 。 6、4阶群必就是 群或 群。 7、下面偏序格就是分配格的就是 。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是 。 * a b c a b c a b c b b c c c b
二、选择 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的补元( ).
2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元,其中第三单元的名称是( A ). 选择一项: , A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 . 答案已保存 满分 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合,其中第2章关系与函数中的第3个知识点的名称是( D ). ) 选择一项: A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 < 题目3 答案已保存 满分 标记题目 题干 ; 本课程所有教学内容的电视视频讲解集中在VOD点播版块中,VOD点播版块中共有(B)讲. 选择一项:
A. 18 B. 20 C. 19 , D. 17 题目4 答案已保存 满分 标记题目 … 题干 本课程安排了7次形成性考核作业,第3次形成性考核作业的名称是(C).选择一项: A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 ~ C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分 " 标记题目 题干 课程学习平台左侧第1个版块名称是:(C). 选择一项: A. 课程导学 … B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 ^ 满分
标记题目 题干 课程学习平台右侧第5个版块名称是:(D). 选择一项: % A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 《 答案已保存 满分 标记题目 题干 “教学活动资料”版块是课程学习平台右侧的第( A )个版块. 、 选择一项: A. 6 B. 7 C. 8 D. 9 @ 题目8 答案已保存 满分 标记题目 题干 ( 课程学习平台中“课程复习”版块下,放有本课程历年考试试卷的栏目名称是:(D ).选择一项:
《离散数学》期末考试题(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.设A 和B 都是命题,则A →B 的真值为假当且仅当 。 A. A 为假,B 为真 B. A 为假,B 为假 C. A 为真,B 为真 D. A 为真,B 为假 2.下列公式中为重言式的是 。 A. P →(P ∨Q ∨R) B. ┐(Q →P)∧P C. (P →Q)→(Q →┐P) D. (P ∧┐P)←→Q 3.设A ={a ,{a}},P(A)表示A 的幂集,下面各式中错误的是 。 A. {a}∈P(A) B. {a}?P(A) C. {{a}}∈P(A) D. {{a}}?P(A) 4.设A ={1,2,3,4,5,6}上的关系为R ={
一、单项选择题(共 10 道试题,共 100 分。) 1. 设集合A = {1, a },则P(A) = ( D ). A. {{1}, {a}} B. { ,{1}, {a}} C. {{1}, {a}, {1, a }} D. { ,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A},则R的性质为(C ). A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A={ a,{a},{1,2}},则下列表述正确的是( C ). A. {a,{a}} A B. {1,2} A C. {a} A D. A 4. 设集合A ={1 , 2, 3}上的函数分别为:f = {<1, 2>,<2, 1>,<3, 3>},g = {<1, 3>,<2, 2>,<3, 2>},h = {<1, 3>,<2, 1>,<3, 1>}, 则h =( A ). A. f?g
C. f?f D. g?g 5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>,<2, 2>,<2, 3>,<4, 4>},S={<1, 1>,<2, 2>,<2, 3>,<3, 2>,<4, 4>},则S是R的( C )闭包. A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1,2},B={1,2,{1,2}},则下列表述正确的是( A ). A. A B,且A B B. B A,且A B C. A B,且A B D. A B,且A B 7. 设集合A={1,2,3,4,5},偏序关系£是A上的整除关系,则偏序集上的元素5是集合A的( C ). A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10,则其幂集的元素个数为( A ).
一.判断题(共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?{,},则R是A上的等价关系。求等价类[a]R、[c]R及商集A/R。 24.求图示带权图中的最小生成树,并计算最小生成树的权。 25.设R*为正实数集,代数系统< R*,+>、< R*,·>、< R*,/>中的运算依次为普通加法、乘法和除法运算。试确定这三个代数系统是否为群?是群者,求其单位元及每个元素的逆元。 四、证明题(共3小题,共20分) 26 (8分)在自然推理系统P中构造下述推理的证明: 前题:p→(q∨r),?s→?q,p∧?s 结论:r 27 (6分)设
离散数学试题(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
(2)P(a) T(1),ES (3)x(P(x)Q(y)∧R(x)) P (4)P(a)Q(y)∧R(a) T(3),US (5)Q(y)∧R(a) T(2)(4),I (6)Q(y) T(5),I (7)R(a) T(5),I (8)P(a)∧R(a) T(2)(7),I (9)x(P(x)∧R(x)) T(8),EG (10)Q(y)∧x(P(x)∧R(x)) T(6)(9),I 四、某班有25名学生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解:A,B,C分别表示会打排球、网球和篮球的学生集合。则|A|=12,|B|=6,|C|=14,|A∩C|=6,|B∩C|=5,|A∩B∩C|=2。 先求|A∩B|。 ∵6=|(A∪C)∩B|=|(A∩B)∪(B∩C)|=|(A∩B)|+|(B∩C)|-|A∩B∩C|=|(A∩B)|+5-2,∴|(A∩B)|=3。 于是|A∪B∪C|=12+6+14-6-5-3+2=20。不会打这三种球的人数25-20=5。五、已知A、B、C是三个集合,证明A-(B∪C)=(A-B)∩(A-C)(10分)。 证明:∵x A-(B∪C) x A∧x(B∪C) xA∧(xB∧x C) (x A∧x B)∧(x A∧xC) x(A-B)∧x(A-C) x(A-B)∩(A-C) ∴A-(B∪C)=(A-B)∩(A-C) 六、已知R、S是N上的关系,其定义如下:R={
全国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={
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸,将答题过程手工书写,并拍照上传. 一、填空题 1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是15 . 2.设给定图G(如右由图所示),则图G的点割集是 { f },{ e,c} . 3.设G是一个图,结点集合为V,边集合为E,则 G的结点度数之和等于边数的两倍. 4.无向图G存在欧拉回路,当且仅当G连通且不含奇数度结 点. 5.设G=
8.结点数v与边数e满足e=v - 1 关系的无向连通图就是树. 9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树. 10.设正则5叉树的树叶数为17,则分支数为i = 4 . 二、判断说明题(判断下列各题,并说明理由.) 1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路. 答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。” 2.如下图所示的图G存在一条欧拉回路. 答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。 3.如下图所示的图G不是欧拉图而是汉密尔顿图.
填空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
全国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
电大离散数学本形考任 务 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次,内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第一次作业,大家要认真及时地完成集合论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸张,将答题过程手工书写,并拍照上传. 一、填空题 1.设集合{1,2,3},{1,2} A B ==,P(A)-P(B )={{3},{1,3},{2,3},{1,2,3}},A B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} . 2.设集合A有10个元素,那么A的幂集合P(A)的元素个数为 1024 .
3.设集合A={0, 1, 2, 3},B={2, 3, 4, 5},R是A到B的二元关系, 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}. 4.设集合A={1, 2, 3, 4 },B={6, 8, 12},A到B的二元关系 R=} x∈ y y > <那么R-1={<6,3>,<8,4>}. x = ∈ 2 , , x , {B A y 5.设集合A={a, b, c, d},A上的二元关系R={, , ,
一、填空 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) =