《离散数学》题库答案第2，3章(数理逻辑)1.答：（2），（3），（4）2.答：（2），（3），（4），（5），（6）3.答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是4.答：（1）P↔（4）QP→⌝P⌝Q→⌝（2）QP⌝→（3）Q5.答：（1）6.答：2不是偶数且-3不是负数。

7.答：（2）8.答：⌝P ，Q→P9.答：P(x)∨∃yR(y)10.答：⌝∀x(R(x)→Q(x))11、a、(P→Q)∧R解：(P→Q)∧R⇔(⌝P∨Q )∧R⇔(⌝P∧R)∨(Q∧R) （析取范式）⇔(⌝P∧(Q∨⌝Q)∧R)∨((⌝P∨P)∧Q∧R)⇔(⌝P∧Q∧R)∨(⌝P∧⌝Q∧R)∨(⌝P∧Q∧R)∨(P∧Q∧R)⇔(⌝P∧Q∧R)∨(⌝P∧⌝Q∧R)∨(P∧Q∧R)⇔m3∨ m1∨m7 （主析取范式）⇔m1∨ m3∨m7⇔M0∧M2∧M4∧M5∧M6 （主合取范式）b、Q→(P∨⌝R)解：Q→(P∨⌝R)⇔⌝Q∨P∨⌝R⇔M5（主合取范式）⇔ m0∨ m1∨ m2∨m3∨ m4∨m6 ∨m7 （主析取范式）c、P→(P∧(Q→P))解：P→(P∧(Q→P))⇔⌝P∨(P∧(⌝Q∨P))⇔⌝P∨P⇔ 1 (主合取范式)⇔ m0∨ m1∨m2∨ m3 （主析取范式）d、P∨(⌝P→(Q∨(⌝Q→R)))解：P∨(⌝P→(Q∨(⌝Q→R)))⇔ P∨(P∨(Q∨(Q∨R)))⇔ P∨Q∨R⇔ M0 (主合取范式)⇔ m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式)12、a、P→Q，⌝Q∨R，⌝R，⌝S∨P=>⌝S证明：(1) ⌝R 前提(2) ⌝Q∨R 前提(3)⌝Q （1），（2）析取三段论(4) P→Q 前提(5)⌝P （3），（4）拒取式(6)⌝S∨P 前提(7) ⌝S （5），（6）析取三段论b、P→(Q→R)，R→(Q→S) => P→(Q→S)证明：（1） P 附加前提（2） Q 附加前提（3） P→(Q→R) 前提（4） Q→R （1），（3）假言推理（5） R （2），（4）假言推理（6） R→(Q→S) 前提（7） Q→S （5），（6）假言推理（8） S （2），（7）假言推理c、A，A→B， A→C， B→(D→⌝C) => ⌝D证明：（1） A 前提（2） A→B 前提（3） B (1)，(2) 假言推理（4） A→C 前提（5） C (1)，(4) 假言推理（6） B→(D→⌝C) 前提（7） D→⌝C (3)，(6) 假言推理（8）⌝D (5)，(7) 拒取式d、P→⌝Q，Q∨⌝R，R∧⌝S⇒⌝P证明、(1) P 附加前提（2） P→⌝Q 前提（3）⌝Q （1），（2）假言推理（4） Q∨⌝R 前提(5) ⌝R （3），（4）析取三段论(6 ) R∧⌝S 前提（7） R （6）化简（8） R∧⌝R 矛盾（5），（7）合取所以该推理正确13.写出∀x(F(x)→G(x))→(∃xF(x) →∃xG(x))的前束范式。

解：原式⇔∀x(⌝F(x)∨G(x))→(⌝(∃x)F(x) ∨ (∃x)G(x))⇔⌝(∀x)(⌝F(x)∨G(x)) ∨(⌝(∃x)F(x) ∨ (∃x)G(x))⇔ (∃x)((F(x)∧⌝ G(x)) ∨G(x)) ∨ (∀x) ⌝F(x) ⇔ (∃x)((F(x) ∨G(x)) ∨ (∀x) ⌝F(x)⇔ (∃x)((F(x) ∨G(x)) ∨ (∀y) ⌝F(y)⇔ (∃x) (∀y) (F(x) ∨G(x) ∨⌝F(y))（集合论部分）1、答：(4)2.答：323.答：（3）4.答：A1=A2=A3=A6， A4=A55. 答：（4）6.答：（1）7.答：（2），（4）8、设Ａ，Ｂ，Ｃ是三个集合，证明：a、A⋂ (B－C)＝(A⋂B)－(A⋂C)证明：(A⋂B)－(A⋂C)= (A⋂B)⋂~（A⋂C）=(A⋂B) ⋂（~A⋃~C）=(A⋂B⋂~A)⋃(A⋂B⋂~C)= A⋂B⋂~C=A⋂（B⋂~C）=A⋂（B-C）b、(A－B)⋃(A－C)=A－(B⋂C)证明：(A-B)⋃(A-C)=(A⋂~B)⋃(A⋂⋂~C) =A⋂ (~B ⋃~C)=A⋂~（B⋂C）= A-(B⋂C)c、A⋃B=A⋃(B-A)证明：A⋃(B-A)=A⋃(B⋂~A)=(A⋃B)⋂(A⋃~A)=(A⋃B)⋂E= A⋃B9、P(A)⋃P(B)⊆P(A⋃B) （P(S)表示S的幂集）证明：∀S∈P(A)⋃P(B)，有S∈P(A)或S∈P(B)，所以S⊆A或S⊆B。

从而S⊆A⋃B，故S∈P(A⋃B)。

即P(A)⋃P(B)⊆P(A⋃B)10、P(A)⋂P(B)=P(A⋂B) （P(S)表示S的幂集）证明：∀S∈P(A)⋂P(B)，有S∈P(A)且S∈P(B)，所以S⊆A且S⊆B。

从而S⊆A⋂B，故S∈P(A⋂B)。

即P(A)⋂P(B)⊆P(A⋂B)。

∀S∈P(A⋂B)，有S⊆A⋂B，所以S⊆A且S⊆B。

从而S∈P(A)且S∈P(B)，故S∈P(A)⋂P(B)。

即P(A⋂B)⊆P(A)⋂P(B)。

故P(A⋂B)=P(A)⋂P(B)（二元关系部分）1、答：（1）R={<1,1>,<4,2>} (2) R 1-={<1,1>,<2,4>} 2.答：R R ={〈1,1〉，〈1,3〉，〈2,2〉，〈2,4〉} R -1 =｛〈2,1〉，〈1,2〉，〈3,2〉，〈4,3〉｝3.答：R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}4.答：R 的关系矩阵=⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡000000001000000001R 1-的关系矩阵=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0000000100000000015.若R 和S 都是非空集A 上的等价关系，则R ⋂S 是A 上的等价关系。

证明：∀a ∈A ，因为R 和S 都是A 上的等价关系，所以xRx 且xSx 。

故xR ⋂Sx 。

从而R ⋂S 是自反的。

∀a,b ∈A ，aR ⋂Sb ，即aRb 且aSb 。

因为R 和S 都是A 上的等价关系，所以bRa 且bSa 。

故bR ⋂Sa 。

从而R ⋂S 是对称的。

∀a,b,c ∈A ，aR ⋂Sb 且bR ⋂Sc ，即aRb ，aSb,bRc 且bSc 。

因为R和S 都是A 上的等价关系，所以aRc 且aSc 。

故aR ⋂Sc 。

从而R ⋂S 是传递的。

故R ⋂S 是A 上的等价关系。

6、设R ⊆A ×A ，则R 自反 ⇔I A ⊆R 。

证明：⇒∀x ∈A ， R 是自反的，∴xRx 。

即<x,x>∈R ，故I A ⊆R 。

⇐∀x ∈A ， I A ⊆R ，∴<x,x>∈R 。

即xRx ，故R 是自反的。

7、设A 是集合，R ⊆A ×A ，则R 是对称的⇔R ＝R －1。

证明：⇒∀<x,y>∈R ， R 是对称的，∴yRx 。

即<y,x>∈R ，故<x,y>∈R _1。

从而R ⊆R -1。

反之∀<y,x>∈R -1,即<x,y>∈R 。

R 是对称的，∴yRx 。

即<y,x>∈R ，R _1⊆R 。

故R=R -1。

⇐∀x ，y ∈A ，若<x,y>∈R ，即<y,x>∈R -1。

R=R -1，∴<y,x>∈R 。

即yRx ，故R 是对称的。

8、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：解：（1）R={<2,1>,<3,1>,<2,3>};M R =⎪⎪⎪⎭⎫ ⎝⎛001101000;它是反自反的、反对称的、传递的；（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};M R =⎪⎪⎪⎭⎫⎝⎛011101110;它是反自反的、对称的；（3）R={<1,2>,<2,1>,<1,3>,<3,3>};M R =⎪⎪⎪⎭⎫⎝⎛100001110;它既不是自反的、也不是反自反的、也不是对称的、也不是反对称的、也不是传递的。

9、R 是A={1,2,3,4,5,6}上的等价关系，R=I A ⋃{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>}求R诱导的划分。

解：R诱导的划分为{{1,5},{2,4},{3,6}}。

10．画出下列集合关于整除关系的哈斯图.(1){1, 2, 3, 4, 6, 8, 12, 24}.(2){1,2,…..,9}.并指出它的极小元，最小元，极大元，最大元。

在图（2）中极小元，最小元是1，极大元是5，6，7，8，9，没有最大元。