离散数学习题答案

1、 离散数学习题选解习题一1.命题有：（1）、（2）、（3）、（6）、（7）、（10）、（11）、（12）、（13）.简单命题有：（1）、（2）、（7）、（10）、（13）.真命题有：（1）、（2）、（3）、（10）、（11）. 真值待定的命题有：（7）、（13）3.（2）解：令：是无理数，则原命题可符号化为，其否式为是无理数，其符号化为，的真值为0.（4）解：令：是整数，其否式为不是整数，其可符号化，的真值为0.4.（3）解：令：2是最小的素数， ：2是最小的自然数，则此命题可符号化为， 其值为1. （5）解：令：4是素数， ：4是偶数，则此命题可符号化为，其值为0.5.解：（4）令：3是偶数

2、， ：4是偶数，则此命题可符号化为，其值为1. （5）令：3是素数， ：4是偶数，则此命题可符号化为，其值为0.6.解：（2）令：刘晓月只选学英语，：刘晓月只选学日语，则此命题可符号化为 或.7.解：因为与不能同时为真.8.解：(5) 令：， ：，则此命题可符号化为，其值为0.（6）令：， ：，则此命题可符号化为，其值为1.11.解：(1)令：， ：地球是动的，则此命题可符号化为,其值为0.(4) 令：地球上有水， ：是无理数，则此命题可符号化为，其值为1.12.解：(2)令：， ：，则此命题可符号化为，其值为0. （4）令：， ：，则此命题可符号化为，其值为1.13.解：（3）令：今天是星期

3、一， ：明天是星期二，则此命题可符号化为，其值为1.（4）令：今天是星期一， ：明天是星期三，则此命题可符号化为，其值为0.14.解：（7）令：他吃饭， ：他听音乐，则此命题可符号化为.（9）令：他乘班车上班， ：天下大雨，则此命题可符号化为.（11）令：下雪， ：路滑，：他迟到了，则此命题可符号化为.（12）令：2是素数， ：4是素数，则此命题可符号化为.（13）令：2是素数， ：4是素数，则此命题可符号化为.15.解：的真值分别为1，1，0，于是有：（1），（2），（3）（4），16.解：因为，所以（1），（2），（3），（4），17.解：令：是无理数，：3是无理数，：是无理数，：6能被2

4、整除， ：6能被4整除，的值分别为1，0，1，1，0，则此题可符号化为，其值为，因此此论述为真.18.解：令：小王会唱歌，：小李会跳舞，则此题可符号化为 由题设条件知，又，所以的值分别为1，0，即当小王会唱歌而小李不会跳舞时，就满足题目的要求.19.解：（5）因为原式共有3个不同的变元，故其真值表为： ()()0 0 0110 1 00 0 1 1 1 0 1 00 1 0 1 0 0 0 11 0 0 0 1 0 0 11 0 1 0 1 1 0 00 1 1 1 0 0 0 11 1 0 0 0 0 0 11 1 1 0 0 1 0 0所以此式为非重言式的可满足式.（6）因为原式共有3个不

5、同的变元，故其真值表为：（）（）（）0 0 011110 0 111110 1 010111 0 001010 1 111111 0 101111 1 010011 1 11 111 所以此式为重言式.（7）因为原式共有4个不同的变元，故其真值表为：（）（）0 0 0 01110 0 0 11000 0 1 01000 0 1 11110 1 0 01110 1 0 11000 1 1 01000 1 1 11111 0 0 00101 0 0 10011 0 1 00011 0 1 10101 1 0 01111 1 0 11001 1 1 01001 1 1 1111 所以此式为非重言式的

6、可满足式.20.解：（3），所以原式的成真赋值为00，01，11.注：此题也可用真值表法来做.21.解：（2），所以原式的成假赋值为010，100，101，110. （3）所以原式的成假赋值为100，101. 注：此题也可用真值表法来做. 22.解：因为，所以0，故 为矛盾式，它没有成真赋值，其所有个赋值全为成假赋值.23.解：因为，所以，故 为重言式，它没有成假赋值，其所有个赋值全为成真赋值.24.解：因为，所以且 ，即和均为重言式.25.解：因为，所以且，即它们都是矛盾式.26.解：因为，所以.故为矛盾式，又，所以为重言式.27.证明：若，则，即均为重言式，反之若，则，即为重言式.28.解

7、：，则有下列三种情形：（1）（2），（3） ，因此由是矛盾式，不能得出与都是矛盾式的结论.29.证明：若，则即均为矛盾式，若则，即为矛盾式.32.解：若，则有下列三种情形：（1），（2），（3）（2），因此由为重言式，不能得出与都是重言式的结论.习题二1.解：公式与共含有两个变元，故它们的真值表为 （）0 0110000 1010001 0101001 101000所以.3.解：（2）原式，所以此式为重言式. （3）原式 ，所以此式为非重言式的可满足式，其成真赋值为000，001，101，111. 注：此题可用真值表法求出成真赋值和成假赋值.4.证明：（3） （4） 5.解：（2），所以此式的

8、主析取范式为0，它没有成真赋值.（3），所以此式为重言式.所以它的所有个赋值都是成真赋值.（1）所以此式的成真赋值为00，10，11. 注：此题共有2个不同的变元.6.解：（1）.所以此式为矛盾式，其所有个赋值都是成假赋值. （2），所以此式的成假赋值为100.（3），所以此式为重言式，所以此式的主合取范式为1，它没有成假赋值.7.解：（1）.（2） .8.解：（1）.所以此式的主合取范式为1，它的主析取范式为.（2） .(3).所以它的主析取范式为0, 主合取范式为.9.解：（1）因为原式共有3个不同的变元，故其真值表为：()()0 0 010000 0 110110 1 011010 1

9、111111 0 001011 0 101011 1 001011 1 10101(2) （1）因为原式共有2个不同的变元故其真值表为： ()()0 011000 101111 010111 10100所以它的主析取范式为.10.解：（1）因为原式共有3个不同的变元，故其真值表为：()0 0 0000 0 1010 1 0001 0 0001 0 1011 1 0111 1 1110 1 101 所以它的主合取范式为.(2) 因为原式共有3个不同的变元，故其真值表为：()()0 0 01110 0 11110 1 01000 1 11111 0 00101 0 10101 1 01001 1

10、1111 所以它的主合取范式为.11.解：（2）因为原式共有3个不同的变元，故其真值表为：()0 0 0010 0 1110 1 0110 1 1111 0 0111 0 1111 1 0111 1 111所以此式为重言式, 它的主析取范式为 主合取范式为1.(3) 因为原式共有2个不同的变元故其真值表为：() ()0 011000 111001 001001 10010 所以此式为矛盾式，它的主合取范式为,它的主析取范式为0. (1) 因为原式共有3个不同的变元，故其真值表为：()r0 0 0000 0 1000 1 0100 1 1111 0 0101 0 1111 1 0101 1 11

11、1 所以它的主析取范式为 , 它的主合取范式为.12.解：的主合取范式为，它的主析取范式为.13.解：的主合取范式为，它的主析取范式为.14.解：，所以它的主合取范式为1. 注：的主析取范式为.14.解：（1）.,所以与不等值.（2），所以 与不等值.16.解：（1），所以 . （2），.所以与不等值.17.解：（1）原式.（2）原式.（3）原式.18.解：（1）原式.（2）原式.（3）原式或原式或原式或原式.19.解：（1）原式.（2）原式.（3）原式.20.解：（1）原式.（2）原式.（3）原式.21.证明：（1）. （2）.而.所以与不等值.而.所以与不等值.22.解：（1）的真值表为0

12、 010 111 011 10所以.（2）的真值表为0 010 101 001 10所以.（3）原式的真值表为原式0 0110000 1100111 0011011 100000所以原式.（4）原式的真值表为（）0010011010011110所以原式.27.解：情况一，情况二，情况三，情况四，则(a).(b)由(a)知.或先把化简为.注：还有其他的等价形式.(c)由（b）可知或.注：还有其他的等价形式.29.解：令：李强为生活委员，：王小红为班长，：丁金生为班长，：王小红为生活委员，：李强为班长，：王小红为学习委员，则有：甲说对一半，乙说对一半，丙说对一半，由于每人不能兼任，所以有：因此，而

13、所以，即为1，为0，为1，为0，为1，因此李强为生活委员，丁金生为班长，王小红为学习委员.30.解：令：赵去，：钱去，：李去，：周去，：孙去，则条件1：条件2：条件3：条件4：条件5：.因此有：全部条件，所以为1，为1，为0，为1，为0，或者为0，为0，为1，为0，为1。因此赵、钱、周去或者孙、李去.注：在计算过程中，多次用到.习题三6.解：（1）令：今天是星期一，：明天是星期三，则前提：结论：推理的形式结构：等值演算法： ，由定理3.1知此推理正确.主析取范式法：，由定理3.1知此推理正确.真值表法：（）0 0000 1011 0001 111 所以不会出现前提的合取式为真而结论为假的情况，

14、因此推理正确.（3）令：今天是星期一，：明天是星期三，则前提：结论：推理的形式结构：等值演算法：，因此推理正确.主析取范式法：，因此推理正确.直接构造推理证明的方法.证明： 前提引入 前提引入 拒取式真值表法：它们的真值表为：（）0 0110 1011 0001 100所以不会出现前提的合取式为真而结论为假的情况，因此推理正确.（4）令：今天是星期一，：明天是星期二，则前提：结论：推理的形式结构：等值演算法：，所以当为0，为1时，原式为0，因此不是重言式，由定理3.1知此推理不正确.主析取范式法：，因此不是重言式，由定理3.1知此推理不正确.真值表法：它们的真值表为：（）0 0110 1101

15、 0011 100所以会出现前提的合取式为真而结论为假的情况，因此推理不正确.（6）令：今天是星期一，：明天是星期三，则前提：结论：推理的形式结构：等值演算法：，由定理3.1知此推理正确.主析取范式法：，由定理3.1知此推理正确.真值表法：它们的真值表为：（）0011010010011100所以不会出现前提的合取式为真而结论为假的情况，因此推理正确.直接构造推理证明的方法.证明： 前提引入 置换规则 化简规则 前提引入 拒取式9.证明：令： 是奇数， ：能被2整除，：是偶数，则前提：，结论：推理的形式结构：证法一（附加前提的证法）： 前提引入 前提引入 附加前提引入 假言推理 拒取式证法二（直

16、接构造推理证明的方法） 前提引入 前提引入 合取引入 置换规则 破坏性二难 置换规则证法三（主析取范式法）：,由定理3.1知此推理正确.证法四（真值表法）：因为共含有3个不同的变元，故其真值表为：（）（）0 0 0110 0 1010 1 0110 1 1111 0 0111 0 1111 1 0011 1 100所以不会出现前提的合取式为真而结论为假的情况，因此推理正确.10.证明：令：两数之积是负数，：，：，则前提：结论：推理的形式结构：证法一（真值表法）：因为共含有3个不同的变元，故其真值表为：()()0 0 0110 0 1100 1 0100 1 1011 0 0101 0 1001

17、 1 0001 1 100所以会出现前提的合取式为真而结论为假的情况，因此推理不正确.证法二（主析取范式法），因此此式不是重言式，由定理3.1知此推理不正确.11.证明： 前提引入 前提引入 析取三段论 前提引入 析取三段论 前提引入 假言推理12.证明： 附加前提引入 化简规则 化简规则 前提引入 假言推理 假言推理 前提引入 假言推理 假言推理13.证法1（等值演算法）：（1）关于结论1的推理的形式结构：，关于结论2的推理的形式结构：，关于结论3的推理的形式结构：，由于，所以有：，同理可得：， ，因此由这些前提推出结论1、结论2、结论3的推理都是正确的.注：可用真值表法.（2）设为任一个结

18、论，则，由定理3.1知此推理正确.14.证明：（1） 前提引入 前提引入 假言推理 前提引入 假言推理 附加规则(2)证法1（直接证法）： 前提引入 置换规则 前提引入 析取三段论 前提引入 拒取式 证法2（归谬法）： 结论的否定引入 前提引入 假言推理 置换规则 前提引入 析取三段论 合取引入最后的式子，所以结论是有效的.（3）证明（附加前提证法）： 前提引入 附加前提引入 假言推理 合取引入（4）证明： 前提引入 前提引入 等价三段论 置换规则 化简规则 前提引入 化简规则 假言推理 前提引入 假言推理 合取引入（5）证明： 前提引入 前提引入 前提引入 化简规则 化简规则 假言推理 假言

19、推理 合取引入（6）证明（附加前提证法）： 附加前提引入 前提引入 化简规则 化简规则 前提引入 析取三段论 附加规则15.证明：（1） 附加前提引入 前提引入 假言推理 前提引入 假言推理 前提引入 假言推理（2） 附加前提引入 附加规则 前提引入 假言推理 化简规则 附加规则 前提引入 假言推理16.证明：（1） 结论的否定引入 前提引入 假言推理 前提引入 析取三段论 前提引入 化简规则 合取引入由于，所以结论是有效的.（2） 结论的否定引入 置换规则 化简规则 化简规则 前提引入 拒取式 前提引入 拒取式 合取引入 置换规则 前提引入 合取引入由于，所以结论是有效的.17.证明：令：曾

20、到过受害者房间，：11点以前离开受害者房间，：犯了谋杀罪，：看门人看见，则前提：，结论：证明过程如下： 前提引入 前提引入 拒取式 前提引入 合取引入 前提引入 假言推理18.证明：（1）令：今天是星期六，：我们到牙颐和园，：我们到牙圆明园去玩，：颐和园游人太多，则前提：,结论：证明过程如下： 前提引入 前提引入 假言推理 前提引入 前提引入 假言推理 析取三段论(2)令：小王是理科学生，：小王的数学成绩很好，：小王是文科学生，则前提：，结论：证明过程如下： 前提引入 前提引入 拒取式 前提引入 拒取式习题四1.解：（1）令：学过，令：小王，：英语，：法语，则此命题可符号化为.（2）令：是东北

21、人，：怕，：李健，：冷，则此命题可符号化为（3）令：，：3，：3，：4，则此命题可符号化为.（4）令：是偶数，：3，则此命题可符号化为.（5）令：是素数，：2，：3，此命题可符号化为.2.解：（）令：是有理数，：能被2整除，则（1） 可符号化为，其真值为0；（2）可符号化为，其真值为1；（2） （）（1）可符号化为，其真值为0；（2）可符号化为，真值为1；7.解：（3）此式被解释为：存在整数，使得对任意整数和，都成立，为假命题.8. 解：（3）在中，为指导变元，和的辖域均为，约束出现，自由出现，在中，的辖域为，约束出现，自由出现，因此在整个式子中，约束出现2次，约束出现2次，自由出现1次，自由

22、出现2次.9.解：（3）在解释I下，原式，此时公式的真值为1.10.解：（2）在此解释下，原式，此时此时公式的真值为0.（因为2+2=4，4+22）11.解：（2）在任一解释I下，均为真，为假，因而前件总是真，后件总是假，因此此式为矛盾式（永假式）.12.解：（1）、（4）不是命题，因为它们含有自由变元；（2）、（3）是命题，因为它们不含有自由变元.13.解：（3）给出解释I如下：D=N，：是奇数，：是偶数，：整除，则在解释I下此式的真值为0，即I为成假解释. 再给出解释I如下：D为整数集，：是整数，：是偶数，：整除，则在解释I下此式的真值为1，即I为成真解释.14.证明：（2）给出解释I如下

23、：D=N，：是奇数，：是偶数，：，则在解释I下此式的真值为1，即I为成真解释；再给出解释I如下：D为正整数集，：， ：，：，则在解释I下此式的真值为0，即I为成假解释.习题五2.解：（3）原式.（4）原式.3.解：（2）给出解释I如下：D为整数集，：是奇数，：是偶数，则在解释I下此式的真值为0，即I为成假解释；再给出解释I如下：D为整数集，：能被2整除，：能被3整除，则在解释I下此式的真值为1，即I为成真解释.4.解：（2） ，可见：若 ，则，所以在解释I下的真值不一定为1.5.解：（3）原式 .6.解：因为中含有的出现，不符合量词辖域的收缩与扩张等值式的要求（见公式（5.3），所以甲错了，乙

24、说对子。7.解：，因此此演算中的两个等值式右边都错.12.解：（1）原式 （换名规则） （置换规则） （量词否定等值式） （量词辖域的收缩与扩张等值式） （量词辖域的收缩与扩张等值式）（2）原式 （代替规则） （置换规则） （量词辖域的收缩与扩张等值式）（3） 原式 （换名规则） （置换规则） （置换规则） （量词否定等值式）（量词辖域收缩与扩张等值式） （换名规则） （量词辖域收缩与扩张等值式）.（4） 原式（换名规则）（量词辖域收缩与扩张等值式）(同第二步)(同第二步).（5） 原式（代替规则）（量词否定等值式）（量词辖域收缩与扩张等值式）（量词辖域收缩与扩张等值式）13.解：令：是汽车，

25、：是火车，：比跑得快，个体域D为全总个体域，则命题（1）可符号化为（此式已是前束范式）；命题（2）可符号化为；命题（3）可符号化为；又令：是飞机，命题（4）可符号化为.15.（1）证明： 前提引入 规则 前提引入 置换规则 置换规则 置换规则 规则 规则 置换规则 假言推理 附加规则 假言推理 规则注：在此类证明中，凡是有形如的存在式作式作为前提，必须比前提中形如的前提先引进来，然后使用规则，即在证明过程中每个规则必须放在任一个规则之前，否则出错。（2）证明： 前提引入 规则 前提引入 规则 假言推理 化简规则 合取引入 规则（3）证明： 前提引入 置换规则 规则 前提引入 规则 析取三段论 规则（4）证