大學(xué)《離散數(shù)學(xué)》試題及答案(一)

第第1頁共3頁大學(xué)《離散數(shù)學(xué)》試題及答案一、證明題（10分）1)(P∧(Q∧R))∨(Q∧R)∨(P∧R)R((P∨Q)∧R)∨((Q∨P)∧R)((P∨Q)∨(Q∨P))∧R2)x(A(x)B(x))xA(x)xB(x)x(A(B(x)xA(xB(x)A(xxB(xxA(xxB(xxA(xxB(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∨m7M3∨M4∨M5∨M6三、推理證明題（10）1）C∨D,E,E(A∧B),∧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)(A(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)(6)C∨D(9)P(a)∧R(a)(7)R∨S(10)x(P(x)∧R(x))2)x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))證明

(11)Q(y)∧x(P(x)∧R(x))第第3頁共3頁mm的整數(shù)倍證明設(shè)aa1 2

，…，

m1

m去除它們所得余數(shù)只能由抽屜原理可知，aa1 2

，…，a

m1

這m＋1個整數(shù)中至少存在兩個數(shù)as

和amat

和am的整數(shù)倍。t五、已知A、B、C是三個集合，證明A-(B∪C)=(A-B)∩(A-C)（15分）證明∵xA-（B∪C）xA∧x（B∪C）xA∧（xB∧xC）（xA∧xB）∧（xA∧xC）x（A-B）∧x（A-C）x（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C）RS是NR={<x,y>|x,yN∧y=x2}S={<x,y>|x,yN∧y=x+1R-1、R*S、S*R、R{1,2}、S[{1,2}]（10）R-1={<y,x>|x,yN∧y=x2R*S={<x,y>|x,yN∧y=（x+1）2}，f:A→Bg:B→C（gf）-1=f-1g-1（10。證明：因為f、g是雙射，所以gf：A→C是雙射，所以gf有逆函數(shù)（gf）-1：C→A。同理可推f-1g-1：C→A是雙射。因為<x,y>∈f-1g-1存在（<x,z>∈g-1<z,y>∈f-1存在（<y,z>∈f<z,x>∈g）<y,x>∈gf<x,y>∈（gf）-1,所以（gf）-1=f-1g-1。R{1,2}={<1,1>,<2,4>}，S[{1,2}]={1,4}。（15）設(shè)<A，*>Aa證明：A。Aa。對A中任意元b和有。證明 由題意可知，若則必有(1)由所以。(2)由*(**)＝(*)*(*)＝**(*)＝(**)***＝(3)由(＝(a*b*c)*(a*c)，所以有a*b*c＝a*c。九、給定簡單無向圖。試證：若C2m1

＋2，則G是哈密爾頓圖證明C2m1

＋2，則2≥2－3＋6 （1。若存在兩個不相