下载文档原格式
离散数学第二版屈婉玲简介《离散数学第二版》是由屈婉玲编写的离散数学教材。
离散数学是计算机科学中的一门基础课程，主要研究离散对象及其结构、性质和相互关系。
这本教材系统地介绍了离散数学的各个方面，具有循序渐进、清晰易懂的特点，适合计算机科学及相关专业本科生使用。
目录•离散数学概论–离散数学的基本概念–命题逻辑–谓词逻辑与推理–集合与命题逻辑的应用•图论基础–图的基本概念–有向图与无向图–图的遍历–最短路径•关系与函数–二元关系–关系的闭包与等价关系–函数与映射关系–函数的复合与反函数•计数原理–基本计数原理–排列与组合–生成函数–容斥原理•离散数学中的数论–整数与整除性–模运算与同余关系–素数与因子分解–公约数与最大公约数•离散结构中的代数系统–代数系统的基本概念–半群与幺半群–群与子群–环与域内容概述离散数学概论第一章介绍了离散数学的基本概念和离散对象的性质。
包括集合论、命题逻辑和谓词逻辑等内容。
后续讲解了命题逻辑的推理规则，以及如何应用集合论和命题逻辑解决实际问题。
图论基础第二章介绍了图论的基本概念和图的表示方法。
包括有向图和无向图的概念、图的遍历算法和最短路径算法。
通过实例讲解了如何使用图论解决实际问题。
关系与函数第三章介绍了关系与函数的概念和性质。
包括二元关系的定义和性质、关系的闭包和等价关系的概念，以及函数与映射关系的概念和性质。
通过实例讲解了如何使用关系和函数解决实际问题。
计数原理第四章介绍了计数原理的基本概念和计数方法。
包括基本计数原理、排列与组合、生成函数和容斥原理等内容。
通过实例讲解了如何使用计数原理解决实际问题。
离散数学中的数论第五章介绍了离散数学中的数论知识。
包括整数与整除性、模运算与同余关系、素数与因子分解、公约数与最大公约数等内容。
通过实例讲解了如何使用数论知识解决实际问题。
离散结构中的代数系统第六章介绍了离散结构中的代数系统。
包括代数系统的基本概念、半群与幺半群、群与子群、环与域等内容。
离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p：李辛与李末是兄弟，则命题符号化的结果是p（6）王强与刘威都学过法语p q解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班q p解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是（11）下雪路滑，他迟到了解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(p q)r15、设p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：(p q r)((p q)r)（4）解：p=1，q=1，r=0，(p q r)(110)1，((p q)r)((11)0)(00)1 (p q r)((p q)r)111 19、用真值表判断下列公式的类型：(p p)q（2）解：列出公式的真值表，如下所示：p p qq(p p)(p p)q0 0 1 1 1 10 1 1 0 1 01 0 0 1 0 11 1 0 0 0 1由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值：（4）(p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：p0(p q) 1q0q0成真赋值有：01，10，11。
所以公式的习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）(p q)(q r)解：原式(p q)q r(p p)q rq r，此即公式的主析取范式，m m(p q r)(p q r)37所以成真赋值为011，111。
*6、求下列公式的主合取范式，并求成假赋值：（2）(p q)(p r)解：原式，此即公式的主合取范式，M(p p r)(p q r)(p q r)4所以成假赋值为100。
7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）(p q)r解：原式p q(r r)((p p)(q q)r)(p q r)(p q)r(p q)r(p q)r(p q)r(pq r(p q r)(p q)r(p q)r(p q)r(pq r，此即主析取范式。
离散数学习题答案习题二及答案：（P38）5、求下列公式的主析取式，并求成真赋值： （2）()()p q q r ⌝→∧∧ 解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取式，所以成真赋值为011，111。
6、求下列公式的主合取式，并求成假赋值： （2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取式，所以成假赋值为100。
7、求下列公式的主析取式，再用主析取式求主合取式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ⇔∧∧⌝∨∨⌝∨∧⌝∨∧()()()()()()p q r p q r p q r p q r p q r p q r ⇔∧∧⌝∨∧∧∨⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ⇔⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧⌝∨∧∧13567m m m m m ⇔∨∨∨∨，此即主析取式。
主析取式中没出现的极小项为0m ，2m ，4m ，所以主合取式中含有三个极大项0M ，2M ，4M ，故原式的主合取式024M M M ⇔∧∧。
9、用真值表法求下面公式的主析取式： （1）()()p q p r ∨∨⌝∧ 解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取式，故主析取式1234567m m m m m m m ⇔∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。
前提：,,,p q q r r s p ⌝∨⌝∨→结论：s 证明：① p 前提引入 ② p q ⌝∨ 前提引入 ③ q ①②析取三段论 ④q r ⌝∨ 前提引入⑤ r ③④析取三段论 ⑥r s → 前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u →证明：用附加前提证明法。
《离散数学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→P6.答：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、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)⇔ (∃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. 答：（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) R1-={<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 的关系矩阵=⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡000000001000000001 R 1-的关系矩阵=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡0000000100000000015、解：（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;它既不是自反的、也不是反自反的、也不是对称的、也不是反对称的、也不是传递的。
第一章 命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e 是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q ：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p ：刘晓月选学英语，q ：刘晓月选学日语；.7.因为p 与q 不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）pq ，真值为1；（4）p→r，若p 为真，则p→r 真值为0，否则，p→r 真值为1.16 设p 、q 的真值为0；r 、s 的真值为1，求下列各命题公式的真值。
（1）p ∨(q ∧r)⇔ 0∨(0∧1) ⇔0（2）（p?r ）∧(﹁q ∨s) ⇔（0?1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p ∧⌝q ∧r ）?(p ∧q ∧﹁r) ⇔（1∧1∧1） ? (0∧0∧0)⇔0(4)（⌝r ∧s ）→(p ∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。
离散数学习题答案习题二及答案：（P38）5、求下列公式的主析取式，并求成真赋值： （2）()()p q q r ⌝→∧∧ 解：原式()p q q r ⇔∨∧∧q r ⇔∧()p p q r ⇔⌝∨∧∧()()p q r p q r ⇔⌝∧∧∨∧∧37m m ⇔∨，此即公式的主析取式，所以成真赋值为011，111。
6、求下列公式的主合取式，并求成假赋值： （2）()()p q p r ∧∨⌝∨解：原式()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔，此即公式的主合取式，所以成假赋值为100。
7、求下列公式的主析取式，再用主析取式求主合取式： （1）()p q r ∧∨ 解：原式()(()())p q r r p p q q r ⇔∧∧⌝∨∨⌝∨∧⌝∨∧()()()()()()p q r p q r p q r p q r p q r p q r ⇔∧∧⌝∨∧∧∨⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧ ()()()()()p q r p q r p q r p q r p q r ⇔⌝∧⌝∧∨⌝∧∧∨∧⌝∧∨∧∧⌝∨∧∧13567m m m m m ⇔∨∨∨∨，此即主析取式。
主析取式中没出现的极小项为0m ，2m ，4m ，所以主合取式中含有三个极大项0M ，2M ，4M ，故原式的主合取式024M M M ⇔∧∧。
9、用真值表法求下面公式的主析取式： （1）()()p q p r ∨∨⌝∧ 解：公式的真值表如下：由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取式，故主析取式1234567m m m m m m m ⇔∨∨∨∨∨∨习题三及答案：（P52-54）11、填充下面推理证明中没有写出的推理规则。
前提：,,,p q q r r s p ⌝∨⌝∨→结论：s 证明：① p 前提引入 ② p q ⌝∨ 前提引入 ③ q ①②析取三段论 ④q r ⌝∨ 前提引入⑤ r ③④析取三段论 ⑥ r s → 前提引入⑦ s ⑤⑥假言推理15、在自然推理系统P 中用附加前提法证明下面推理： （2）前提：()(),()p q r s s t u ∨→∧∨→ 结论：p u →证明：用附加前提证明法。
离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语p q解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班q p解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是（11）下雪路滑，他迟到了解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(p q)r15、设p：2+3=5.q：大熊猫产在中国.r：太阳从西方升起.求下列复合命题的真值：(p q r)((p q)r)（4）解：p=1，q=1，r=0，(p q r)(110)1，((p q)r)((11)0)(00)1 (p q r)((p q)r)11119、用真值表判断下列公式的类型：(p p)q（2）解：列出公式的真值表，如下所示：p p qq(p p)(p p)q0 0 1 1 1 10 1 1 0 1 01 0 0 1 0 11 1 0 0 0 1由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值：（4）(p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：p0(p q) 1q0q0成真赋值有：01，10，11。
所以公式的习题二及答案：（P38）5、求下列公式的主析取范式，并求成真赋值：（2）(p q)(q r)解：原式(p q)q r(p p)q rq r，此即公式的主析取范式，m m(p q r)(p q r)37所以成真赋值为011，111。
*6、求下列公式的主合取范式，并求成假赋值：（2）(p q)(p r)解：原式，此即公式的主合取范式，M(p p r)(p q r)(p q r)4所以成假赋值为100。
7、求下列公式的主析取范式，再用主析取范式求主合取范式：（1）(p q)r解：原式p q(r r)((p p)(q q)r)(p q r)(p q)r(p q)r(p q)r(p q)r(pq r(p q r)(p q)r(p q)r(pq)r(pq r，此即主析取范式。
第一章命题逻辑基本概念课后练习题答案1.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.2.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；3.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.4.因为p与q不能同时为真.5.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.返回第二章命题逻辑等值演算本章自测答案5.(1)：∨∨,成真赋值为00、10、11；(2)：0，矛盾式，无成真赋值；(3)：∨∨∨∨∨∨∨,重言式，000、001、010、011、100、101、110、111全部为成真赋值；7.(1)：∨∨∨∨⇔∧∧；(2)：∨∨∨⇔∧∧∧；8.(1)：1⇔∨∨∨,重言式；(2)：∨⇔∨∨∨∨∨∨；(3)：∧∧∧∧∧∧∧⇔0，矛盾式.11.(1)：∨∨⇔∧∧∧∧；(2)：∨∨∨∨∨∨∨⇔1；(3)：0⇔∧∧∧.12.A⇔∧∧∧∧⇔∨∨.第三章命题逻辑的推理理论本章自测答案6.在解本题时，应首先将简单陈述语句符号化，然后写出推理的形式结构*，其次就是判断*是否为重言式，若*是重言式，推理就正确，否则推理就不正确，这里不考虑简单语句之间的内在联系(1)、(3)、(6)推理正确，其余的均不正确，下面以(1)、(2)为例，证明(1)推理正确，(2)推理不正确(1)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*1)在本推理中，从p与q的内在联系可以知道，p与q的内在联系可以知道，p与q不可能同时为真，但在证明时，不考虑这一点，而只考虑*1是否为重言式.可以用多种方法（如真值法、等值演算法、主析取式）证明*1为重言式，特别是，不难看出，当取A为p,B为q时，*1为假言推理定律，即(p→q)∧p→q ⇒ q(2)设p:今天是星期一，q:明天是星期三，推理的形式结构为(p→q)∧p→q(记作*2)可以用多种方法证明*2不是重言式，比如，等值演算法、主析取范式（主和取范式法也可以）等(p→q)∧q→p⇔(┐p∨q) ∧q →p⇔q →p⇔┐p∨┐q⇔⇔∨∨从而可知，*2不是重言式，故推理不正确，注意，虽然这里的p与q同时为真或同时为假，但不考虑内在联系时，*2不是重言式，就认为推理不正确.9.设p:a是奇数，q:a能被2整除，r:a：是偶数推理的形式结构为(p→q┐)∧(r→q)→(r→┐p) (记为*)可以用多种方法证明*为重言式，下面用等值演算法证明：(p→┐q)∧(r→q)→(r→┐p)⇔(┐p∨┐q) ∨(q∨┐r)→(┐q∨┐r) (使用了交换律)⇔(p∨q)∨(┐p∧r)∨┐q∨┐r⇔(┐p∨q)∨(┐q∧┐r)⇔┐p∨(q∨┐q)∧┐r⇔110.设p:a,b两数之积为负数，q:a,b两数种恰有一个负数，r：a，b都是负数.推理的形式结构为(p→q)∧┐p→(┐q∧┐r)⇔(┐p∨q) ∧┐p→(┐q∧┐r)⇔┐p→(┐q∧┐r) (使用了吸收律)⇔p∨(┐q∧┐r)⇔∨∨∨由于主析取范式中只含有5个W极小项，故推理不正确.11.略14.证明的命题序列可不惟一，下面对每一小题各给出一个证明① p→(q→r)前提引入② P前提引入③ q→r①②假言推理④ q 前提引入⑤ r③④假言推理⑥ r∨s前提引入（2）证明：① ┐(p∧r)前提引入② ┐q∨┐r①置换③ r前提引入④ ┐q ②③析取三段论⑤ p→q前提引入⑥ ┐p④⑤拒取式（3）证明：① p→q前提引入② ┐q∨q①置换③ (┐p∨q)∧(┐p∨p) ②置换④ ┐p∨(q∧p③置换⑤ p→(p∨q) ④置换15.(1)证明：① S结论否定引入② S→P前提引入③ P①②假言推理④ P→(q→r)前提引入⑤ q→r③④假言推论⑥ q前提引入⑦ r⑤⑥假言推理（2）证明：① p附加前提引入② p∨q①附加③ (p∨q)→(r∧s)前提引入④ r∧s②③假言推理⑤ s④化简⑥ s∨t⑤附加⑦ (s∨t)→u前提引入⑧ u⑥⑦拒取式16.(1)证明：① p结论否定引入② p→ ┐q前提引入③ ┐q ①②假言推理④ ┐r∨q前提引入⑤ ┐r③④析取三段论⑥ r∧┐s前提引入⑦ r⑥化简⑧ ┐r∧r⑤⑦合取（2）证明：① ┐(r∨s)结论否定引入② ┐r∨┐s①置换③ ┐r②化简④ ┐s②化简⑤ p→r前提引入⑥ ┐p③⑤拒取式⑦ q→s前提引入⑧ ┐q④⑦拒取式⑨ ┐p∧┐q⑥⑧合取⑩ ┐(p∨q)⑨置换口p∨q前提引入⑾①口┐(p∨q) ∧(p∨q) ⑩口合取17．设p：A到过受害者房间，q: A在11点以前离开，r：A犯谋杀罪，s：看门人看见过A。
