北邮函授考试离散数学期末考试复习题_2015秋

..一、填空2．A ，B ，C 表示三个会合，文图中暗影部分的会合表达式为 (B⊕C)-AA C4．公式(PR)(SR)P的主合取范式为(PSR) ( PS R)。

5．若解说I 的论域D 仅包括一个元素，则 xP(x) xP(x) 在I 下真值为 1 。

6．设A={1，2，3，4}，A 上关系图以下，则 R^2={(1,1),(1,3),(2,2),(2,4)}。

//备注： 0 1 0 01 0 1 0 0 1 0 1R 1 0 1 0 R 20 0 0 1 0 0 0 00 0 0 00 0 0 07．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图以下，则R={(a,b),(a,c),(a,d),(b,d),(c,d)}U{(a,a),(b,b)(c,c)(d,d)}。

备注：偏序知足自反性，反对称性，传达性8．图 的补图为 。

//补图:给定一个图G,又G 中全部结点和全部能使 G 成为完整图的增添边构成的图,成为补图. 自补图:一个图假如同构于它的补图,则是自补图 9．设A={a ，b ，c ，d}，A 上二元运算以下：* a b c da abcd b b c d a ccdabd d a b c那么代数系统<A ，*>的幺元是 a ，有逆元的元素为a,b,c,d，它们的逆元分别为a,b,c,d 。

//备注：二元运算为 x*y=max{x,y}，x,y A 。

10．以下图所示的偏序集中，是格的为 c。

//（注：什么是格？即随意两个元素有最小上界 和最大 下界的偏序）二、选择题 1、以下是真命题的有（ C 、D ）A ．{a} {{a}}；B ．{{}} { ,{}}；C ．{{}, }； D ．{} {{ }}。

2、以下会合中相等的有（ B 、C ）A ．{4，3} ；B ．{ ，3，4}；C ．{4， ，3，3}；D ．{3，4}。

;....3、设A={1，2，3}，则A 上的二元关系有（ C ）个。

一、选择题：1．命题公式 )()(P Q Q P ∨⌝→→⌝ 中极小项的个数为（ ）。

A ．0B ．1C ．2D ．32．设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。

A ．3B ．6C ．7D ．83．设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为，则R 具有（ ）性质。

A ．自反性、对称性、传递性B ．反自反性、反对称性C ．反自反性、反对称性、传递性D ．自反性4．设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系如下|}||(|)(,|,{t s A P t s t s R =∧∈><=，则R A P |)(=（ ）A ．AB ．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}C ．P(A)D ．{[{1}]，[{1，2}]，[{1，2，3}]，[{1，2，3，4}]}5．下列函数是双射的为（ ）A ．f : I →E , f (x) = 2xB ．f : N →N ⨯N, f (n) = <n , n+1>C ．f : R →I , f (x) = [x]D ．f :I →N, f (x) = | x |（注：I —整数集，E —偶数集， N —自然数集，R —实数集）6．在下列代数系统中，不是环的只有（ ）A ．>•+<,,Z ，其中Z 为整数集，+，• 分别为整数加法和乘法。

B. >•+<,,Q ，其中Q 为有理数集，+，• 分别为有理数加法和乘法。

C . >•+<,,R ，其中R 为实数集，+为实数加法，b a b a 2+=•。

D. >•+<,),(R M n ，其中)(R M n 为n 阶实数矩阵集，+，• 分别为矩阵加法和乘法。

7．设 * 是有理数集Q 上的运算，定义为ab b a b a -+=*，则*的单位元为：（ ）A ．1 B.2 C .0 D. -18．设群>⊕=<}),,({b a P G ，其中⊕为集合的对称差运算，则方程}{},{b b a X =⊕的解为：（ ）A. },{b a B . }{a C. Φ D.}{b9．极大平面图G 中有r 个面，n 个顶点，m 条边，则它每个面的次数为：_________A. rB. nC. m D . 310．一棵树有7片树叶，3个3度顶点，其余的都是4度顶点，则该树有_________个4度顶点。

北邮离散数学期末复习题 第一章集合论 一、判断题（1）空集是任何集合的真子集． （ 错 ）（2）{}φ是空集． （ 错 ） （3）{}{}a a a },{∈ （ 对 ） （4）设集合{}{}{}{}AA 22,1,2,1,2,1⊆=则. ( 对 ） （5）如果B A a ⋃∉，则A a ∉或B a ∉． （ 错 ）解 B A a ⋃∉则B A B A a ⋂=⋃∈，即A a ∈且B a ∈，所以A a ∉且B a ∉（6）如果A ∪.,B A B B ⊆=则 （ 对 ）（7）设集合},,{321a a a A =，},,{321b b b B =，则},,,,,{332211><><><=⨯b a b a b a B A （ 错 ）（8）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A2到A 的关系． （ 对 ）解 A 2}},1{},0{,{A φ=， =⨯A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><><A A φφ（9）关系的复合运算满足交换律． （ 错 ）（10）.条件具有传递性的充分必要上的关系是集合ρρρρA =ο （ 错 ）（11）设.~,上的传递关系也是则上的传递关系是集合A A ρρ ( 对 ) （12）集合A 上的对称关系必不是反对称的. （ 错 ）（13）设21,ρρ为集合A 上的等价关系, 则21ρρ⋂也是集合A 上的等价关系( 对 )（14）设ρ是集合A 上的等价关系, 则当ρ>∈<b a ,时， ρρ][][b a = ( 对 )（15）设21,ρρ为集合 A 上的等价关系, 则 ( 错 )二、单项选择题（1）设R 为实数集合，下列集合中哪一个不是空集 （ A ）A. {}R x x x ∈=-且,01|2 B ．{}R x x x ∈=+且,09|2C. {}R x x x x ∈+=且,1|D. {}R x x x ∈-=且,1|2（2）设B A ,为集合，若φ=B A \，则一定有 （ C ）A. φ=B B ．φ≠B C. B A ⊆ D. B A ⊇（3）下列各式中不正确的是 （ C ）A. φφ⊆ B ．{}φφ∈ C. φφ⊂ D. {}}{,φφφ∈ （4）设{}}{,a a A =，则下列各式中错误的是 （ B ）A. {}A a 2∈ B ．{}A a 2⊆ C. {}A a 2}{∈ D. {}Aa 2}{⊆ （5）设{}2,1=A ，{}c b a B ,,=，{}d c C ,=，则)(C B A I ⨯为 （ B ） A. {}><><c c ,2,1, B ．{}><><c c ,2,,1C. {}><><2,,,1c cD. {}><><2,,1,c c（6）设{}b A ,0=，{}3,,1b B =，则B A Y 的恒等关系为 （ A ） A. {}><><><><3,3,,,1,1,0,0b b B ．{}><><><3,3,1,1,0,0C. {}><><><3,3,,,0,0b bD. {}><><><><0,3,3,,,1,1,0b b（7）设{}c b a A ,,=上的二元关系如下，则具有传递性的为 （ D ）A. {}><><><><=a b b a a c c a ,,,,,,,1ρB ． {}><><=a c c a ,,,2ρC. {}><><><><=c b a b c c b a ,,,,,,,3ρD. {}><=a a ,4ρ（8）设ρ为集合A 上的等价关系，对任意A a ∈，其等价类[]ρa 为 （ B ）A. 空集； B ．非空集； C. 是否为空集不能确定； D. }|{A x x ∈.（9）映射的复合运算满足 （ B ）A. 交换律 B ．结合律 C. 幂等律 D. 分配律（10）设A ，B 是集合，则下列说法中（ C ）是正确的.A ．A 到B 的关系都是A 到B 的映射B ．A 到B 的映射都是可逆的C ．A 到B 的双射都是可逆的D ．B A ⊂时必不存在A 到B 的双射（11）设A 是集合，则（ B ）成立.A ．A A #22#=B ．A X X A⊆↔∈2 C ．{}A2∈φ D ．{}AA 2∈ （12）设A 是有限集（n A =#），则A 上既是≤又是～的关系共有（B ）.A ．0个B ．1个C ．2个D ．n 个三、填空题1. 设}}2,1{,2,1{=A ，则=A2____________.填}}},2,1{,2{}},2,1{,1{},2,1{}},2,1{{},2{},1{,{2A A φ=2.设}}{,{φφ=A ，则A 2= . 填}}},{{},{,{2A A φφφ=3.设集合B A ,中元素的个数分别为5#=A ，7#=B ，且9)(#=⋃B A ，则集合B A ⋂中元素的个数=⋂)(#B A .34.设集合}4,1001|{Z x x x x A ∈≤≤=的倍数，是，}5,1001|{Z x x x x B ∈≤≤=的倍数，是，则B A Y 中元素的个数为 .405.设 },{b a A =, ρ 是 A2 上的包含于关系，,则有ρ= .},,},{,}{},{,},{,}{},{,,,}{,,}{,,,{><><><><><><><><><A A A b b b A a a a A b a φφφφφ6.设21,ρρ为集合 A 上的二元关系, 则=21ρρο .~1~2ρρο7.集合A 上的二元关系ρ为传递的充分必要条件是 ．ρρρ⊆ο8. 设集合{}{}><><==0,2,2,02,1,01ρ上的关系A 及集合A 到集合{}4,2,0=B 的关系=2ρ｛><b a ,|><b a ,A b a B A ∈⨯∈,且∩}=21,ρρο则B ___________________.填 }2,2,0,2,2,0,0,0{><><><><四、解答题1. 设 A d c b a A },,,,{=上的关系 },,,,,,,,,,,,,,,{><><><><><><><><=c d d c a b b a d d c c b b a a ρ（1）写出ρ的关系矩阵；（2）验证ρ是A 上的等价关系；（3）求出A 的各元素的等价类。

《失散数学》试题及答案一、选择或填空（数理逻辑部分）1、以下哪些公式为永真包含式？()(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），（5），（6）4、公式 x((A(x) B(y ，x))z C(y ，z)) D(x) 中，自由变元是 ( )，拘束变元是( )。

答： x,y,x,z5、判断以下语句能否是命题。

假如，给出命题的真值。

()(1)北京是中华人民共和国的国都。

(2)陕西师大是一座工厂。

(3)你喜爱唱歌吗？(4)若 7+8＞18，则三角形有 4 条边。

(5)行进！(6)给我一杯水吧！答：（ 1）是， T（2）是， F（3）不是（4）是， T（5）不是（6）不是6、命题“存在一些人是大学生”的否认是()，而命题“所有的人都是要死的”的否认是 ()。

答：所有人都不是大学生，有些人不会死7、设 P：我患病， Q：我去学校，则以下命题可符号化为( )。

(1)只有在患病时，我才不去学校 (2) 若我患病，则我不去学校(3)当且仅当我患病时，我才不去学校 (4) 若我不患病，则我必定去学校答：（1）Q P（2）P Q（3）P Q（4）P Q8、设个体域为整数集，则以下公式的意义是( )。

(1)x y(x+y=0) (2)y x(x+y=0)答：（ 1）对任一整数 x 存在整数 y 知足 x+y=0（ 2）存在整数 y 对任一整数 x 知足 x+y=0 9、设全体域 D是正整数会合，确立以下命题的真值：(1)x y (xy=y)()(2)x y(x+y=y)()(3)x y(x+y=x)()(4)x y(y=2x)()答：（ 1） F（2） F（3）F（4）T10、设谓词 P(x) ： x是奇数， Q(x) ：x 是偶数，谓词公式x(P(x) Q(x)) 在哪个个体域中为真 ?()(1) 自然数(2)实数(3)复数(4) (1)--(3)均建立答：（ 1）11、命题“ 2 是偶数或 -3 是负数”的否认是（）。

离散数学期末考试试题(配答案)1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。

2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____；=A _____；=B A Y __ _____3. 设{}{}b a B c b a A ,,,,==；则=-)()(B A ρρ__ __________；=-)()(A B ρρ_____ ______。

二．选择题（每小题2分；共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=；A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。

（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ；求)(),(),(R t R s R r 的关系矩阵；并画出R ；)(),(),(R t R s R r 的关系图。

（10分）5. 试判断),(≤z 是否为格？说明理由。

（5分）（注：什么是格？Z 是整数；格：任两个元素；有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。

（10分）2. 设R 是实数集；b a b a f R R R f +=→⨯),(,:；ab b a g R R R g =→⨯),(,:。

求证：g f 和都是满射；但不是单射。

（10分）一；1； _ ∃x ∃y¬P(x)∨Q(y)2； {2} {4；5} {1；3；4；5}3； {{c}；{a ；c}；{b ；c}；{a ；b ；c}} Φ_ 二；B D三；解：主合取方式：p ∧q ∨r ⇔(p ∨q ∨r)∧(p ∨¬q ∨r)∧(¬p ∨q ∨r)= ∏0.2.4主析取范式：p ∧q ∨r ⇔(p ∧q ∧r) ∨(p ∧q ∧¬r) ∨(¬p ∧q ∧r) ∨(¬p ∧¬q ∧r) ∨(p ∧¬q ∧r)= ∑1.3.5.6.7 四；1；证明：编号 公式 依据 （1） （¬B∨C ）∧¬C 前提 （2） ¬B∨C ；¬C （1） （3） ¬B （2） （4） A →B （3） （5） ¬A （3）（4） （6） ¬（¬A∧D ） 前提 （7） A ∨¬D （6） （8）¬D （5）（6）2；证明：要证f 是满射；即∀y ∈R ；都存在（x1；x2）∈R ×R ；使f （x1；x2）=y ；而f （x1；x2）=x1+x2；可取x1=0；x2=y ；即证得；再证g 是满射；即∀y ∈R ；；都存在（x1；x2）∈R ×R ；使g （x1；x2）=y ；而g （x1；x2）=x1x2；可取x1=1；x2=y ；即证得；最后证f 不是单射；f （x1；x2）=f （x2；x1）取x1≠x2；即证得；同理：g （x1；x2）=g （x2；x1）；取x1≠x2；即证得。

离散数学考试题及答案一、选择题1. 关于图论的基本概念，以下哪个说法是正确的？A. 无向图中的边无方向性，有向图中的边有方向性。

B. 有向图中的边无方向性，无向图中的边有方向性。

C. 无向图和有向图都是由顶点和边组成的。

D. 无向图和有向图都只由边组成。

答案：A2. “若顶点集合为V，边集合为E，那么图G可以表示为G(V, E)”是关于图的哪个基本概念的描述？A. 图的顶点B. 图的边C. 图的邻接D. 图的表示方法答案：D3. 以下哪个命题是正确的？A. 若集合A和B互相包含，则A和B相等。

B. 若集合A和B相交为空集，则A和B相等。

C. 若集合A和B相等，则A和B互相包含。

D. 若集合A和B相等，则A和B相交为空集。

答案：C二、填空题1. 有一个集合A = {1, 2, 3, 4}，则集合A的幂集的元素个数为__________。

答案：162. 设A = {a, b, c}，B = {c, d, e}，则集合A和B的笛卡尔积为__________。

答案：{(a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, c), (c, d), (c, e)}3. 若p为真命题，q、r为假命题，则合取范式(p ∨ q ∨ r)的值为__________。

答案：真三、计算题1. 计算集合A = {1, 2, 3, 4}和集合B = {3, 4, 5, 6}的交集、并集和差集。

答案：交集：{3, 4}并集：{1, 2, 3, 4, 5, 6}差集：{1, 2}2. 计算下列命题的真值：(~p ∨ q) ∧ (p ∨ ~q)，其中p为真命题，q为假命题。

答案：真四、证明题证明：对于任意集合A和B，如果A和B互相包含，则A和B相等。

证明过程：假设A和B互相包含，即A包含于B且B包含于A。

设x为集合A中的任意元素，则x也必然存在于集合B中，即x属于B。

同理，对于集合B中的任意元素y，y也属于集合A。

离散数学期末试卷一、选择题（共10题，每题2分，共20分）1.下列哪个是真值？–[ ] A. $P \\vee \\sim P$–[ ] B. $P \\wedge \\sim P$–[ ] C. $P \\rightarrow \\sim P$–[ ] D. $P \\leftrightarrow \\sim P$2.下列哪个式子是永真式？–[ ] A. $(P \\rightarrow Q) \\wedge (Q \\rightarrow P)$–[ ] B. $(P \\rightarrow Q) \\vee (Q\\rightarrow P)$–[ ] C. $(P \\wedge \\sim P) \\vee (Q \\wedge \\sim Q)$–[ ] D. $(P \\rightarrow Q) \\rightarrow (Q \\rightarrow P)$3.下列集合中的哪个是无穷集合？–[ ] A. $\\{1, 2, 3\\}$–[ ] B. $\\{1, 2, 3, ...\\}$–[ ] C. $\\{\\emptyset\\}$–[ ] D. $\\{\\emptyset, \\{1\\}, \\{2\\}\\}$4.对于集合$A = \\{1, 2, 3\\}$和$B = \\{3, 4, 5\\}$，下面哪个选项是$A \\cap B$？–[ ] A. $\\{1, 2\\}$–[ ] B. $\\{2, 4\\}$–[ ] C. $\\{3\\}$–[ ] D. $\\{1, 3\\}$5.对于集合$A = \\{1, 2, 3\\}$和$B = \\{3, 4, 5\\}$，下面哪个选项是$A \\cup B$？–[ ] A. $\\{1, 2, 4, 5\\}$–[ ] B. $\\{\\emptyset\\}$–[ ] C. $\\{1, 2, 3, 4, 5\\}$–[ ] D. $\\{1, 3\\}$6.哪个选项是集合$A = \\{2, 4, 6, 8, 10\\}$的幂集？–[ ] A. $\\{2, 4, 6, 8, 10\\}$–[ ] B. $\\{2, 4, 6, 8, 10, \\{\\}\\}$–[ ] C. $\\{\\{2\\}, \\{4\\}, \\{6\\}, \\{8\\},\\{10\\}, \\{2, 4\\}, \\{2, 6\\}, \\{2, 8\\}, \\{2, 10\\}, \\{4, 6\\}, \\{4, 8\\}, \\{4, 10\\}, \\{6, 8\\}, \\{6,10\\}, \\{8, 10\\}, \\{2, 4, 6\\}, \\{2, 4, 8\\}, \\{2, 4, 10\\}, \\{2, 6, 8\\}, \\{2, 6, 10\\}, \\{2, 8, 10\\}, \\{4, 6, 8\\}, \\{4, 6, 10\\}, \\{4, 8, 10\\}, \\{6, 8, 10\\},\\{2, 4, 6, 8\\}, \\{2, 4, 6, 10\\}, \\{2, 4, 8, 10\\}, \\{2, 6, 8, 10\\}, \\{4, 6, 8, 10\\}, \\{2, 4, 6, 8, 10\\}\\}$–[ ] D. $\\{\\{\\}, \\{2\\}, \\{4\\}, \\{6\\},\\{8\\}, \\{10\\}, \\{2, 4\\}, \\{2, 6\\}, \\{2, 8\\},\\{2, 10\\}, \\{4, 6\\}, \\{4, 8\\}, \\{4, 10\\}, \\{6,8\\}, \\{6, 10\\}, \\{8, 10\\}, \\{2, 4, 6\\}, \\{2, 4,8\\}, \\{2, 4, 10\\}, \\{2, 6, 8\\}, \\{2, 6, 10\\}, \\{2, 8, 10\\}, \\{4, 6, 8\\}, \\{4, 6, 10\\}, \\{4, 8, 10\\},\\{6, 8, 10\\}, \\{2, 4, 6, 8\\}, \\{2, 4, 6, 10\\}, \\{2, 4, 8, 10\\}, \\{2, 6, 8, 10\\}, \\{4, 6, 8, 10\\}, \\{2, 4, 6, 8, 10\\}\\}$7.下列哪个命题是正确的？–[ ] A. 如果x>10，则x>5–[ ] B. 如果x>5，则x>10–[ ] C. 如果x>10，则x<5–[ ] D. 如果x<5，则x>108.哪个选项是命题$P: (P \\rightarrow Q) \\wedgeP$的否定？–[ ] A. $\\sim P \\rightarrow (\\sim Q \\vee \\sim P)$–[ ] B. $(P \\rightarrow \\sim Q) \\vee P$–[ ] C. $(P \\rightarrow Q) \\wedge \\sim P$–[ ] D. $Q \\rightarrow P$9.对于命题$P: (x > 5) \\wedge (y < 10)$，下列哪个选项是x与$Q: (x < 2) \\vee (y > 8)$的合取式？–[ ] A. $(x > 5) \\wedge (y < 10) \\vee (x < 2) \\vee (y > 8)$–[ ] B. $(x > 5) \\vee (y < 10) \\wedge (x < 2) \\vee (y > 8)$–[ ] C. $(x > 5) \\vee (y < 10) \\vee (x < 2) \\wedge (y > 8)$–[ ] D. $(x > 5) \\vee (x < 2) \\vee (y < 10) \\vee (y > 8)$10.下列哪个命题是等价的？–[ ] A. $P \\rightarrow Q$–[ ] B. $\\sim P \\vee Q$–[ ] C. $\\sim Q \\rightarrow \\sim P$–[ ] D. $P \\wedge \\sim Q$二、填空题（共5题，每题4分，共20分）1.集合$\\{x | x > 0\\}$的基数是\\\\\\。

一．填空题（每小题2分，共10分)1。

谓词公式)()(x xQ x xP ∃→∀的前束范式是__ ∃x ∃y¬P(x ）∨Q(y ） __________. 2。

设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =__{2}__，=A _{4,5}____,=B A __ ｛1，3，4,5｝ _____3。

设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ {{c},｛a ，c}，｛b ，c ｝,｛a,b ，c}｝ __________,=-)()(A B ρρ_____Φ_______.4。

在代数系统(N,+）中，其单位元是0，仅有 1 有逆元. 5．如果连通平面图G 有n 个顶点，e 条边,则G 有___e+2—n ____个面。

二．选择题（每小题2分,共10分）1. 与命题公式)(R Q P →→等价的公式是( ）（A ）R Q P →∨)( （B)R Q P →∧)( (C ）)(R Q P ∧→ （D ）)(R Q P ∨→2. 设集合{}c b a A ,,=，A 上的二元关系{}><><=b b a a R ,,,不具备关系( ）性质 （A ） （A ）传递性 （B)反对称性 (C)对称性 (D)自反性3. 在图>=<E V G ,中，结点总度数与边数的关系是（ ) （A)E v i 2)deg(= (B) E v i =)deg((C ）∑∈=Vv iE v 2)deg(（D ） ∑∈=Vv iE v )deg(4。

设D 是有n 个结点的有向完全图，则图D 的边数为( ) （A))1(-n n （B))1(+n n (C)2/)1(+n n (D ）2/)1(-n n 5. 无向图G 是欧拉图，当且仅当( ）(A) G 的所有结点的度数都是偶数 （B)G 的所有结点的度数都是奇数（C ）G 连通且所有结点的度数都是偶数 (D) G 连通且G 的所有结点度数都是奇数。

《离散数学》试题及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(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），（5），（6）4、公式?x((A(x)?B(y，x))??z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z5、判断下列语句是不是命题。

若是，给出命题的真值。

( ) (1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） P Q →⌝ （2） Q P ⌝→ （3） Q P ⌝↔ （4）Q P →⌝8、设个体域为整数集，则下列公式的意义是( )。

(1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0)答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=09、设全体域D 是正整数集合，确定下列命题的真值：(1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( )(3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( )答：（1） F （2） F （3）F （4）T10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 ?x(P(x)?Q(x))在哪个个体域中为真?( )(1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（ ）。

冑散数学试题(B卷篆亲U一、证明题(10分)1)(「P/\ J Q/\R) ) V (Q/\R) V (PAR)oRiW：左端n(-P/\-QAR) V((QVP) AR)<^>((_PA-fi)AR))V( (QVP) AR)o(-1(PVQ)AR)V((QVP)AR)o(-WQ)V(QVP))ARoJGVQ)\/(P\/Q))ARoTAR(l^)62)3x (A(X)T B(X))O V X A(X)^3X B(X):3X(A(X)T B(X))U3X(-A(X) VB(x))<^x-A(x) V2xB(x)<^=>-iVxA(x) \/3}£(x)oVxA (x)—>3xB (x)二、求命题公式(PV(QAR))^(PAQAR)的主析取范式和主合取范式(10分)。

证明：(PV(QAR))^(PAQAR)<»-(PV(QAR))V(PAQAR))O (^PA(-nQV^R)) V(PAQAR)o JP/\「Q)v (-PA^R)) V (PAQAR)o(「P/\「QAR)v (-nPA-QA^R) V (-nP AQ A-R)) V (-.PA-nQ A^R)) V (PAQAR)<=>moVmi VmzVmT^M O VM^VM B VM G三、推理证明题(10分)1) CVD, (CVD)T「E, 「E T(A/\「B), (AA-nB)-^(RVS)=>RVS证明：(1) (CVD)T「E P(2)「E T(A/UB) P(3) (CVD)^(AA-nB) T(l)(2), I(4) (AA^B)^(RVS) p(5) (CVD)T(RVS) T⑶⑷，I(6) CVD p(7) RVS T(5), I2) Vx(P(x)TQ(y) AR(x)), 3xP (x) =>Q (y) A 3x (P (x) A R (x))证明(l)3xP(x) P(2)P(a)(3)Vx(P(x)TQ(y)AR(x))(4)P(a)^Q(y) AR(a)(5)Q(y) AR(a)(6)Q(y)(7)R(a)(8)P(a) AR(a)(9)3x(P(x)AR(x))(10)Q(y) A3x(P(x) AR(x)) T ⑴,ESPT(3), UST⑵⑷，IT(5), IT(5), IT(2) (7), IT(8), EGT(6) (9), I四、某班有25需学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5 人会打篮球和网球，还有2人会打这三种球。

离散数学试题(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(置换)⇔R2) ∃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)，I2) ∀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人会打这三种球。

离散数学考试试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个选项表示“属于”关系？A. ⊆B. ⊂C. ∈D. ⊇答案：C2. 以下哪个命题是真命题？A. p ∧ ¬pB. p ∨ ¬pC. p → ¬pD. ¬(p → q) → p答案：B3. 以下哪个选项是命题逻辑中的德摩根定律？A. ¬(p ∨ q) = ¬p ∧ ¬qB. ¬(p ∧ q) = ¬p ∨ ¬qC. ¬(p → q) = p ∧ ¬qD. ¬(p ∨ q) = ¬p ∨ ¬q答案：A4. 以下哪个选项是命题逻辑中的蕴含等价？A. p → q ≡ ¬p ∨ qB. p → q ≡ ¬q → ¬pC. p → q ≡ p ∨ ¬qD. p → q ≡ ¬p ∧ q答案：A5. 以下哪个选项是关系的性质？A. 反身性B. 对称性C. 传递性D. 所有选项都是答案：D6. 以下哪个选项是图论中的有向图？A. 无向图中的边没有方向B. 有向图中的边有方向C. 混合图中的边既有方向也有无方向D. 所有选项都是答案：B7. 在图论中，以下哪个选项是树的性质？A. 树是无环的B. 树是连通的C. 树是无向图D. 所有选项都是答案：D8. 以下哪个选项是布尔代数的基本运算？A. 与（AND）B. 或（OR）C. 非（NOT）D. 所有选项都是答案：D9. 以下哪个选项是组合数学中的排列？A. 从n个不同元素中取出m个元素的组合B. 从n个不同元素中取出m个元素的排列C. 从n个相同元素中取出m个元素的组合D. 从n个相同元素中取出m个元素的排列答案：B10. 以下哪个选项是集合论中的幂集？A. 一个集合的所有子集的集合B. 一个集合的所有真子集的集合C. 一个集合的所有超集的集合D. 一个集合的所有子集的个数答案：A二、简答题（每题10分，共30分）1. 简述命题逻辑中的等价命题是什么？答案：等价命题是指两个命题在所有可能的真值赋值下都具有相同真值的命题。

离散数学期末复习题第一章集合论一、判断题（1）空集是任何集合的真子集. （错）（2） {0}是空集. （错）（3）{a}e {{a},a}（对）（4）设集合A = {1,2,{1,2}},则{{1,2}}匸2".（对）（5）如果Au B f则A或agB.（错）解Au B则= 即ae A且awB,所以A且aG B（6）如果AU B = B,则AuB. （对）（7）设集合A = {a]9a2,a3} f B = {b},b2.b3],贝!）AxB = {< a},h x >.< a2.b2 >.< a3.h3 >}（错）（8 ）设集合A = {0,1},贝9 p = {< ^0 >,< ^,1 >,< {0},0 >,< {0},l >}是2A至U A 的关系. （对）解2—{0,{0},{1},小, 2A X A={< 0,0 >,< 0,1 >,<{0},0 >,<{0},1 >,<{1},0 >,<{1},1 >,< A,0 >,< A,1 >}（9）关系的复合运算满足交换律. （错）（10）pop = p是集合A上的关系p具有传递性的充分必要条件.（错）（11）设Q是集合A上的传递关系，则0也是人上的传递关系. （对）（12）集合A上的对称关系必不是反对称的.（错）（13）设卩,/?2为集合A上的等价关系，则p、cp?也是集合A上的等价关系（对）（14）设。

是集合A上的等价关系，则当<a,b>w p时，[a]p =[h]p（对）（15）设卩，°2为集合人上的等价关系，则Q】°Q2=Q I°Q2（错）二、单项选择题（1）设7?为实数集合，下列集合中哪一个不是空集（A ）A. [x\x2 - I = 0,X XG R]B. {x|x2 + 9 = 0,M XG R]C. [x\x =兀 +1,且兀w R}D. [r| x2 = R](2)设A,B为集合，若A\B =(f),则一定有A. B =(/)B> B ^(/)C・ A c B D. Aq B(3)下列各式中不正确的是(C )A. 0 匸0B. 0w{©}C. 0 u 0D. 0w{0,{0}}(4)设A = {a y{a}},则下列各式中错误的是(B )A. {a}e 2AB. {a}^2AC. {{a}}e 2AD. {{«}}c2A(5)设A = {1,2}, B = {a, /?, c}, C = {c, d}f则Ax(BAC)为(B )A.{< c,l >, < 2, c >}B. {< l,c >, < 2,c >}C. {< 1, c >, v c2 >}D. {< c,l >, < c,2 >}(6)设A 二{0,b}, B = {1, ft, 3}，则AU B 的恒等关系为(A )A.{< 0,0 >, < 1,1 >,< b.b >, < 3,3 >}B. {< 0,0 >, < 1,1 >,< 3,3 >}C. {< 0,0 >,</?,/?>,< 3,3 >}D. {< 0,1 >, < l.b >,</?,3 >, < 3,0 >}(7)设A二{a,b,c}上的二元关系如下，则具有传递性的为(D )A.p、= {< a.c >, < c.a >,< a.b >,<b.a >}B.p2二{v Q,C >, V C,d >}C.p y- {< a.b >, < c,c>,< b.a >,< b.c >}D.p4={< a, a >}(8)设。