离散数学期末考试试题(有几套带答案1)..docVIP

离散数学试题(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分） 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))  五、已知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={x,y| x,y?N∧y=x2}，S={x,y| x,y?N∧y=x+1}。求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分） 解：R-1={y,x| x,y?N∧y=x2}，R*S={x,y| x,y?N∧y=x2+1}，S*R={x,y| x,y?N∧y=（x+1）2}， 七、若f:A→B和g: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?存在z（x,z∈g-1?z,y∈f-1）?存在z（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}。 离散数学试题(B卷及答案） 一、证明题（10分） 1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T 证明 左端?((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律) ? ((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律) ? ((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R)) (等幂律) ?T (代入) 2)?x(P(x)?Q(x))∧?xP(x)??x(P(x)∧Q(x)) 证明 ?x(P(x)?Q(x))∧?xP(x)??x((P(x)?Q(x)∧P(x))??x((?P(x)∨Q(x)∧P(x))??x(P(x)∧Q(x))??xP(x)∧?xQ(x)??x(P(x)∧Q(x)) 二、求命题公式(?P?Q)?(P∨?Q) 的主析取范式和主合取范式（10分） 解：(?P?Q)?(P∨?Q)??(?P?Q)∨(P∨?Q)??(P∨Q)∨(P∨?Q)?(?P∧?Q)∨(P∨?Q) ?(?P∨P∨?Q)∧(?Q∨P∨?Q)?(P∨?Q)?M1?m0∨m2∨m3 三、推理证明题（10分） 1)(P?(Q?S))∧(?R∨P)∧Q?R?S 证明：（1）R 附加前提 (2)?R∨P P (3)P T(1)(2