清华离散数学(第2版):1.3
- 格式:ppt
- 大小:508.00 KB
- 文档页数:19
附录2 习题答案习题一答案1.1下列各语句中哪些是命题?1) 不是;2) 是;3) 不是;4) 不是;5) 不是;6) 是;7) 是;8) 不是9) 不是;10)是;11)不是;12)是。
1.2 将下列命题符号化。
1) p∧⌝q, p:太阳明亮,q:湿度高;2) q→⌝p, p:明天你看到我,q:我要去深圳。
3) p→q, p:我出校,q:我去图书城;4) q→p , p:你去,q:我去;5) 5.1) p∧q; 5.2) p∧⌝q; 5.3) p∧q; 5.4) p∧⌝q;6) 6.1) p∨q 6.2) ⌝(p ↔q) 6.3) p∧¬q6.4) ¬ (p∧r) 6.5) (p∧q) →r 6.6)¬ (r→ (p∧q))7) p:蓝色和黄色可以调配成绿色;8) ⌝(p↔q), p:李兰现在在宿舍, q:李兰在图书馆里;9) ¬p→¬ q, p:一个人经一事,q:一个人长一智;10) (p∧¬q) →⌝(r↔ s), p:晚上小王做完了做业, q: 晚上小王没有其他事情,r: 晚上小王看电视, s: 晚上小王看电影。
11) ⌝(r↔ s), r:小飞在睡觉, s:小飞在游泳;12) ¬p∧¬q∧r, p:这个星期天我看电视,q: 这个星期天我外出,r:这个星期天我在睡觉。
13) p→q , p:卫星上天了,q:国家强大了;14) p→q, p:今天没有课,q:我呆在图书馆里;15) p→q,p:我去图书城,q:我有时间;16) ¬p→¬q , p:人们辛劳,p: 人们收获1.3 1) 小李家住北大西门外, 他现在坐在公共汽车里看书,没有考虑问题;2) 小李在思考问题, 他没有乘坐公共汽车,也没有看书;3) 小李只要乘坐公共汽车,他就看书或考虑问题;4) 小李乘坐公共汽车,要么看书不考虑问题,要么考虑问题不看书,5) 同4);6) 如果小李家住北大西门外,则他现在没有乘坐公共汽车,没有看书,也没有考虑问题。
离散数学(第⼆版)最全课后习题答案详解习题⼀1.下列句⼦中,哪些是命题?在是命题的句⼦中,哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道?(1)中国有四⼤发明.答:此命题是简单命题,其真值为 1.(2)5是⽆理数.答:此命题是简单命题,其真值为 1.(3)3是素数或4是素数.答:是命题,但不是简单命题,其真值为 1.(4)2x+ <3 5答:不是命题.(5)你去图书馆吗?答:不是命题.(6)2与3是偶数.答:是命题,但不是简单命题,其真值为0.(7)刘红与魏新是同学.答:此命题是简单命题,其真值还不知道.(8)这朵玫瑰花多美丽呀!答:不是命题.(9)吸烟请到吸烟室去!答:不是命题.(10)圆的⾯积等于半径的平⽅乘以π .答:此命题是简单命题,其真值为 1.(11)只有6是偶数,3才能是2的倍数.答:是命题,但不是简单命题,其真值为0.(12)8是偶数的充分必要条件是8能被3整除.答:是命题,但不是简单命题,其真值为0.(13)2008年元旦下⼤雪.答:此命题是简单命题,其真值还不知道.2.将上题中是简单命题的命题符号化.解:(1)p:中国有四⼤发明.(2)p:是⽆理数.(7)p:刘红与魏新是同学.3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值.(1)5是有理数.答:否定式:5是⽆理数. p:5是有理数.q:5是⽆理数.其否定式q的真值为 1.(2)25不是⽆理数.答:否定式:25是有理数. p:25不是⽆理数. q:25是有理数.其否定式q的真值为1.(3)2.5是⾃然数.答:否定式:2.5不是⾃然数. p:2.5是⾃然数. q:2.5不是⾃然数.其否定式q的真值为1.(4)ln1是整数.答:否定式:ln1不是整数. p:ln1是整数. q:ln1不是整数.其否定式q的真值为1.4.将下列命题符号化,并指出真值.(1)2与5都是素数答:p:2是素数,q:5是素数,符号化为p q∧,其真值为1.(2)不但π是⽆理数,⽽且⾃然对数的底e也是⽆理数.答:p:π是⽆理数,q:⾃然对数的底e是⽆理数,符号化为p q∧,其真值为 1.(3)虽然2是最⼩的素数,但2不是最⼩的⾃然数.答:p:2是最⼩的素数,q:2是最⼩的⾃然数,符号化为p q∧?,其真值为1.(4)3是偶素数.答:p:3是素数,q:3是偶数,符号化为p q∧,其真值为0.(5)4既不是素数,也不是偶数.答:p:4是素数,q:4是偶数,符号化为? ∧?p q,其真值为0.5.将下列命题符号化,并指出真值.(1)2或3(3)3或5是偶数.(4)3不是偶数或4不是偶数.(5)3不是素数或4不是答: p:2是偶数,q:3是偶数,r:3是素数,s:4是偶数, t:5是偶数偶数.(1)符号化: p q∨,其真值为 1.(2)符号化:p r∨,其真值为1. (3)符号化:r t∨,其真值为0.(4)符号化:? ∨?q s,其真值为 1.(5)符号化:? ∨?r s,其真值为0.6.将下列命题符号化.(1)⼩丽只能从筐⾥拿⼀个苹果或⼀个梨.答:p:⼩丽从筐⾥拿⼀个苹果,q:⼩丽从筐⾥拿⼀个梨,符号化为: p q∨ .(2)这学期,刘晓⽉只能选学英语或⽇语中的⼀门外语课.答:p :刘晓⽉选学英语,q :刘晓⽉选学⽇语,符号化为: (? ∧∨∧?p q )(p q ) . 7.设 p :王冬⽣于 1971年,q :王冬⽣于1972年,说明命题“王冬⽣于1971年或 1972年”既可以化答:列出两种符号化的真值表: p q 0 0 1 10 1 0 10 1 1 00 1 1 1根据真值表,可以判断出,只有当 p 与 q 同时为真时两种符号化的表⽰才会有不同的真值,但结合命题可以发现,p 与 q 不可能同时为真,故上述命题有两种符号化⽅式.8.将下列命题符号化,并指出真值.,就有(1)只要(2)如果(3)只有(4)除⾮(5)除⾮(6),则:;设 q:,则:答:设 p: .符号化真值(1)(2)(3)(4)(5)1 1 0 0 0(6) 19.设p:俄罗斯位于南半球,q:亚洲⼈⼝最多,将下⾯命题⽤⾃然语⾔表述,并指出其真值:(1)(2);;;(3)(4);;(5)(6)(7);;.答:根据题意,p为假命题,q为真命题.⾃然语⾔真值(1)(2)(3)(4)(5)(6)(7)只要俄罗斯位于南半球,亚洲⼈⼝就最多只要亚洲⼈⼝最多,俄罗斯就位于南半球11111 只要俄罗斯不位于南半球,亚洲⼈⼝就最多只要俄罗斯位于南半球,亚洲⼈⼝就不是最多只要亚洲⼈⼝不是最多,俄罗斯就位于南半球只要俄罗斯不位于南半球,亚洲⼈⼝就不是最多只要亚洲⼈⼝不是最多,俄罗斯就不位于南半球10.设p:9是3的倍数,q:英国与⼟⽿其相邻,将下⾯命题⽤⾃然语⾔表述,并指出真值:.答:根据题意,p为真命题,q为假命题.⾃然语⾔真值(1)(2)(3)9是3的倍数当且仅当英语与⼟⽿其相邻9是3的倍数当且仅当英语与⼟⽿其不相邻9不是3的倍数当且仅当英语与⼟⽿其相邻11(4)9不是 3的倍数当且仅当英语与⼟⽿其不相邻 011.将下列命题符号化,并给出各命题的真值:(1)若 2+2=4,则地球是静⽌不动的;(2)若 2+2=4,则地球是运动不⽌的;(3)若地球上没有树⽊,则⼈类不能⽣存;(4)若地球上没有⽔,则是⽆理数. 答:命题 1命题 2符号化真值(1)(2)(3)(4)p:2+2=4 q:地球是静⽌不动的 q:地球是静⽌不动的 q:⼈类能⽣存0 p:2+2=4 1 1 1p:地球上有树⽊ p:地球上有树⽊q:⼈类能⽣存12.将下列命题符号化,并给出各命题的真值:(1)2+2=4当且仅当 3+3=6;(2)2+2=4的充要条件是 3+36;(3)2+2 4与 3+3=6互为充要条件;(4)若 2+2 4,则 3+3 6,反之亦然. 答:设p:2+2=4,q:3+3=6. 符号化真值 (1) (2) (3) (4)(3)今天是星期⼀当且仅当明天是星期⼆;(4)若今天是星期⼀,则明天是星期三.答:设p:今天是星期⼀,q:明天是星期⼆,r:明天是星期三.符号化真值讨论(1)(2)(3)(4)不会出现前句为真,后句为假的情况不会出现前句为真,后句为假的情况必然为1若p为真,则真值为0;若p为假,则真值为114.将下列命题符号化:(1)刘晓⽉跑得快,跳得⾼;(2)⽼王是⼭东⼈或者河北⼈;(3)因为天⽓冷,所以我穿了⽻绒服;(4)王欢与李乐组成⼀个⼩组;(5)李欣与李末是兄弟;(6)王强与刘威都学过法语;(7)他⼀⾯吃饭,⼀⾯听⾳乐;(8)如果天下⼤⾬,他就乘班车上班;(9)只有天下⼤⾬,他才乘班车上班;(10)除⾮天下⼤⾬,否则他不乘班车上班;(11)下雪路滑,他迟到了;(12)2与4都是素数,这是不对的;(13)“2或4是素数,这是不对的”是不对的.答: 命题1 命题2命题3符号化(1)(2)p:刘晓⽉跑得快q:刘晓⽉跳得⾼-p:⽼王是⼭东⼈p:天⽓冷q:⽼王是河北⼈----q:我穿⽻绒服p:王欢与李乐组成p:王欢与李乐组成⼀个--⼀个⼩组⼩组p:李⾟与李末是兄p:李⾟与李末是兄弟弟(6)(7) p:王强学过法语p:他吃饭q:刘威学过法语q:他听⾳乐q:他乘车上班q:他乘车上班q:他乘车上班q:路滑--(8) p:天下⼤⾬p:天下⼤⾬p:天下⼤⾬p:下雪-(9) -(10)(11)r:他迟到了p:2是素数p:2是素数q:4是素数--q:4是素数15.设p:2+3=5.q:⼤熊猫产在中国.r:太阳从西⽅升起.求下列符合命题的真值:(1)(2)(3)(4)解:p真值为1,q真值为1,r真值为0.(1)0,(2)0,(3)0,(4)116.当p,q的真值为0,r,s的真值为1时,求下列各命题公式的真值:(1)(2)(3)(4)解:(1)0,(2)0,(3)0,(4)117.判断下⾯⼀段论述是否为真:“是⽆理数.并且,如果3是⽆理数,则外,只有6能被2整除,6才能被4整除.”也是⽆理数.另解:p:是⽆理数q: 3是⽆理数r:是⽆理数s: 6能被2整除18.在什么情况下,下⾯⼀段论述是真的:“说⼩王不会唱歌或⼩李不会跳舞是正确的,⽽说如果⼩王会唱歌,⼩李就会跳舞是不正确的.”解:p:⼩王会唱歌。
离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科,它研究离散对象及其关系、结构和运算方法。
离散数学的应用非常广泛,包括计算机科学、信息科学、密码学、人工智能等领域。
而离散数学第2版是一本经典的教材,它系统地介绍了离散数学的基本概念、原理和方法。
本文将为读者提供离散数学第2版课后习题的答案,帮助读者更好地理解和掌握离散数学的知识。
第一章:基本概念和原理1.1 命题逻辑习题1:命题逻辑的基本符号有哪些?它们的含义是什么?答:命题逻辑的基本符号包括命题变量、命题联结词和括号。
命题变量用字母表示,代表一个命题。
命题联结词包括否定、合取、析取、条件和双条件等,分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。
括号用于改变命题联结词的优先级。
习题2:列举命题逻辑的基本定律。
答:命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。
1.2 集合论习题1:什么是集合?集合的基本运算有哪些?答:集合是由一些确定的对象组成的整体,这些对象称为集合的元素。
集合的基本运算包括并、交、差和补等。
习题2:列举集合的基本定律。
答:集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。
第二章:数理逻辑2.1 命题逻辑的推理习题1:什么是命题逻辑的推理规则?列举几个常用的推理规则。
答:命题逻辑的推理规则是用来推导命题的逻辑规则。
常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。
习题2:使用推理规则证明以下命题:如果A成立,则B成立;B不成立,则A不成立。
答:假言推理规则可以用来证明该命题。
根据假言推理规则,如果A成立,则B成立。
又根据假言推理规则,如果B不成立,则A不成立。
2.2 谓词逻辑习题1:什么是谓词逻辑?它与命题逻辑有何区别?答:谓词逻辑是一种扩展了命题逻辑的逻辑系统,它引入了谓词和量词。
与命题逻辑不同,谓词逻辑可以对个体进行量化和描述。
离散数学是计算机科学、电子工程、数学工
程等多个领域中必备的基础课程。
本书《离
散数学及其应用》第2版是被广泛使用的教材,它采用了清晰的教学方式和生动的实例,深入浅出地介绍了离散数学的基本概念、方
法和技巧,为学生提供了一种系统化的方法
来解决离散问题。
本书包含了大量的例题和习题,既有较为基
础的内容,也有一些较为高级的内容。
它包
括了算法、图论、逻辑、布尔代数、关系代
数和集合论等多个方面,深入掌握这些知识,将有助于读者在计算机和工程领域的实际应
用中快速解决实际问题。
此外,本书也包含有一些扩展的内容,例如确定有限自动机(DFA)、上下文无关语法(CFG)、正则表达式和语言等,在很多实际问题中这些内容也是非常重要的。
离散数学及其应用第2版课后练习题含答案1. 引言《离散数学及其应用》是一本经典的离散数学教材,是计算机科学和数学专业的必修课程。
本文将为读者提供《离散数学及其应用》第2版课后练习题的答案,并希望能够帮助读者加深对离散数学的理解。
2. 答案解析第一章习题 1.11.给定一组七个数字 {1, 3, 3, 4, 6, 9, 12},请给出这组数字的中位数。
答案:中位数为 4。
2.给出两个整数 a 和 b 的三进制表示: a = 111011,b = 101101。
求 a + b。
答案:a + b = 1011000。
3.证明奇奇数的积为奇数。
答案:令两个奇数分别为 2n + 1 和 2m +1,则有:(2n + 1) × (2m + 1) = 4nm + 2n + 2m + 1 = 2(2nm + n + m) + 1,即奇奇数的积还是一个奇数。
习题 1.21.证明:如果一个整数 n 能同时被 2 和 3 整除,则它也能被 6 整除。
答案:首先,n 能同时被 2 和 3 整除,则分别有 n = 2k 和 n = 3m。
联立方程组 2k = 3m,得 k = (3/2)m。
因此,n = 2k = (3m/2) × 2 = 3m× (2/2) = 6m,可以被 6 整除。
2.求 10010 的八进制表示。
答案:将 10010 转换为四位一组的二进制数,得 0010 0100。
将 0010 和 0100 分别转换为八进制数,得 2 和 4。
因此,10010 的八进制表示为 24。
3.已知 547a5 是 11 的倍数,求 a 的值。
答案:根据 11 的倍数的规律,将 547a5 中的奇数位数字相加,再将偶数位数字相加,然后将两个和的差求出来: (5 + 7 + a) - (4 + 5) = 13 + a - 9 = a + 4。
因为547a5 是 11 的倍数,所以 a + 4 也必须是 11 的倍数。
离散数学(第2版)——关于数学中重要的研究方向
离散数学是一门涉及数学中各种离散对象的研究方向,包括数论、图论、代数等。
离散数学是计算机科学、通信工程和其他许多工科领域的基础,对于理解计算机算法的原理和应用具有重要意义。
本文将对离散数学(第2版)这本数学教材进行介绍。
离散数学(第2版)是由美国杜克大学的Kenneth H. Rosen所著的数学教材。
这本书共分为五章,分别是基础概念、逻辑和计算、数论、图论、代数和应用。
第一章主要介绍了离散数学的基础概念,包括逻辑基础、集合、关系和函数。
第二章介绍了逻辑和计算的相关内容,包括命题逻辑、谓词逻辑、计算机科学中的逻辑和布尔代数。
第三章是关于数论的章节,包括质数、最大公约数、最小公倍数、模运算、同余方程等内容。
第四章是关于图论的章节,包括无向图、有向图、连通图、生成树、最短路径、最小生成树等内容。
第五章是关于代数和应用的章节,包括代数系统、群、域、同余环、线性代数和代数应用等内容。
本书还附有大量的练习题,帮助读者检验自己的学习效果。
离散数学(第2版)是一本系统而全面的数学教材,涵盖了离散数学的各个方面。
它适合作为计算机科学和工科领域的数学基础教材,也可作为普及离散数学的参考书。
清华用的离散数学教材
清华大学使用的离散数学教材可能会有多种选择,这取决于具体的课程安排和教师的个人喜好。
以下列出几本可能被采用的离散数学教材:
1. 《离散数学及其应用(原书第7版)》(Discrete Mathematics and its Applications, 7th Edition),作者:肯尼斯·罗森(Kenneth H. Rosen)。
这是一个广受欢迎的离散数学教材,在全球范围内被广泛使用。
2. 《离散数学及其应用(原书第5版)》(Discrete Mathematics and its Applications, 5th Edition),作者:肯尼斯·罗森(Kenneth H. Rosen)。
这是前述书籍的较早版本,也被广泛采用。
3. 《离散数学导论(原书第3版)》(Introduction to Discrete Mathematics, 3rd Edition),作者:Richard Johnsonbaugh。
这是一本介绍离散数学基本概念和应用的教材,也是一门非常经典的教材。
4. 《离散数学导论(修订版)》(Discrete Mathematics: An Introduction),作者:Susanna S. Epp。
这本教材也是一本常用的离散数学教材,适合初学者。
这些教材通常涵盖离散数学的基本原理、逻辑、集合论、代数结构、图论、计算理论等内容。
请注意,具体使用哪本教材可
能因课程和教师的不同而有所变化,学生们可以根据教学大纲和教师的要求来确定使用哪本教材。
离散数学课后答案详解第二版离散数学课后答案详解第二版是一本重要的参考书,在学习离散数学的过程中能够提供很大的帮助。
下面就是本书中的一些重要知识点和解答,希望对各位读者有所帮助。
一、命题逻辑1.什么是命题?命题是用来陈述某个陈述语句真假的陈述句。
2.什么是合取和析取?合取是将两个命题连接起来,且要求两者同时成立,符号用“∧”表示;析取是也将两个命题连接起来,但是只要求其中一个成立即可,符号用“∨”表示。
3.什么是条件和双条件?条件是指前者为真则后者为真,否则后者为假,符号用“→”表示;双条件是指前者为真则后者为真,否则后者为假;同时后者为真则前者也为真,反之后者为假则前者也为假,符号用“↔”表示。
4.什么是命题公式?命题公式是用变量、命题连接词和括号构成的表达式,构成命题公式的常常为命题或者是一些常用的命题连接词。
二、谓词逻辑1.什么是一阶逻辑?一阶逻辑是对命题进行量化的扩展。
除了命题外,一阶逻辑还包括了“个体”和它们之间的关系,以及用于描述这些关系的“量词”。
2.什么是量词?量词包括“存在量词∃”和“全称量词∀”,前者表示存在至少一个使谓词成立的个体,后者表示所有个体都满足该谓词。
3.什么是命题函数?命题函数是将数学函数和逻辑命题符号相结合的一种新型命题符号。
4.什么是名词?名词是指代对象的标签,它是一般化的名词。
例如,女人是一般化的名词,梅丽莎是特定的名词。
三、集合论和图论1.什么是集合?集合是指具有某种共同特征而组成的元素的整体。
2.什么是集合的理论?集合的理论是关于集合的性质、关系和操作的一种抽象理论。
3.什么是图?图是用来描述一些个体之间的关系的工具,由节点和边构成。
其中节点表示个体,边表示个体之间的某种关系。
4.什么是路径?路径是指通过边连接一些节点的一系列节点。
四、树和排序1.什么是树?树是一种数据结构,它由一组节点和边构成。
节点可以包含数据,边用于连接节点并表示关系。
2.什么是排序?排序是一种对数据进行重新排列的操作,目的是使数据具有某种有序结构。
习题答案习题一答案1.1下列各语句中哪些是命题?1) 不是;2) 是;3) 不是;4) 不是;5) 不是;6) 是;7) 是;8) 不是9) 不是;10)是;11)不是;12)是。
1.2 将下列命题符号化。
1) p∧⌝q, p:太阳明亮,q:湿度高;2) q→⌝p, p:明天你看到我,q:我要去深圳。
3) p→q, p:我出校,q:我去图书城;4) q→p , p:你去,q:我去;5) 5.1) p∧q; 5.2) p∧⌝q; 5.3) p∧q; 5.4) p∧⌝q;6) 6.1) p∨q 6.2) ⌝(p ↔q) 6.3) p∧¬q6.4) ¬ (p∧r) 6.5) (p∧q) →r 6.6)¬ (r→ (p∧q))7) p:蓝色和黄色可以调配成绿色;8) ⌝(p↔q), p:李兰现在在宿舍, q:李兰在图书馆里;9) ¬p→¬ q, p:一个人经一事,q:一个人长一智;10) (p∧¬q) →⌝(r↔ s), p:晚上小王做完了做业, q: 晚上小王没有其他事情,r: 晚上小王看电视, s: 晚上小王看电影。
11) ⌝(r↔ s), r:小飞在睡觉, s:小飞在游泳;12) ¬p∧¬q∧r, p:这个星期天我看电视,q: 这个星期天我外出,r:这个星期天我在睡觉。
13) p→q , p:卫星上天了,q:国家强大了;14) p→q, p:今天没有课,q:我呆在图书馆里;15) p→q,p:我去图书城,q:我有时间;16) ¬p→¬q , p:人们辛劳,p: 人们收获1.3 1) 小李家住北大西门外, 他现在坐在公共汽车里看书,没有考虑问题;2) 小李在思考问题, 他没有乘坐公共汽车,也没有看书;3) 小李只要乘坐公共汽车,他就看书或考虑问题;4) 小李乘坐公共汽车,要么看书不考虑问题,要么考虑问题不看书,5) 同4);6) 如果小李家住北大西门外,则他现在没有乘坐公共汽车,没有看书,也没有考虑问题。
离散数学第二版课后答案pdf选择题:1. 以下哪个函数不是单射?A. f(x)=x+1B. f(x)=x²C. f(x)=sin(x)D. f(x)=|x|2. 设 A={1,2,3},B={2,3,4},则A∪B=?A. {1,2,3,4}B. {2,3}C. {1,2,3}D. {1,2,3,4,5}3. 若 5n+1 是完全平方数,则 n 的取值范围是?A. n 是任意自然数B. 1、3、11C. 2、3、7D. 0、2、84. 若 P(A)=0.4,P(B)=0.3,P(AB)=0.1,则P(A∪B)=?A. 0.2B. 0.3C. 0.4D. 0.55. 在一个 10 个点的完全图中,不同颜色的边有红、蓝、绿三色,其中红边有 3 条,蓝边有 2 条,绿边有 5 条,则将这 10 个点分成涂3 种颜色的三部分的方案数为?A. 6552B. 1260C. 3150D. 5040选择题答案:1. C2. D3. B4. A5. C填空题:1. 用 1,2,3,4,5 这 5 个数字,能组成多少个长度为 3 的无重复的数字串?答:602. 已知 a+b=7,a-b=3,则 a²-b²=?答:203. 一个无向图有 8 条边,则它的图的边数有多大范围?答:4≤边数≤284. 在一组含有 5 个正整数的数列中,最大值是最小值的 3 倍,则这5 个数中的最小值不能小于多少?答:55. 若 G 是一个有 n 个点的简单无向图,且 G 不是完全图,则 G 中边的数量最少是多少?答:n填空题答案:1. 602. 203. 4≤边数≤284. 55. n解答题:1. 一张简单无向图 G 有 10 个顶点和 20 条边,证明 G 中至少有 3 个度数为偶数的顶点。
答:设 G 中度数为奇数的点的个数为 x,度数为偶数的点的个数为 y,则 x+y=10,2x+4y=40,化简得 x=2y-10,由于每个点的度数都是偶数或奇数,所以 2x+20-y 是偶数,即 2(2y-10)+20-y=3y-10 是偶数,即 y 是奇数。
附录2 习题答案习题一答案1.1下列各语句中哪些是命题?1) 不是;2) 是;3) 不是;4) 不是;5) 不是;6) 是;7) 是;8) 不是9) 不是;10)是;11)不是;12)是。
1.2 将下列命题符号化。
1) p∧⌝q, p:太阳明亮,q:湿度高;2) q→⌝p, p:明天你看到我,q:我要去深圳。
3) p→q, p:我出校,q:我去图书城;4) q→p , p:你去,q:我去;5) 5.1) p∧q; 5.2) p∧⌝q; 5.3) p∧q; 5.4) p∧⌝q;6) 6.1) p∨q 6.2) ⌝(p ↔q) 6.3) p∧¬q6.4) ¬ (p∧r) 6.5) (p∧q) →r 6.6)¬ (r→ (p∧q))7) p:蓝色和黄色可以调配成绿色;8) ⌝(p↔q), p:李兰现在在宿舍, q:李兰在图书馆里;9) ¬p→¬ q, p:一个人经一事,q:一个人长一智;10) (p∧¬q) →⌝(r↔ s), p:晚上小王做完了做业, q: 晚上小王没有其他事情,r: 晚上小王看电视, s: 晚上小王看电影。
11) ⌝(r↔ s), r:小飞在睡觉, s:小飞在游泳;12) ¬p∧¬q∧r, p:这个星期天我看电视,q: 这个星期天我外出,r:这个星期天我在睡觉。
13) p→q , p:卫星上天了,q:国家强大了;14) p→q, p:今天没有课,q:我呆在图书馆里;15) p→q,p:我去图书城,q:我有时间;16) ¬p→¬q , p:人们辛劳,p: 人们收获1.3 1) 小李家住北大西门外, 他现在坐在公共汽车里看书,没有考虑问题;2) 小李在思考问题, 他没有乘坐公共汽车,也没有看书;3) 小李只要乘坐公共汽车,他就看书或考虑问题;4) 小李乘坐公共汽车,要么看书不考虑问题,要么考虑问题不看书,5) 同4);6) 如果小李家住北大西门外,则他现在没有乘坐公共汽车,没有看书,也没有考虑问题。
第二版高等教育出版社课后答案第一章部分课后习题参考答案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.判断下面一段论述是否为真:“ 是无理数。
并且,如果 3 是无理数,则 2 也是无理数。
另外6 能被2 整除,6 才能被4 整除。
答:p: 是无理数1q: 3 是无理数0r:2是无理数1s: 6 能被 2 整除1t: 6 能被 4 整除0命题符号化为:p∧(q→ r)∧(t→ s)的真值为1,所以这一段的论述为真19.用真值表判断下列公式的类型:4)(p→ q) →( q→p)5)(p∧ r) ( p∧q)6)((p→ q) ∧ (q→ r)) →(p→r)答: ( 4)p q p→q q p0 0 1 1 10 1 1 0 11 0 0 1 01 1 1 0 0所以公式类型为永真式( 5)公式类型为可满足式(方法如上例) q→ p111(p→q)→( q→ p)1111( 6)公式类型为永真式(方法如上例)第二章部分课后习题参考答案3.用等值演算法判断下列公式的类型,对不是重言式的可满足式,再用真值表法求出成真赋值.(1)](pAq-q)(2)(p^(pVq))V (p^r)⑶(pVq) 一(pAr)答:(2) (p一(pVq)) V(p-r)= (一pV(pVq))V(「pVr)=「pVpVqVru 1 所以公式类型为永真式⑶p q r PV q p A r (pV q) f (p/\「)0 0 0 0 0 10 0 1 0 0 10 1 0 1 0 00 1 1 1 0 01 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以公式类型为可涉足式4,用等值演算法证明下面等值式:⑵(p 一q)A(p—r) u (p 一(qAij)⑷(p A「q) V「pAq)u (p Vq) A」(p A q)证明(2) (p -q) A (p->r)u (」pVq) A(「pVr)u「P V (q A ij)u p一(q A r)(4) (pA「q) V(「pAq)u (p V(^pAq)) A(「qV(「pAq). (p V「p) A (p Vq) A (「qV「p) A(「qVq)u 1 A (p V q) A - (p A q) A 1u (p V q) A (p A q)5.求下列公式的主析取范式与主合取范式,并求成真赋值(1)(「p-q)-(「qVp)(2)](p - q) AqAr(3)(p V(q Ar)) 一(p VqVr)解:( 1)主析取范式( p→q)→( q p)(p q) ( q p)( p q) ( q p)( p q) ( q p) ( q p) (p q) (p q)( p q) (p q) (p q)m0 m2 m3∑ (0,2,3) 主合取范式:( p→q) →( q p)(p q) ( q p)( p q) ( q p)( p ( q p)) ( q ( q p))1 (p q)(p q) M1∏ (1)(2)主合取范式为:(p →q) q r ( p q) q r(p q) q r 0所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为0(3)主合取范式为:(p (q r)) →(p q r)(p (q r)) →(p q r)( p ( q r)) (p q r)( p (p q r)) (( q r)) (p q r))11所以该式为永真式.永真式的主合取范式为1主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案14. 在自然推理系统P 中构造下面推理的证明:(2)前提:p q, (q r),r结论:p(4)前提:q p,q s,s t,t r结论:p q证明: ( 2)①(q r) 前提引入②q r ①置换③q r ②蕴含等值式④r 前提引入⑤q ③④拒取式⑥p q 前提引入⑦¬p( 3) ⑤⑥拒取式证明( 4) :①t r 前提引入②t ①化简律③q s 前提引入④s t 前提引入⑤q t ③④等价三段论⑥( q t ) (t q) ⑤ 置换⑦( q t ) ⑥化简⑧q ②⑥ 假言推理⑨q p 前提引入15在自然推理系统 P 中用附加前提法证明下面各推理:(1) 前提:p(q r),s p,q结论:s r证明① s 附加前提引入 ② s p 前提引入 ③ p ①②假言推理 ④ p (q r)前提引入 ⑤ q r ③④假言推理 ⑥ q 前提引入 ⑦ r ⑤⑥假言推理16 在自然推理系统 P 中用归谬法证明下面各推理:(1) 前提: p q, r q,r s 结论: p证明:① p 结论的否定引入 ② p ﹁ q 前提引入 ③﹁q ①②假言推理 ④¬r q 前提引入 ⑤¬r ④化简律 ⑥ r ¬s 前提引入⑦ r ⑥化简律 ⑧ r ﹁r⑤⑦ 合取由于最后一步 r ﹁ r 是矛盾式 , 所以推理正确 .⑩p (11)p q ⑧⑨假言推第四章部分课后习题参考答案3.在一阶逻辑中将下面将下面命题符号化, 并分别讨论个体域限制为(a),(b) 条件时命题的真值:(1)对于任意x, 均有2=(x+ )(x ).(2)存在x, 使得x+5=9.其中(a) 个体域为自然数集合.(b) 个体域为实数集合.解:F(x): 2=(x+ )(x ).G(x): x+5=9.(1)在两个个体域中都解释为xF(x),在( a)中为假命题,在(b) 中为真命题。