下载文档原格式
第4章 习题解答4．1 A ：⑤； B ：③； C ：①； D ：⑧； E ：⑩4．2 A ：②； B ：③； C ：⑤； D ：⑩； E ：⑦4．3 A ：②； B ：⑦； C ：⑤； D ：⑧； E ：④分析 题4.1-4.3 都涉及到关系的表示。
先根据题意将关系表示成集合表达式，然后再进行相应的计算或解答，例如，题4.1中的}2,2,1,2,2,1,1,1{},2,2,1,1{><><><><=><><=s s E I};2,2,2,1,1,1{><><><=s I而题4.2中的}.1,4,4,3,1,2,4,1,1,1{><><><><><=R为得到题4.3中的R 须求解方程123=+y x ，最终得到}.1,9,2,6,3,3{><><><=R求R R 有三种方法，即集合表达式、关系矩阵和关系图的主法。
下面由题4.2的关系分别加以说明。
1°集合表达式法将ranR ran domR domR,, 的元素列出来，如图4.3所示。
然后检查R 的每个有序对，若R y x >∈<,，则从domR 中的x 到ranR 中的y 画一个箭头。
若danR 中的x 经过2步有向路径到达ranR 中的y ，则R R y x >∈<,。
由图4.3可知}.1,3,4,2,1,2,4,4,1,44,1,1,1{><><><><>><<><=R R如果求G F ，则将对应于G 中的有序对的箭头画在左边，而将对应于F 中的有序对的箭头画在右边。
对应的三个集合分别为ranF domF ran domG ,, ，然后，同样地寻找domG 到ranF 的2步长的有向路径即可。
（完整版）离散数学电子教材1（可编辑修改word版）第1 章命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。
辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。
形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。
数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。
所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。
因此数理逻辑也称为符号逻辑。
数理逻辑的基础部分是命题逻辑和谓词逻辑。
本章主要讲述命题逻辑，谓词逻辑将在第2 章进行讨论。
1.1命题及其表示1.1.1命题的基本概念数理逻辑研究的中心问题是推理（Inference)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。
在数理逻辑中，将能够判断真假的陈述句称为命题。
因此命题就成为推理的基本单位。
在命题逻辑中，对命题的组成部分不再进一步细分。
定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。
命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。
真值为真的命题称为真命题，真值为假的命题称为假命题。
从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。
例1.1.1 判断下列句子是否为命题（1）北京是中国的首都。
（2）请勿吸烟！（3）雪是黑的。
（4）明天开会吗？（5）x+y=5。
（6）我正在说谎。
（7）9+5≤12 。
（8）1+101=110 。
（9）今天天气多好啊！（10）别的星球上有生物。
解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y 取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。
离散数学北美教材
在北美地区，离散数学是计算机科学和数学专业的重要课程之一。
以下是一些常见的北美离散数学教材：
《Discrete Mathematics and Its Applications》（离散数学及其应用）- Kenneth H. Rosen：这本教材是离散数学领域的经典教材之一。
它涵盖了离散数学的各个主题，包括集合论、图论、逻辑、证明技巧、组合数学等。
该教材以清晰的讲解和丰富的例子，帮助学生理解离散数学的基本概念和应用。
《Concrete Mathematics: A Foundation for Computer Science》（具体数学：计算机科学基础）- Ronald L. Graham, Donald E. Knuth, Oren Patashnik：这本教材是计算机科学领域的经典之作，它将离散数学与计算机科学的应用紧密结合。
该教材涵盖了离散数学的各个主题，包括递归、生成函数、离散概率等。
它以严谨的数学推导和实际的计算机科学问题，帮助学生培养数学建模和问题解决的能力。
《Discrete Mathematics: An Open Introduction》（离散数学：开放式导论）- Oscar Levin：这本教材是一本开放式教材，可以免费在线获取。
它涵盖了离散数学的基本概念和技巧，包括集合论、图论、逻辑、证明技巧等。
该教材以易懂的语言和丰富的练习题，帮助学生掌握离散数学的核心概念。
这些教材都是离散数学领域的经典教材，被广泛使用于北美的大学和学院。
具体选择教材时，可以根据个人的学习风格和教师的推荐来决定。
另外，还可以参考课程教材清单或与教师咨询，以获取更准确的教材推荐。
清华用的离散数学教材
清华大学使用的离散数学教材可能会有多种选择，这取决于具体的课程安排和教师的个人喜好。
以下列出几本可能被采用的离散数学教材：
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。
这本教材也是一本常用的离散数学教材，适合初学者。
这些教材通常涵盖离散数学的基本原理、逻辑、集合论、代数结构、图论、计算理论等内容。
请注意，具体使用哪本教材可
能因课程和教师的不同而有所变化，学生们可以根据教学大纲和教师的要求来确定使用哪本教材。
第4章映射（函数）映射（函数）是一个基本的数学概念，它是一个特殊的二元关系，我们可以把映射看作输入输出关系，它把一个集合（输入集合）的元素变成另一个集合（输出集合）的元素。
例如，计算机中的程序可以把一定范围内的任一组数据变化成另一组数据，它就是一个映射。
映射的概念经常出现在开关理论、自动机理论和可计算理论等领域中，在计算机科学中有着广泛的应用。
4.1映射（函数）的概念考虑下面几个由图4-1所示的集合x到集合y的关系.在这6个关系中，后4个关系％, &, R「凡与凡，凡不同，它们都有下而两个特点：(1)其定义域为X；(2)x中任一元素。
对应唯一一个y中的元素〃。
我们称具有这样两个特征的关系为映射(函数)。
定义4.1.1设x,y是两个任意的集合，而/是x到丫的一个关系，若对每一个xeX，都存在一个唯一的yeY ,使得,则称关系/为X到V的映射(Mapping),记作/： X -丫或若(X,)),则称X为自变量(Independent Variable),称y为映射f在X处的值(或像(Image)), (x,))e/亦可记作y =/(x) , /的值域ran/yy,有时也记为H,,即穴/ = 3, £丫人(石)。
£X A y = /(%)))或记为/(X) = {/(x)|xeX)集合Y称为f的共域，R,亦称为映射f的像集合。
对于A三X ,称/(A)为A的像(Image of A),定义为/(A) = {f(x)卜£A} = {y |3A-(X e A A y = /(x))}显然,，/") =。
J({M) = {/W}(xe X) °映射/是x到y的特殊的二元关系，其特殊性在于：(1)dom/ = X,即关系/的前域是X本身，而不是X的真子集。
(2)若依加f ,则映射/在4处的值y是唯一的，即(X,加//\(x,Z)e/ = y = Z例4.1.1 设X=S，bcd},Y = {123,4,5},且有f = {(a,l),(b,3),(c,4),〈4,4»,求dom /、( 和/(x)。
离散数学第四版课后答案第1章习题解答1．1 除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。
分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。
本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。
其次，4）这个句子是陈述句，但它表示的判断结果是不确定。
又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。
（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。
这里的“且”为“合取”联结词。
在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。
但要注意，有时“和”或“与”联结的是主语，构成简单命题。
例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。
1．2 （1）p: 2是无理数，p为真命题。
（2）p:5能被2整除，p为假命题。
（6）p→q。
其中，p:2是素数，q：三角形有三条边。
由于p与q都是真命题，因而p→q为假命题。
（7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。
由于p为假命题，q为真命题，因而p→q为假命题。
（8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。
（9）p：太阳系外的星球上的生物。
它的真值情况而定，是确定的。
1（10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。
第9章树[离散数学离散数学(第四版)清华出版社]第二章一阶逻辑（Predicate Logic）1、一阶逻辑基本概念2、一阶逻辑公式及解释3、一阶逻辑等值式1、一阶逻辑基本概念前两节介绍的命题与命题演算是命题逻辑的内容，其基本组成单位是原子命题。
一般地，原子命题作为具有真假意义的句子至少由主语和谓语两部分组成。
例如，电子商务是计算机技术的一个应用系统，这里“电子商务”是主语，而“是……”是谓语。
当主语改变为“电子政务”时就得到新的原子命题：电子政务是计算机技术的一个应用系统。
由此可知，主语是独立存在的个体，而谓语用来描述该个体的性质或个体间的关系，这里我们称其为谓词。
用P表示谓词“是……”。
则P（电子商务）或P（电子政务）分别等值于前述两个命题的表达。
将个体用变量（称为个体变量）x推广，则P(x)表示：x是计算机技术的一个新的应用系统。
这时该语句就不是一个命题，而是一个命题函数。
DEFINITION 1.一个谓词P连同相关的n(n≥0)个个体变量组成的表达式称为n元谓词(n-predicate)，记P(x1, x2, …, x n)，其中n是该表达式中不同个体变量的数目。
EXAMPLE 1设P(x)表示语句“x > 3.”，则P(4)和P(2)的真值是多少?P(4) = 1P(2) = 0EXAMPLE 2设Q(x, y)表示语句“x = y + 3.”，则Q(1, 2) 和Q(3, 0)的真值是多少?Q(1,2) = 0Q(3,0) = 1EXAMPLE 3设R(x, y, z) 表示语句“x+y=z.”，则R(1, 2, 3) 和R(0, 0, 1) 的真值是多少?R(1, 2, 3)= 1R(0, 0, 1)= 0当n>1时，通常P给出了xi(i=1,2,…,n)之间的关系。
例如，P(x,y,z)表示x位于y与z之间，是一个三元谓词。
当x,y,z分别用赤道、南半球、北半球代入时，得到命题：赤道位于南半球与北半球之间，其真值为1。
