离散数学模拟试卷和答案
北京语言大学网络教育学院
《离散数学》模拟试卷一
注意：
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个
8、一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点（）。
[A] G没有奇数度结点 [B] G有1个奇数度结点
[C] G有2个奇数度结点[D] G没有或有2个奇数度结点
9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是（）。
[A] G中有幺元 [B] G中么元是唯一的
[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元
10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）
[A] p→┐q [B] p∨┐q
[C] p∧q [D] p∧┐q
11、设图G=
[A]{v1} [B]{v2} [C]{v3} [D]{v2,v3}
12、下面4个推理定律中，不正确的为（）。
[A]A=>(A∨B) (附加律) [B](A∨B)∧┐A=>B (析取三段论) [C](A→B)∧A=>B (假言推理) [D](A→B)∧┐B=>A (拒取式)
,v v的初级回路有多少条（）
13、在右图中过
12
[A] 1 [B] 2 [C] 3 [D] 4
14、若*
,R是环，且R中乘法适合消去律，则R是（）。
+,
[A]无零因子环[B]除环
[C]整环 [D]域
15、无向图G中有16条边，且每个结点的度数均为2，则结点数是（）。
[A]8 [B]16 [C]4 [D]32
二、【判断题】(本大题共8小题，每小题3分，共24分)正确的填T ，错误的填F ，填在答题卷相应题号处。
16、{}?是空集。 （ ） 17、设,S T 为任意集合，如果S —T=φ，则S=T 。
（ ）
18、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。 （ ） 19、关系的复合运算满足交换律。 （ ） 20、集合A 上任一运算对A 是封闭的。 （ ） 21、
}0,1,2,3,4,max,min
是格。 （ ）
22、强连通有向图一定是单向连通的。 （ ） 23、设都是命题公式，则()P Q Q P →?∧?。 （ ） 三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分）请将答案填写在答题卷相应题号处。
24、设集合A ＝{a , b , c }，B ={b , d , e }，求 （1）B ?A ； （2）A ?B ； （3）A －B ； （4）B ⊕A ． 25、设非空集合A ，验证(A A P ,~,,,),(???)是布尔代数
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI 语言而且学过C++语言。只要他学过DELPHI 语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
《离散数学》模拟试卷一 答案
一、【单项选择题】(本大题共15小题，每小题3分，共45分)
二、【判断题】(本大题共8小题，每小题3分，共24分)
三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分） 24、设集合A ＝{a , b , c }，B ={b , d , e }，求 （1）B ?A ； （2）A ?B ； （3）A －B ； （4）B ⊕A ． 标准答案：（1）B ?A ={a , b , c }?{b , d , e }={ b }
（2）A ?B ={a , b , c }?{b , d , e }={a , b , c , d , e }
（3）A －B ={a , b , c }－{b , d , e }={a , c }
（4）B ⊕A = A ?B －B ?A ={a , b , c , d , e }－{ b }={a , c , d , e }
复习范围或考核目标：考察集合的基本运算，包括交集，并集,见课件第一章第
二节,集合的运算。
25、设非空集合A ，验证(A A P ,~,,,),(???)是布尔代数
标准答案：证明 因为集合A 非空，故P (A )至少有两个元素，显然?，?是P (A )上的二元运算. 由定理10 ，任给B ,C ,D ∈P (A ), H 1 B ?D =D ?C C ?D =D ?C
H 2 B ?(C ?D )=(B ?C )?(B ?D ) B ?(C ?D )=(B ?C )?(B ?D )
H 3 P (A )存在?和A ，?B ∈P (A ), 有B ??＝B ， B ?A ＝B
H4，?B∈P(A), B?A，存在A?~B，有
B?A?~B)= A B?(A?～B)=?
所以(
A
A
P,
~,
,
,
),
(?
?
?)是布尔代数.
复习范围或考核目标：考察布尔代数的基本概念，集合的运算，见课件代数系统中布尔代数小节。
26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。
标准答案：令p：他是计算机系本科生
q：他是计算机系研究生r：他学过DELPHI语言
s:他学过C++语言
t:他会编程序
前提：(p∨q)→(r∧s),(r∨s)→t
结论：p→t
证①p P(附加前提)
②p∨q T①I
③(p∨q)→(r∧s) P(前提引入)
④r∧s T②③I
⑤r T④I
⑥r∨s T⑤I
⑦(r∨s)→t P(前提引入)
⑧t T⑤⑥I
复习范围或考核目标：考察数理逻辑的应用,详见课件数理逻辑中命题逻辑的命题演算的推理理论。
北京语言大学网络教育学院
《离散数学》模拟试卷二
注意：
1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。
2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。
3.本试卷满分100分，答题时间为90分钟。
4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。
一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、若集合A ＝{2，a ，{ a }，4}，则下列表述正确的是（ ）。
[A]
[B]
[C]
[D]
2、若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ ）。 [A] [B] [C]
[D]
3、下列式子中正确的有（ ）。 [A]
[B]
[C]
[D]
4.设{,,},{,,,}A a b c B a b c d ==，则下列正确的是（ ）。 [A]A B ? [B]A B ? [C] A B ∈ [D] 以上都不对 5、设{0,1},{2,3}A B ==,则A B ?=（ ）。
[A] {0,2,0,3,1,2,1,3}<><><><> [B] {0,2,1,2,1,3}<><><> [C] {0,3,1,2,1,3}<><><> [D] {0,2,0,3,1,2}<><><> 6、设{0,1},{2,3}A B ==,则B A ?=（ ）。
[A] {2,0,3,0,1,2,1,3}<><><><> [B] {2,0,3,0,2,1,3,1}<><><><> [C] {0,3,1,2,1,3}<><><> [D] {0,2,0,3,1,2}<><><> 7、下列式子正确的是（ ）。 [A]p q q p →?→ [B]p q p q →??∨ [C]p q q p →??∨ [D]p q q p →??∨?
8、设P,Q,R 是命题公式,则P →R ，Q →R ，P ∨┐Q ?（ ）。
[A] P [B] Q [C] R [D] ┐R
9、11:,()3i
f Z R f i →=，则1f 是（ ）。
[A] 单射 [B] 满射 [C] 双射 [D] 以上说法都不对 10、 124:{0,1,2,3},()()f Z f i res i →=，则1f 是（ ）。 [A] 单射 [B] 满射 [C] 双射 [D] 以上说法都不对 11、 若复合映射τσo 是满射，则（ ）。
[A] τ是满射 [B] σ 是满射 [C] τ是单射 [D] σ是单射 12.、设R 为实数集，映射
，则σ是（ ）。
[A]单射而非满射 [B]满射而非单射 [C]双射 [D] 既不是单射，也不是满射 13.、I 是一个整数集，*是加法运算，代数系统中的幺元是（ ）。 [A]0 [B]1 [C] 2 [D] 3
14、A 是整数集，*是乘法运算，代数系统中的幺元是（ ）。
[A]0 [B]1 [C] 2 [D] 3 15、在代数系统,Z <+>中，零元是（ ）。 [A]0 [B]1 [C] 2 [D] 不存在
二、【判断题】(本大题共8小题，每小题3分，共24分)正确的填T ，错误的填F ，填在答题卷相应题号处。
16、陈述句“x+y>4”是个命题。 ( ) 17、命题“如果1+2=3，那么雪是黑的”是真命题。 ( ) 18、（P ∨→（Q ∧R ））是一个合式命题公式，其中P 、Q 、R 是命题变元。 ( ) 19、（P →（Q ∧R →?Q ）是一个合式命题公式，其中P 、Q 、R 是命题变元。 ( ) 20、基本联结词“∧，∨，?，→”是可交换的 ( ) 21、p∧┐(q→p)是永假式 （ ） 22、命题公式“（P ∧（P →Q ））→Q ”是重言式。 ( ) 23、如果f 是g 的逆映射，则g 是f 的逆映射。 （ ） 三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分）请将答案填写在答题卷相应题号处。 24、如果
和
是A 上的自反关系，判断结论：“
、、
是自反的”
是否成立？并说明理由。
25、设集合{
}5,4,3,2,1=A ，A 上的二元关系R 为 ()()()()()()()(){}5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1=R (1)写出的关系矩阵，画出的关系图； (2)证明是A 上的半序关系，画出其哈斯图。 26、化简下列各式：
（1）A∨（?A∨（B∧?B））
（2）（A∧B∧C）∨（?A∧B∧C）
《离散数学》模拟试卷二答案
一、【单项选择题】(本大题共15小题，每小题3分，共45分)
题号 1 2 3 4 5 6 7 8 9 10 答案 B B B A A B B A A B 题号11 12 13 14 15
答案 A D A B D
二、【判断题】(本大题共8小题，每小题3分，共24分)
题号16 17 18 19 20 21 22 23 答案 F F F F T T T T
三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分）
24、如果和是A上的自反关系，判断结论：“、、是自反的”是否成立？并说明理由。
标准答案：解：结论成立．
因为R1和R2是A上的自反关系，即I A?R1，I A?R2．
由逆关系定义和I A?R1，得I A? R1-1；
由I A?R1，I A?R2，得I A? R1∪R2，I A? R1?R2．
所以，R1-1、R1∪R2、R1?R2是自反的．
复习范围或考核目标：考察集合论相关知识，关系的自反性，详见课件集合论中的二元关系。
25、设集合{
}5,4,3,2,1=A ，A 上的二元关系R 为 ()()()()()()()(){}5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1=R (1)写出的关系矩阵，画出的关系图； (2)证明是A 上的半序关系，画出其哈斯图。 标准答案：解 （1）R 的关系矩阵为
???
??
?
?
?
??=111000100001100
00010
00001R M R 的关系图略
（2）因为R 是自反的，反对称的和传递的，所以R 是A 上的半序关系。(A,R)为半
序集， (A,R)的哈斯图如下
复习范围或考核目标：考察关系中的二元关系，详见课件集合论中的二元关系。 26、化简下列各式
（1）A ∨（?A ∨（B ∧?B ）） （2）（A ∧B ∧C ）∨（?A ∧B ∧C ） 标准答案：（1）A ∨（?A ∨（B ∧?B ）） ＝A ∨（?A ∨0）＝A ∨?A ＝1 （2）（A ∧B ∧C ）∨（?A ∧B ∧C ） ＝（A ∧（B ∧C ））∨（?A ∧（B ∧C ））
。4 。1
。3 。2
。5
＝（A ∨?A ）∧（B ∧C ） ＝1∧（B ∧C ） ＝B ∧C
复习范围或考核目标：考察数理逻辑的应用,详见课件数理逻辑中的命题逻辑公式及等值演算。
北京语言大学网络教育学院
《离散数学》模拟试卷三
注意：
1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。
2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。
3.本试卷满分100分，答题时间为90分钟。
4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。
一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、下列关于群说法不正确的是（ ）。
[A] G 的每个元素的逆元都是唯一的 [B] ,G <>o 无零元 [C] o 必须有单位元 [D] o 是不可结合的 2、集合{}1,2,3,4有（ ）个真子集。
[A]4 [B]8 [C]14 [D]16 3、下列说法中正确的是（ ）。
[A] 设a,b,c 是阿贝尔群,G <+>的元素，则有-(a+b+c)=(-a)+(-b)+(-c) [B] 设a,b 是群,G 的元素，则对于n N ∈，有(.).n
n
n
a b a b =
[C] 设a ，b 是群,G 的元素，则对于任意,a b G ∈，有2
2
2
.(.)a b a b =
[D] 设a 是群,G 的元素，记{|..}H y y G y a a y =∈=且，则,H 是,G 的子群
4、下列集合关于所给定的运算成为群的是（ ）。
[A] 已给实数a 的正整数次幂的全体，且a ?{0，1，-1}，关于数的乘法 [B] 所有非负整数的集合，关于数的加法 [C] 所有正有理数的集合，关于数的乘法 [D] 实数集，关于数的除法
5、半群、群及独异点的关系是（ ）。 [A] {群}?{独异点}?{半群} [B] {独异点}?{半群}?{群} [C] {独异点}?{群}?{半群}
[D] {半群}?{群}?{独异点}
6、设,G 是群，则对任意的,,a b c G ∈，下列关于群的性质中不正确的是（ ）。 [A] 方程有唯一解1
.x a b -= [B] 方程有唯一解1
.y b a -= [C] 如果,则有
[D] 1
11(.)
.a b a b ---=
7、下列关于格说法不正确的是（ ）。 [A] {}0,1,2,3,4,max,min <>是格
[B] 设,a b 是格,,L <∨∧>中的元素，则有a b a a b b ∧=?∨= [C] 设集合{},,A a b c =，则{}{}{}{}
,,,,,,,,a a b a b c U I 是格 [D] 设,,,L <∨∧>是布尔代数，则,,L <∨∧>是格
8、设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>，<4，4>}，则R 的性质是 （ ）。 [A]自反、对称、传递的 [B]自反、对称、反对称的
[C]对称、反对称、传递的 [D]只有对称性 9、下列关于布尔代数说法不正确的是（ ）。
[A] 设集合{2,3,4,6,8,12,36,60}L =，L 上的偏序关系{,|,,|}a b a b L a b ρ=∈，则,L ρ是格
[B] 设集合,,,L <∨∧>是布尔代数，则对任意,a b L ∈有a b a b ∧=∨ [C] 设集合,,,L <∨∧>是布尔代数，则对任意,a b L ∈a b a b ∧=∨则a b = [D] 设集合,,,L <∨∧>是布尔代数，则对任意a L ∈都有b L ∈使得
1,0a b a b ∨=∧=
10、设A 为集合，则下列关于格2,,A
<>U I 元素的说法中不正确的是（ ）。 [A] 对于格中任意的元素B ，有B A p [B] 对于格中任意的元素B ，有B ?p
[C] 对于格中任意的元素,B C ，,B C 的最小上界为B C U [D] 不存在格中的元素B ，使得A B p
11、设{}0,1,2,3,4,5,6,7,8,9A =，则下列关于格2,,A
<>U I 元素的说法中正确的是
（ ）。
[A] {}{}1,2,3,42,3,4,5,6p [B] {}{}0,3,4,5,62,3,4,5p [C] {}{}1,2,3,40,2,3,4,1p [D] {}{}1,2,3,40,2,3,4,11p 12、设,,,L <∨∧>是布尔代数，,a b L ∈，则下列说法中错误的是（ ）。 [A] 1a a ∧= [B] 1a a ∨= [C] 0a a ∧= [D] 1a a ∨= 13、下列关于图说法正确的是（ ）。 [A] 在图G 中,i j v v 的初级通路是,i j v v 的短程
[B] 完全图中任意两个点的距离为1 [C] n 阶完全图的边数不确定
[D] 在无向图中，初级回路不一定是简单回路
14、已知图G 有i 个i 度的结点（1,2,3,4i =），则图G 的边数为（ ）。 [A] 15 [B] 10 [C] 20 [D] 12
15、在右图中度数最大点的度数为（ ）。
[A] 3 [B] 2 [C] 4 [D] 5
二、【判断题】(本大题共8小题，每小题3分，共24分)正确的填T ，错误的填F ，填在答题卷相应题号处。
16、说所有人都爱吃面包是不对的。可符号化为：┐?x(F(x)→G(x)) 其中，F(x)：x 是人，G(x):x 爱吃面包。 （ ） 17、命题公式 ┐P ∨(Q→R)的成假赋值是110。 ( ) 18、一阶逻辑公式?x (F(x) →G(x,y))是闭式。 ( )
19、
()()(()()()()()()x y P x Q y x P x y Q y ??→??→? ( ) 20、设A={φ}，B = P （P （A ）），则有{φ}∈B ，且{φ}?B ( ) 21、设A ≠Φ，A 上的恒等关系I A 既是A 上的等价关系也是A 上的偏序关系。 ( ) 22、设A 、B 、C 为任意的三个集合，则笛卡尔积：A ×(B ×C)=A ×(B ×C)。 ( ) 23、设A={a ，b ，c}，R A A ??且R={，}，则R 是传递的。 ( )
三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分）请将
答案填写在答题卷相应题号处。
24、证明),,(Θ?Z 是环，其中Z 是整数集，运算Θ?,定义如下：
ab b a b a b a b a -+=?-+=Θ,1
25、在布尔代数(,,,∧∨B )中，对,,,B c b a ∈?有
)()()()(b c b a b c b a ∧∨∧=∨∧∨
26、试将下列公式化为析取范式和合取范式 （1）P ∧(P →Q ) （2）?(P ∨Q )?(P ∧Q )
《离散数学》模拟试卷三 答案
一、【单项选择题】(本大题共15小题，每小题3分，共45分)
二、【判断题】(本大题共8小题，每小题3分，共24分)
三、【解答题】（本大题共3小题，24、25每小题10分，26小题11分，共31分） 24、证明),,(Θ?Z 是环，其中Z 是整数集，运算Θ?,定义如下：
ab b a b a b a b a -+=?-+=Θ,
1
标准答案：证明 (Z ,Θ)是交换群.
证明：Z c b a ∈?,,，
)
()(21)1()(2
)1()(c b a c b a c b a c b a c b a c b a c b a c b a ΘΘ=ΘΘ∴
-++=--+Θ=ΘΘ-++=Θ-+=ΘΘ
显然有a b b a Θ=Θ
又11Θ==Θa a a ，即1是运算Θ的单位元.
)(11)2()2(,2,单位元有=--+=-Θ∈-∈?a a a a Z a Z a ，即2－a 是a 关于
运算Θ的逆元. 所以，(Z ,Θ)是交换群.
复习范围或考核目标：考察代数系统中群的基本概念及性质，详见课件代数系统中群的基本概念和性质。
25、在布尔代数(,,,∧∨B )中，对,,,B c b a ∈?有
)()()()(b c b a b c b a ∧∨∧=∨∧∨
标准答案：证明：因为(,,,∧∨B )，故10条算律在其上成立，所以
)()()()()
)()(())(()()(b b b a c b c a b b a c b a b c b a ∧∨∧∨∧∨∧=∧∨∨∧∨=∨∧∨分配律
)
()()()()]()[())(()]
()[()(b a c b b c a b c a b a c b b b c a b a c b c a ∧∨∧∨∧∧∨∧∧=∧∨∧∨∨∧∧=∧∨∧∨∧=
)
()()()()(])[()]())([(b c b a b a c b b a c b a bc b c a ∧∨∧=∧∨∧=∧∨∧∧∨∧∨∧∧=
所以 )()()()(b c b a b c b a ∧∨∧=∨∧∨
复习范围或考核目标：考察对布尔代数基本概念和基本性质的应用，见见课件代数系统中布尔代数小节。
26、试将下列公式化为析取范式和合取范式 （1）P ∧(P →Q ) （2）?(P ∨Q )?(P ∧Q ) 标准答案：（1）P ∧(P →Q ) ＝P ∧(?P ∨Q ) （合取范式）
＝（P∧?P）∨（P∧Q）（析取范式）
（2）?(P∨Q)?(P∧Q)
＝（?(P∨Q) → (P∧Q)）∧（(P∧Q) →? (P∨Q)）
＝（(P∨Q) ∨(P∧Q)）∧（? (P∧Q)∨?(P∨Q)）
＝(P∨Q) ∧(?P∨?Q) （合取范式）
＝(?P∧P)∨(?P∧Q)∨(?Q∧P)∨(?Q∧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>}。
离散数学第五版 模拟试题 及答案
《离散数学》模拟试题3 一、填空题（每小题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. 已知命题公式R Q P G→ ∧ ? =) (，则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分） 1. （6分）设全集E＝N，有下列子集：A＝{1，2，8，10}，B＝{n|n2<50 ，n∈N}，C＝ {n|n可以被3整除，且n<20 ，n∈N}，D＝{n|2i，i<6且i、n∈N}，求下列集合：（1）A∪(C∩D) （2）A∩(B∪(C∩D)) （3）B－(A∩C) （4）(～A∩B) ∪D 2. （6分）设集合A＝{a, b, c}，A上二元关系R1，R2，R3分别为：R1＝A×A， R2 ＝{(a，a)，(b，b)}，R3 ＝{(a，a)}，试分别用 定义和矩阵运算求R1·R2 ，22R，R1·R2 ·R3 ， (R1·R2 ·R3 )－1 。 3.（6分）化简等价式（﹁P∧（﹁Q∧R））∨（Q∧R）∨（P∧R）. 4.(8分) 设集合A＝{1,2,3}，R为A上的二元关系，且 M R＝ 写出R的关系表达式，画出R的关系图并说明R的性质. 5. （10分）设公式G的真值表如下. 试叙述如何根据真值表求G的 主析取范式和主合取范式，并 写出G的主析取范式和主合取范式. 1 0 0 1 1 0 1 0 0
2离散数学模拟题
一、填空 1、 设p ：天气热，q ：他去游泳，则命题“如果天气热，则 他就去游泳”可符号化为 2、 设A={2，3，4，5，6}上的二元关系 }|,{是质数x y x y x R ∨<><=，则R= （列举法）。R 的关系矩阵M R = 。 3、设A={1，2，3}，则A 上既是对称的又是反对称的关系R= 。 4、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 5、 设A 为任意的命题公式，B 为重言式，则B A ∨的类型为 ； 二、选择 1、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 则R 具有（ ）性质。 A ．自反性、对称性、传递性； B ．反自反性、 反对称性；
C ．反自反性、反对称性、传递性； D ．自反性 。 2、在如下各图中（ ）欧拉图。 3. 设{}1,2,3A =，则A 上的二元关系有几个？（ ） A. 32 . B. 23 . C. 332? . D. 323?. 4．下列哪个命题是真命题？（ ） A ．我正在说谎. B. 若011=+，则雪是黑色的. C. 9518+>. D.存在最大的质数. 5. 下面四组数能构成无向简单图的度数列的有（ ）。 A 、（2，2，2，2，2）； B 、（1，1，2，2，3）； C 、（1，1，2，2，2）； D 、（0，1，3，3，3）。 三、计算 1、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。 2. 利用主析取范式，求公式R Q Q P ∧∧→?)(的类型。 3. 设A={1，2}，A 上所有函数的集合记为A A ,试给出A A 四、证明 1. 若无向图G 为欧拉图，证明G 中无桥.
离散数学试卷及答案一
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) ( 7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 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 的关系图为 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个 一、单项选择题（本大题共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 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ） A ．一定是等价关系 B ．一定是相容关系 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 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个 离散数学期末试题及答 案 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的补元( ). 《离散数学》课程试题(A)卷 课程代码： 080800111 本试卷适用理学系数学与应用数学专业和信息与计算科学专业 （时量：120分钟；总分为100分） 注 意： 1、所有答案和解答均应写在答题纸上，答在试卷上不记分 2、答案必须写明题目序号，并按题号顺序答题 3、请保持行距，保持卷面整洁 一、填空题：（每题3分，本大题共24分） 1．设}4,}3{,,2{a A =，}1,4,3,}{{a B =，请在下列每对集合中填入适当的符号：?∈, 。 （1）}{a B , (2) }}3{,4,{a A 。 2．设}1,0{=A ，N 为自然数集，???=是偶数。，是奇数， ，x x x f 10)( 若A A f →： ，则f 是 射的，若A N f →： ，则f 是 射的。 3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，2， 则G 中有 条边，根据 。 4．两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。 5．在一阶逻辑中将命题：凡对顶角都相等，符号化为_____________________。 6.集合A 有n 个元素，则A 上共有_____________________个既是对称又是反对称的的关系。 7. 连通简单无向图有17条边。则该图至少有_____________________个结点。 8. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没得优，那么两次考试都得优的学生的人数是_____________________。 二、单项选择题：（每小题3分，本大题共30分） 1．设}16{2<=x x x 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 是（ ）。 A 、}}{{Φ ； B 、}{Φ ； C 、}}{,{ΦΦ ； D 、Φ。 华南理工大学网络教育学院 2016–2017学年度第一学期期末考试 《 离散数学 》试卷（模拟卷） （客观题电脑给分，主观题依过程给分） 教学中心： 专业层次： 学 号： 姓 名： 座号： 注意事项：1. 本试卷共 三 大题，满分100分，考试时间90分钟，闭卷； 2. 考前请将以上各项信息填写清楚； 3. 所有答案必须做在答题纸上,做在试卷、草稿纸上无效； 4．考试结束，试卷、答题纸、草稿纸一并交回。 一、单项选择题（本大题30分，每小题6分） 1．设，P ：他聪明；Q ：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为：( ) A ．P ∧ Q B ．P → Q C ．P ∨ ?Q D ．P ∧?Q 【答案：A 】 2．下列式子( )是永真式 A ．Q →（P ∧ Q ） B ．P →（P ∧ Q ） C ．（P ∧ Q ）→ P D ．（P ∨Q ）→ Q 【答案：C 】 3．设S （x ）：x 是运动员，J （y ）：y 是教练员，L （x ，y ）：x 钦佩y 。命题“所有运动员都钦佩一些教练员”的符号化公式是( ) A ．?x （S （x ）∧ ? y （J （y ）∧ L （x ，y ））） B ．?x ?y （S （x ）→（J （y ）→ L （x ，y ））） C ．?x （S （x ）→ ?y （J （y ）∧ L （x ，y ））） D ．?y ?x （S （x ）→（J （y ）∧ L （x ，y ））） 【答案：C 】 4．下列命题是真的是( ) 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 【答案：D 】 5．设G 是n 有个结点，m 条边的简单有向图。若G 是连通的，则m 的下界是（ ） A ．n B ．1n - C ．()1n n - D ．()1 12 n n - 【答案：B 】 二、 判断题（本大题20分，每小题4分） 1. 设A ，B 是命题公式，则蕴涵等值式为A →B ??A ∧B 。 （ × ） 2、?x ?yA(x,y)? ?y ?xA(x,y) 。 （ × ） 模 拟 试 题 1 一．将下面命题写成符号表达式。(3,4题要使用句后给定的谓词。) 1.如果小张去，则小王与小李都不去，否则小王与小李不都去。 2.我们不能既划船又跑步。 3.有些运动员是大学生。(L(x)：x 是运动员；,S(x)：x 是大学生。) 4.每个运动员都钦佩一些教练。( L(x):x 是运动员，A(x,y):x 钦佩y ，J(x):x 是教练。) 二．写出命题公式 (Q →?P)→Q 的主合取范式。（要求有解题过程） 三．令集合A={1,{1}}, B={1}, P(A)表示A 的幂集 1.判断下面命题的真值。并说明原因，否则不给分。 (1) B ∈A, (2) P(B) ?P(A) (3) {Φ}?P(A) (4) {1}∈P(B) 2.分别计算: (1) A ×P(B) (2) A ⊕B (3) P(A)－P(B) 四．用谓词逻辑推理证明下面推理的有效性。 ?x(A(x)∧(B(x)→?C(x))), ?x(A(x) → (C(x) ∨?D(x))), ?x(A(x) →D(x)) ? ?x(A(x) ∧? B(x)) 五．令Ａ＝{1,2,3,4 }，给出Ａ中关系R 1,R 2,R 3, R 4如下： R 3={<1,2>,<2,2>,<1,3>,<2,4>,<1,1>,<1,4>, <3,3>,<4,4>} R 4={<2,2>,<3,2>,<4,1>,<2,1>,<1,4>,<2,3>,<2,4>,<1,2>,<3,3>,<3,4>, <4,2>,<4,4>,<4,3>,<1,1>} 1．求复合关系~R 4oR 2c 。 2．分别画出R 1、R 3、R 4关系的有向图。 3．分别指出上面各个关系是否具有自反性、反自反性、对称性、反对称性、传递性。 4．上述四个关系中，哪些是等价关系？哪些是偏序关系？哪些是从Ａ到Ａ的函数？如果是等价关系，请写出该等价关系的各个等价类。 如果是函数，请指出该函数的类型。 六．设I 是整数集合，在I 上定义二元运算 * 如下：对于任何a,b ∈I a *b=a+ b ＋4 求证 安徽大学20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 一、单项选择题（每小题2分，共20分） 1. 设:P 天没下雪，:Q 我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ D ） A.Q P ?→?； B. P Q ?→?； C.Q P ?∧； D. Q P ?∧?。 2.下列命题是重言式的是（ C ） A.)()(P Q Q P →∧→； B. )()(Q P P Q P ???∧； C. )(Q P Q P →→∧； D. Q P R Q P ∧?∧?∨→))((。 3. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 一、选择题（每小题只有一个正确答案，每题2分，共30分） 1、令A（x）:x是实数，B（x）:x是有理数，则命题：并非所有有理数都是实数。符号化为：（） A、x┐(A(x)∧B(x)) B、┐x(B(x)→A(x)) C、┐x(A(x)∧B(x)) D、┐x(B(x)∧┐A(x)) 2、设A={{1，2，3}，{4，5}，{6，7，8}}，则下列选项正确的是（） A、1∈A， B、φ∈A C、{1，2，3} A， D、{{4，5}} A 3、设A、B为集合，A-B=φ，则有（） A、B=φ B、B≠φ C、A B D、B A 4、一个连通有向图，如果它的每个结点的出度均等于入度，那么它有一条（）。 A、基本回路 B、欧拉回路 C、欧拉通路 D、简单回路 5、一棵树有2个结点度数为2，2个结点度数为3，3个结点度数为4，则它的树叶数为（） A、8 B、9 C、10 D、12 6、G是连通平面图，有5个顶点、6个面，则G的边数为（） A、6 B、5 C、11 D、9 7、设A={1，2，3}，B={1，2，3，4，5}，C={2，3}，则（A∪B）+C=（） A、{1，2} B、{2，3} C、{1，4，5} D、{1，2，3} 8、下列命题中为假的是（） A、{a，{b}}{{a，{b}}} B、φP(∪{φ,{φ}}) C、{a}XaX D、X∪Y=YX=φ 9、设解释T为：个体域为D={—2，3，6}，谓词A(x)：x 6，B(x)：x>5，则根据解释，公式x(A(x)∨B(x))的真值为（） A、0 B、1 C、没有确定真值 10、一个教室公用一个电源，如果想接34盏灯，则至少需要4个插线孔的接线板（）个。 A、10 B、11 C、12 D、34 11、下列说法错误的是（） A、n个结点m条边的有向树和无向树均满足：m=n－1. B、树都是二部图。 C、有向树都是单侧连通的 D、有桥的图不是欧拉图 一、 填空 1．不能再分解的命题称为，至少包含一个联结词的命题称为。 2．一个命题公式A(P , Q, R)为真的所有真值指派是000, 001, 010, 100，则其主析取范式是，其主合取范式是。 3．设 {}，{}，{}，则( A ? B ) ⊕C ＝ 。 4．幂集 P(P(?)) ＝ 。 5．设A 为任意集合，请填入适当运算符，使式子?；’=?成立。 6．设{0，1，2，3，6}，{〈〉≠y ∧(∈A)∧y≡x( 3)}，则D(R)，R(R)。 7．称集合S 是给定非空集合A 的覆盖：若{S 1，S 2，…，}，其中?，≠?，1，2，…，n ，且 ；进一步若 ，则S 是集合A 的划分。 8．两个重言式的析取是 式，一个重言式和一个永假式的合取式是 式。 9．公式 ┐(P ∨Q) ←→(P ∧Q)的主析取范式是 。 10. 已知Π={{a}{}}是{}的一个划分，由Π决定的A 上的一个等价关系是 。 二、 证明及求解 1．求命题公式（P →Q ）→（Q ∨P ）的主析取范式。 2．推理证明题 1）?P ∨Q ，?Q ∨R ，R →S ?P →S 。 2) (?x)(P(x)→Q(y)∧R(x))，(?x)P(x)?Q(y)∧(?x)(P(x)∧R(x)) 3．设{0，1，2，3}，{〈〉∈A ∧(1∨2x )}，{〈〉∈A ∧（2）}。试求οο。 4．证明：R 是传递的?R *R ?R 。 5．设R 是A 上的二元关系，{ 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 目录 离散数学模拟题一 (1) 离散数学模拟题二 (3) 离散数学模拟题三 (7) 离散数学模拟题四 (9) 离散数学模拟题五 (12) 离散数学模拟题六 (16) 离散数学模拟题七 (18) 离散数学模拟题八 (21) 离散数学模拟题九 (24) 离散数学模拟题十 (25) 离散数学模拟题十一 (27) 离散数学模拟题十二 (33) 离散数学模拟题十三 (34) 离散数学模拟题十四 (37) 离散数学模拟题十五 (42) 离散数学模拟题十六 (50) 离散数学模拟题一 一、判断题（共12分，每小题1分） ( ) 1、（?p∨?q）→(p→?q)不是重言式。 ( )2、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。 ( ) 3、命题函数是命题。 ( ) 4、设A，B，C是Q的子集，则有A?(B⊕C)≠（A?B）⊕（A?C）。 ( )5、设A、B为集合，若B≠Φ，则A-B包含于A。 ( ) 6、若R为集合A上的非对称关系，则R2亦然。 ( )7、存在一种建立在某个集合上的关系，它可以是对称的、反对称的、自反的、反自反和可传递的。 ( )8、设〈G，*〉是群，对于G中的任意元素a，b有：（a ? b）-1=b-1 ? a-1。 ( )9、在一个代数系统中，某个元素有多个左逆元，就不可能有右逆元。 ( )10、设是非连通平面图G的对偶图中的顶点数，边数和面数，则它们之间不满足欧拉公式； ( )11、设无向图G具有割点，则G中一定不存在汉密尔顿回路； ( )12、有向图G是单侧连通； （G） 二、求出下列命题公式的主析取范式和主合取范式。（10分） (P→(Q∧R))∧(?P→(?Q∧R)) 三、逻辑推证（10分） （1）?（P→Q）→? (R∨S)，((Q→P) ∨?R) ，?(R→P) ? P→Q 四、用谓词推理理论来论证下述推证（10分） 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行。 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 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 ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、? ； C 、∈ ； D 、? 。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=* ； B 、),max(b a b a =* ； C 、b a b a 5+=* ； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则离散数学模拟题(开卷)
离散数学试卷及答案(2)
离散数学模拟试卷和答案
自考离散数学试题及答案
离散数学模拟试卷和答案
离散数学期末试题及答案完整版
离散数学模拟卷(简单)
离散数学试题2018模拟1+答案
离散数学模拟题1
《离散数学》(上)试卷(A卷)及参考答案
离散数学模拟试题1
离散数学模拟题及答案
离散数学试卷及答案(17)
离散数学模拟试卷(中文)
离散数学试卷及答案7
的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。