《离散数学》复习题
一、填空题（每小题1分，共10分）
1、P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；
2、一阶逻辑公式()()()()()()x F x G x y F y G y ?→∧??→的类型是_______。
3、设个体域为整数集合，命题()0=+??y x y x 的真值为_______。
4、对于任意两个集合A,B,它们有共同的子集_______。
5、 如果关系R 是传递的，则?R R _______。
6、集合S={α，β，γ，δ}上的二元运算*为
那么，代数系统
8、无向图G 有12条边，6个的3度节点和2个4度节点。此命题的真值为_______。 9、当3≥n 并且n 为奇数时，无向完全图n k 是欧拉图。此命题的真值为_______。 10、 设代数系统,*V =，其中Q 是有理数集合，*表示对Q y x ∈?,有xy y x y x -+=*，则Q 上关于*的幺员（或称单位元）是_______。 二、选择题（每小题1分，共10分）
1．设{},(()),A B A ρρ=?=以下不正确的式子是（ ） A.
{{},}B ??∈ B. {{}}B ?∈ C. B ?? D. {{{{}},}}B ???
2．设E(x)：“x 是偶数”；D （x,y ）：“x 除尽y ”，P(x):“x 是质数”，则公式))),()(()((y x D y E y x P x ∧?→? 正确的翻译是：( )
A 、所有质数都能除尽偶数；
B 、所有不能除尽偶数的数是质数；
C 、对任一质数，都有被它除尽的偶数；
D 、对任一偶数，都有被它除尽的质数。
3．下列论述哪个是错误的？（ ）
A 、任何一个群，均无零元；
B 、任何一个群，其中至少有两个元素是等幂元；
C 、任何一个群，其中的二元运算满足消去律；
D 、群中每个元素的逆元是唯一的。 4．设集合{1,2,3,4},R A =下列关系中是等价关系的是（） A.{}2,2,3,3,1,4,4,11,1,R <><><><>=<> B. {}2,2,3,3,3,2,2,31,1,R <><><><>=<>
C. {}2,2,3,3,4,4,1,2,2,1,3,4,4,31,1,R <><><><><><><>=<>
D. {}2,2,3,3,4,4,1,2,2,3,3,4,1,3,1,41,1,R <><><><><><><><>=<> 5．设{}1,2,3,{1,2},A B ==则下列命题不正确的是( ) A 、B A ? B 、{}1,2,3A B ⊕= C 、A-B={3} D 、A B ≠?
6．下面哪个序集是格？其中｜是整除关系。（ ） A 、（{2,3,4,6,8,12},|）； B 、（{2,3,4,6,8,12,24},|）； C 、（{1,2,3,4,6,8,12,24},|）； D 、（{1,2,3,4,6,8,12},|）。 7．在下列代数系统中，不是群的只有（ ） A.,,Q 其中Q 是有理数，×是通常的乘法运算； B. ,,Q <+>其中Q 是有理数，＋是通常的加法运算； C.全体n 阶实对称矩阵集合，对矩阵的加法运算； D.{}0,R <-?>，其中R 为实数集，×是通常的乘法运算。
8．设无向图G 中有10条边，已知G 中3度结点有4个，其余结点的度均小于3，则G 中的结点数至少是（ ）
A ．6 B.9 C.8 D.7
9．下列既是欧拉图又是哈密尔顿图的是（ ）
10．一棵树有1个4度结点，4个3度结点，其余的结点是树叶，则该树中结点的个数是（）
A.8；
B.15；
C.7 ；
D.13
三、名词解释（每题4分，共20分）
1、等价关系-----
2、命题公式-----
3、强连通图------
4、半群-----
5、格------
四、简答题（每题5分，共30分）
1、设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24}，“≤”为S上整除关系，问：偏序集≤>
<,
S 的Hass图如何？偏序集}
{≤
S 的极小元、最小元、极大元、最大元是什么?
,
2、设解释R如下：D R是实数集，D R中特定元素a=0，D R中特定函数y
)
,
=
(，特定
f-
y
x
x
谓词y
y
x
F
z
f
F
x
f
y
?
?
=的涵义如何？真值如
?
A→
y
x
z
),
:)
,
(，问公式)))
F<
(z
x
y
,
x
(
(
,
)
,
(
(
何？
3、什么是有向图的欧拉路？指出判断一个图中有欧拉路的充分必要条件。
∈}，加法是S上的二元代数运算么？乘法呢？
4、设S={2|n n N
5、判定下列各题的正确与错误：
（1）a{{a}}；
（2）{a}{ a，b，c }；
（3）{ a，b，c }；
（4）{ a，b，c }；
（5）{a，b}{a，b，c，{ a，b，c }}；
（6）{{a}，1，3，4}{{a}，3，4，1}；
（7）{a，b}{a，b，{ a，b }}；
（8）如果A B=B，则A=E。
6、将下列三个命题符号化：
（1）每一个有理数都是实数。
（2）某些实数是有理数。
五、证明题（30分）
1、命题演绎证明：F
∨
?
→
∨,
A→
→
∧
D
F
A
B
E
D
C
2、证明：在6个结点12条边的连通平面简单图中，每个面的面度数都是3。
一、填空题（每空2分，共30分）
(1) 设A 为任意的公式，B 为重言式，则A ∧B 的类型为______________. (2) 无向图G 是欧拉图的充分必要条件是__________________________． (3) (A B )A ________________为假言推理定律．
(4) 在一阶逻辑中将命题符号化时，若没指明个体域，则使用_____________个体域. (5) 若R 既是_________、_____________、______________则称R 是整环；
(6) 设[0,1]和(0,1)分别表示实数集上的闭区间和开区间，则下列命题中为真的是____________________________；
A. {0,1}? (0,1)
B. {0,1}? [0,1]
C. (0,1)?[0,1]
D. [0,1]?Q
E. {0,1}?Z (7) 已知R ?A ?A 且A ={a ,b ,c }，R 的关系矩阵
M (R )=????
??????110110001
则传递闭包t (R )的关系矩阵M (t (R ))=__________________________.；
(8) 设R 为实数集合，f ：R →R , f (x )=x 2-x +2，g ：R →R , g (x )=x -3, 则f ?g (x )=_______； (9) 设Z 为整数集，?a ,b ∈Z , a b = a +b -1, ?a ∈Z , a 的逆元a -1 =____________；
(13) 在完全图K 2k （k ≥2）上至少加___________条边，才能使所得图为欧拉图； (14) 6阶无向连通图至多有____________棵不同构的生成树； (15) 在环中计算=+3
)(b a _______ ___；
二、在自然推理系统P 中，用直接证明法构造下面推理的证明（10分）
前提：(p q ), q →
r , r
结论：p
三、证明题（每题10分共30分）
1.设E ={1,2,...,12}，A ={1,3,5,7,9,11}, B ={2,3,5,7,11}，C ={2,3,6,12}, D ={2,4,8}，计算：A ?B , A ?C , C -(A ?B ), A -B , C -D , B ⊕D.
2. 设18Z 为模18整数加群, 求所有元素的阶.
3．求带权为5,5,6,7,10,15,20,30的最优树T ，并求W (T )．
四、应用题（每题10分共20分）
1. 判断正整数集合Z + 和下面的每个二元运算是否构成代数系统. 如果是，则说明这个运算是否适合交换律、结合律和幂等律，并求出单位元和零元.
a b = max(a ,b ), a ?b = min(a ,b ), a ?b = a b , a ◇b = (a /b )+(b /a )
2. 计算机系张、王、李、赵4位教授下学期要承担他们都熟悉的4门课程：数据结构、操作系统、C 语言和JA V A．
(1) 试讨论学院安排他们授课的方案数；
(2) 在上述各方案中，有多少种是完全不同的方案(即，每位教授所授课程都不相同的方案数)?
五、判断解答（10分）
判断正整数集合Z+ 和下面的每个二元运算是否构成代数系统. 如果是，则说明这个运算是否适合交换律、结合律和幂等律，并求出单位元和零元.
a b = max(a,b), a?b = min(a,b), a?b = a b, a◇b = (a/b)+(b/a)
答案
一、填空
1. 矛盾式
2.
G 连通且无奇度顶点. 3. B 4. 全总
5. 交换环、含幺环、无零因子环
6. B,C,E
7. M (R )
8. x 2-x -1 9. 2-a
10.5
7
11
13
17
19
23
,,,,,,,a a a a a a a a 11. 7, 12.
2
kn 13. k 14.6 15.略
二．略
三. 计算（每题9分共27分）
1.设E ={1,2,...,12}，A ={1,3,5,7,9,11}, B ={2,3,5,7,11}，C ={2,3,6,12}, D ={2,4,8}，计算：A ?B , A ?C , C -(A ?B ), A -B , C -D , B ⊕D.
{1,2,3,5,7,9,11}{3}
(){6,12}{1,9}{3,6,12}{3,4,5,7,8,11}
A B A B C A B A B C D B D ?=?=-?=-=-=⊕=
2. |0| = 1, |9| = 2， |6| = |12| = 3, |3| = |15| = 6,
|2| = |4| = |8| = |10| = |14| = |16| = 9, |1| = |5| = |7| = |11| = |13| = |17| =18 3．求带权为5,5,6,7,10,15,20,30的最优树T ，并求W (T )． 答案W (T )=267
四.判断解答（每题9分共18分）
1. 判断正整数集合Z + 和下面的每个二元运算是否构成代数系统. 如果是，则说明这个运算是否适合交换律、结合律和幂等律，并求出单位元和零元.
a b = max(a ,b ), a ?b = min(a ,b ), a ?b = a b , a ◇b = (a /b )+(b /a )
,, 1.
***运算构成代数系统；和运算满足交换律、结合律与幂等律.运算零元是1，运算单位元是
2. 4！ 4种完全不同的方案。
五、判断解答
判断正整数集合Z + 和下面的每个二元运算是否构成代数系统. 如果是，则说明这个运算是否适合交换律、结合律和幂等律，并求出单位元和零元.
a b = max(a ,b ), a ?b = min(a ,b ), a ?b = a b , a ◇b = (a /b )+(b /a )
,, 1.
***运算构成代数系统；和运算满足交换律、结合律与幂等律.运算零元是1，运算单位元是
一、填空题（每小题1分，共10分）
1、设P(x):x 是偶数；R(x,y):x+y 是偶数，变量x,y 代表整数，则(,),x yR x y ??表示的语义是__________________________________________。
2、设A,B 为非空集合，m A =，n B =，那么从A 到B 的不同函数有______个。
3、设集合{},A a =?，则(){}A ρ??＝ 。
4、对任何一个图G , (),()()G k G G λδ和分别是它的边连通度、点连通度和最小度，则它们之间的关系是__________________。
5、如图所示是偏序关系R 的哈斯图，则集合 {c , d , f}的最小上界是________________________。
6、设
7、无向图G 为欧拉图，当且仅当G 是连通的，且G 中无________________结点． 8、设谓词A(x)的论域是12{,,
,}n a a a ，则12()()()n A a A a A a ∧∧
∧?_____________。
9、如果把可达性看成是有向图结点集一个二元关系，那么它具有___________和________________性质。
10、布尔代数{0,1},,,<∨∧>上的布尔表达式1212(,)E x x x x =∧的合取范式是___________________________。
二、选择题（每小题1分，共10分）
1．下面命题公式（ ）不是重言式。
A 、)(Q P Q ∨→；
B 、P Q P →∧)(；
C 、)()(Q P Q P ∨?∧?∧?；
D 、)()(Q P Q P ∨??→。 2．命题“没有不犯错误的人”符号化为（ ）。
设x x M ：
)(是人，x x P ：)(犯错误。
A 、))()((x P x M x ∧?；
B 、)))()(((x P x M x ?→??；
C 、)))()(((x P x M x ∧??；
D 、)))()(((x P x M x ?∧??。 3．设}{Φ=A ，B = ( (A))，下列各式中哪个是错误的（ ）。
A 、
B ?Φ； B 、B ?Φ}{，
C 、B ∈Φ}}{{；
D 、?ΦΦ}}{,{ (A)。
4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）。
A 、),min(b a b a =*；
B 、b a b a 2+=*；
C 、3++=*b a b a ；
D 、)3(mod ,b a b a =*。 5．设Z 为整数集，下面哪个序偶不够成偏序集（ ）。
A 、)(,小于关系：<>< B 、)(,小于等于关系：≤>≤ C 、)(,于关系：等=>= D 、)(,关系：整除> A 、不能构成群； B 、不一定能构成群； C 、不能构成交换群； D 、能构成交换群。 7．设≤><,A 是一个有界格，它也是有补格，只要满足（ ）。 A 、每个元素都有一个补元； B 、每个元素都至少有一个补元； C 、每个元素都无补元； D 、每个元素都有多个补元。 8．设>=< E V G ,为无向图，23, 7==E V ，则G 一定是（ ） 。 A 、完全图； B 、树； C 、简单图； D 、多重图。 9．给定无向图>= A 、},,,{4341><> B 、},,,{6451><> C 、},,,{8474><> D 、},,,{3221><> 10．有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件（ ）。 A 、63-≥m n ； B 、63-≤m n ； C 、63-≥n m ； D 、63-≤n m 。 三、名词解释（每题4分，共20分） 1、拟序关系------ 2、演绎----- 3、Hamilton 图----- 4、整除------- 5、子群------ 四、简答题（每题5分，共30分） 1、举例说明什么是环？ 2、用等值演算法求下面公式的主析取范式，并求其成真赋值。 R Q P →∨)( 3、集合}4,3,2,1{=A 上的关系 }4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1{><><><><><><><><=R ，写出关 系矩阵R M ，画出关系图并讨论R 的性质。 4、有n 个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少 种药品？ 5、一棵树T 中，有3个2度结点，一个3度结点，其余结点都是树叶。 （1）T 中有几个结点； （2）画出具有上述度数的所有非同构的无向图。 6、下列问题，若成立请证明，若不成立请举出反例： （1） 已知C B C A ∨?∨，问B A ?成立吗？ （2） 已知B A ???，问B A ?成立吗？ 五、证明题（30分） 1、符号化下列各题，并说明结论是否有效（用推理规则）。 凡15的倍数都是3的倍数，凡15的倍数都是5的倍数，所以有些5的倍数是3的倍数。 2、设>∧∨<,,S 是一个分配格，S a ∈，令a x x f ∨=)(，对任意S a ∈，证明：f 是>∧∨<,,S 到自身的格同态映射。 离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（） 离散数学复习要点第一章命题逻辑 一、典型考查点 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：他用功，命题“他虽聪明但不用功”的符号化正确的是（） 离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (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 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分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧()) 下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（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>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。 2016注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．令p : 今天下雪了，q :路滑，r :他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。 A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨? 2.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。 A. (()((),0))x P x L f x ?∧ B. (()((),0))x P x L f x ?→ C. ()((),0)xP x L f x ?∧ D. ()((),0)xP x L f x ?→ 3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。 A ．(()())x F x G x ?∧ B ． (()())x F x G x ??→? C ．(()())x F x G x ??∧ D ． (()())x F x G x ??∧? *4.下列命题公式不是永真式的是（ A ）。 A . ()p q p →→ B . ()p q p →→ C . ()p q p ?∨→ D . ()p q p →∨ 5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。 A. p q ∧ B. ()p q ?∧ C. p q ?∧? D. p q ?∧ 6．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ A ） A ．()(()())?→x R x Q x B ．()(()())?∧x R x Q x C ．()(()())x R x Q x ?∧ D ．(()())x R x Q x ?→ 7. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( C ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 8．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点， 则G 一共有（ C ）个顶点。 离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8. C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D= D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为 离散数学 一、逻辑和证明 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也是可数的。 1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f 2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208] 1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧? 答案： 令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y，都有x+y≥x。 答案： 令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化： 某些人对某些药物过敏。 答案： 令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式： 答案： 15. 证明： 答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明： 前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ? 《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。在x A和x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x 为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 离散数学测试题 一．选择题（10*2） 1.设L (x )：x 是演员，J (y )：y 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老 师”符号化为( ) (A) ),()(y x A x xL →? (B) ))),()(()((y x A y J y x L x ∧?→? (C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧?? 2.令F(x):x 是有理数，G(x):x 是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为 （ ） A.?x(F(x)∧G(x))∧?x(G(x)→?F(x)) B.?x(F(x)→G(x))∧?x(G(x)∧?F(x)) C.?x(F(x)∧G(x))∧?x(G(x)∧?F(x)) D.?x(F(x)→G(x))∧?x(G(x)→?F(x)) 3．设R 是集合A={a,b,c,d}上的二元关系， R={ 离散数学习题参考答案 第一章集合 １.分别用穷举法,描述法写出下列集合 （１）偶数集合 (２)36的正因子集合 (３)自然数中3的倍数 (４)大于１的正奇数 (1)E={?,-6,-4,-2,0,2,4,6,?} ={2 i | i∈I } (2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3) N3= { 3, 6, 9, ```} = { 3n | n∈N } (4) A d= {3, 5, 7, 9, ```} = { 2n+1 | n∈N } ２.确定下列结论正确与否 (１)φ∈φ× (２)φ∈｛φ｝√ (３)φ?φ√ (４)φ?｛φ｝√ (５)φ∈｛ａ｝× (６)φ?｛ａ｝√ (７)｛ａ,ｂ｝∈｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝× (８)｛ａ,ｂ｝?｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝√(９)｛ａ,ｂ｝∈｛ａ,ｂ,｛｛ａ,ｂ｝｝｝× (１０)｛ａ,ｂ｝?｛ａ,ｂ,｛｛ａ,ｂ｝｝｝√ ３.写出下列集合的幂集 (１)｛｛ａ｝｝ {φ, {{ a }}} ( 2 ) φ {φ} (３)｛φ,｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} } (４)｛φ,ａ,｛ａ,ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}, {a, {a b }}, {φ,a,{ a, b }} } (５)Ｐ(Ｐ(φ)) {φ, {φ}, {{φ}}, {φ,{φ}} } ４.对任意集合Ａ,Ｂ,Ｃ,确定下列结论的正确与否(１)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ∈Ｃ√ (２)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ?Ｃ× (３)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ∈Ｃ× (４)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ?Ｃ × ５.对任意集合Ａ,Ｂ,Ｃ,证明 右 分配差差左=--=--)C A ()B A ()C B (A M .D )C B (A )C B (A ) C A ()B A ()C B (A )1(I Y I Y I I I I I Y 右 差分配差左右差的结论差左=--=-------=-)C A ()B A ()C A ()B A () C B (A M . D )C B (A )2)C A ()B A ()C A ()B A ()1()C B (A )1) C A ()B A ()C B (A )2(Y I Y I Y I I I Y I Y Y I 右 交换结合幂等差左=--=-)C A ()B A (,)C B ()A A () C B (A M . D )C B (A ) C A ()B A ()C B (A )3(I I I I I I I I Y I I Y ))B )B (A ())B B ()B A ((,)B )B A (()B )B A ((B )B A (B A B )B A )(4(I I Y I Y I I Y I I Y --⊕=⊕+结合分配对称差差左 右 零一互补==φ-φ-)B A ()B A () A ()U ) B A ((Y Y I I Y 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 《离散数学》综合复习资料参考答案 一、判断题 1．命题逻辑中任何命题公式的主析取范式如果存在一定是唯一的。（） 2．A、B、C是任意集合，如果A?B及B∈C，则A?C。（） 3．整数集是不可数集。（） 4．代数系统 7． 设树T 有17条边，有12片树叶，2个3度结点，求4度结点数。 8． 设A={1,2}，试构成集合P(A)?A 。 9. 设*运算是有理数集Q 上的二元运算，对于任意的a,b ∈Q ，a*b=a+b-a ?b ，问运算*是否可交换、可结合的？ 10.试求下面有向图的强分图、单侧分图和弱分图。 11、将下列命题符号化 （1）他即聪明又用功。（P ∧Q ） （2）仅当你走我才留下。（Q → P ） （3）所有老的国家选手都是运动员。（(?x)(R(x)→Q(x))） （4）某些教练是年老的，但是健壮的。（(?x)(P(x)∧Q(x) ∧R(x))） 12、设A 是一个非空集合，*是A 上的二元运算，对于任意a,b ∈A ，有a*b=b ，判定*运 算是否可结合的、可交换？ 13、试求下面有向图的强分图、单侧分图和弱分图 三、证明题 1． 设 离散数学考试试题(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再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(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) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是 ．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B. 离散数学期末试题及答 案 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的补元( ).(完整word版)离散数学期末练习题带答案
离散数学复习要点
离散数学模拟题一套及答案
2016离散数学练习题 (答案修改)
离散数学期末复习
离散数学知识点整理
离散数学模拟试题讲解
离散数学复习题及答案
离散数学题库及复习资料
离散数学模拟试卷和答案
离散数学考试题
离散数学期末复习试题及答案
离散数学模拟试题及答案
《离散数学》综合复习资料
离散数学考试试题(A、B卷及答案)
离散数学复习题
离散数学期末试题及答案完整版
相关主题
文本预览