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

离散试卷及答案 第 1 页 共 12 页

离散数学试题(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)⇔⌝00000000000000(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 的整数倍

证明 设1a ，2a ，…，1+m a 为任取的m ＋1个整数，用m 去除它们所得余数只能是0，1，…，m －1，由抽屉原理可知，

1a ，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={<x,y>| x,y ∈N ∧y=x 2

}，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=x 2

}，R*S={<x,y>| x,y ∈N ∧y=x 2

+1}，S*R={<x,y>| x,y ∈N ∧y=（x+1）2

}， 七、若f:A →B 和g:B →C 是双射，则（gf ）-1

=f -1g -1

（10分）。

第1页下一页