大学《离散数学》试题及答案(一)

第第1页共3页大学《离散数学》试题及答案一、证明题（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的整数倍证明设aa1 2

，…，

m1

m去除它们所得余数只能由抽屉原理可知，aa1 2

，…，a

m1

这m＋1个整数中至少存在两个数as

和amat

和am的整数倍。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有逆函数（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）设<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。若存在两个不相