北京交通大学2007-2008学年第二学期《离散数学基础(信科专业)》期末考试卷(A)学院:____________ _专业:___________________ 班级____________姓名:学号:□选修□必修一、填空题(共10分,每空1分)1.在推理理论中,推导过程中如果一个或多个公式重言蕴涵某个公式,则这个公式就可以引入推导过程中,这一推理规则叫做(T规则)。
2.设A={a,{b}},则A的幂集是P (A)= {Φ, a,{b}, {a,{b}};3.设R 是集合A上的二元关系,如果关系R同时具有自反性、反对称性和传递性,则称R是A上的一个偏序关系。
4.既是满射,又是单射的映射称为1-1映射(双射)。
5.设S为非空有限集,代数系统<P(S),∪>的单位元和零元分别为S和φ。
6.具有n个顶点的无向完全图共有n(n-1)/2条边。
7.简单图是指无环、无重边的图。
8.k-正则图是指所有顶点的度数均为k的的图。
9.Hamilton通路是指通过图中所有顶点一次且仅一次的通路。
10.设G=(E,V)是图,如果G是连通的,则P(G)= 1 。
11.命题公式(P→Q) ∧ (P→R)的主析取范式中包含极小项( A )A.P∧Q∧R;B.P∧Q∧⌝R;C .P ∧⌝Q ∧R ;D .P ∧⌝Q ∧⌝R12. 下列谓词公式中( A )不正确。
A .(∃x)(A(x) →B) ⇔ (∃x) A(x) →B ; B .(∃x)(B →A(x)) ⇔ B →(∃x) A(x);C .(∀x)(B →A(x)) ⇔ B →(∀x) A(x);D .(∀x)(A(x)∨B) ⇔(∀x)A(x)∨B ;13. 设S = {2,a ,{3},4},R ={{a},3,4,1},指出下面的写法中正确的是( D )(A )R=S ; (B ){a,3}⊆S ; (C ){a}⊆R ;(D )φ⊆R ;14. 下列命题公式不是重言式的是 C 。
A. Q →(P ∨Q);B.(P ∧Q)→P ;C.⌝(P ∧⌝Q );D.⌝(⌝P ∧0)。
15. 下列谓词公式中( )不正确。
(A) (∃x)(A(x) →B) ⇔ (∃x) A(x) →B ; (B) (∃x)(B →A(x)) ⇔ B →(∃x) A(x); (C) (∀x)(B →A(x)) ⇔ B →(∀x) A(x); (D) (∀x)(A(x)∨B) ⇔(∀x)A(x)∨B ; 16. 下列命题中正确的是( B )。
(A) φ∪{φ}=φ; (B) {φ,{φ}}-{{φ}}={φ};(C) {φ,{φ}}-{φ}={φ,{φ}}; (D) {φ,{φ}}-φ={{φ}}; 17. 设A,B,C 为任意三个集合,下列各命题中正确的是( A )。
(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 。
18. ⎩⎨⎧<-≥=→3 ,23,)( ,: 2x x x x f R R f 设,则,2)(,:+=→x x g R R g =))((x g f A 。
(A )⎩⎨⎧<-≥+121 )2(2x x x ;(B )⎩⎨⎧<-≥+323 )2(x x x ;(C )⎩⎨⎧<-≥+1 21 )2(2x x x ;(D )⎩⎨⎧<≥+303 )2(2x x x .19. 设R 1,R 2是集合A={a ,b ,c ,d}上的两个关系,其中R 1={(a ,a ),(b ,b ),(b ,c ),(d ,d )},R 2={(a ,a ),(b ,b ),(b ,c ),(c ,b ),(d ,d )},则R 2是R 1的( B )闭包。
(A) 自反 (B) 对称(C) 传递 (D) 以上都不是20.设偏序关系R是集合A={1,2,3,4,5,6}中数的“整除”关系,则A的极大元、极小元的个数分别是( C )。
(A) 2,1 (B) 2,2 (C) 3,1 (D) 3,2二、计算题(共40分,每小题10分)1.求命题公式(P∧Q)∨(⌝P∧R)的主合取范式。
2.在一个班级的50个学生中,有26人在第一次考试中得到A,21人在第二次考试中得到A。
假如有17人两次考试都没有得到A,问有多少学生两次考试中都得到了A?3.设为一个偏序集,其中,A={1,2,3,4,6,9,24,54}是A上的整除关系。
(1)画出的哈斯图;(2)求R关于A的极大元;(3)求B={4,6,9}的最小上界和最大下界。
4.用逻辑推理方法证明:{P→Q,R→S,P∨R }蕴涵Q∨S。
5.将公式P→((P→Q)∧⌝(⌝Q∨⌝P))化为主析取范式和主合取范式:解:P→((P→Q)∧⌝(⌝Q∨⌝P))⇔⌝P∨((⌝P∨Q) ∧ Q∧P)⇔⌝P∨(Q∧P)⇔ (⌝P ∧(Q∨⌝Q)) ∨(Q∧P)⇔ (⌝P ∧Q) ∨(⌝P∧⌝Q) ∨(Q∧P) (主析取范式)P→((P→Q)∧⌝(⌝Q∨⌝P))⇔⌝P∨((⌝P∨Q) ∧ Q∧P)⇔⌝P∨(Q∧P)⇔(⌝P∨Q) ∧(⌝P∨P)⇔⌝P∨Q (主合取范式)6.化简(A-B-C)⋃((A-B)⋂C)⋃(A⋂B-C)⋃(A⋂B⋂C)解:(A-B-C)⋃((A-B)⋂C)⋃(A⋂B-C)⋃(A⋂B⋂C)=(A⋂~B⋂~C)⋃(A⋂~B⋂C)⋃(A⋂B⋂~C)⋃(A⋂B⋂C)=((A⋂~B)⋂(~C⋃C))⋃((A⋂B)⋂(~C⋃C))=((A⋂~B)⋂E)⋃((A⋂B)⋂E)E为全集=(A⋂~B)⋃(A⋂B)= A⋂(~B⋃B)= A⋂E= A7.写出下面有向图(关系图)所表示的关系R的关系矩阵,并求出R的自反闭包和对称闭包。
解:1{,,,,,,,}110001010(){,,,,,,,,,,,}(){,,,,,,,,,}R AR a a a b b c c b M r R R I a a b b c c a b b c c b s R R R a a a b b a b c c b -=<><><><>⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦=⋃=<><><><><><>=⋃=<><><><><>8. 设图G 中各点的度都是3,且点数n 与边数m 满足2n-3=m 。
问:G 中点数n 和边数m各为多少? 解:由图G 中各点的度都是3知,)()(v G P v Gd∑∈=3n ,而)()(v G P v Gd∑∈=2m ,故,3n=2m 。
再由已知2n-3=m ,解得n=6,m=9。
9. 张三说李四在说谎,李四说王五在说谎,王五说张三、李四都在说谎。
问张三、李四、王五三人到底谁说真话,谁说假话?解:10. 对102名学生调查表明,有35人学日语,20人学法语,45人学英语,15人既学日语又学英语,8人既学日语又学法语,10人既学法语又学英语,28人不学这三门中的任何一门。
(1) 求三门语言都学的人数; (2) 求至少两门语言的人数;(3) 求只学英语,只学法语,只学日语的人数。
解:REFx15 -x10 -x8-x2+x12+x20+x(1) 45+20+2+x+18=102,1).x=7 (2) 至少学两门的人数为15+4=19,(3) 只学英语27人, 只学法语9人, 只学日语19人,11. 设为一个偏序集,其中,A={1,2,3,4,6,9,24,54}是A 上的整除关系。
(1)画出的哈斯图;(2)求R 关于A 的极大元;(3)求B={4,6,9}的最小上界和最大下界。
12. 设A = {0,1},B ={1,2},试确定下列集合: (1) A ×{1}×B ; (2) A 2×B ; (3) (B ×A)2。
解:13. 画出K4的所有非同构的生成子图,其中有几个是连通图?非同构的生成子图有11个,其中六个连通图. 三、 证明题(共28分)1. 用逻辑推理方法证明:{P →Q , R →S ,P ∨R }蕴涵Q ∨S 。
证明:(1) P ∨R 规则P (2) ⌝R →P 规则Q ,根据(1) (3) P →Q 规则P (4) ⌝R →Q 规则Q ,根据(2)(3) (5) ⌝Q →R 规则Q ,根据(4) (6) R →S 规则P (7) ⌝Q →S 规则Q ,根据(5)(6) (8)Q ∨S 规则Q ,根据(7)2. 证明集合等式(A-B )∪(B-A )=(A ∪B )-(A ∩B ).3. 设R 是一个关系,用R -1表示R 的逆关系,s(R)表示S 的对称闭包,证明 s(R)=R ∪R -1。
证明:①任取(x,y)∈ R ∪R -1 ,则(x,y)∈ R 或(x,y)∈ R -1,若(x,y)∈ R ,则有(y,x)∈R -1,所以(y,x)∈ R ∪R -1;若(x,y)∈ R -1 ,则有(y,x)∈R ,所以(y,x)∈ R ∪R -1 , R ∪R -1具有对称性;②显然,R ⊆ R ∪R -1③对A 上任意关系R '', 若R ⊆ R '',且R ''是对称的,往证R ∪R -1⊆R ''。
任取(x,y)∈R∪R -1,则(x,y)∈ R 或(x,y)∈ R -1,若(x,y)∈ R ,因为R ⊆ R '',则(x,y)∈ R '' ;若(x,y)∈ R -1,则有(y,x)∈R ,则(y,x)∈R '',因为R ''是对称的,所以(x,y)∈R '' , 因此,R ∪R -1⊆R ''。
4. 设R 是一个二元关系,证明:(1) 若R 是自反的,则s (R )和t (R )是自反的; (2) 若R 是对称的,则r (R )和t (R )是对称的;5.在半群<G,*>中,若对∀a,b∈G,方程a*x=b 和y*a=b都有惟一解,则关于运算*存在单位元。
证明:任意取定a∈G,记方程a*x=a的惟一解为e R。
即a*e R=a。
下证e R为关于运算*的右单位元。
对∀b∈G,记方程y*a=b的惟一解为y。
因为<G,*>是半群,所以运算*满足结合律。
从而b*e R=(y*a)*e R=y*(a*e R)=y*a=b。
故e R 为关于运算*的右单位元。