离散数学单项选择题习题(有答案)集(DOC)
单项选择题
第一章第二章
1. 下列表达式正确的有( )
A. Q Q P ? → ? ) (
B.P Q P ?∨ C .P Q P Q P ??∧∨∧)()( D.T Q P P ?→→)(
2. 下列推理步骤错在( )
①))()((x G x F x →?
P ②)()(y G y F →
US① ③)(x xF ?
P ④)(y F
ES③ ⑤)(y G
T②④I ⑥)(x xG ? EG⑤
A.②
B.④
C.⑤
D.⑥
3. 设P ：2×2=5，Q ：雪是黑的，R ：2×4=8，S ：太阳从东方升起，下列( )命题的真值为真。
A.R Q P ∧→
B.S P R ∧→
C.R Q S ∧→
D.)()(S Q R P ∧∨∧
4. 下列公式中哪些是永真式？( )
A.(┐P ∧Q )→(Q→?R)
B.P→(Q→Q)
C.(P ∧Q)→P
D.P→(P ∧Q)
5. 下列等价关系正确的是( )
A.)()())()((x xQ x xP x Q x P x ?∨??∨? B .)()())()((x xQ x xP x Q x P x ?∨??∨?
C.Q x xP Q x P x →??→?)())((
D.Q x xP Q x P x →??→?)())((
6. 下列推导错在( )
①)(y x y x >??
P ②)(y z y >?
US① ③z z >
ES② ④)(x x x >? UG③
A.②
B. ④ C . ③ D.无
7. 若公式)()(R P Q P ∧?∨∧的主析取范式为111110011001m m m m ∨∨∨则它的主合取范式为( )
A.111110011001m m m m ∧∧∧
B.101100010000M M M M ∧∧∧ ；
C.111110011001M M M M ∧∧∧
D.101100010000m m m m ∧∧∧ 。
8. 在下述公式中不是重言式为( )
A ．)()(Q P Q P ∨→∧
B ．))()(()(P Q Q P Q P →∧→??
C ．Q Q P ∧→?)(
D ．)(Q P P ∨→
9. 下列各式中哪个不成立( )
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 ∧??∧?)())((
10.命题“尽管有人聪明，但未必一切人都聪明”的符号化（P(x)：x 是聪明的，M(x)：x 是人）( )
A.)))()((())()((x P x M x x P x M x →??∧→?
B.)))()((())()((x P x M x x P x M x ∧??∧∧?
C.)))()((())()((x P x M x x P x M x →??∧∧?
D.)))()((())()((x P x M x x P x M x →??∨∧?
11.下述命题公式中，是重言式的为( )
A.)()(q p q p ∨→∧
B.q p ∨))()((p q q p →∨→?
C.q q p ∧→?)(
D.q q p →?∧)(
12.谓词公式)())()((x Q y yR x P x →?∨?中的x 是( )
A.自由变元
B.约束变元
C.既是自由变元又是约束变元
D.既不是自由变元又不是约束变元
13.命题“有的人喜欢所有的花”的逻辑符号化为( )
设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y
A. ))),()(()((y x H y F y x M x →?→?
B.))),()(()((y x H y F y x M x →?∧?
C. ))),()(()((y x H y F y x M x →?→?
D.))),()(()((y x H y F y x M x →?∧?
14.下列等价式成立的有( )
A.Q P Q P ?→??→
B.R R P P ?∧∨)(
C.Q Q P P ?→∧)(
D.R Q P R Q P →∧?→→)()(
15.给定公式)()(x xP x xP ?→?，当D={a,b}时，解释( )使该公式真值为0。
A.P(a)=0、P(b)=0 B .P(a)=0、P(b)=1 C.P(a)=1、P(b)=1
16.设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 ?∧??
17.下列语句是命题的有( )
A.明年中秋节的晚上是晴天
B.0>+y x
C.0>xy 当且仅当x 和y 都大于0
D.我正在说谎
18.下列公式是重言式的有( )
A.)(Q P ?? B .Q Q P →∧)( C.P P Q ∧→?)( D.P Q P ?→)(
19.下列集合中哪个是最小联结词集( )
A .},{→? B.{?, } C. {?, } D.},,{∨∧?
20.设L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩y ，命题“所有演员都钦佩某些老师”符号化为( )
A.)),()((y x A x L x →?
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 →∧??
21.下列各命题中真值为真的命题有( )
A.2+2=4当且仅当3是奇数
B.2+2=4当且仅当3不是奇数
C.2+2≠4当且仅当3是奇数
D.2+2=4仅当3不是奇数
22.命题逻辑演绎的CP 规则为( )
A.在推演过程中可随便使用前提
B.在推演过程中可随便使用前面演绎出的某些公式的逻辑结果
C .如果要演绎出的公式为C B →形式，那么将B 作为前提，演绎出C
D.设)(A Φ是含公式A 的命题公式，A B ?，则可用B 替换)(A Φ中的A
第三章
23.设A={1，2，3，4}，P （A ）（A 的幂集）上规定二元系|}||(|)(,|,{t s A p t s t s R =∧∈><=则P （A ）/ R=( )
A ．A
B ．P(A)
C ．{[Φ]R ，[{1}]R ，[{1，2}]R ，[{1，2，3}]R ，[{1，2，3，4}]R }
D ．{[Φ]R ，[2]R ，[2，3]R ，[2，3，4]R ，[A]R }
24.集合A={1,2,…,10}上的关系R={
A.自反的
B.对称的
C.传递的，对称的
D.传递的
25.集合A={1，2，3，4}上的偏序关系为，则它的Hass 图为( C )
26.设R ，S 是集合A 上的关系，则下列说法正确的是( )
A ．若R ，S 是自反的， 则S R 是自反的
B ．若R ，S 是反自反的， 则S R 是反自反的
C ．若R ，S 是对称的， 则S R 是对称的
D ．若R ，S 是传递的， 则S R 是传递的
27.Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确 ( )
A.A ?B ，B ?C 则A ?C
B.A ?B ，B ?C 则 A∈B
C.A∈B，B∈C 则 A∈C
28.设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“?”的哈斯图为( C )
29.设f ，g 是函数，当( C )时，f=g
A.)()( x g x f domf x =∈?都有
B. 的表达式相同与g f
C. g f domf domg ?? 且
D.rangef rangef domf domg ==,
30.设}}{,{,ΦΦ=Φ=B A ，则B －A 是( )
A.}}{{Φ
B.}{Φ
C.}}{,{ΦΦ
D.Φ
31.集合A={1，2，3，4}上的偏序关系图如下左，则它的哈斯图为( C )
32.设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系,
,
则由R 产生的S S ?上一个划分共有( B )个分块。
A ．4
B ．5
C ．6
D ．9
33.下列是真命题的有( )
A ． }}{{}{a a ?
B ．}},{{}}{{φφφ∈
C ．}},{{φφφ∈
D ．}}{{φφ∈
34.设B A S ??，下列各式中( B )是正确的
domS ?B B.domS ?A C.ranS ?A D.domS ? ranS = S
35.设} 3 ,2 ,1 {=S ，S 上关系R 的关系图如下 ，则R 具有( D )性质
A ．自反性、对称性、传递性
B ．反自反性、反对称性
C ．反自反性、反对称性、传递性
D ．自反性
36.设} |{是偶数或奇数
x x A =,)}2( |{y x I y y x B =∧∈?=,)}12( |{+=∧∈?=y x I y y x C , },4,4,3,3,2,2,1,1,0|{ ----=x D 下列相等的集合是( D )
A.A 的B
B.B 和C
C.C 和D
D.A 和D
37.设{}b a A ,=，则P （A ）×A = ( C)
A.A
B.P （A ）
C.{}><><><><><><>Φ<>Φ
D.{}><><><><><><>Φ<>Φ 38.A 是素数集合，B 是奇数集合，则A-B=( D ) A.素数集合 B.奇数集合 C.Φ D.{2} 39.设R 和S 是P 上的关系，P 是所有人的集合，},|,{的父亲是y x P y x y x R ∧∈><=， },|,{的母亲是y x P y x y x S ∧∈><=则1-S R 表示关系 ( A ) A.},|,{的丈夫是y x P y x y x ∧∈>< B.},|,{的孙子或孙女 是y x P y x y x ∧∈>< C.Φ D.},|,{的祖父或祖母 是y x P y x y x ∧∈>< 40.在自然数集N 上，（对任意N b a ∈,）下列( B)运算是可结合的 A.b a b a -=* B.),max(b a b a =* C.b a b a 5+=* D.b a b a -=* 41.Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ，则 A.a B.b C.1 D.0 42.公式),()),(),((y x xP z y Q y x P y x ?∧∨??换名( A ) A.),()),(),((y x xP z u Q u x P u x ?∧∨?? B.),()),(),((u x xP z u Q u x P y x ?∧∨??； C.),()),(),((u x xP z y Q y x P y x ?∧∨?? D.),()),(),((y u uP z y Q y u P y u ?∧∨??。 43.下面蕴涵关系不成立的是( C ) A.))()(()()(x Q x P x x xQ x xP ∨???∧? B.))()(()()(x Q x P x x xQ x xP →???→? C.))()(()()(x Q x P x x xQ x xP →???→? D.),(),(y x xA y y x yA x ????? 44.N 是自然数集，定义3mod )()( ,:x x f N N f =→（即x 除以3的余数）,则f 是(D) A.满射不是单射 B.单射不是满射 C.双射 D.不是单射也不是满射 45.集合A={2，3，6，12，24，36}上偏序关系R 的Hass 图为 则集合B={2，3，6，12}的上确界( ) B={2，3，6，12}的下界( ) C={6，12，24，36}的下确界( ) D={6，12，24，36}的上界( ) A. 12,无,6,36 B. 12,2,6,36 C. 12,2,12,36 D .12,无,6,无 46.下列哪个偏序集构成有界格( ) A.（N ，≤） B.（Z ，≥） C.（{2，3，4，6，12}，|（整除关系）） D .(P （A ），?) 47.六阶群的子群的阶数可以是( D) A.1，2，5 B.2，4 C.3，6，7 D.2，3 48.对右图，则)(),(),(G G G k δλ分别为( C ) A.2、2、1 B.1、1、2 C.1、1、1 D.1、2、2 49.一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有( A )个4度结点 A.1 B.2 C.3 D.4 50.具有6 个顶点，12条边的连通简单平面图中，每个面都是由( C )条边围成 A.2 B.4 C.3 D.5 51.设G 是有n 个结点m 条边的连通平面图，且有k 个面，则k 等于( A) A.m-n+2 B.n-m-2 C.n+m-2 D.m+n+2 52.下列哪个公式为永真式？( C ) A.?Q=>Q→P B.?Q=>P→Q C.P=>P→Q D.?P ∧(P ∨Q)=>P 53.“人总是要死的”谓词公式表示为( )（论域为全总个体域）M(x)：x 是人；Mortal(x)：x 是要死的 A.)()(x Mortal x M → B.)()(x Mortal x M ∧ C. ))()((x Mortal x M x ∧? D.))()((x Mortal x M x →? 54.设}}2,1{},1{,{Φ=S ，则有( A )S ? A.{{1,2}} B.{1,2 } C.{1} D.{2} 55.判断下列命题哪个正确？( B ) A.若A∪B＝A∪C，则B ＝C B.{a,b}={b,a} C.P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集） D.若A 为非空集，则A ≠A∪A 成立 56.下列结果正确的是( ) A.B A B A =-?)( B.Φ=-?A B A )( C.A B B A =?-)( D.Φ=Φ?Φ}{ 57.集合},2{N n x x A n ∈==对( )运算封闭 A. 乘法 B.减法 C. 加法 D.y x - 58.设I 为整数集合，m 是任意正整数，m Z 是由模m 的同余类组成的同余类集合，在m Z 上定义运算 ]mod )[(][][m j i j i ?=?，则代数系统>? A.封闭的代数系统 B.半群 C.独异点 D.群 59.设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于”关系，则 N b a ∈?,有=∨b a ( ) A.a B.b C.min(a ，b) D. max(a ，b) 60.一棵无向树T 有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T 中有( )片树叶 A.3 B.4 C.5 D.6 61.有向图D= A.0 B.1 C.2 D.3 62.设},,,,,{f e d c b a V =，},,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ，则有向图 >= A.强连通的 B.单侧连通的 C.弱连通的 D.不连通的 63.设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点 A.10 B.4 C.8 D.12 64.下列命题正确的是( C ) A.S S N N ∈∈∈2 ,2则 B.S N S Q Q N ?∈?则 , C.R N R Q Q N ???则 , D.S N S N ??Φ?Φ?Φ则 , 65.设A={a,{a}}，下列命题错误的是( B ) A.{a}∈P(A) B.{a}?P(A) C.{{a}}∈P(A) D.{{a}}?P(A) 66.设A={Φ} ，B=Р(Р(A)) 下列( )表达式不成立 A.B ?Φ B.{}B ?Φ C. B ?Φ D. {}{}B ∈Φ 67.设R ，S 是集合A 上的关系，则下列( )断言是正确的 A .S R ,自反的，则S R 是自反的 B.若S R ,对称的，则S R 是对称的 C.若S R ,传递的，则S R 是传递的 D.若S R ,反对称的，则S R 是反对称的 68.设P={x|(x+1)2≤4且x ∈R},Q={x|5≤x 2+16且x ∈R},则下列命题哪个正确( ) A.Q ?P B.Q ?P C.P ?Q D.P=Q 代数系统 69.),2(⊕=S G ，其中}3,2,1{=S ，⊕为集合对称差运算，则方程}3,1{}2,1{=⊕x 的解为( ) A. Φ B.}3,2,1{ C.}3,1{ D. }3,2{ 70.在有理数集Q 上定义的二元运算*，Q y x ∈?,有xy y x y x -+=*， 则Q 中满足( ) A. 1,≠∈?x Q x 时有逆元1-x B.只有唯一逆元 C. 所有元素都有逆元 D.所有元素都无逆元 71.设S={0，1}，*为普通乘法，则< S ， * >是( ) A.半群，但不是独异点 B.只是独异点，但不是群 C.群 D.环，但不是群 72.设A={1，2，…，10 }，则下面定义的运算*关于A 封闭的有( ) A.x*y=max(x ，y) B.x*y=质数p 的个数使得y p x ≤≤ C.x*y=gcd(x ， y) (gcd (x ，y)表示x 和y 的最大公约数) D.x*y=lcm(x ，y) （lcm(x ，y) 表示x 和y 的最小公倍数） 73.设[{a ， b ， c}，*]为代数系统，*运算如下： 则零元为( C) A.a B.b C.c D.没有 74.设>=< },2,1,0{1G ，>=<},*1,0{2G ，其中 表示模3加法，*表示模2乘法，在集合21G G ?上定义如下运算：,,,,21G G d c b a ?>∈<>*>=< A.<0，0> B.<0，1> C.<1，0> D.<1，1> 75.设R 是实数集合，“?”为普通乘法，则代数系统 A ．群 B ．独异点 C ．半群 76.设是一个格，由格诱导的代数系统为>∧∨<, , A ，则( )成立 A.的分配律对满足∧∨>∧∨<,,A B.b b a b a A b a =∨?≤∈?,, C.c b c a b a A c b a =∨=∨∈?则若 ,,, D.b b a a b b a a A b a =∨∧=∧∨∈?)( )(,,且有 77.设}4,4 1,3,31,2,21,1{=s ，*为普通乘法，则 A.代数系统 B.半群 C.群 D.都不是 78.设}4,4 1,3,31,2,21,1{=s ，*为普通乘法，则 79.在自然数集N 上，下列哪种运算是可结合的？( ) A.a*b=a-b B.a*b=max{a ，b} C.a*b=a+2b D.a*b=|a-b| 80.设≤><,A 是一个有界格，如果它也是有补格，只要满足( ) A. 每个元素都至少有一个补元 B. 每个元素都有多个补元 C.每个元素都无补元 D. 每个元素都有一个补元 81.具有如下定义的代数系统>*<,G ，( )不构成群 A.}10,1{=G ，*是模11乘 B.}9,5,4,3,1{=G ，*是模11乘 C.Q G =（有理数集），*是普通加法 D .Q G =（有理数集），*是普通乘法 82.在( )中，补元是唯一的 A.有界格 B.有补格 C.分配格 D.有补分配格 83.在布尔代数>-∧∨<,, , A 中，0=∧c b 当且仅当( ) A.c b ≤ B.b c ≤ C.c b ≤ D.b c ≤ 84.设是偏序集，“≤”定义为：b a b a A b a |,,?≤∈?，则当A=( )时，是格 A.{1，2，3，4，6，12} B.{1，2，3，4，6，8，12，14} C.{1，2，3，…，12} D.{1，2，3，4} 85.设>-∧∨<,, , A 是布尔代数，f 是从A n 到A 的函数，则( ) A.f 是布尔代数 B.f 能表示成析取范式，也能表示成合取范式 C.若A={0，1}，则f 一定能表示成析取范式，也能表示成合取范式 D.若f 是布尔函数，它一定能表示成析（合）取范式 图论 86.连通非平凡的无向图G 有一条欧拉回路当且仅当图G ( ) A.只有一个奇度结点 B.只有两个奇度结点 C.只有三个奇度结点 D.没有奇度结点 87.设>= A.完全图 B.树 C.简单图 D.多重图 88.若一棵完全二元（叉）树有2n-1个顶点，则它( )片树叶 A.n B.2n C.n-1 D.2 89.图给出一个格L，则L是( ) A.分配格 B.有补格 C.布尔格 D.A，B，C都不对 90.在Peterson图中，至少填加( )条边才能构成Euler图 A.1 B.2 C.4 D.5 91.在有n个顶点的连通图中，其边数( ) A.最多有n-1条 B.至少有n-1 条 C.最多有n条 D.至少有n 条 92.图中从v1到v3长度为2的通路有( )条 A． 0 B． 3 C． 2 D． 1 93.下面那一个图可一笔画出( A ) 94.一个割边集与任何生成树之间( ) A.没有关系 B.割边集诱导子图是生成树 C.有一条公共边 D.至少有一条公共边 95.在任何图中必定有偶数个( ) A.度数为偶数的结点 B.入度为奇数的结点 C.度数为奇数的结点 D.出度为奇数的结点 96.一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( ) A.5 B.7 C.8 D.9 97.下列偏序集( C )能构成格 98.连通图G 是一棵树当且仅当G 中( ) A.有些边是割边 B.每条边都是割边 C.所有边都不是割边 D.图中存在一条欧拉路径 99.有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件( ) A.63-≥m n B.63-≤m n C.63-≥n m D.63-≤n m 100. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点 A.10 B.4 C.8 D.12 101. 在有n 个顶点的连通图中，其边数( ) A.最多有n-1条 B.至少有n-1条 C.最多有n 条 D.至少有n 条 102. 给定无向图>= A.},,,{4341><> B.},,,{6454><> C.},,,{8474><> D.},,,{3221><> 103. 如右图 相对于完全图K 5的补图为( A ) 104. 下列哪一种图不一定是树( ) A.无回路的简单连通图 B.每对顶点间都有通路的图 C.有n 个顶点n-1条边的连通图 D.连通但删去任何一条边便不连通的图 105. 下面偏序集( B )能构成格 106. 6阶有限群的任何子群一定不是( ) A.2阶 B.3 阶 C.4 阶 D.6 阶 107. 在如下的有向图中，从V 1到V 4长度为3 的道路有( )条 A ．1 B ．2 C ．3 D ．4 108. n 个结点的无向完全图n K 的边数为( ) A.)1(+n n B.2)1(+n n C.)1(-n n 109. 设G 是一个哈密尔顿图，则G 一定是( ) A.欧拉图 B.树 C.平面图 D.连通图 110. 在如下各图中( B)是欧拉图 111. 下列图中( )是根树 A.>><><><=<},,,,,{},,,,{1d c b a a a d c b a G B.>><><><=<},,,,,{},,,,{2d c d b b a d c b a G C.>><><><=<},,,,,{},,,,{3a c d a b a d c b a G D.>><><><=<},,,,,{},,,,{4d d c a b a d c b a G 112. 下面给出的集合中，哪一个是前缀码？( ) A.{0，10，110，101111} B.{1，11，101，001，0011} C.{b ，c ，aa ，ab ，aba} D.{01，001，000，1} 113. 左图[0]相对于完全图的补图为( A ) 114. 下列图中是欧拉图的有( A ) 115.设n阶图G有m条边，每个结点度数不是k就是k+1，若G中有N k个k度结点，则N k=( ) A.n×k B.n×(k+1) C.n×(k+1)-m D.n×(k+1)-2m 116.设G是简单有向图，可达矩阵P(G)刻画下列 ( C )关系 A.点与边 B.边与点 C.点与点 D.边与边 117.设G是一棵树，n,m分别表示顶点数和边数，则( ) A.n=m B. n=m+1 C. m=n+1 D.不能确定 . 离散数学试题(A卷及答案） 一、证明题（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 (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={ 习题 1. 下列句子中，哪些是命题哪些不是命题如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗 ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。 ⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：p→q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：pq ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：pq。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：p→q；该命题是真命题。 ⑶原命题符号化为：p→q；该命题是假命题。 ⑷原命题符号化为：p→q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：pq；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：pq；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。 习题 离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分） 离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】 一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则 离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨?? ②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。 离散数学考试试题（A卷及答案） 一、（10分）证明?(A∨B)→?(P∨Q)，P，(B→A)∨?P A。 证明：(1)?(A∨B)→?(P∨Q) P (2)(P∨Q)→(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B→A)∨?P P (6)B→A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的： (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分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)→Q(x)) P (2)P(y)→Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG 解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。 正确的推理过程为： (1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)→Q(x)) P (4)P(c)→Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG 四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。 解设R＝{ 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 试卷二试题与参考答案 一、填空 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、设代数系统 二、选择 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、下面偏序集( )能构成格。 离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。 （A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边 二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧? 5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨ ７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→?? 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的补元( ). 5. 设G 是(7, 15)简单平面图，则G 一定是( )图，且其每个面恰由( )条边围成，G 的面数为( ). 离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是 （１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分） 1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧? 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 ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨ 7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(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 )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→?? 离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群} 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (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=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）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P 欢迎共阅 一、填空题 1设集合A,B ，其中A ＝{1,2,3},B={1,2},则A-B ＝____________________; ?(A)-?(B)＝__________________________. 2.设有限集合A,|A|=n,则|?(A×A)|=__________________________. 3.设集合A={a ,b },B={1,2},则从A 到B 的所有映射是_______________________________________,其中双射的是__________________________. 4.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题的幺元为( 0 )
是( )是( ) A.代数系统 B.半群 C.群 D.都不是离散数学期末考试试题(有几套带答案)
离散数学 第1章 习题解答
离散数学考试题详细答案
离散数学试题及答案精选版
离散数学习题三 含答案
离散数学考试试题(A卷及答案)
离散数学题库
离散数学试题与答案
离散数学试题及解答
离散数学题库及答案
离散数学复习题及标准答案
《离散数学》期末试题及答案
离散数学期末考试试卷(A卷)
离散数学复习题及答案
离散数学练习题及答案
山东大学离散数学题库及答案
《离散数学》试习题及答案