离散数学第二版答案(1-5章).doc

目录第一章命题逻辑11.1第7页11.2第15页61.3第22页131.4第27页14第二章 谓词逻辑222.2第43页222.3第46页31第三章 集合论343.1第50页343.2 第59页373.3第62页433.4第66页46第四章 二元关系494.1第69页494.2第78页534.3第86页584.5第103页67第五章 函数715.1第108页715.2第111页735.3第113页74(1)任取xA,有76(c) 将A上的函数f满足ff = IA,则任取xA,有775.4第116页785.5第118页795.6第121页83第一章 命题逻辑1.1第7页1. 给出下列命题的否定命题： （1）大连的每条街道都临海。否命题：不是大连的每条街道都临海。（2）每一个素数都是奇数。否命题： 并非每一个素数都是奇数。2. 对下述命题用中文写出语句：（1）如果非P与R，那么Q。（2）Q并且R。4. 给出命题，我们把、分别称为命题的逆命题、反命题、逆反命题。（1）如果天不下雨，我将去公园。 解：逆命题：如果我去公园，则天不下雨； 反命题：如果天下雨，则我不去公园； 逆反命题：如果我不去公园，则天下雨了。（2）仅当你去我才逗留。解：（此题注意：p仅当q翻译成） 逆命题：如果你去，那么我逗留。 反命题：如果我不逗留，那么你没去。 逆反命题：如果你没去，那么我不逗留。（3）如果n是大于2的正整数，那么方程无整数解。解：逆命题：如果方程无整数解，那么n是大于2的正整数。 反命题：如果n不是大于2的正整数，那么方程有整数解。 逆反命题：如果方程有整数解，那么n不是大于2的正整数。7. 给P和Q指派真值T，给R和S指派真值F，求出下列命题的真值。（1）=（2）=（3）=（4）=8 构成下列公式的真值表：（1）PQFFFTFTTFTFFTTTTT（2）PQRFFFTFFFFTTFFFTFTFFFTTFTFTFFFTFTFTFTFTTFFTFTTTFTF（3）PQRFFFTFFFFTTFFFTFFFTFTTFFTTFFFTTTFTFFTTTFTTTTTTTFF（4）PQRFFFTTFFTFFFTFTTFTTFFTFFTTTFTFFTTFFTTTTFF9. 使用真值表证明：如果为，那么和都是，反之亦然。证明：PQFFTTTFTFTFTFFFTTTTTT由上表可知：当为时，和都是；和为时，为。故命题得证。10. 使用真值表证明：对于和的所有值，与有同样的真值。PQFFTTFTTTTFFFTTTT11. 一个有两个运算对象的逻辑运算符，如果颠倒其运算对象的次序，产生一逻辑等价命题，则称此逻辑运算符是可交换的。（1）确定所给出的逻辑运算符哪些是可交换的：，。（2）用真值表证明你的判断。解：（1），是可交换的。（2）真值表如下：PQFFFFFFTTTTFTFFTTTFFFTFFFTTFTFFTTTTTTTTTT12.设是具有两个运算对象的逻辑运算符，如果和逻辑等价，那么运算符是可结合的。（1）确定逻辑运算符，哪些是可结合的？（2）用真值表证明你的判断。解：（1）是可结合的。 （2）真值表如下：PQRFFFFFFTFFTFTTTFTFFTFTFTTFTTFTFFFTTTTFTFTTFTTFFTFFTTTTTTTPQRFFFFFTTFFTFTTTFTFFTTTFTTFTTFTFFFTTTTFTFTTFTTFFTFFTTTTTTT13. 令表示命题“苹果是添的”，表示命题“苹果是红的”，表示命题“我买苹果”。试将下列命题符号化：（1）如果苹果甜而红，那么我买苹果。（2）苹果不是甜的。（3）我没买苹果，因为苹果不红也不甜。解：（1）（2）（3）14解：如何我问你是你是不是总说谎的，你会说是吗？ 回答不是的都是说实话的，回答是的都是说谎的。1.2第15页1. 指出下面命题公式哪些是重言式、永假式或可满足式。解：（1）重言式（2）永假式（3）重言式（4）重言式 （5）重言式（6）重言式 = （7）重言式 =（8）重言式=（9）重言式 =（10）可满足式=，当为真时公式为真，为假时公式为假。故为可满足式。（11）重言式（12）重言式 （13）可满足式 的真值表如下：PQFFTTTFTTFFTFFFTTTTTT（14）可满足式= 当或有一个为真时公式为真；当和均为假时，若和真值相同时，公式为真；真值不同时，公式为假。故公式是可满足式。2. 写出与下面给出的公式等价并且仅含有联接词与的最简公式。（1）（2）（3）（4）（5）3. 写出与下面的公式等价并且仅含联结词和的最简公式。（1）（2）（3）4. 使用常用恒等式证明下列各式，并给出下列各式的对偶式。（1）证明： 对偶式：（2）证明：对偶式：（3）证明：对偶式：5. 试证明下列合式公式是永真式。（1）证明：（2）证明：（3）证明：（4）证明：6. 证明下列蕴含式。（1）证明：（2）证明：（3）证明：（4）证明：（5）证明：（6）证明：7. 对一个重言式使用代入规则后仍为一个重言式，对一个可满足式和一个矛盾式，使用代入规则后，结果如何？对重言式、可满足式和矛盾式，使用替换规则后，结果如何？解：对于代入规则：（1）如果是可满足式，使用代入规则后可能是重言式、可满足式或矛盾式。如：可满足式，将分别替换为，分别得到重言式和可满足式，对于可满足式，将替换为得到矛盾式。（2）如果是矛盾式，使用代入规则后仍然是矛盾式。设是矛盾式，则是重言式。而对于重言式使用代入规则后仍为重言式，即是重言式，故是矛盾式。对于替换规则：由于替换规则是一种对子公式逻辑上等价的替换，故对于重言式、可满足式和矛盾式使用替换规则后其真值不变。8. 求出下列各式的代入实例。（1）；用代，用代。解：（2）；用代，用代解：9证明下列等价式：（1）证明： 因此，得证。1.3第22页1.求下列各式的主合取范式。（1）解： （2）（3）2.求下列公式的主析取范式和主合取范式：（1）合取范式：析取范式：（2）合取范式：析取范式：（3）合取范式：析取范式：（4）析取范式：合取范式：1.4第27页1.试用真值表法证明：不是,和的有效结论。解：构造真值表如下：A B C D E0 0 0 0 0111000 0 0 0 1110100 0 0 1 0111000 0 0 1 1110100 0 1 0 0110000 0 1 0 1111100 0 1 1 0100000 0 1 1 1101100 1 0 0 0001000 1 0 0 1000100 1 0 1 0001000 1 0 1 1000100 1 1 0 0000000 1 1 0 1001100 1 1 1 0010000 1 1 1 1011101 0 0 0 0010101 0 0 0 1010111 0 0 1 0010101 0 0 1 1010111 0 1 0 0011101 0 1 0 1011111 0 1 1 0001101 0 1 1 1001111 1 0 0 0100101 1 0 0 1100111 1 0 1 0100101 1 0 1 1100111 1 1 0 0101101 1 1 0 1101111 1 1 1 0111101 1 1 1 111111第6，31行前提取值均为1时，结论为0。故命题得证。2.，和是前提。在下列情况下，试确定结论C是否有效（可以使用真值表法证明。）（1）证明：真值表如下：P Q0 0110 1111 0001 111第1，2，4行当前提取值为1时，结论都为1。故结论C是有效的。（2）证明：1（1）P规则1（2）T规则，（1），3（3）P规则1，3（4）T规则，（2），（3），5（5）P规则1，3，5（6）T规则，（4），（5），结论C是有效结论。（3）（4）证明：1（1）P规则（附加前提）2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），1，2，4（6）规则，（1），（5）3.不构成真值表证明：不是、和的有效结论。证明：（1） P规则 （2） P规则 （3） T规则，(1)(2) （4） P规则 （5） T规则,(1)(4) （6） T规则(5) （7） T规则(3) （8） T规则(6)(7) （9） T规则(8)因此，是题目的有效结论，不是。4.使用推理的方法证明：是和的有效结论。证明：1（1）P规则1（2）T规则，（1），1（3）T规则，（2），1（4）T规则，（3），1（5）T规则，（1），1（6）T规则，（5），1（7）T规则，（6），1（8）T规则，（4），（7），9（9）P规则1，9（10）T规则，（8），（9），5.不构成真值表证明下列命题公式不能同时全为真。（1），证明：1（1）P规则2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），6（6）P规则1，2，4，6（7）T规则，（5），（6），8（8）P规则(1，2，4，6，8)（9）T规则，（7），（8），推出结论与前提矛盾，因此命题公式不能同时为真。（2），证明：1（1）P规则2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），推出的结论与命题公式矛盾，因此命题公式不能同时为真。6. ，和是前提，根据推理规则断定，在下列情况下是否是有效结论。（1） 证明：1（1）P规则（假设前提）2（2）P规则1，2（3）T规则，（1），（2），4（4）P规则1，2，4（5）T规则，（3），（4），6（6）P规则1，2，4，6（7）T规则，（5），（6），1，2，4，6（8）T规则，（1），（7），1，2，4，6（9）F规则，（1），（8）因此是有效结论。（2）证明：因为，再由前提，得到、的值任意，即、的值任意。因此不是有效结论。7.证明下列结论的有效性。（1），证明：（1）P规则（2）P规则（3）T规则，（1），（2），（4）P规则（5）T规则，（4），（6）T规则，（3），（5），（2），证明：（1） P规则 （2） P规则 （3） T规则（1）（2） （4） P规则 （5） T规则（3）（4） （6） T规则（5）8.导出下列结论（如果需要，就是用规则）（1）证明： （1） P P规则（假设前提） （2） P规则 （3） Q T规则（1）（2） （4） P规则 （5） R T规则（3）（4） （6） P规则 （7） S T规则（5）（6） （8） CP规则（1）（7）（2）证明： （1） P P规则（假设前提） （2） P规则 （3） Q T规则（1）（2） （4） T规则（1）（3） （5） CP规则（1）（4）（3）证明： （1） P规则（假设前提） （2） P T规则（1） （3） Q T规则（1） （4） T规则（2）（3） （5） P规则 （6） R T规则（4）（5） （7） CP规则（1）（6）9.证明下列各式的有效性（如果需要，就使用间接证明法）。（1）证明： （1） P规则（假设前提） （2） P T规则（1） （3） P规则 （4） Q T规则（2）（3） （5） P规则 （6） T规则（4）（5） （7） P规则 （8） R T规则（6）（7） （9） P规则 （10） T规则（8）（9） （11） T规则（4）（10） （12） F规则（1）（11）（2）证明： （1） P规则（假设前提） （2） P T规则（1） （3） P规则 （4） Q T规则（2）（3） （5） P规则 （6） T规则（4）（5） （7） P规则 （8） R T规则（6）（7） （9） P规则 （10） T规则（8）（9） （11） F规则（1）（10）（3）证明： （1） R P规则 （2） P规则 （3） T规则（1）（2） （4） T规则（1） （5） P规则 （6） T规则（4）（5） （7） T规则（6） （8） T规则（3）（7） （9） T规则（8）第二章 谓词逻辑2.2第43页2.证明下列各式。（1），证明：（1）P（2）US，（1）（3）P（4）US，（3）（5）T，（2），（4），（6）EG，（5）（2）证明： （1） P（假设前提） （2） T （3） T （4） T （5） T （6） T （7） P （8） T（5）（7） （9） ES（6） （10） US（8） （11） T（9）（10） （12） F（1）（11）（3），证明：（1）P（假设前提）（2）T，（1）（3）US，（2）（4）T，（3）（5）T，（3）（6）P（7）US，（6）（8）T，（5），（7）（9）P（10）US，（8）（11）T，（4），（10）（12）T，（8），（11）（4）证明： （1） P （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） P （7） US（6） （8） T（5）（7） （9） UG（8）3.用CP规则证明下列各式。（1）证明： （1） P（假设前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）（2）证明：由于 因此，原题等价于证明 （1） P（假设前提） （2） US（1） （3） P （4） US（3） （5） T（2）（4） （6） UG（5） （7） CP（1）（6）4.将下列命题符号化并推证其结论。（1）所有的有理数是实数，某些有理数是整数，因此某些实数是整数。解：首先定义如下谓词：是有理数是实数是整数于是问题符号化为：推理如下： （1） P （2） ES（1） （3） P （4） US（3） （5） T（2） （6） T（2） （7） T（4）（5） （8） T（6）（7） （9） EG（8）（2）任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。解：首先定义如下谓词：是人喜欢步行喜欢乘汽车x喜欢骑自行车于是问题符号化为：推理如下： （1） P （2） ES（1） （3） T（2） （4） T（2） （5） P （6） US（5） （7） T（3）（6） （8） T（4）（7） （9） P（10） US（9）（11） T（8）（10）（12） T（11）（13） T（3）（12）（14） T（3）（13）（15） EG（14）（3）每个科学工作者都是刻苦钻研的，每个刻苦钻研而且聪明的科学工作者在他的事业中都将获得成功。华为是科学工作者并且他是聪明的，所以，华为在他的事业中将获得成功。解：首先定义如下谓词：是科学工作者是刻苦钻研的是聪明的在他的事业中将获得成功定义个体a：华为于是命题符号化为：推理如下： （1） P （2） US（1） （3） P （4） T（3） （5） T（3） （6） T（2）（4） （7） P （8） US（7） （9） T（3）（6）（10） T（8）（9）（4）每位资深名士或是中科院院士或是国务院参事，所有的资深名士都是政协委员。张伟是资深名士，但他不是中科院院士。因此，有的政协委员是国务院参事。解：首先定义如下谓词：是资深名士是中科院院士是国务院参事是政协委员定义个体a：张伟于是命题符号化为：推理如下： （1） P （2） T（1） （3） T（1） （4） P （5） US（4） （6） T（2）（5） （7） P （8） US（7） （9） T（2）（8）（10） T（3）（9）（11） T（6）（10）（12） EG（11）（5）每一个自然数不是奇数就是偶数，自然数是偶数当且仅当它能被2整除。并不是所有的自然数都能被2所整除。因此，有的自然数是奇数。解：首先定义如下谓词：是自然数是奇数是偶数能被2整除于是命题符号化为：推理如下： （1） P （2） T（1） （3） ES（2） （4） T（3） （5） T（3） （6） P （7） US（6） （8） T（4）（7） （9） T（5）（8）（10） P（11） US（10）（12） T（4）（11）（13） T（9）（12）（14） T（4）（13）（15） EG（14）（6）如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些人未曾失败过，所以，有些人不怕困难。解：首先定义如下谓词：是人怕困难曾获得成功曾获得失败于是命题符号化为：推理如下： （1） P （2） ES（1） （3） T（2） （4） T（2） （5） P （6） US（5） （7） T（3）（6） （8） T（4）（7） （9） P （10） US（9） （11） T（8）（10） （12） T（11） （13） T（3）（12） （14） T（3）（13） （15） EG（14）6.试找出下列推导过程中的错误，并问结论是否有效？如果有效，写出正确的推导过程。 解：错误，第2行的y是泛指，第4行的y是特制更改如下： （1） P （2） ES（1） （3） P （4） US（3） （5） T（2）（4） （6） EG（5）7.用构成推导过程的方法证明下列蕴含式。（1） 证明：（2）证明： （1） P （2） T（1） （3） T（2） （4） T（3） （5） T（4）2.3第46页1.将下列公式化为前束范式。（1）解： （2）解：（3）解：2.求等价于下面公式的前束主析取范式与前束主合取范式。（1）解：前束主析取范式：前束主合取范式：（2）解：前束析取范式由于是基本和，因此前束合取范式与前束析取范式一样：（3）前束主析取范式：前束主合取范式与前束主析取范式相同。（4）解：前束析取范式：前束合取范式：3.将下列公式化为斯柯林范式。（1）（2）第三章 集合论3.1第50页1.解：(1) 集合可表示为(2) 集合可表示为(3) 集合可表示为(4) 集合可表示为(5) 集合可表示为2.解：设戏剧、音乐、广告分配的时间分别为(1) 可表示为(2) 可表示为(3) 可表示为(4) 可表示为3.给出集合、和的例子，使得，而。解：4.(1) 该命题为假命题(2) 该命题为假命题(3) 该命题为真命题证明：任取，由于，所以必有。又，所以必有。即对于任意的，都有，所以如果且，则。(4) 该命题为假命题(5) 该命题为假命题。5.解：可能。若，则且。8.(1) 解：设 则(2)解：设则(3) 解：设则(4) 解：设 则(5)解：设则9.解： (1) ，(2) ，(3) ，10.证明：充分性： ， 充分性得证。必要性： 必要性得证。11.（1）解：子集个数（2）解：元素的奇数的子集个数为（3）解：不会有102个元素的子集。12.解：把17化为二进制，是00010001，；把31化为二进制，是00011111，编码为01000110，为，编码为10000001，为3.2 第59页1.解： 2. 解： 4.解： (1) (2) (3) (4) 5.证明：充分性：由于 所以，即 充分性得证。 必要性：由于 所以 所以 必要性得证。6.（1）证明： 上面是一种简单的方法，还可以利用文字叙述，任取x属于，。证明。还有一种方法，就是利用第五章的特征函数证明，下面给出过程所以，从而可得，。（2）证明： （3）证明：因此，7.解: 8.(1) 证明： 证明BA。充分性：若，则若，那么必有。因此，若，则必有，即若xB，则有xA，即BA；必要性：若BA，则若xB，则有xA，即若，则必有。那么，若，那么必有，即；由以上两点可知：BA。 证明：AB=B 充分性：若，那么有或。 若，则由可知，必有，所以若，必有，即； 若，那么必有，即，所以AB=B，充分性得证； 必要性：因为AB=B，所以，对于任意的，必有，所以，必要性得证； 由以上两点可知：AB=B 证明：AB=A 充分性：若，那么必有，即；若，那么由可知，必有，所以，即，所以，AB=A； 必要性：因为AB=A，所以对于任意的，必有，所以；由以上两点可知，AB=A。由以上三点可知，BA AB=BAB=A。(2) 证明:AB 充分性：因为，所以对于任意的，若，则必有，即xB，所以AB； 必要性：因为AB，所以对于任意的，若，则必有xB，即，所以；由以上两点可知：AB 证明：BA 充分性：因为，所以对于任意的，若，则必有，即xA，所以BA； 必要性：因为BA，所以对于任意的，若，则必有xA，即，所以；由以上两点可知：BA.由上可知：ABBA.(3) 证明：AB=EAB充分性：因为 AB=E，所以若，则必有，即若xA，则必有，所以AB；必要性：因为AA=E，又AB，必有AB=E；由以上两点可知：AB=EAB 证明：AB=EBA充分性：因为 AB=E，所以若，则必有，即若xB，则必有，所以BA；必要性：因为BB=E，又BA，必有AB=E；由以上两点可知：AB=EBA.由上可知：AB=EABBA.。(4) 证明：A=BAB=充分性：由于A=B，所以AB=,BA= 所以AB=ABBA=必要性：因为AB=ABBA= 所以AB=且BA= 因为AB=，所以AB 又BA=，所以BA 所以A=B。由上可知：A=BAB=。9.(1) 解：不一定。 若，此时有，但。(2) 解：不一定。 若，此时有，但。(3) 解：一定有。10.（1）解：由于，因此必有且。也就是并且。（2）解：由于，因此必有且。也就是并且。（3）解： 因此，意味着（4）解： 两种可能，第一种，即B=C；第二种，或者因此，此题答案为。12.证明： 因此，。3.3第62页1.解： 设A，B，C分别表示参加足球队、篮球队和棒球队的队员的集合即同时参加两个对的队员共有18个。2. 解：设A，B，C分别表示读甲种、乙种、丙种杂志的学生的集合。(1) 所以确定读两种杂志的学生的百分比为60%。(2) 所以不读任何杂志的学生的百分比为30%。3. 解：设A，B，C分别表示骑木马、坐滑行轨道和乘宇宙飞船的儿童集合。由公园的总收入知，因此，没有坐过任何一种的儿童总数为答：一共10个儿童没有坐过其中任何一种游乐设备。4.解：用A，B分别表示在第一次考试和第二次考试中得A的学生的集合。(1) 又 ，则所以有14个学生两次考试都取得A。(2) 又，则所以有34个学生在两次考试中都取得A。所以有6个学生仅在第一次考试中取得A。所以有6个学生仅在第二次考试中取得A。5.解：设A，B，C分别是学习数学、物理、生物的大一学生集合。由题意可知，解方程，得因此，一共有22人三门功课都学。3.4第66页1.（1）解：（2）解（3）解：2.解：表示在在笛卡尔坐标系中，且的矩形区域内的点集。3（1）证明：任取,有 由取值的任意性知，。（2）证明： 当时，于是。当时，任取，可知，由知，于是得到。所以，。5.证明： 必要性：若，； 同理，若，； 若，则显然有； 必要性得证。 充分性性：由于 所以对于任意的,必有 即若则必有；若，则必有，所以当时，； 充分性得证。6,（1）解：任取,有选择A=1，B=2，C=a，D=b则因此该等式不成立。（2）解：任取,有选择A=1，2，B=1，C=a，b，D=a因此，该等式不成立。（3）解：设A=1，2，B=2，C=3，4，D=4则因此，该等式不成立