离散数学集合论部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。
一、填空题
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的二元关系，
∈
x
∈
R?
<
且
=且
>
y
∈
{B
,
,
x
A
y
A
y
B
x
}
则R的有序对集合为{<2，2>，<2，3>，<3，2>，<3，
3>} ．
4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系
R＝}
y
y
x∈
>
<
=
∈
A
2
,
x
,
,
{B
y
x
那么R－1＝{<6，3>，<8，4>}
5．设集合A=｛a, b, c, d｝，A上的二元关系R={
6．设集合A=｛a, b, c, d｝，A上的二元关系R={
7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．
8．设A={1, 2}上的二元关系为R={
9．设R是集合A上的等价关系，且1 , 2 , 3是A中的元素，则R中至少包
含<1，1>，<2，2>，<3，3> 等元素．10．设集合A={1, 2}，B={a, b}，那么集合A到B的双射函数是{<1，a>，<2，b>}或{<1，b>，<2，a>}
．
二、判断说明题（判断下列各题，并说明理由．）
1．若集合A = {1，2，3}上的二元关系R={<1, 1>，<2, 2>，<1, 2>}，则
(1) R是自反的关系；(2) R是对称的关系．
(1) 错误。R不具有自反的关系，因为<3,3>不属于R。
(2) 错误。R不具有对称的关系，因为<2,1>不属于R。
2．如果R1和R2是A上的自反关系，判断结论：“R-11、R1∪R2、R1∩R2是自反的”是否成立？并说明理由．
解：成立．
因为R1和R2是A上的自反关系，即IA∩R1，IA∩R2。
由逆关系定义和IA∩R1，得IA∩R-11；
由IA∩R1，IA∩R2，得IA∩R1∪R2，IA∩ R1∩R2。
所以，R-11、R1∪R2、R1∩R2是自反的。
3．若偏序集
解：错误．
集合A的最大元不存在，a是极大元
ο
οοο
a
b c
d
图一
ο
ο
ο
g e f
h ο
4．设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，，判断下列关系f是否构成函数f：A→，并说明理由．
B
(1) f={<1, 4>, <2, 2,>, <4, 6>, <1, 8>}；(2)f={<1, 6>, <3, 4>, <2, 2>}；(3) f={<1, 8>, <2, 6>, <3, 4>, <4, 2,>}．
解：
（1）不构成函数。因为对于3属于A，在B中没有元素与之对应。
（2）不构成函数。因为对于4属于A，在B中没有元素与之对应。
（3）构成函数。因为A中任意一个元素都有A中唯一的元素相对应。
三、计算题
1．设}4,2{
=C
=
=
A
E，求：
B
4,1{
},
5,2,1{
},
},
5,4,3,2,1{=
(1) (A?B)?~C；(2) (A?B)-(B?A) (3) P(A)－P(C)；(4) A⊕B．
2．设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}>}
3．设A={1，2，3，4，5}，R={
解：R={<1,1>,<1,2>,<1,3><2,1><2,2><3,1>}
S=空集 R*S=空集 S*R=空集
R-1={<1,1>,<2,1><3,1><1,2><2,2><1,3>}
S-1 =空集
r(S)={<1,1><2,2><3,3><4,4><5,5>}
s(R)={<1,1><1,2><1,3><2,1><2,2><3,1>}
4．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}．
(1) 写出关系R的表示式；(2 )画出关系R的哈斯图；
(3) 求出集合B的最大元、最小元．
(1)R={<1,1><1,2><1,3><1,4><1,5><1,6><1,7><1,8><2,2><2,4><2,6><2,8>
<3,3><3,6><4,4><4,8><5,5><6,6><7,7><8,8>}
（2）
(3)集合B没有最大元，最小元是2
四、证明题
1．试证明集合等式：A? (B?C)=(A?B) ? (A?C)．
证明：设，若x∈A? (B?C)，则x∈A或x∈B?C，
即x∈A或x∈B 且x∈A或x∈C．
即x∈A?B 且x∈A?C ，
即x∈T=(A?B) ? (A?C)，
所以A? (B?C) ∈ (A?B) ? (A?C)．
反之，若x∈(A?B) ? (A?C)，则x∈A?B 且x∈A?C，
即x∈A或x∈B 且x∈A或x∈C，
即x∈A或x∈B?C，
即x∈A? (B?C)，
所以(A?B) ? (A?C) ∈ A? (B?C)．
因此．A? (B?C)=(A? B) ? (A? C)
2．试证明集合等式A? (B?C)=(A?B) ? (A?C)．
设S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，则x∈A且x∈B∪C，即
x∈A且x∈B 或x∈A且x∈C，
也即x∈A∩B 或x∈A∩C ，即x∈T，所以S∈T．
反之，若x∈T，则x∈A∩B 或x∈A∩C，
即x∈A且x∈B 或x∈A且x∈C
也即x∈A且x∈B∪C，即x∈S，所以T∈S．
因此T=S．
3．对任意三个集合A, B和C，试证明：若A?B = A?C，且A≠?，则B = C．（1）对于任意
（2）同理，对于任意
有（1）（2）得B=C
4．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．
若R与S是集合A上的自反关系，则任意x∈A,＜x,x＞∈R,＜x,x＞∈S,
从而＜x,x＞∈R∩S,注意x是A的任意元素，所以R∩S也是集合A上的自反关系．
浙江工业大学期终考试命题稿 2010 /2011 学年第1 学期 命题注意事项： 一、命题稿请用A4纸电脑打印，或用教务处印刷的命题纸，并用黑 墨水书写，保持字迹清晰，页码完整。 二、两份试题必须同等要求，卷面上不要注明A、B字样，由教务处 抽定A、B卷。 三、命题稿必须经学院审核，并在考试前两周交教务处。
浙江工业大学2012/2013 学年 第1学期试卷 课程＿＿＿＿＿＿＿＿ 姓名 ＿＿＿＿＿＿＿＿ 班级＿＿＿＿＿＿＿＿ 学号 ＿＿＿＿＿＿＿＿ 题序 一 二 三 四 五 六 七 八 九 十 总分 计分 一、 1．下列语句是命题的是（ A ）。 A 、离散数学是重要的一门必修课。 B 、1+101=110？ C 、我正在说谎。 D 、全体起立！ 2．图 的邻接矩阵为( C )。 A 、 1 111111*********?? ? ? ? ??? B 、1 110011*********?? ? ? ? ??? C 、0 110001*********?? ? ? ? ??? D 、0 111101*********-?? ? - ? ?-- ?-?? 3．下列排列能构成图的顶点度序列的是（ A ）。 A 、1,2,2,3,4 B 、2,3,4,5,6,7 C 、2,1,1,1,2 D 、3,3,5,6,0 4．设{}b a A ,=，则I A =（D ）。 A 、 A ； B 、A×I A ； C 、 I A ×A ； D 、{,,,}a a b b <><>。 5．下述命题公式中，是重言式的为（ C ）。 A 、)()(q p q p ∨→∧； B 、))())(()(p q q p q p →∧→??； C 、q q p ∧→?)(； D 、q p p ??∧)(。 二、填空题15分 （每小题 3分） 1已知一棵无向树T 有三个3度顶点,一个2度顶点,其余的都是1度顶点, 则T 中有 5 个1度顶点。
,考试作弊将带来严重后果！ 华南理工大学期末考试 《Discrete Mathematics 》 ： 1. 考前请将密封线内填写清楚； 所有答案请直接答在答题纸上； ．考试形式：闭卷； 本试卷共 4 大题，满分100分， 考试时间120分钟。 ． Choose an answer to the following question. (10 x 2’ = 20’) ) B) x > 1.5 D) Help me. is true for all possible assignments of truth values to p q except for which assignment?( ) ）p false, q true B ）p true, q false ）p false, q false D ）p true, q true “No Computer Major is taking any courses ” where C(x) is the statement x is a Computer ) A ） B ） C ） D ） (4) Function f is defined as x x x f Z Z f 2)(,:-=→, so f is ( ) A ）onto B ） both onto and one-to-one C ）one-to-one D ） neither onto nor one-to-one (5) Supposed a binary relation R (Figure 1) on the set A = { 1, 2, 3 }, R is ( ) A) irreflexive, symmetric, non-transitive B) reflexive, antisymmetric, transitive C) irreflexive, antisymmetric, transitive Figure 1. D) reflexive, antisymmetric, non-transitive (6) Which of these arguments is true?( ) A) (P(S), subset of ) is a poset and also total orderedB) (Z +,|) is totally ordered C) 可整除) “ | ” is a partial ordering on the set of positive +,|) is a poset. D) (N, >=) is well-ordered (7) (A ?B )-C = ( )
离散数学2012年12月28 日 √√计科21101、21102、信科11001、11002 一二三四五六七八 一、单选题: (2分×10=20分) 1.设p:我们听课,q:我们打球.命题“我们不能既听课又打球”符号化为( ). A．┓p→┓q B．┓p∨┓q C．┓(p→q) D．p?┓q 2.设个体域A={a,b},公式?xP(x)∧?yQ(y)消去量词后为( ) A.P(x)∧Q(y) B.P(a)∧P(b)∧(Q(a)∨Q(b)) C.P(a)∧Q(b) D. P(a)∧P(b)∧Q(a)∨Q(b) 3．设A={1,2,3}, 则A上的等价关系有( ) A．3个B．4个C．5个D．6个 4．设Z是整数集，+，·分别是普通加法和乘法，则〈Z，+，·〉是（）A．域B．整环和域C．整环D．含零因子环 5．Q为有理数集，·是普通乘法,则代数系统〈Q，*〉不能构成（）A．群B．独异点C．半群D．交换半群 6．N是自然数集，≤是小于等于关系，则〈N，≤〉是（） A．有界格B．有补格C．分配格D．有补分配格 7．有限布尔代数的元素个数必定等于（） A．2n B．2n C．n2D．3n 8．给定下列序列，可构成无向简单图的度数序列的是（） A．1,1,2,2,3 B．1,1,2,2,2 C．0,1,3,3,3 D．1,3,4,4,5 9．任何无向图中顶点间的连通关系是（） A．偏序关系B．等价关系C．非偏序关系D．非等价关系10．设D=〈V，E〉为有向图，V={a,b,c,d}， E={
命题人： 审核人： 试卷分类（A 卷或B 卷） B 五邑大学 试 卷 学期： 2012 至 2013 学年度 第 1 学期 课程： 离散数学 课程代号： 使用班级： 姓名： 学号： 将下列命题符号化（有量词的用谓词符号，没有的用命题符号）（8分） 1. 如果天下雨，我就乘汽车上班。 2. 如果a 和b 是奇数，则a+b 不是奇数。 3．每个人或者喜欢乘汽车，或者喜欢骑自行车。 4．虽然有的人聪明，但不是每个人都聪明。 设P ：2＞1；Q (x )：x ≤3,；R (x )：x ≥6；a =5.而且论域为{-2，1，7}，求（)())()((a R x Q P x ∨→?的值。（6分）
求公式（P ∧Q ）∨（? P ∧ Q ∧ R ）的主析取范式，主合取范式。（10分） 四、（16分） （1）用命题推理理论构造下列推理。 前提：P Q ?∨，R Q ∨?，R S → 结论：P S →
（2）符号化下列命题，判断它们是否有效？ 有理数和无理数都是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。 五、 判断下图中关系的性质，并说明理由。（8分） （1） （2） （3） a
六、 证明题（10分） 证明：定义在实数集R上的关系S={x,y>| x,y∈R, (x-y)可以被5整除}是一个等价关系。 七、（12分） G={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,24}，p为整除关系，作出偏序集的哈斯图，令A={2, 4, 6, 11, 12}，并求出在偏序集
一、 命题逻辑部分 1．计算真值表、并由此写出主析取与主合取范式 2．证明 P →(Q →R )?Q →(P →R )? ┐R →(Q → ┐P ) 3．证明从前提P →Q ，┐(Q ∨R)可演绎出┐P . 4．证明R →S 可从前提P →(Q →S)，┐R ∨P 和Q 推出。├ 5、使用推理规则或归结推理，论证推理形式 1) P →Q, R →?Q ,R ∨S, S →Q ? ├?P 2) ?P ?Q, S →?Q, ?R, R ∨S ├ P 二、 谓词逻辑 1、 写出谓词的含义、一个谓词公式的解释应包含什么内容？ 2、 并非一切劳动都能用机器代替。 解 设 L(x): x 是一种劳动, M(x): x 是一种机器, R(x, y): x 被y 代替。命题表示为: ?(?x) (L(x) → (?y) (M(y)∧R(x,y))) 3、数学分析中函数f (x)在点a 连续的定义为: 对任意的ε>0, 存在一个δ>0, 使得对所有x, 若|x – a|<δ, 则 |f (x) – f (a)|<ε, 符号化此定义。 解 令R(x): x 是实数, G(x, y): x 大于y 。 (?ε) ((R(ε)∧G(ε, 0)) → (?δ) (R(δ)∧G(δ, 0)∧(?x) ((R(x)∧G(δ, |x – a|)) →G(ε, |f (x) – f (a)| ) )))。 4、 证明等价式：┐(?x )A ?(?x )┐A 5、 证明等价式：(?x )(A (x )∧B (x ))?(?x )A (x )∧(?x )B (x ) 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 ((p →q ) →(?q →?p )) ∨r ?q →?p p →q p q r
浙 02324# 离散数学试卷 第1页（共4页） 全国2012年7月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P :他看电影，Q :他学习，将命题“他在学习或在看电影”符号化正确的是（ ） A.P →Q B.P ∧Q C.P ∨Q D.Q →?P 2.下列命题公式不是．．永真式的是( ) A.()P Q P →→ B.()P Q →∨P C.P ?∨()Q P → D.()P Q P →→ 3.下列等价式正确的是（ ） A.()()()()x A x x A x ????? B.()()()(()) A x B x x A B x →???→ C.()(())()()x A x B x A x B ?→??→ D.()(())()()x A x B x A x B ?→??→ 4.设A(x):x 是鸟，B(x):x 会飞，命题“有的鸟不会飞”符号化为（ ） A.()(()x A x ??∧())B x B.()(()x A x ??∧())B x C.()(()())x A x B x ??→ D.()(()())x A x B x ??→ 5.设X ={,{},{,}}a a ??，则下列陈述正确的是（ ） A.a X ∈ B.{,}a X ?? C.{{,}}a X ?? D.{}X ?∈ 6.设A B B = ,则有（ ） A.A B A = B.A B -=? C.A B B = D.A B ? 7.设A =｛a ,{b , c }｝,则其幂集P （A ）的元素总个数为（ ） A.3 B.4 C.6 D.8 8.在整数集Z 上，下列定义的运算满足结合律的是（ ） A.1a b b *=+ B.1a b a *=- C.1a b ab *=- D.1a b a b *=++
2012-2013离散数学试题A 卷答案 一填空题（每空3分） 1.{}{}{}{}{}3,2,2,1,3,1； 2. 6； 3. ??? ???42314321；4. 两个或零个奇数度结点；5. ()()x xB x xA ?→?；6. 偶数个；7.???? ??????100111001；8.N 或 阿列夫零 9. ()()y f x f ? 二（本题10分） 证明整数集合是可数的 证：因为自然数集N 是可数的，所以只要证明N Z =即可，建立下面的一一对应关系： Λβββββββ-3 6352423-121100 -Z N （5分） 即(),1 ,120,2???≥-≤-=x x x x x f 其中Z x ∈. （3分） 则有N Z = 故整数集合是可数的 （2分） 三、（本题8分）求公式()P Q Q R →∧?→?)( 的主合取范式,并判断公式的类型. 解()()P Q Q R P Q Q R ∨?∧?∨?→∧?→?)()( （2分） ()()()()Q R P Q R P R Q P R Q P ?∨?∨∧?∨∨∧∨?∨?∧∨?∨?（4分） 该公式是可满足式 （2分）
四、（每小题8分，共计16分） 1.设图()m n G ,=是每个区域（面）至少由k 条边围成的连通平面图，证明 ()2 2--≤k n k m ，其中3≥k 证：1）因为 2=+-r m n ，m n r +-=2 （2分） 2）又因为()r m r r i 32deg 1≥=∑= （2分） 将1）代人2）整理得：()2 2--≤ k n k m （4分） 2. 一个树T 有2个次数为2的结点，1个次数为3的结点， 3个次数为4的结点，问该树有几片叶？ 解 设树T=()m n ,有x 片叶， 因为 1=-m n （1） （1分） x x n +=+++=6312 （2） （1分） ()()122deg 1 -==∑=n m v n i i （3） （2分） ()()x x n m v n i i +=+?++?=-==∑=1943322122deg 1 （2分） 即()x x +=+1952 （1分） x =9 （1分） 五. （本题12分） 设{} 1-=Q S ,其中Q 为有理数集合，在S 上定义了二元运算“ο”，对于()y y x y x S y x +-=∈?1,,ο有. 证明: ()ο,S 是交换群. 证明：（1）结合律成立（略） （2分） （2）单位元素 =e 0 （3分） x e xe x e x S x =+-=∈?ο,，()01=-x e ，0=e
全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） 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 )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001
诚信应考 考出水平 考出风格 浙江大学城市学院 2011 — 2012 学年第 二 学期期末考试试卷 《 离散数学 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间：_2012_年_6_月_12_日； 所需时间： 120 分钟 一．选择题 (本大题共10题，每题2分，共20分。选择题答案请填到下面表格的相 应栏中) 1．下列式子中是永真式的为（ ）。 A ．) B A (A ∧∨ B ．)B A ()B A (∧?∨∧ C ．))B B (A (A ?∧∨?∨ D ．B A ? 2．命题公式Q Q →→∧))P (P (是（ ）。 A ．矛盾式 B ．蕴含式 C ．重言式 D ．等价式 3．设R(x)：x 是实数；Q(x)：x 是有理数。命题“所有有理数是实数”可以符号化为（ ）。 A ．))(R )(Q )((x x x ∧? B ．))(R )(Q )((x x x →? C ．))(R )(Q )((x x x ∧? D ．))(R )(Q )((x x x →? 4．设A={1，2，3}，则A 上的二元关系有（ ）个。 A ． 23 ； B ． 32 ； C ． 3 32 ?； D ． 2 23 ?。
5．设A={1，2，3}，如右图所示关系图表示的二元关系具有 ( ) 。 A ． 自反性 B ． 对称性 C ． 传递性 D ． 反对称性 6．设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“?”的哈斯图为（ ） 7．对于集合A={x ∣-10
中国民航学院2012－2013 学年第 1学期 《离散数学》期末试卷A 课程编号：03401519 试卷类型： 考试形式：闭卷 考试日期：2012年12月28日(15:30-17:30) 南3-203，211 注意事项：1.试卷答在答题纸上，后一页为草稿纸，可以撕下；2.不准携带任何书籍、资料、纸张等。 一 (30分) 选择 (答案写在答题纸上) 1）下列运算中，哪种运算关于整数集不能构成半群() (1) a 。b-max (a, b): (2) a 。b=b; (3) a 。b=2ab; (4) a 。b=∣a-b ∣ 答案:〔(4)〕 2）设I 是整数集，+，·分别是普通加法和乘法，则〈I ，+，·〉是 (1)域 (2)整环和域 (3)整环; (4)含零因子环. 答案〔(3)] 3）下面哪个哈斯图表示的偏序关系不能构成格如图1-1所示() d f c (1) (2) d f (3) (4) 图 1-1
答案:〔(2)) 4）给定无向图G=(V,E)如图1-2所示，则其割点为（ ) a1 a6a5 a3 图 1-2 (1) a1； (2)a5； (3 )a4； ( 4)a6 ,.答案:[(3)] 5）图1-3中哪一个图可一笔画出 () (1) (2) (3) (4) 图 1-3 答案:[(1)」 6）完全图K 4的所有非同构的生成子图中有几个是3条边的 (1) 1 ;（2）3; :( 3) 4 ;（4）2 答案:〔(2)〕 二(20分)填空(答案写在答题纸上) 1）设(G ,*)是非零实数乘法群，f:G →G 是同态映射F(x)=1/x ，则f(G)=__,ker(f)=__ 答案.(G: {1}] 2）有限群的阶数为____时，它无非平凡子群，根据_______ 答案〔素数;拉格朗日定理〕 3）在任何图G=(V .E)中。结点v 的度数为____________图G 的最大度△ (G)=____________________.图G 的最小度δ(G) =________________________ 答案.[结点u 关连的边数,max{deg(v)︱v ∈V};min{deg(v)v ∈V))
孝感学院新技术学院Array 2011 — 2012 学年度第二学期期中考核试卷考核课程：离散数学考核类型：考试考核形式：闭卷 学生所在院系：信息工程系年级： 21117141 试卷： A 一、单项选择题（本大题共10小题，每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子是．命题的是（） A．我们要努力学习！B．今天是星期天吗？ C．雪是黑色的D．太好了！ 2．下列式子不是 ．．析取的性质的是（） A．P∨P?P B．P∧┐P? 0 C．P∨(P∧Q)P? P D．P∨(Q∧R) ?(P∨Q) ∧(P∨R) 3．下列式子是命题公式的是（） A．┐P∨Q∨B．(┐P∨Q∨R) ∧（┐P∧┐Q） C．（┐P∧Q）→D．P∨（Q∨R∨ 4．张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，则说真话的是（）A．张三说真话 B．李四说真话 C．王五说真话 D．张三和王五都说真话 5．下列各式不是前束范式的是（） A．?x?y?z（P（x，y，z）→Q（x，y）） B．?x?y?z（P（x，y，z）→?x?y Q（x，y） C．?x?y（P（x，y，z）→Q（x，y）） D．?x?y（P（x，y）∧Q（x，y）） 命题教师院系负责人签字
6．已知指定一个解释I如下： （1）个体域为自然数集合N； （2）指定常项a=0； （3）指定谓词F（x，y）为x=y； （4）N上的指定函数f（x，y）=x+y，g（x，y）=x*y。 在以上指定的解释I下，下列公式的真值为假的是（） A．?x F（g（x，a），x）B．?x?y（F(f（x，a），y) →F(f（y，a），x) C．F(f（x，y），f（y，z）) D．F(g（x，y），f（y，x）) 7．下列有关图的概念不正确的是（） A．规定顶点集和边集均为空的图为空图 B．规定含有平行边的图称为多重图 C．规定有自环和平行边的图称为简单图 D．规定顶点集和边集均不为有限集的图称为有限图 8．下列有关的命题等价式错位的是（） A．幂等率：A∨A?A A∧A?A B．吸收率：A∧（A∨B）?B A∨（A∧B）?B C．互补率：A∨┐A?1 A∧┐A?0 D．假言易位：A→B?┐B→┐A 9．有题9图得出的如下结论错误的是（） d g A．（g，h，c，d，a，b，c，e，f，g）是回路，但不是环 a c f B．（h，c，d，a，b，c，e，f）是通路，也是基本通路 C．（a，b，c，d，a）是环 b e D．（h，g，f）是h与f之间的短程题9图 10．下列图是欧拉图的是（） 二、填空题（本大题共5小题，每空2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．请写出表示德摩根律的两个命题公式等价定理___________，___________。 17．请将下列命题符号化： P；李明是计算机系的学生。Q：李明是男生。R：李明是女生； ______________________ 18．置换规则：假设A为含公式X的命题公式，Y也为公式且___________如果用Y置换A中的X，得到新的
,考试作弊将带来严重后果！ 华南理工大学期末考试 《Discrete Mathematics 》 ： 1. 考前请将密封线内填写清楚； 所有答案请直接答在答题纸上； ．考试形式：闭卷； 本试卷共 4 大题，满分100分， 考试时间120分钟。 ． Choose an answer to the following question. (10 x 2’ = 20’) ) B) x > 1.5 D) Help me. is true for all possible assignments of truth values to p q except for which assignment?( ) ）p false, q true B ）p true, q false ）p false, q false D ）p true, q true “No Computer Major is taking any courses ” where C(x) is the statement x is a Computer ) A ） B ） C ） D ） (4) Function f is defined as x x x f Z Z f 2)(,:-=→, so f is ( ) A ）onto B ） both onto and one-to-one C ）one-to-one D ） neither onto nor one-to-one (5) Supposed a binary relation R (Figure 1) on the set A = { 1, 2, 3 }, R is ( ) A) irreflexive, symmetric, non-transitive B) reflexive, antisymmetric, transitive C) irreflexive, antisymmetric, transitive Figure 1. D) reflexive, antisymmetric, non-transitive (6) Which of these arguments is true?( ) A) (P(S), subset of ) is a poset and also total ordered B) (Z +,|) is totally ordered
2012级 离散数学 课程试题（A 卷） 合分人： 复查人： 一、 选择题：（每题1分，共15分） 1．设谓词是实数， ,则语句“没有最小的实数”可符号化为( )。 A. B. C. D. 2.下列语句是真命题的是（ ）。 A.雪是黑色的，当且仅当5<0 B. 自然数中存在最大素数 C.今天天气真好呀 D. 只有5<0，雪才是白色的 3．设，则下列陈述正确的是（ ）。 A. B. C. D. 4.设，则（ ）。 A. B. C. D. 5.设 ，则其幂集 的元素总个数为（ ）。 A.2 B.3 C.4 D.8 6.设 ，A 上的等价关系 ，则对应 于R 的A 的划分是（ ）。 A ．}}{},,{},{{d c b a B ．}}{},{},,{{d c b a C ．}}{},{},{},{{d c b a D ．}},{},,{{d c b a
7．是一个偏序集，其中A 是正整数12的正因子的集合，为整除关系，则能盖住 元素3的元素是（ ）。 A.1 B.3 C.6 D.12 8．在整数集Z 上，下列定义的运算满足结合律的是（ ）。 A. B. C. D. 9.设 是群，则下列陈述不正确的是（ ）。 A.n n n ab a b =（） B. -11n n a ba a b a -=（） C. n m nm a a =（） D.n m n m a a a += 10. 设}0{=X ，下列关于代数系统>< ),(X P 的陈述正确的是（ ）。 A. 0是幺元 B. Φ是幺元 C.｛0｝是幺元 D.没有幺元 11.设Z 是整数集，+， 分别是普通加法和乘法，则（Z ，+， ）是（ ）。 A ．域 B ．整环和域 C ．整环 D ．含零因子环 12．设简单图G 所有顶点的度数之和为36，则G 的边数为（ ）。 A.12 B.18 C.36 D.72 13.下列无向图不一定是树的是（ ）。 A. 有n 个结点，n -1条边的图 B. 无回路的连通图 C. 连通但删去一条边则不连通的图 D.无回路但添加一条边则有一个回路的连通图 14．下列必为欧拉图的是（ ） A.有回路的连通图 B.不可以一笔画的图 C.有1个奇数度顶点的连通图 D.无奇数度顶点的连通图 15．在简单无向图>= 2012-2013离散数学A 一．下列句子哪些是命题？是命题的句子中哪些属于简单命题？哪些是复合命题？并将复合命题符号化。（5分） 1.你会来吗？ 2.大熊猫产在我国西安。 3.这朵花真好看！ 4.李梅能歌善舞。 5.如果我有时间，我就来看你。 解：命题：（2），（4），（5) 简单命题：（2），复合命题：（4），（5） 命题符号化：（4）P^Q（5）P->Q 二．判断下列式子是否为永真式。(5分) (P→Q)→((R→Q)→((PνR)→Q)) 解： P Q R P→Q R→Q PνR（PνR)→Q(R→Q)→((PνR)→Q)(P→Q)→((R→Q)→((PνR)→Q)) 0 0 0 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 三．求下式的主合取范式和主析取范式。(10分) P→(Q→R) 解： P Q R Q→R P→(Q→R) 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 由真值表可知：主合取范式为∑(6) 主析取范式为∏（0,1,2,3,4,5,7） 四．在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出如下判断：甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后，说：你们3人中有一人全说对，一人全说错，还有一人对错各半。 试用逻辑演算法判断王教授是哪里人？(10分) 解设设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分) 某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。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 全国2012年7月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P :他看电影，Q :他学习，将命题“他在学习或在看电影”符号化正确的是（ ） A.P →Q B.P ∧Q C.P ∨Q D.Q →?P 2.下列命题公式不是．． 永真式的是( ) A.()P Q P →→ B.()P Q →∨P C.P ?∨()Q P → D.()P Q P →→ 3.下列等价式正确的是（ ） A.()()()()x A x x A x ????? B.()()()(())A x B x x A B x →???→ C.()(())()()x A x B x A x B ?→??→ D.()(())()()x A x B x A x B ?→??→ 4.设A(x):x 是鸟，B(x):x 会飞，命题“有的鸟不会飞”符号化为（ ） A.()(()x A x ??∧())B x B.()(()x A x ??∧())B x C.()(()())x A x B x ??→ D.()(()())x A x B x ??→ 5.设X ={,{},{,}}a a ??，则下列陈述正确的是（ ） A.a X ∈ B.{,}a X ?? C.{{,}}a X ?? D.{}X ?∈ 6.设A B B = ,则有（ ） A.A B A = B.A B -=? C.A B B = D.A B ? 7.设A =｛a ,{b , c }｝,则其幂集P （A ）的元素总个数为（ ） A.3 B.4 C.6 D.8 8.在整数集Z 上，下列定义的运算满足结合律的是（ ） A.1a b b *=+ B.1a b a *=- C.1a b ab *=- D.1a b a b *=++ 9.设 东华理工大学2012-2013年B卷 一．下列句子哪些是命题？是命题的句子中哪些属于简单命题？哪些是复合命题？并将复合命题符号化。（5分） 1.你回去吗？ 2.小王和小李是同学。 3.别讲话了！ 4.李梅能歌善舞。 5.你只有不怕困难，才能战胜困难。 解：命题：（2），（4），（5) 简单命题：（2），复合命题：（4），（5） 命题符号化：设李梅会唱歌为P，会跳舞为Q（4）P^Q 设不怕困难为P，战胜困难为Q（5）P->Q 二．判断下列式子是否为永真式。(5分) (P→Q)→((R→P)→(R→Q)) 解： P Q R P→Q R→P R→Q(R→P)→(R→Q)(P→Q)→((R→P)→(R→Q)) 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 三．求下式主合取范式和主析取范式。(10分) (PνQ)→R 解： P Q R PνQ(PνQ)→R 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 由真值表可知：主合取范式为∑(2.4.6) 主析取范式为∏（0,1,3,5,7） 四．甲、乙、丙、丁4人有且仅有两个人参加围棋优胜比赛。关于谁参加比赛，下列4种判断都是正确的：(10分) 1．甲和乙只有一人参加； 2．丙参加，丁必参加； 3．乙或丁至多参加一人； 4．丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 解：符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有， (1)甲和乙只有一人参加，符号化为A⊕B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C→D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D→?A。 所以原命题为：(A⊕B)∧(C→D)∧(?(B∧D))∧(?D→?A) ?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A) ?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A)) ?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T 但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B ∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛 五.将下列推理形式化，并对正确的推理给出推理过程，要求指明所设命题或谓词含义。(10分) 每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，并非每个人都喜欢骑自行车，因而有人不喜欢步行。 六．令X={x1,x2,…,xm}，Y={y1,y2,…,yn}，问：(10分) 1.有多少不同的由X到Y的关系？ 2.有多少不同的由X到Y的映射？ 3.有多少不同的由X到Y的单射，双射？ 七．设A，B均为非空集合，R1和R2分别为A和B上的等价关系，置： R3={((x1,y1),(x2,y2))|(x1,x2)∈R1∧(y1,y2)∈R2}，证明R3是A?B上的等价关系。(10 3 2 1 ,考试作弊将带来严重后果！ 华南理工大学期末考试 《Discrete Mathematics 》 ： 1. 考前请将密封线内填写清楚； 所有答案请直接答在答题纸上； ．考试形式：闭卷； 本试卷共 4 大题，满分100分， 考试时间120分钟。 ． Choose an answer to the following question. (10 x 2’ = 20’) ) B) x > 1. 5 D) Help me. is true for all possible assignments of truth values to p q except for which assignment?( ) ）p false, q true B ）p true, q false ）p false, q false D ）p true, q true “No Computer Major is taking any courses ” where C(x) is the statement x is a Computer ) A ） B ） C ） D ） (4) Function f is defined as x x x f Z Z f 2)(,:-=→, so f is ( ) A ）onto B ） both onto and one-to-one C ）one-to-one D ） neither onto nor one-to-one (5) Supposed a binary relation R (Figure 1) on the set A = { 1, 2, 3 }, R is ( ) A) irreflexive, symmetric, non-transitive B) reflexive, antisymmetric, transitive C) irreflexive, antisymmetric, transitive Figure 1. D) reflexive, antisymmetric, non-transitive (6) Which of these arguments is true?( ) A) (P(S), subset of ) is a poset and also total ordered B) (Z +,|) is totally ordered 东南大学考试卷（ A 卷） 适用专业计算机科学与技术考试形式闭卷考试时间长度120分钟一、选择题（每题2分，共10分） 1．下列语句中，（）是命题。 （A）如果天黑了你就把灯打开； （B）这世界一切言论都是谎言； （C）2和3都是奇数； （D）x + 5 > 6； 2、设I是如下一个解释：D={a , b}, P(a,a)=1, P(a,b)=0, P(b,a)=1, P(b,b)=0, 则在解释I下，取真值为1的公式为（）D （A）?x?yP(x,y)；（B）?x?y P(x,y)； （C）?x P(x,x)；（D）?x?yP(x,y)； 3、设命题公式G=?(P→Q)，H=P→(Q→?P)，则G与H的关系是（） （A）G?H；（B）H?G； （C）G?H；（D）以上都不是； 4、设集合为A={2，{a}，3，4}，B={{a}，3，4，1}，E为全集下列命题为真的是（）（A）{2}∈A；（B）{a}?A； （C）Φ?{{a}}?B?E；（D）{{a}，1，3，4}?B； 5、设集合A={1，2，3}，A上的关系R={<1,1>,<2,2>,<2,3>,<3,2>,<3,3>}, 则R不具备（） （A）自反性；（B）传递性； （C）对称性；（D）反对称性； 共 4 页第 1 页 二、填空题（每空2分，共20分） 则代数系统2012-2013离散数学A(1)
全国2012年7月高等教育自学考试离散数学试题
2012-2013离散数学B
2012离散数学A卷
东南大学2012年6月离散数学A
相关主题
文本预览