离散数学概论 第2版 习题及答案 第1-4章

第一章习题答案1.判断下列语句哪些是命题并给出命题的真值。(1)20是偶数。(2)今天是晴天吗？(3)平行四边形两对边分别平行。(4)直角三角形其中两边相互垂直。(5)16既能被2整除，又能被8整除。(6)请尊老爱幼！(7)4是2的倍数。(8)我们去郊游当且仅当今天不下雨。(9)我和李霞是朋友。(10)人只要肯努力就一定能成功。答：（1）、（2）、（4）、（5）、（7）、（8）、（9）、（10）是命题，其中（1）、（2）、（4）、（7）、（9）是简单命题，（5）、（8）、（10）是复合命题。简单命题（1）、（2）、（4）、（7）是真命题，（9）可为真命题，也可为假命题，故是命题变项。（5）因为是简单命题“16能被2整除”和“16能被8整除”的合取，且两个简单命题为真命题，故（5）的真值为真，而（8）、（10）的真值即可为真也可为假。2.给出下列命题的否定命题。(1)杭州的每条街道都有绿化。(2)每一个素数都是偶数。答：(1)的否定命题为：杭州的每条街道都没有绿化。(2)的否定命题为：每一个素数都不是偶数。3.将下列命题符号化。(1)如果天晴，我将去公园。(2)仅当你去我才离开。(3)2既能整除4又能整除8。(4)张亮和赵鹏是同班同学。(5)两个三角形全等当且仅当它们对应的两条边相等且由这两条边构成的夹角相等。(6)周六没有英语课或离散数学课。(7)张磊和李楠只有一人能参加这次英语竞赛。(8)只要我们肯想办法，总能克服这些困难。(9)星期天天晴或下雨。(10)只有年龄满14岁或身高超过1.4米才能坐过山车。答：(1)令p：天晴，q：我去公园。命题符号化为：(2)令p：你去q，：我离开。命题符号化为：(3)令p：2能整除，q：4能整除8。命题符号化为：(4)令p：张亮和赵鹏是同班同学命题符号化为：p。(5)令p：两个三角形全等，q：对应的两条边相等，r：两条边构成的夹角相等。命题符号化为：(6)令p：周六有英语课，q：周六有离散数学课。命题符号化为：(7)令p：张磊参加这次英语竞赛，q：李楠参加这次英语竞赛。命题符号化为：(8)令p：我们肯想办法，q：我们能克服这些困难。命题符号化为：(9)令p：星期天天晴，q：星期天下雨。命题符号化为：(10)令p：年龄满14岁，q：身高超过1.4米，r：能坐过山车。命题符号化为：4.令p表示命题“苹果是添的”，q表示命题“苹果是红的”，r表示命题“我买苹果”。试将下列命题符号化：(1)如果苹果甜而红，那么我买苹果。(2)苹果不是甜的。(3)我没买苹果，因为苹果不红也不甜。答：(1)命题符号化为：(2)命题符号化为：(3)命题符号化为：5.设p表示“该地区曾出现过灰熊”，q表示“在路上远足很安全”，r表示“沿途苹果成熟了”，给出描述下列命题公式的语句。(1)答：该地区未曾出现过灰熊。(2)答：该地区曾出现过灰熊或者在路上远足很安全。(3)答：如果该地区曾出现过灰熊，那么在路上远足就不安全。(4)答：该地区曾出现过灰熊且在路上远足不安全。(5)答：该地区曾出现过灰熊或者在路上远足很安全。(6)答：若沿途苹果成熟了则在路上远足是安全的，当且仅当该地区未出现过灰熊。6.构成下列公式的真值表，写出成真赋值和成假赋值。(1)pq0011010110111101成真赋值为：00,01,10,11。(2)pq00110010111011011011成真赋值为：01,11；成假赋值为：00,10。(3)pq00001011001010011111成真赋值为：00,11；成假赋值为：01,10。(4)pq0011111011011110010011100111成真赋值为：00,01,10,11。(5)pq00101011101000111111成真赋值为：00,10,11；成假赋值为：01。(6)pqr0000001000101001010100010111110010011100101111001101110011111100成真赋值为：001,010；成假赋值为：000,011,100,101,110,111。7设p、q的真值为0，r、s的真值为1，求下列命题的真值。(1)答：当p、q的真值为0，r的真值为1，该命题真值为1。(2)答：当p、q的真值为0，r、s的真值为1，该命题真值为1。(3)答：当p、q的真值为0，r、s的真值为1，该命题真值为0。(4)答：当p、q的真值为0，r、s的真值为1，该命题真值为1。(5)答：当p、q的真值为0，r、s的真值为1，该命题真值为1。8.通过真值表方法判断下列命题公式的类型。(1)p011011100100答：根据真值表可知公式真值可真可假，所以该公式是可满足式。(2)pqr0000000101010110111110011101111101111111答：根据真值表可知公式真值可真可假，所以该公式是可满足式。(3)pq0000011010111110答：根据真值表可知公式真值可真可假，所以该公式是可满足式。(4)pq00001011111011111111答：根据真值表可知公式真值都为真，所以该公式是永真式。(5)pqr0001111100111111010101010111111110001001101011011101000111111111答：根据真值表可知公式真值都为真，所以该公式是永真式。(6)pq001101010011101011110101答：根据真值表可知公式真值都为真，所以该公式是永真式。9.写出与下面给出的公式等价并且仅含有联接词与的最简公式。(1)答：(2)答：(3)答：(4)答：(5)答：10.写出与下面的公式等价并且仅含联结词和的最简公式。(1)答：(2)答：(3)答：11.用等值演算法判断下列命题公式的类型。(1)答：此公式为永真式。(2)答：此公式为永真式。(3)答：此公式为可满足式。12.用真值表法和等值演算法证明下列等值式。(1)真值表如下：pq00011011001010011011根据真值表，和有相同真值，故等式成立。等值演算法： 所以，等式成立。(2)真值表如下：pqr0001101100110100010011000110010010011011101111111101111111111111根据真值表，和有相同真值，故等式成立。 所以，等式成立。(3)pqac00001111000111110010100000111111010011110101111101100000011111111000111110011111101011111011111111001111110111111110010011111111根据真值表，和有相同真值，故等式成立。等值演算法： 所以，等式成立。(4)pq001111011111100100110010根据真值表，和有相同真值，故等式成立。等值演算法：所以，等式成立。(5)pq001101011011010011100000000110000111根据真值表，和有相同真值，故等式成立。等值演算法： 所以，等式成立。(6)pq0011000011000010001111100101根据真值表，和p有相同真值，故等式成立。等值演算法：所以，等式成立。(7)pq001100100011001100100011000110011000根据真值表，和有相同真值，故等式成立。等值演算法：所以，等式成立。13.化简下列公式。(1)解：(2)解：(3)解：(4)解：(5)解：14.用真值表法求下列各式的主析取和主合取范式。(1)pqr000111001101010111011101100011101011110111111111原式的主析取范式为：原式的主合取范式为：F(2)pqr000111001111010100011111100011101111110001111111原式的主析取范式为： 原式的主合取范式为：15.分别等值演算法求下列各式的主析取和主合取范式。(1) 原式的主合取范式为： (2) 原式的主合取范式为：(3)原式的主析取范式为：16.用主析取范式判断下列各组命题公式是否等值。(1)；解：是第一个公式的主合取范式，故第一个公式的主析取范式为：；第二个公式经等值演算的主析取范式为：，故两公式相等。(2)；第一个公式的主析取范式为：第二个公式本身就是主析取范式，故两公式相等。(3)；第一个公式的主析取范式为：第二个公式的主析取范式为：故两式相等。17.证明下列蕴含式成立。(1)故有：(2)故有：(3)故有：。18.证明和是逻辑等价的。故两式逻辑等价。19.化简逻辑式，并设计该逻辑式的电路图。20.使用非门，或门和与门构建组合电路，该组合电路从输入位p，q和r产生输出。第二章习题答案1.令表示“x是偶数”，判断下列各式的真值是什么？(1)(2)(3)解：(1)假，(2)真，(3)真2.令P(x)表示“”。个体域是整数，判断下列各式的真值是什么？(1)P(0)(2)P(1)(3)P(2)(4)P(-1)(5)(6)解：(1)真，(2)真，(3)假，(4)假，(5)真，(6)假3.若个体域是正整数集合，令表示，下列公式中哪些公式的值为真值？(1)(2)(3)(4)(5)(6)(7)(8)解：(1)假，(2)假，(3)真，(4)真，(5)假，(6)假，(7)真，(8)真4.将下列命题用谓词逻辑符号化。解：令P(x)：x会说俄语；Q(x)：x会phython编程语言；R(x)：x在这所学校。(1)在这所学校有个能说俄语且会phython编程语言的学生。(2)在这所学校有个能说俄语但不会phython编程语言的学生。(3)在这所学校每个学生都会说俄语且会phython编程语言。(4)在这所学校没有一个学生会说俄语或会phython编程语言。5.将下列命题用谓词逻辑符号化。(1)在这个班里有个学生家里有一只猫和一条狗。解：令P(x)：x是这个班里的学生；Q(x,y)：x家里有只y；a：狗；b：猫。(2)赵勋既努力又聪明。解：令P(x)：x努力；Q(x)：x聪明；a：赵勋。或符号化为：令p：赵勋努力；q：赵勋聪明。(3)并不是所有的女人都喜欢追剧。解：令P(x)：x是女人；Q(x)：x喜欢追剧。(4)如果你不努力，就一定不能取得成功。解：令P(x)：x努力；Q(x)：x能取得成功。(5)有些人喜欢小动物，但不是所有的人都喜欢小动物。解：令P(x)：x喜欢小动物；Q(x)：x能取得成功。(6)这个班里所有学生都选修了人工智能专业的课程。解：令P(x)：x是这个班里的学生；Q(x)：x选修了人工智能专业的课程。(7)任何偶数都能被2整除。解：令P(x)：x是偶数；Q(x)：x能被2整除。(8)这个班里的男生都喜欢打篮球。解：令P(x)：x是这个班里的男生；Q(x)：x喜欢打篮球。(9)如果今天是星期六，明天就是星期日。解：令P(x)：x是星期六，a：今天；Q(x)：x是星期天，b：明天。令p：今天是兴趣六；q：命题是星期日。(10)天气好我们就去郊游。解：令p：天气好；q：我们去郊游。6.在一阶逻辑中将下面命题符号化。(1)每个用户只能注册一个账号。解：令P(x)：x只能注册一个账号。(2)有些女生喜欢甜食。解：令P(x)：x喜欢甜食。(3)在杭州定居的人未必都是杭州人。解：令P(x)：x是在杭州定居的人；Q(x)：x是杭州人。(4)所有女人都爱看电视剧。解：令P(x)：x是女人；Q(x)：x爱看电视剧。(5)班上每个学生都报考了研究生考试。解：令P(x)：x是班上学生；Q(x)：x报考研究生考试。7.设个体域D={-2,-1,0}。消去下列各公式中的量词。(1)(2)(3)(4)(5)(6) (7)(8) (9) (10)8.设个体域D={-1,1,2}，用析取和合取联结词表示下列命题。(1)(2) (3)(4)(5)9.给定解释I如下：i.个体域为自然数集N；ii.元素a=1；iii.iv.N中的特定谓词表示：x-y=0，：x>y。在解释I下，求下列各式的真值。(1)(2)(3) (4) 10.给定解释I如下：i.个体域为自然数集N；ii.元素a=1；iii.iv.N中的特定函数；v.N中的特定谓词表示：x<y，：x>y。在解释I下，求下列各式的真值。(1)(2) (3) (4)11.指出下列各公式中每个量词的作用域，并指出个体变元是约束出现还是自由出现。(1)解：的作用域为，的作用域也为，个体变元为x和y为约束出现。(2)解：的作用域也为，约束出现的个体变元为中的x，中的y和中的x和y为自由出现的个体变元。(3)解：第一个的作用域也为，第二个的作用域也为，第一个公式和中的x为约束出现的个体变元，第一个公式和中的y为自由出现的个体变元，第二个公式中的y为约束出现的个体变元，而第二个公式的x为自由出现的个体变元。(4)解：的作用域为，的作用域也为，个体变元为x和y为约束出现。12.求下列公式的前束范式。(1)解：(2)解：(3)解：(4)解：13.求下列公式的前束范式。(1)解：(2)解：(3)解：14.化简下列各式。(1)解：(2)解：(3)解：(4)解：15.指出下列推导中的错误，并加以改正。(1)前提引入(2)(1)UI(3)前提引入(4)(3)EI(5)(4)化简律(6)(2)(5)假言推理(7)(6)EG解：第一步和第三步的顺序错误，应该先存在量词消去，后全称量词消去。改正序列：(1)前提引入(2)(1)EI(3)前提引入(4)(3)UI(5)(2)化简律(6)(4)(5)假言推理(7)(6)EG16.构造下面的推理的证明。(1)前提：，，结论：q证明：(1) 前提引入(2)前提引入(3)(1)(2)析取三段论(4)前提引入I(5)q(2)(5)假言推理(2)前提：，，结论：证明：(1) 前提引入(2)前提引入(3)(1)(2)假言推理(4)前提引入I(5)(3)(4)假言推理(6)(5)双重否定律(7)(6)蕴涵等值式(3)前提：，，结论：证明：(1) 前提引入(2)(5)双重否定律(3)(2)蕴含式(4)前提引入(5)(2)(3)假言三段论(6)(5)假言推理(7)前提引入(8)(6)(7)假言三段论(4)前提：，，结论：证明：(1) 前提引入(2)(1)蕴含式(3)前提引入(4)(3)假言易位(5)(2)(4)假言三段论(6)前提引入(7)(5)(6)假言三段论(5)前提：q，，，结论：证明：(1)附加前提(2)前提引入(3)p(2)(3)析取三段论(4)前提引入(5)(3)(4)假言推理(6)q前提引入(7)s(5)(6)假言推理17.构造下列推理的证明。(1)前提：结论：证明：(1)前提引入(2)(1)EI(3)前提引入(4)(3)EI(5)(4)UI(6)(2)(5)假言推理(7)附加(8)(6)(7)假言推理(9)(8)EU(2)前提：结论：证明：(1)前提引入(2)(1)EI(3)前提引入(4)(3)EI(5)(4)UI(6)(2)(5)假言推理(7)附加(8)(6)(7)假言推理(9)(8)EU(3)前提：结论：(4)前提：结论：(5)前提：结论：(6)前提：结论：(7)前提：结论：18.证明前提：(1)若A队得第一，则B队或C队获亚军;（2）若C队获亚军，则A队不能获冠军;（3）若D队获亚军，则B队不能获亚军;（4）A队获第一。可以推出结论：D队不是亚军。19.符号化下面的论断，并给出相应的推理证明。(1)如果今天天气晴，我们就去放风筝或划船；如果刮风，我们就不去划船。今天天气晴但有风，所以我们就去放风筝。(2)如果期末复习肯努力，就一定能通过离散数学考试。身体不好且考试科目多。没有通过离散数学考试。所以，期末复习没努力且考试科目多。20.符号化下列命题，并给出推理证明。(1)如果李楠是理科学生，她必须学习微积分。如果她不是文科学生，那么她必须是理科学生。她没有学微积分。所以她是一个文科生。(2)王敏学习英语或日语。如果王敏学习过英语，那么她就去了英国。如果去过英国，那么她去过日本。于是王敏学习日语或去了日本。(3)这个班的学生李格知道如何用JAVA编写程序。每个知道如何用JAVA编写程序的人都可以得到一份高薪工作。因此，这个班的学生都可以得到一份高薪工作。(4)这个班的人都喜欢观看鲸鱼表演。每个喜欢观看鲸鱼表演的人都关心海洋污染。因此，这个班上每个人都关心海洋污染。(5)这个班的每位都拥有一台个人计算机。拥有个人计算机的每个学生都可以使用文字处理程序。因此，这个班的李爽可以使用文字处理程序。”第三章习题答案1.判断下列集合是否相等。(1){1,2,3}和{1,1,3,2,2}(2){}和(3){}和{{},}2.设集合A={1,2,3,4,5,6}和集合B={0,3,6}。试计算下列各式：(1)(2)(3)(4)(5)(6)3.判断下列各式是否正确。(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)4.求下列集合的幂集。(1)(2){1,{a,b}}(3){,{}}(4){2,2,2,3}5.设A={}，B={1,2}，试计算。6.请用文氏图表示以下集合。(1)(2)(3)(4)(5)7.设A和B是任意集合，证明下列恒等式。(1).(2).(3)(4)(5)(6)8.已知A、B、C是三个集合，证明：(1)(2)(3)A∩(B∪C)=(A∩B)∪(A∩C)9.已知A、B、C是三个集合，证明：(1)(2)10.假设全集U={1,2,3,4,5,6,7,8,9,10}。如果i在集合中，则字符串中第i位为1，否则为0。请按上述规则的位字符串表示下列集合。(1){3,4,5}(2){1,3,6,10}(3){2,3,4,7,8,9}11.设矩阵，计算下列各式：(1)，(2)，(3)12.设矩阵，计算下列各式：(1)，(2)13.设矩阵和。计算下列各式：(1)，(2)AT，(3)BT14.设矩阵和。计算下列各式：(1)，(2)，(2)，15.设矩阵和。计算下列各式：(1)，(2)，(3)第四章习题答案1.设集合A={a,b,c}，试求。2.设关系，试求(1)(2)ranR(3)domR3.设是集合A=上的二元关系，,。试求：(1)(2)(3)(4)4.设关系R是人类集合上的二元关系，试判断关系是否是自反的，对称的，反对称的或传递的？(1)田蕾比赵艳漂亮。(2)田蕾和赵艳是同班同学。(3)田蕾比赵艳高。(4)田明和田蕾是兄妹。5.设R1和R2是关系，且矩阵分别表示为：和试计算下列各式：(1)(2)(3)(4)(5)(5)(6)6.画出下面关系的关系图。7.设集合A={1,2,3,4},R是集合A上的二元关系。试给出关系R的自反闭包