离散数学版屈婉玲（答案）

《离散数学1-5章》练习题答案

第2，3章(数理逻辑)

1.答：（2），（3），（4）

2.答：（2），（3），（4），（5），（6）

3.答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 4.答：（4） 5.答：?P ，Q?P 6.答：P(x)? ?yR(y) 7.答：??x(R(x)?Q(x))

8、 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 (主析取范式)

9、

1 / 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）假言推理 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）合取

所以该推理正确

10.写出?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)

2 / 6

? (?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.答：32 3.答：（3） 4. 答：（4） 5.答：（2），（4）

6、设Ａ，Ｂ，Ｃ是三个集合，证明： 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)

（二元关系部分）

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>}

3 / 6

4.

?1?0?0?答：R的关系矩阵=?0??0??000?00??100000??00??000100? ?1 R的关系矩阵=??10????000000??00?00??

5、解：

?000???（1）R={<2,1>,<3,1>,<2,3>};MR=?101?;它是反自反的、反对称的、

?100???传递的；

?011???（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=?101?;它是反

?110???自反的、对称的；

?011???（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=?100?;它既不是自反的、也

?001???不是反自反的、也不是对称的、也不是反对称的、也不是传递的。 6、解：

R诱导的划分为{{1,5},{2,4},{3,6}}。 7．画出下列集合关于整除关系的哈斯图.

(1){1, 2, 3, 4, 6, 8, 12, 24}. (2){1,2,…..,9}.

并指出它的极小元，最小元，极大元，最大元。

4 / 6